Demostración biyectiva

La simetría de los coeficientes binomiales afirma que

${\displaystyle {n \choose k}={n \choose n-k}}$.

En otras palabras, que hay tantas combinaciones de ${\displaystyle k}$ elementos como de ${\displaystyle n-k}$ elementos de entre ${\displaystyle n}$.

${\displaystyle n \choose k}$ es, por definición, el número de subconjuntos de ${\displaystyle k}$ elementos de un conjunto de ${\displaystyle n}$. Entonces, tenemos que biyectar los siguientes dos conjuntos: los subconjuntos de ${\displaystyle k}$ elementos de uno de ${\displaystyle n}$ y los subconjuntos de ${\displaystyle n-k}$ elementos de uno de ${\displaystyle n}$. Esta biyección es sencilla: es el complementario. Un subconjunto de ${\displaystyle k}$ elementos se puede entender como una elección de ${\displaystyle k}$ elementos de entre los ${\displaystyle n}$ posibles. Ahora, dado uno de estos subconjuntos (una elección) podemos definir un subconjunto de ${\displaystyle n-k}$ elementos eligiendo los ${\displaystyle n-k}$ elementos que no estaban elegidos. Recíprocamente, dada una elección de ${\displaystyle n-k}$ elementos podemos definir otra de ${\displaystyle k}$ eligiendo los que no hayan sido elegidos. Por tanto, tenemos una biyección entre los subconjuntos de ${\displaystyle k}$ elementos de uno de ${\displaystyle n}$ y los subconjuntos de ${\displaystyle n-k}$ elementos de uno de ${\displaystyle n}$. Por las propiedades de las biyecciones, esto quiere decir que ambos conjuntos tienen el mismo número de elementos y, por definición, que ${\displaystyle {n \choose k}={n \choose n-k}\quad \square }$

Se trata de la siguiente relación, válida para ${\displaystyle n\geq 1}$:

${\displaystyle \sum _{0\leqslant 2k\leqslant n}{\binom {n}{2k}}=\sum _{0\leqslant 2k+1\leqslant n}{\binom {n}{2k+1}}}$

La primera suma es el número de partes de un conjunto ${\displaystyle A}$ (con ${\displaystyle n}$ elementos) con un número par de elementos. La segunda es el número de partes con un número de elementos impar. Fijando un elemento ${\displaystyle a\in A}$ tenemos la siguiente biyección entre partes pares e impares: dada una parte, le añadimos el elemento ${\displaystyle a}$ si no lo tenía y se lo quitemos si ya lo tenía. Así, dada una parte par obtenemos una impar y viceversa. Por tanto, tenemos una biyección entre las partes pares e impartes, por lo que hay el mismo número de unas que de las otras, lo que es equivalente al enunciado. ${\displaystyle \quad \square }$

A continuación se presentan algunos ejemplos clásicos de demostraciones biyectivas del análisis combinatorio:

• Muchos resultados sobre los coeficientes binomiales utilizan demostraciones combinatorias, como la famosa barras y estrellas.
• Los múltiples recuentos que conducen a los números de Catalan se obtienen mediante biyecciones.
• El código de Prüfer, una biyección que permite demostrar la fórmula de Cayley sobre árboles etiquetados.
• La correspondencia de Robinson-Schensted, biyección que permite demostrar la fórmula de Burnside para el grupo simétrico.
• La conjugación de tablas de Young permite obtener una demostración de la fórmula para las particiones de un entero.
• La demostración por biyección del teorema del número pentagonal.

• Mazur, David E. (2010), Combinatorics / A Guided Tour, The Mathematical Association of America, p. 28. ISBN 978-0-88385-762-5.
• Loehr, Nicholas A. (2011), Bijective Combinatorics. ISBN 978-1439848845.

• Esta obra contiene una traducción derivada de «Preuve par bijection» de Wikipedia en francés, concretamente de esta versión, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.