Hispanopedia WikiEn combinatoria , la demostración biyectiva es una técnica para probar que dos conjuntos tienen la misma cantidad de elementos, o que los conjuntos de dos clases combinatorias tienen el mismo tamaño, mediante la búsqueda de una función biyectiva que mapea un conjunto sobre el otro de forma biyectiva. Esta técnica puede ser útil para hallar una fórmula que calcule el número de elementos de ciertos conjuntos, al relacionarlos con otros conjuntos más fáciles de contar. Además, la naturaleza de la biyección en sí misma suele proporcionar información valiosa sobre uno o ambos conjuntos.
Ejemplos básicos
Demostrando 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 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 demostración biyectiva se puede entender con un ejemplo sencillo: seleccionar k niños para que sean 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 para que no reciban conos de helado.
Otros ejemplos
Los problemas que admiten demostraciones biyectivas no se limitan a 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 las 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 demostraciones biyectivas en combinatoria incluyen:
- Secuencia de Prüfer , que proporciona una demostración de la fórmula de Cayley para el número de árboles etiquetados .
- Algoritmo de Robinson-Schensted , que proporciona una demostración de la fórmula de Burnside para el grupo simétrico .
- Conjugación de diagramas de Young , que proporciona una demostración de un resultado clásico sobre el número de ciertas particiones enteras .
- Demostraciones biyectivas del teorema del número pentagonal .
- Demostraciones biyectivas de la fórmula para los números de Catalan .
Véase también
Referencias
Lecturas adicionales
Enlaces externos
- "División por tres" – por Doyle y Conway .
- "Una demostración biyectiva directa de la fórmula de la longitud del gancho" – por Novelli, Pak y Stoyanovsky.
- "Censo biyectivo y generación aleatoria de mapas planares eulerianos con grados de vértice prescritos" – por Gilles Schaeffer.
- "Demostración constructiva de Kathy O'Hara sobre la unimodalidad de los polinomios gaussianos" – por Doron Zeilberger .
- "Biyecciones de partición, un estudio" – por Igor Pak .
- Principio de involución de Garcia-Milne – de MathWorld .
- Combinatoria enumerativa
- Demostraciones matemáticas