Dar una prueba combinatoria de una identidad multiset

Question

Debo dar una prueba combinatoria del, $\binom{\binom n2}{2}$ = 3 $\binom{n}{4}$ + n $\binom{n-1}{2}$.

Sé que $\binom{n}{k}$ = $\frac{n!}{k!(n-k)!}$ y $(\binom{n}{k}) = \binom{n+k-1}{k}$ pero estoy en una pérdida en cuanto a qué hacer con el $\binom{\binom n2}{2}$

¿Alguien puede señalarme en la dirección correcta en cuanto a cómo proceder con una prueba combinatoria para esta identidad de la escritura?

Answer 1

LHS puede ser interpretado como contar las maneras en que usted puede crear dos tipos de pares de dos elementos diferentes, tomados de un conjunto de $n$ juguetes; mientras que las parejas deben ser diferentes, no tienen por qué ser distinto: ellos podrían tener un juguete en común.

RHS cuenta la misma cantidad de pares de una manera diferente: se pueden crear dos tipos de tales par de pares: discontinuo queridos $(a,b)(c,d)$ y la superposición queridos $(a,b)(a,c)$. Recuerda que cada par deben ser diferentes y las dos parejas deben ser diferentes. El primer tipo de parejas puede ser elegido de la siguiente manera: el primero que eligió $4$ juguetes en $\binom{n}{4}$ maneras, a continuación, elija una de las $3$ formas de dividir el $4$ en dos pares (para ver que no se $3$ formas, se centran en uno de los cuatro: debe ser emparejado con uno de los tres restantes, y que determina la partición). El segundo tipo de pares puede ser elegida por el primero escoger el juguete $a$ que será común para ambos pares en $n$ maneras, entonces eligió $2$ juguetes de los restantes$n-1$$\{b,c\}$; el orden no importa aquí, por lo que la elección final puede ser hecho en $\binom{n-1}{2}$ maneras.

Answer 2

Considere la posibilidad de un gráfico de $G=(V,E)$ tal que $|V|=n$ $|E|={n \choose 2}$ (es decir, cualquiera de los dos vértices están conectados). Que el lado izquierdo de su identidad es el número de pares no ordenados de los bordes. Cualquier par se determina por cuatro vértices o por tres. En el primer caso, primero seleccionamos 4 vértices y, a continuación, conectar en cualquiera de las 3 formas que nos da total $3{n \choose 4}$ combinaciones. En el segundo caso, primero se debe seleccionar el vértice que pertenece a ambos bordes, y luego seleccione los otros dos vértices restantes $n-1$ vértices que nos da $n{n-1 \choose 2}$ posibilidades. Resumiendo tenemos la RHS.

Answer 3

RHS mediante combinatoria simple fórmula se simplifica a $\frac{(n)(n-1)^2(n-2)}{8}$ ahora lhs ${n\choose 2}=\frac{(n)(n-1)}{2}$ así que podemos escribir lhs $\frac{(n^2-n)!}{(2!).(\frac{n^2-n-4}{2})}$ ahora tratar $n^2-n=y$ por lo que se convierte en $\frac{(n^2-n)(n^2-n-2)}{8}=\frac{(n)(n-1)^2(n-2)}{8}=Rhs$