En combinatoria , la prueba biyectiva es una técnica de prueba para demostrar que dos conjuntos tienen el mismo número de elementos, o que los conjuntos en dos clases combinatorias tienen el mismo tamaño, al encontrar una función biyectiva que asigna un conjunto uno a uno al otro. Esta técnica puede resultar útil como forma de encontrar una fórmula para el número de elementos de determinados conjuntos, correlacionándolos con otros conjuntos que sean más fáciles de contar. Además, la naturaleza de la biyección misma a menudo proporciona información poderosa 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 puede entenderse a partir de un ejemplo sencillo: 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 a los n − k niños a los que se les negará el hielo. conos de crema.
De manera más abstracta y general, [1] las dos cantidades que se afirman 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 n−k subconjuntos 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 tanto es un miembro. de B . Más formalmente, 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, primero supongamos que f ( X 1 ) = f ( X 2 ) , es decir, X 1 c = X 2 c . Tome los complementos de cada lado (en S ), utilizando el hecho de que el complemento de un complemento de un conjunto es el conjunto original, para obtener X 1 = X 2 . Esto muestra que f es uno a uno . Ahora tome 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 tanto, un elemento de A. Dado que f ( Y c ) = ( Y c ) c = Y , f también es sobrey , por tanto, una biyección. El resultado ahora se sigue 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 pruebas biyectivas no se limitan a identidades de coeficientes binomiales. A medida que aumenta la complejidad del problema, una prueba biyectiva puede volverse muy sofisticada. Esta técnica es particularmente ú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 pruebas biyectivas en combinatoria incluyen:
