Demostración biyectiva

En combinatoria, una demostración biyectiva es una técnica de demostración utilizada para probar que dos conjuntos tienen el mismo número de elementos, o que los conjuntos de dos clases combinatorias tienen el mismo tamaño, mediante la descripción de una biyección entre un conjunto y el otro (es decir, una correspondencia de uno a uno entre los conjuntos). Esta técnica puede ser útil para encontrar una fórmula para el número de elementos de ciertos conjuntos, biyectándolos con otros más fáciles de contar. Además, la naturaleza de la biyección en sí misma proporciona información valiosa sobre uno o ambos conjuntos.

Ejemplos

Simetría de los coeficientes binomiales

La simetría de los coeficientes binomiales afirma que

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

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

Demostración biyectiva

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

Igualdad de la suma de coeficientes binomiales de rango par con los de rango impar

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

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

Demostración biyectiva

La primera suma es el número de partes de un conjunto $A$ (con $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 $a\in A$ tenemos la siguiente biyección entre partes pares e impares: dada una parte, le añadimos el elemento $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. $\quad \square$

Otros ejemplos

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.

Bibliografía

• 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.

Enlaces externos

• Datos: Q592286