Prueba biyectiva

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.

Ejemplos básicos

Prueba de la simetría de los coeficientes binomiales

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 biyectiva

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

Relación de recurrencia del triángulo de Pascal

por Prueba biyectiva

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.

Otros ejemplos

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:

Véase también

Notas

Literatura

Enlaces