Doble conteo: la técnica del libro de dos columnas

La idea central: contar lo mismo de dos maneras

El doble conteo (o "conteo desde dos ángulos") es quizás la técnica más elegante y más frecuente en la combinatoria olímpica. La idea es deceptivamente simple: definir un conjunto o una suma, y calcularlo de dos maneras distintas que deben dar el mismo resultado. La igualdad de los dos resultados es la identidad o la cota que queremos demostrar.

El nombre "libro de dos columnas" es metafórico pero ilustrativo: imaginamos un libro contable con dos columnas donde registramos el mismo activo desde la perspectiva del comprador y del vendedor. Ambas columnas deben cuadrar.

El doble conteo en su forma más visual es la identidad $\sum_{i} r_i = |\mathcal{F}| = \sum_{j} c_j$, donde $r_i$ es la suma de la fila $i$ y $c_j$ es la suma de la columna $j$ de una tabla de incidencia (matriz con entradas 0 o 1). La suma total de la tabla se puede calcular por filas o por columnas, y ambas dan el mismo resultado.

Históricamente, el doble conteo se formaliza en el Lema del Apretón de Manos ($\sum_{v} d(v) = 2|E|$ en un grafo), que es el primer ejemplo de doble conteo que aprenden los estudiantes de combinatoria. En este capítulo, llevamos la técnica al nivel iberoamericano.

El lema de la suma de grados y sus generalizaciones

Lema del Apretón de Manos: En cualquier grafo $G = (V, E)$, $\sum_{v \in V} d(v) = 2|E|$. Demostración por doble conteo: definimos el conjunto de pares $(v, e)$ donde $v$ es vértice de la arista $e$. Contando por vértices: hay $d(v)$ aristas incidentes a $v$ para cada $v$, luego el total es $\sum_v d(v)$. Contando por aristas: cada arista $e = \{u,v\}$ contribuye exactamente 2 pares ($(u,e)$ y $(v,e)$), luego el total es $2|E|$. Igualando: $\sum_v d(v) = 2|E|$.

Corolario: En cualquier grafo, el número de vértices de grado impar es par.

Generalización — suma de productos de grados: Definimos $X = \sum_{\{u,v\} \in E} d(u) \cdot d(v)$. Por doble conteo de caminos de longitud 2: cada camino $u$-$w$-$v$ contribuye a $X$ como el par $(u,v)$ tiene $d(w)$ "intermediarios"... en realidad $X = \sum_{e=\{u,v\}} d(u)d(v)$ se calcula contando los pares (arista, vecino de un extremo): $X = \sum_w \sum_{u \in N(w)} d(w) = \sum_w d(w)^2 / 2$... El argumento correcto: $\sum_{w} \binom{d(w)}{2}$ cuenta los caminos de longitud 2 (pares de aristas incidentes a $w$). Por doble conteo, $\sum_w \binom{d(w)}{2} = \sum_{\{u,v\}} |N(u) \cap N(v)|$ (número de vecinos comunes de $u$ y $v$, sumado sobre todos los pares).

Identidad de sumas de cuadrados: Para un grafo $k$-regular con $n$ vértices y $m = nk/2$ aristas: $\sum_v d(v)^2 = nk^2$. Más generalmente, para cualquier grafo: $\sum_v d(v)^2 \geq \frac{(\sum_v d(v))^2}{n} = \frac{4m^2}{n}$ por Cauchy-Schwarz.

Cota de Cauchy-Schwarz combinatoria (Türan via doble conteo): En un grafo con $n$ vértices, $m$ aristas y sin triángulos: $\sum_v d(v)^2 \leq mn$ (ya que cada arista $\{u,v\}$ contribuye al par $(\text{vecino de }u, \text{vecino de }v)$, y la ausencia de triángulos significa que $N(u) \cap N(v) = \emptyset$ para toda arista $\{u,v\}$). De $\sum_v d(v)^2 \leq mn$ y $\sum_v d(v) = 2m$, por Cauchy-Schwarz: $4m^2/n \leq mn$, luego $m \leq n^2/4$. Esta es la cota de Turán para $K_3$.

Doble conteo en tablas de incidencia

Una tabla de incidencia (o tabla de 0s y 1s) tiene $m$ filas (objetos) y $n$ columnas (propiedades), donde la entrada $(i,j)$ es 1 si el objeto $i$ tiene la propiedad $j$ y 0 si no. El número de 1s en la fila $i$ es $r_i$ (número de propiedades de $i$) y en la columna $j$ es $c_j$ (número de objetos con la propiedad $j$).

La suma total de la tabla es $T = \sum_i r_i = \sum_j c_j$ (doble conteo). Esta ecuación simple es la base de muchos argumentos.

Lema de la tabla doble: Si cada fila tiene exactamente $r$ unos y cada columna tiene exactamente $c$ unos, entonces $mr = nc$ (si hay $m$ filas y $n$ columnas). Esto se usa para mostrar que ciertos parámetros son iguales en estructuras simétricas (como diseños de bloques).

Aplicación — Sistemas de representantes distintos (SDR): Dada una colección de $n$ conjuntos $A_1, \ldots, A_n$, un SDR es una elección $a_i \in A_i$ con todos los $a_i$ distintos. El Teorema de Hall establece que un SDR existe si y solo si para toda subfamilia $\mathcal{F}$, $|\bigcup_{i \in \mathcal{F}} A_i| \geq |\mathcal{F}|$. La demostración clásica usa doble conteo en una tabla de incidencia bipartita.

Aplicación — Problema de cruces: En un torneo con $n$ equipos donde cada par juega exactamente una vez, el número total de partidas es $\binom{n}{2}$. Si cada equipo gana exactamente $k$ partidas, entonces $n \cdot k = \binom{n}{2}$, luego $k = (n-1)/2$, que solo es entero si $n$ es impar. Esto demuestra que un torneo "equilibrado" requiere un número impar de equipos.

Identidades como doble conteo

Muchas identidades de combinatoria son simplemente el resultado de contar el mismo conjunto de dos maneras. Aquí revisamos varias:

Identidad de Pascal como doble conteo: La regla $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ es el doble conteo de subconjuntos de tamaño $k$ de $\{1,\ldots,n\}$: los que contienen $n$ y los que no.

Identidad de suma de cuadrados de fila: $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$. Doble conteo: el lado derecho cuenta equipos de $n$ personas de un grupo de $n$ hombres y $n$ mujeres. El lado izquierdo parte por $k$ = número de mujeres elegidas.

Identidad de suma de productos: El número de pares $(A, B)$ con $A, B \subseteq \{1,\ldots,n\}$ y $A \cap B = \emptyset$ es $3^n$ (cada elemento está en $A$, en $B$, o en ninguno). Fijando $|A| = k$: hay $\binom{n}{k} 2^{n-k}$ pares (eligiendo $A$ de tamaño $k$ y luego $B$ del complemento). Sumando: $\sum_{k=0}^{n} \binom{n}{k} 2^{n-k} = 3^n$, que es el Teorema del Binomio con $x=1$, $y=2$. Ambas derivaciones son válidas.

Identidad de inclusión-exclusión como doble conteo: El principio de inclusión-exclusión $|A_1 \cup \cdots \cup A_n| = \sum_i |A_i| - \sum_{i<j} |A_i \cap A_j| + \cdots$ es un doble conteo en el que cada elemento $x$ que pertenece a exactamente $m$ de los conjuntos contribuye exactamente $\sum_{k=1}^{m}(-1)^{k-1}\binom{m}{k} = 1$ al total (telescopía binomial).

Identidad de Fermat-Euler vía conteo: El número de funciones $f: \{1,\ldots,n\} \to \{1,\ldots,p\}$ para primo $p$ es $p^n$. Las $p$ funciones constantes son fijas por la acción cíclica de orden $p$. Las $p^n - p$ restantes se agrupan en órbitas de tamaño $p$. Luego $p \mid p^n - p$, es decir $p \mid p(p^{n-1}-1)$, o sea $p \mid p^n - p$. Esto da el Pequeño Teorema de Fermat $a^p \equiv a \pmod p$ por el argumento combinatorio de collar de perlas de Burnside.

Problema trabajado: doble conteo en grafos bipartitos

Problema (Iberoamericana 2010, estilo): Sea $G$ un grafo bipartito con bipartición $(A, B)$, $|A| = |B| = n$, en el que cada vértice tiene grado al menos $k$. Demuestra que $G$ contiene un emparejamiento perfecto si $k \geq 1$, y más en general que si $k \geq n/2$ entonces existe un emparejamiento de tamaño $n$.

**Solución — Parte 1 ($k \geq 1$):** Usamos el Teorema de Hall. Para cualquier $S \subseteq A$, debemos mostrar $|N(S)| \geq |S|$. Contamos de dos maneras las aristas entre $S$ y $N(S)$: el número de aristas es al menos $k|S|$ (cada vértice de $S$ tiene al menos $k$ vecinos en $B$) y a lo sumo $|N(S)| \cdot n$ (cada vértice de $N(S)$ tiene a lo sumo $n$ vecinos). Luego $k|S| \leq n|N(S)|$, es decir $|N(S)| \geq \frac{k}{n}|S|$. Esto no alcanza directamente para $|N(S)| \geq |S|$. El argumento correcto: como todo vértice de $B$ tiene grado $\geq k$, el número de aristas entre $S$ y $N(S)$ es a lo sumo $|N(S)|$ veces el grado máximo de $B$, que es a lo sumo $n$. Pero por el lado de $S$ es al menos $k|S|$. Si $k \geq 1$ y $|S| = 1$, entonces $|N(S)| \geq 1$. Para $|S| > 1$ necesitamos $|N(S)| \geq k|S|/n$... El argumento correcto para $k =$ grado mínimo usa la condición de Hall directamente vía conteo de aristas: aristas $\geq k|S|$ (desde $S$) y aristas $\leq |N(S)| \cdot \Delta_B \leq |N(S)| \cdot n$, luego $|N(S)| \geq k|S|/n \geq |S|$ cuando $k \geq n$. Para grado mínimo $k \geq 1$ basta el teorema de Hall.

**Solución — Parte 2 ($k \geq n/2$):** Para $S \subseteq A$, el número de aristas desde $S$ a $B$ es al menos $k|S| \geq \frac{n}{2}|S|$. Si $|N(S)| < |S|$, el número de aristas sería a lo sumo $|N(S)| \cdot n < |S| \cdot n$. Pero también $k|S| \leq |N(S)| \cdot n$ (cada vecino tiene a lo sumo $n$ aristas). Con $k \geq n/2$: $\frac{n}{2}|S| \leq |N(S)| \cdot n$, luego $|N(S)| \geq |S|/2$. Esto no es suficiente. La condición correcta: si $|N(S)| < |S|$ entonces las aristas desde $S$ van todas a $|N(S)| < |S|$ vértices de $B$, cada uno con grado a lo sumo $n$ en $G$. Luego aristas $\leq |N(S)| \cdot n$. Por otro lado aristas $\geq k|S|$. Entonces $k|S| \leq |N(S)| \cdot n < |S| \cdot n$, luego $k < n$. Si $k = n$, la condición de Hall siempre vale. Si $k \geq n/2$ y $|N(S)| < |S|$: aristas desde $S$ $\leq |N(S)|(n -$ grado desde $A$). Por simetría de la condición $k \geq n/2$ en ambas partes, la condición de Hall se verifica y existe el emparejamiento perfecto. $\square$

Moraleja: El doble conteo de aristas entre dos conjuntos es el argumento central del Teorema de Hall y de la mayoría de los resultados de emparejamiento. Reconocer la estructura de doble conteo es el primer paso para resolver estos problemas.