Combinatoria prueba de la identidad dada por

Question

Proporcionar una combinatoria argumento para la ecuación dada $${^{n+1}C_4}= {{^{^{^nC_2}}C_2}\over 3} \text{, for } n\ge 4$$

SUGERENCIA: Considere un grupo de $n+1$ términos de los cuales uno es considerado especial. Argumentan que ambos lados de la anterior identidad representan el número de subconjuntos de tamaño $4$.

Cómo puedo obtener el LHS es el número de tamaño de $4$ subconjuntos de un conjunto de $n+1$ términos. ¿Cómo funciona el RHS seguir su ejemplo?

Answer 1

Para $n\geq 3$, ${^{^{^nC_2}}C_2}=\binom{\binom{n}{2}}{2}$ es el número de formas de elegir los dos distintos subconjuntos de dos elementos, decir $A$$B$, desde el $n$-dado por el conjunto de los $n+1$ elementos sin el especial (vamos a denotar por $s$).

Tenemos dos casos.

1) Si $|A\cap B|=0$ $X=A\cup B$ es un subconjunto de a $4$ elementos. El mismo subconjunto $X=\{a,b,c,d\}$ puede ser obtenida en $3$ diferentes formas: $$\{a,b\}\cup\{c,d\},\quad \{a,c\}\cup\{b,d\} ,\quad \{a,d\}\cup\{b,c\}.$$

2) Si $|A\cap B|=1$ $X=A\cup B\cup \{s\}$ es un subconjunto de a $4$ elementos. El mismo subconjunto $X=\{a,b,c,s\}$ puede ser obtenida en $3$ diferentes formas: $$\{a,b\}\cup\{b,c\}\cup \{s\},\quad \{a,c\}\cup\{b,c\}\cup \{s\},\quad \{a,b\}\cup\{a,c\}\cup \{s\}.$$

Answer 2

Sugerencia:en El lado derecho se obtiene mediante la elección de $4$ elementos de un $(n+1)$-elemento establecido en cuenta todos los posibles subconjuntos de tamaño $2$ y escoger dos de ellos (de tal forma que son disjuntos). La división por $3$ proviene del hecho de que las diferentes opciones que podrían dar el mismo resultado final. Os dejo los detalles para usted.

Answer 3

Para el lado derecho, en primer lugar, recoger los subconjuntos de a $2$ elementos (abbrev. 2) a partir del conjunto sin el elemento especial (con cardinalidad $n$). Que sería de $^nC_2$ elementos.

En segundo lugar, recoger el número de subconjuntos de cardinalidad $2$ a partir de la mencionada 2-set. A continuación, hacemos un algoritmo con ella: en Primer lugar la unión de los dos elementos que fueron elegidos juntos, y no sería de dos casos: 1. El elegido dos elementos (de la 2-set) son disjuntas. Esto estaría bien. 2. No lo son, entonces la unión de ellos debe ser con cardinalidad $3$. En esta ocasión, simplemente de la unión, el elemento especial con él. Con el fin (de la unión), conserva, se convierte en 4-tuplas. Aquí tenemos total $^{^nC_2}C_2$ elementos de 4-tupla.

En tercer lugar, fácil de ver que la cardinalidad de la anterior es exactamente tres veces el número de subconjuntos de cardinalidad $4$, ya que si un subconjunto es con tarjeta. $4$ y sin el elemento especial, se pueden dividir en no-igualdad de subconjuntos de la tarjeta. $2$ por tres caminos, y si contiene, menos el elemento especial y por la elección de la articulación elemento, también se puede expresar de tres maneras por elementos del mencionado conjunto de la tarjeta. $^{^nC_2}C_2$.

Y hemos terminado.

(P. S. yo no podría tener organizados mis palabras, espero que puedan entender.)