En combinatoria , la prueba biyectiva es una técnica de prueba para demostrar que dos conjuntos tienen la misma cantidad de elementos, o que los conjuntos en dos clases combinatorias tienen el mismo tamaño, al encontrar una función biyectiva que mapea un conjunto uno a uno sobre el otro. Esta técnica puede ser útil como una forma de encontrar una fórmula para el número de elementos de ciertos conjuntos, al corresponderlos con otros conjuntos que son más fáciles de contar. Además, la naturaleza de la biyección en sí misma a menudo proporciona información valiosa sobre cada uno o ambos conjuntos.
La simetría de los coeficientes binomiales establece que
Esto significa que hay exactamente tantas combinaciones de k cosas en un conjunto de tamaño n como combinaciones de n − k cosas en un conjunto de tamaño n .
La idea clave de la prueba se puede entender a partir de un ejemplo simple: seleccionar k niños para ser recompensados con conos de helado, de un grupo de n niños, tiene exactamente el mismo efecto que elegir en cambio a los n − k niños a los que se les negarán los conos de helado.
De manera más abstracta y general, [1] las dos cantidades que se afirma que son iguales cuentan los subconjuntos de tamaño k y n − k , respectivamente, de cualquier conjunto de n elementos S . Sea A el conjunto de todos los subconjuntos de k elementos de S , el conjunto A tiene tamaño Sea B el conjunto de todos los subconjuntos de n − k de S , el conjunto B tiene tamaño . Hay una biyección simple entre los dos conjuntos A y B : asocia cada subconjunto de k elementos (es decir, un miembro de A ) con su complemento , que contiene precisamente los n − k elementos restantes de S , y por lo tanto es un miembro de B . De manera más formal, esto se puede escribir usando notación funcional como, f : A → B definido por f ( X ) = X c para X cualquier subconjunto de k elementos de S y el complemento tomado en S . Para demostrar que f es una biyección, supongamos primero que f ( X 1 ) = f ( X 2 ) , es decir, X 1 c = X 2 c . Tome los complementos de cada lado (en S ), usando el hecho de que el complemento de un complemento de un conjunto es el conjunto original, para obtener X 1 = X 2 . Esto demuestra que f es uno a uno . Ahora tomemos cualquier subconjunto de n−k elementos de S en B , digamos Y . Su complemento en S , Y c , es un subconjunto de k elementos, y por lo tanto, un elemento de A . Como f ( Y c ) = ( Y c ) c = Y , f también es sobreyectiva y por lo tanto una biyección. El resultado ahora se deduce ya que la existencia de una biyección entre estos conjuntos finitos muestra que tienen el mismo tamaño, es decir,.
Los problemas que admiten demostraciones biyectivas no se limitan a las identidades de coeficientes binomiales. A medida que aumenta la complejidad del problema, una demostración biyectiva puede volverse muy sofisticada. Esta técnica es particularmente útil en áreas de matemáticas discretas como la combinatoria , la teoría de grafos y la teoría de números .
Los ejemplos más clásicos de pruebas biyectivas en combinatoria incluyen:
