Contar lo mismo de dos formas para obtener identidades.
El conteo doble, también conocido como "contar de dos formas", es una técnica combinatoria súper potente que sirve para demostrar identidades o resolver problemas calculando el tamaño de un conjunto usando dos métodos distintos. El principio básico es muy lógico: si cuentas una cantidad correctamente con el Método A y te da $X$, y luego la cuentas correctamente con el Método B y te da $Y$, entonces $X$ tiene que ser igual a $Y$. Esta técnica se usa muchísimo para demostrar propiedades de los coeficientes binomiales, sacar resultados en teoría de gráficas (como el Lema del Apretón de Manos) y resolver problemas complejos de geometría de incidencia.
En las olimpiadas de matemáticas, el conteo doble suele aparecer de dos formas. La primera es la "Historia Combinatoria", donde demuestras una identidad algebraica inventando un escenario hipotético (como formar un comité) y enseñando que ambos lados de la ecuación son formas válidas de contar los resultados. La segunda es el "Conteo de Incidencias", que a veces lo puedes visualizar con una matriz o una gráfica bipartita. Si sumas las "incidencias" (como marquitas en una cuadrícula) fila por fila y comparas eso con la suma columna por columna, puedes sacar igualdades o desigualdades que relacionan los parámetros de las filas y las columnas. Formalmente, a esto lo conocemos como el principio de Fubini para sumas discretas.
El truco principal para dominar este tema es saber cambiar de perspectiva. Cuando veas una suma con términos combinatorios, pregúntate: "¿Qué estructura está contando este término?". Al revés, si tienes un conjunto de restricciones (como puntos y líneas, o alumnos y clases), busca alguna cantidad —muchas veces el número de parejas $(x, y)$ que cumplen cierta condición— que puedas sumar desde la perspectiva de $x$ y, por separado, desde la perspectiva de $y$.
1. El Principio de Incidencia General Sea $S \subseteq A \times B$ una relación entre dos conjuntos finitos $A$ y $B$. Sea $r_a$ el número de elementos en $B$ relacionados con $a \in A$, y $c_b$ el número de elementos en $A$ relacionados con $b \in B$. Entonces: $$ \sum_{a \in A} r_a = |S| = \sum_{b \in B} c_b $$
2. El Lema del Apretón de Manos (Teoría de Gráficas) Para una gráfica $G = (V, E)$, la suma de los grados de los vértices es el doble del número de aristas: $$ \sum_{v \in V} \deg(v) = 2|E| $$
3. La Identidad del "Presidente del Comité" Elegir un comité de tamaño $k$ de entre $n$ personas, y luego nombrar a un presidente de ese comité: $$ k \binom{n}{k} = n \binom{n-1}{k-1} $$
4. Identidad de Vandermonde Sumar las formas de armar un grupo de tamaño $r$ a partir de dos grupos distintos de tamaños $m$ y $n$: $$ \sum_{k=0}^r \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r} $$
5. Suma de Coeficientes Binomiales Contar el número total de subconjuntos de un conjunto de tamaño $n$: $$ \sum_{k=0}^n \binom{n}{k} = 2^n $$
Teorema: Identidad de Vandermonde Para enteros no negativos $m, n, r$, se cumple la siguiente igualdad: $$ \sum_{k=0}^r \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r} $$
Demostración: Vas a demostrar esta identidad contando de cuántas formas puedes formar un comité de tamaño $r$ a partir de un grupo que tiene $m$ hombres y $n$ mujeres. Sea $S$ el conjunto de todos los comités posibles de tamaño $r$. La idea es contar $|S|$ de dos formas distintas.
Método 1: Selección Directa Considera al grupo de hombres y mujeres como un solo conjunto de personas. El número total de personas es $m + n$. Tienes que elegir un comité de $r$ personas de este grupo combinado. Por la definición del coeficiente binomial, el número de formas de hacer esto es: $$ |S| = \binom{m+n}{r} $$
Método 2: Condicionar según la Composición Puedes clasificar cada comité posible basándote en cuántos hombres incluye. Sea $k$ el número de hombres en el comité. Como el tamaño del comité tiene que ser exactamente $r$, si eliges $k$ hombres, tienes que elegir exactamente $r-k$ mujeres. Los valores posibles para $k$ van de $0$ a $r$ (suponiendo que $r \le m$ y $r \le n$ para simplificar, aunque la definición del coeficiente binomial se encarga de los casos donde $k>m$ o $r-k>n$ haciendo que valgan 0).
Para un valor específico de $k$:
Como la elección de hombres y mujeres es independiente, el número de comités con exactamente $k$ hombres es el producto: $$ \binom{m}{k}\binom{n}{r-k} $$
Para encontrar el número total