Doble conteo

Versión para impresión

Es un método de demostración de identidades combinatorias, que consiste en contar los elementos de un conjunto de dos formas, obteniendo así dos expresiones diferentes para el número de elementos del conjunto.

Para demostrar una identidad es necesario primero interpretarla. Por ejemplo, la forma de la siguiente identidad sugiere contar pares ordenados de subconjuntos: $$C(n,r)C(r,k) = C(n,k)C(n-k,r-k)$$

Lo primero que se puede "ver" en la identidad es que el conjunto mayor es de $ n $ elementos, digamos $S=\{1,2,...,\ldots{n}\}$. Consideremos ahora subconjuntos de $ r $ elementos de $S$ (llamémoslos subconjuntos $R$) y subconjuntos de $k$ elementos de $R$ (llamémoslos subconjuntos $K$).

Entonces, el lado izquierdo se puede interpretar como el número de parejas ordenadas $(R,K)$ de subconjuntos de $S$, de tamaño $r,k$, respectivamente, con $K$ subconjunto de $R$. Y esto porque, dado un subconjunto $R$ de $S$ (de los cuales hay $C(n,r)$), el número de subconjuntos de $R$ de tamaño $k$ son $C(r,k).$ Por el principio multiplicativo se obtiene el lado izquierdo.

¿Hay otra forma de obtener el número de parejas $(R,K)$?

El lado derecho sugiere que tomemos un subconjunto $K$ de $S$ (hay $C(n,k)$ de ellos) y luego, de los $n-k$ elementos restantes, elijamos un subconjunto de tamaño $r-k$ (hay $C(n-k, r-k)$ de ellos) para completar el subconjunto de tamaño $ k $. Es decir, contar el número de subconjuntos $R$ que contienen al $K.$ En otras palabras,los complementos posibles de $K$ que lo convierten en un $R.$)

Ahora solamente faltaría revisar el argumento y pulirlo. Pero, en principio, ya está. Lo importante a notar en esta interpretación es que la misma identidad nos sugiere la demostración combinatoria. (En este caso, contando parejas ordenadas --pero ¡de subconjuntos!)