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 demostrar 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: como el lado derecho de la identidad es una fracción, no hay ningún conjunto que cuente obviamente (incluso hace falta pensar un poco para ver que el denominador siempre divide al numerador de manera uniforme). 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 de k conjuntos finitos; si se desea, se podrían aplicar permutaciones a ese conjunto mediante una biyección explícita). Ahora tomemos S como el conjunto de secuencias de k elementos seleccionados de nuestro conjunto de n elementos sin repetición. Por un lado, existe una biyección fácil de S con el producto cartesiano correspondiente al numerador , y por otro lado existe una biyección a partir del conjunto C de pares de una k -combinación y una permutación σ de k a S , 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 la división por k ! esto conduce a la fórmula establecida para . En general, si la fórmula de conteo implica una división, un argumento de conteo doble similar (si existe) proporciona la prueba combinatoria más directa de la identidad, pero los argumentos de conteo doble no se limitan a situaciones donde la fórmula tiene esta forma.
He aquí una prueba combinatoria más simple e informal de la misma identidad:
Supongamos que n personas quisieran entrar a un museo, pero el museo sólo tiene espacio para k personas. Primero, elija qué k personas de entre las n personas podrán entrar. Hay formas de hacer esto por definición. Ahora, ordene a las k personas en una sola fila para que puedan pagar una a la vez. 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 las demás salen. Hay ( n − k )! formas de hacer esto. Pero ahora hemos ordenado todo el grupo de n personas, algo que se puede hacer de n ! formas. 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 (contar 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ía) con dos demostraciones diferentes para su solución. La primera demostración, que no es combinatoria, utiliza la inducción matemática y las funciones generadoras para encontrar que el número de secuencias de este tipo es (2 k −1) n . La segunda demostración 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 desde el conjunto {1, 2, ..., n } hasta 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 | i ∈ 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 la razón de la respuesta simple sea completamente transparente. A menudo ocurre, como ocurrió aquí, que la primera prueba que viene a la mente resulta ser laboriosa y poco elegante, pero que la respuesta final sugiere una prueba combinatoria simple”. Debido tanto a su mayor elegancia que las pruebas no combinatorias como a la mayor comprensión que proporcionan de las estructuras que describen, Stanley formula un principio general de que las pruebas combinatorias son preferibles a otras pruebas, y enumera como ejercicios muchos problemas de búsqueda de 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 para 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 pruebas de este teorema, la primera de las cuales es biyectiva y la última de las cuales es un argumento de doble conteo. También mencionan, pero no describen los detalles, 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 árboles de n 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 a n . Dicha biyección se puede obtener utilizando la secuencia de Prüfer de cada árbol. Cualquier árbol se puede codificar de forma única en una secuencia de Prüfer, y cualquier secuencia de Prüfer se puede decodificar de forma ú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 atribuida 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 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 de la arista que se extiende hacia afuera desde ese nodo; hay n posibles elecciones para el punto final de una sola arista (permitiendo autobucles) y, por lo tanto, n n posibles pseudobosques. 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 conteo debida a Jim Pitman . En esta prueba, Pitman considera las secuencias de aristas dirigidas que pueden agregarse a un grafo vacío de n nodos para formar a partir de él un árbol con una sola raíz, y cuenta el número de tales 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 ordenamiento para las aristas en el árbol, muestra que hay T n n ! secuencias posibles de este tipo. Y al contar el número de formas en que una secuencia parcial puede extenderse por una sola arista, muestra que hay n n − 2 n ! secuencias posibles. Igualando estas dos fórmulas diferentes para el tamaño del mismo conjunto de secuencias de aristas y cancelando el factor común de n ! conduce a la fórmula de Cayley.
