Una prueba biyectiva es una técnica de prueba que encuentra una función biyectiva f : A → B entre dos conjuntos finitos A y B o una función biyectiva que preserva el tamaño entre dos clases combinatorias , que prueba el mismo número de elementos, | un | = | B |. El lugar donde la técnica es útil es cuando queremos saber el tamaño de A , pero no podemos encontrar una forma directa de contar los elementos del conjunto. En este caso, establecer una biyección entre A y algún conjunto B resuelve el problema si el número de elementos del conjunto B es más fácil de calcular. Otra propiedad útil de esta técnica es que la naturaleza de la biyección misma a menudo proporciona información importante sobre cada uno de los dos conjuntos.
La simetría de los coeficientes binomiales establece que
Esto significa que hay exactamente tantas combinaciones de k elementos de un conjunto que contiene n elementos como combinaciones de n − k elementos.
Prueba biyectivaTenga en cuenta que las dos cantidades para las que demostramos la igualdad cuentan el número de subconjuntos de tamaño k y n − k , respectivamente, de cualquier conjunto de n elementos S . Existe una biyección simple entre dos familias F k y F n − k de subconjuntos de S — relaciona cada subconjunto de elementos k con su complemento , que contiene exactamente los n − k elementos restantes de S . Dado que F k y F n − k tienen el mismo número de elementos, los coeficientes binomiales correspondientes deben ser iguales.
prueba _ Contamos el número de formas de seleccionar k elementos de un conjunto de n elementos. De nuevo, por definición, el lado izquierdo de la igualdad es igual al número de formas de elegir k elementos de n . Como 1 ≤ k ≤ n − 1, podemos fijar un elemento e de un conjunto de n elementos, de modo que el subconjunto restante no esté vacío. Para cada conjunto de elementos k , si se elige e , hay
formas de elegir los k − 1 elementos restantes entre las n − 1 posibilidades restantes. De lo contrario, hay
formas de elegir los k elementos restantes entre las n − 1 posibilidades restantes. Entonces hay
Formas de elegir k elementos.
Los problemas que permiten la demostración combinatoria no se limitan a los coeficientes binomiales. A medida que aumenta la complejidad del problema, la prueba combinatoria se vuelve más y más sofisticada. La técnica de prueba biyectiva es útil en áreas de matemáticas discretas como combinatoria , teoría de grafos y teoría de números .
Los ejemplos más clásicos de demostraciones biyectivas en combinatoria son: