En matemáticas , el término prueba combinatoria se utiliza a menudo para referirse a cualquiera de dos tipos de prueba matemática :
El término "prueba combinatoria" también puede usarse de manera más amplia para referirse a cualquier tipo de prueba elemental en combinatoria. Sin embargo, como escribe Glass (2003) en su reseña de Benjamin & Quinn (2003) (un libro sobre pruebas combinatorias), estas dos técnicas simples son suficientes para probar muchos teoremas en combinatoria y teoría de números .
Una prueba arquetípica de doble conteo es la conocida fórmula para el número de k combinaciones (es decir, subconjuntos de tamaño k ) de un conjunto de n elementos:
Aquí no es posible una prueba biyectiva directa: debido a que el lado derecho de la identidad es una fracción, no hay ningún conjunto que obviamente cuente (incluso hay que pensar un poco para ver que el denominador siempre divide uniformemente al numerador). Sin embargo, su numerador cuenta el producto cartesiano de k conjuntos finitos de tamaños n , n − 1 , ..., n − k + 1 , mientras que su denominador cuenta las permutaciones de un conjunto de k elementos (el conjunto contado más obviamente por el denominador sería otro producto cartesiano k conjuntos finitos; si se desea, se podrían asignar permutaciones a ese conjunto mediante una biyección explícita). Ahora tome S como el conjunto de secuencias de k elementos seleccionados de nuestro conjunto de n elementos sin repetición. Por un lado, hay una biyección fácil de S con el producto cartesiano correspondiente al numerador , y por otro lado hay una biyección del conjunto C de pares de una k -combinación y una permutación σ de k a S , por tomando los elementos de C en orden creciente y luego permutando esta secuencia por σ para obtener un elemento de S. Las dos formas de contar dan la ecuación.
y después de dividir por k ! esto lleva a la fórmula indicada para . En general, si la fórmula de conteo implica una división, un argumento de doble conteo similar (si existe) proporciona la prueba combinatoria más sencilla de la identidad, pero los argumentos de doble conteo no se limitan a situaciones en las que la fórmula tiene esta forma.
Aquí hay una prueba combinatoria más simple e informal de la misma identidad:
Supongamos que a n personas les gustaría entrar a un museo, pero el museo solo tiene espacio para k personas. Primero elija qué k personas de entre las n personas podrán ingresar. Hay formas de hacer esto por definición. Ahora ordene a las k personas en una sola fila para que puedan pagar de una en una. ¡Hay k ! formas de permutar este conjunto de tamaño k . A continuación, ordene a las n − k personas que deben permanecer afuera en una sola fila para que luego puedan entrar una a la vez, mientras los demás salen. ¡Hay ( n − k )! maneras de hacer esto. Pero ahora hemos ordenado todo el grupo de n personas, ¡algo que se puede hacer en n ! maneras. Entonces ambos lados cuentan el número de formas de ordenar a las n personas. La división produce la conocida fórmula para .
Stanley (1997) da un ejemplo de un problema de enumeración combinatoria (contando el número de secuencias de k subconjuntos S 1 , S 2 , ... S k , que pueden formarse a partir de un conjunto de n elementos tales que la intersección de todos los subconjuntos está vacío) con dos pruebas diferentes para su solución. La primera prueba, que no es combinatoria, utiliza inducción matemática y funciones generadoras para encontrar que el número de secuencias de este tipo es (2 k −1) n . La segunda prueba se basa en la observación de que hay 2 k −1 subconjuntos propios del conjunto {1, 2, ..., k }, y (2 k −1) n funciones del conjunto {1, 2, . .., n } a la familia de subconjuntos propios de {1, 2, ..., k }. Las secuencias a contar se pueden colocar en correspondencia uno a uno con estas funciones, donde la función formada a partir de una secuencia dada de subconjuntos asigna cada elemento i al conjunto { j | yo ∈ S j }.
Stanley escribe: “La prueba combinatoria anterior no sólo es mucho más corta que nuestra prueba anterior, sino que también hace que el motivo de la respuesta simple sea completamente transparente. A menudo ocurre, como ocurrió aquí, que la primera prueba que nos viene a la mente resulta laboriosa y poco elegante, pero que la respuesta final sugiere una prueba combinatoria simple”. Debido a su frecuente mayor elegancia que las pruebas no combinatorias y a la mayor comprensión que brindan de las estructuras que describen, Stanley formula un principio general de que las pruebas combinatorias deben preferirse a otras pruebas y enumera como ejercicios muchos problemas para encontrar pruebas combinatorias. para hechos matemáticos que se sabe que son verdaderos por otros medios.
Stanley no distingue claramente entre pruebas biyectivas y de doble conteo, y da ejemplos de ambos tipos, pero la diferencia entre los dos tipos de prueba combinatoria se puede ver en un ejemplo proporcionado por Aigner y Ziegler (1998), de pruebas de la fórmula de Cayley que establece que hay n n − 2 árboles diferentes que se pueden formar a partir de un conjunto dado de n nodos. Aigner y Ziegler enumeran cuatro demostraciones de este teorema, la primera de las cuales es biyectiva y la última es un argumento de doble conteo. También mencionan, pero no describen, los detalles de una quinta prueba biyectiva.
La forma más natural de encontrar una prueba biyectiva de esta fórmula sería encontrar una biyección entre n árboles de nodos y alguna colección de objetos que tenga n n − 2 miembros, como las secuencias de n − 2 valores cada uno en el rango de 1 al n . Esta biyección se puede obtener utilizando la secuencia de Prüfer de cada árbol. Cualquier árbol puede codificarse de forma única en una secuencia de Prüfer, y cualquier secuencia de Prüfer puede decodificarse de manera única en un árbol; Estos dos resultados juntos proporcionan una prueba biyectiva de la fórmula de Cayley.
Una prueba biyectiva alternativa, dada por Aigner y Ziegler y acreditada por ellos a André Joyal , implica una biyección entre, por un lado, árboles de n -nodos con dos nodos designados (que pueden ser iguales entre sí), y por el otro. Por otro lado, pseudobosques dirigidos por n nodos . Si hay T n n árboles de nodos, entonces hay n 2 T n árboles con dos nodos designados. Y un pseudobosque puede determinarse especificando, para cada uno de sus nodos, el punto final del borde que se extiende hacia afuera desde ese nodo; Hay n opciones posibles para el punto final de un solo borde (lo que permite bucles automáticos) y, por lo tanto, n n pseudobosques posibles. Al encontrar una biyección entre árboles con dos nodos etiquetados y pseudobosques, la prueba de Joyal muestra que T n = n n − 2 .
Finalmente, la cuarta prueba de la fórmula de Cayley presentada por Aigner y Ziegler es una prueba de doble contabilización debida a Jim Pitman . En esta prueba, Pitman considera las secuencias de aristas dirigidas que se pueden agregar a un gráfico vacío de n nodos para formar a partir de él un árbol con raíz única, y cuenta el número de dichas secuencias de dos maneras diferentes. Al mostrar cómo derivar una secuencia de este tipo eligiendo un árbol, una raíz para el árbol y un orden para las aristas del árbol, demuestra que hay T n n ! posibles secuencias de este tipo. Y al contar el número de formas en que una secuencia parcial puede extenderse en una sola arista, demuestra que hay n n − 2 n ! secuencias posibles. ¡Igualar estas dos fórmulas diferentes para el tamaño del mismo conjunto de secuencias de aristas y cancelar el factor común de n ! conduce a la fórmula de Cayley.
