Doble conteo (técnica de prueba)

En combinatoria , el conteo doble , también llamado conteo de dos maneras , es una técnica de prueba combinatoria para demostrar que dos expresiones son iguales al demostrar que son dos formas de contar el tamaño de un conjunto . En esta técnica, que van Lint y Wilson (2001) llaman "una de las herramientas más importantes en combinatoria", ^[1] se describe un conjunto finito desde dos perspectivas que conducen a dos expresiones distintas para el tamaño del conjunto. Dado que ambas expresiones son iguales al tamaño del mismo conjunto, son iguales entre sí.

Este es un ejemplo simple de conteo doble, que se usa a menudo cuando se enseña la multiplicación a niños pequeños. En este contexto, la multiplicación de números naturales se presenta como una adición repetida y luego se demuestra que es conmutativa al contar, de dos maneras diferentes, una cantidad de elementos dispuestos en una cuadrícula rectangular. Supongamos que la cuadrícula tiene filas y columnas. Primero contamos los elementos sumando filas de elementos cada una, luego una segunda vez sumando columnas de elementos cada una, mostrando así que, para estos valores particulares de y , .${\estilo de visualización n}$${\estilo de visualización m}$${\estilo de visualización n}$${\estilo de visualización m}$${\estilo de visualización m}$${\estilo de visualización n}$${\estilo de visualización n}$${\estilo de visualización m}$${\displaystyle n\veces m=m\veces n}$

Un ejemplo del método de doble conteo cuenta el número de formas en que se puede formar un comité a partir de personas, permitiendo que cualquier número de personas (incluso cero de ellas) forme parte del comité. Es decir, se cuenta el número de subconjuntos que puede tener un conjunto de elementos. Un método para formar un comité es pedir a cada persona que elija si se une o no a él. Cada persona tiene dos opciones (sí o no) y estas opciones son independientes de las de las otras personas. Por lo tanto, hay posibilidades. Alternativamente, se puede observar que el tamaño del comité debe ser un número entre 0 y . Para cada tamaño posible , el número de formas en que se puede formar un comité de personas a partir de personas es el coeficiente binomial Por lo tanto, el número total de comités posibles es la suma de los coeficientes binomiales sobre . Igualar las dos expresiones le da a la identidad un caso especial del teorema binomial . Se puede utilizar un método de doble conteo similar para demostrar la identidad más general ^[2]${\estilo de visualización n}$${\estilo de visualización n}$${\displaystyle 2\veces 2\veces \cdots 2=2^{n}}$${\estilo de visualización n}$${\estilo de visualización k}$${\estilo de visualización k}$${\estilo de visualización n}$$${\displaystyle {n \elige k}.}$$${\displaystyle k=0,1,2,\puntos ,n}$$${\displaystyle \sum _{k=0}^{n}{n \choose k}=2^{n},}$$$${\displaystyle \sum _{k=d}^{n}{n \elegir k}{k \elegir d}=2^{nd}{n \elegir d}}$$

Otro teorema que se demuestra comúnmente con un argumento de doble conteo establece que todo grafo no dirigido contiene un número par de vértices de grado impar . Es decir, el número de vértices que tienen un número impar de aristas incidentes debe ser par. En términos más coloquiales, en un grupo de personas algunas de las cuales se dan la mano, un número par de personas debe haber estrechado la mano a un número impar de otras personas; por esta razón, el resultado se conoce como el lema del apretón de manos .

Para demostrar esto por doble conteo, sea el grado del vértice . El número de incidencias vértice-arista en el grafo se puede contar de dos maneras diferentes: sumando los grados de los vértices, o contando dos incidencias por cada arista. Por lo tanto, donde es el número de aristas. La suma de los grados de los vértices es, por lo tanto, un número par , lo que no podría suceder si un número impar de vértices tuviera grado impar. Este hecho, con esta prueba, aparece en el artículo de 1736 de Leonhard Euler sobre los Siete Puentes de Königsberg que inició por primera vez el estudio de la teoría de grafos .${\estilo de visualización d(v)}$${\estilo de visualización v}$$${\displaystyle \suma _{v}d(v)=2e}$$${\estilo de visualización e}$

¿Cuál es el número de árboles diferentes que se pueden formar a partir de un conjunto de vértices distintos? La fórmula de Cayley da la respuesta . Aigner y Ziegler (1998) enumeran cuatro pruebas de este hecho; escriben sobre la cuarta, una prueba de doble conteo debida a Jim Pitman, que es "la más hermosa de todas". ^[3]$Estilo de visualización T_{n}$${\estilo de visualización n}$$Estilo de visualización T_{n}=n^{n-2}}$

La prueba de Pitman cuenta de dos maneras diferentes el número de secuencias diferentes de aristas dirigidas que se pueden agregar a un grafo vacío en los vértices para formar a partir de él un árbol con raíz . Las aristas dirigidas apuntan en dirección opuesta a la raíz. Una forma de formar dicha secuencia es comenzar con uno de los posibles árboles sin raíz, elegir uno de sus vértices como raíz y elegir una de las posibles secuencias en las que agregar sus aristas (dirigidas). Por lo tanto, el número total de secuencias que se pueden formar de esta manera es . ^[3]${\estilo de visualización n}$$Estilo de visualización T_{n}$${\estilo de visualización n}$${\estilo de visualización (n-1)!}$${\estilo de visualización n-1}$${\displaystyle T_{n}n(n-1)!=T_{n}n!}$

Otra forma de contar estas secuencias de aristas es considerar la adición de las aristas una por una a un grafo vacío, y contar el número de opciones disponibles en cada paso. Si uno ya ha añadido una colección de aristas, de modo que el grafo formado por estas aristas es un bosque con raíces y árboles, hay opciones para la siguiente arista que se añadirá: su vértice inicial puede ser cualquiera de los vértices del grafo, y su vértice final puede ser cualquiera de las raíces distintas de la raíz del árbol que contiene el vértice inicial. Por lo tanto, si uno multiplica el número de opciones del primer paso, el segundo paso, etc., el número total de opciones es Igualando estas dos fórmulas para el número de secuencias de aristas se obtiene la fórmula de Cayley: y Como describen Aigner y Ziegler, la fórmula y la prueba se pueden generalizar para contar el número de bosques con raíces y árboles, para cualquier . ^[3]${\estilo de visualización nk}$${\estilo de visualización k}$${\estilo de visualización n(k-1)}$${\estilo de visualización n}$${\estilo de visualización k-1}$$${\displaystyle \prod_{k=2}^{n}n(k-1)=n^{n-1}(n-1)!=n^{n-2}n!.}$$$${\displaystyle \displaystyle T_{n}n!=n^{n-2}n!}$$$${\displaystyle \displaystyle T_{n}=n^{n-2}.}$$${\estilo de visualización k}$${\estilo de visualización k}$

• Identidad de Vandermonde , otra identidad en sumas de coeficientes binomiales que se puede demostrar mediante conteo doble. ^[4]
• Número piramidal cuadrado . La igualdad entre la suma de los primeros números cuadrados y un polinomio cúbico se puede demostrar contando dos veces los triples de los números , y donde es mayor que cualquiera de los otros dos números.${\estilo de visualización n}$ ${\estilo de visualización x}$${\estilo de visualización y}$${\estilo de visualización z}$${\estilo de visualización z}$
• Desigualdad de Lubell–Yamamoto–Meshalkin . La prueba de Lubell de este resultado sobre familias de conjuntos es un argumento de doble conteo sobre permutaciones , utilizado para demostrar una desigualdad en lugar de una igualdad.
• Teorema de Erdős–Ko–Rado , un límite superior para familias de conjuntos que se intersecan, demostrado por Gyula OH Katona usando una desigualdad de doble conteo. ^[3]
• Pruebas del pequeño teorema de Fermat . Una prueba de divisibilidad por doble conteo: para cualquier número primo y natural , hay palabras de longitud sobre un alfabeto de símbolos que tienen dos o más símbolos distintos. Estos pueden agruparse en conjuntos de palabras que pueden transformarse entre sí mediante desplazamientos circulares ; estos conjuntos se denominan collares . Por lo tanto, (número de collares) y es divisible por . ^[4]${\estilo de visualización p}$${\estilo de visualización A}$$Estilo de visualización A^{p}-A}$${\estilo de visualización p}$${\estilo de visualización A}$${\estilo de visualización p}$${\displaystyle A^{p}-A=p\cdot {}}$${\estilo de visualización p}$
• Pruebas de reciprocidad cuadrática . Una prueba de Eisenstein deriva otro hecho importante de la teoría de números al contar dos veces los puntos de la red en un triángulo.

• Prueba biyectiva . Mientras que el conteo doble implica contar un conjunto de dos maneras, las pruebas biyectivas implican contar dos conjuntos de una manera, mostrando que sus elementos se corresponden uno a uno.
• El principio de inclusión-exclusión , una fórmula para el tamaño de una unión de conjuntos que puede, junto con otra fórmula para la misma unión, utilizarse como parte de un argumento de doble conteo.

• Aigner, Martín; Ziegler, Günter M. (1998), Pruebas del LIBRO , Springer-VerlagEl conteo doble se describe como un principio general en la página 126; la prueba de conteo doble de Pitman de la fórmula de Cayley está en las páginas 145-146; la desigualdad de conteo doble de Katona para el teorema de Erdős–Ko–Rado está en las páginas 214-215.
• Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis" (PDF) , Commentarii Academiae Scientiarum Imperialis Petropolitanae , 8 : 128-140. Reimpreso y traducido en Biggs, NL; Lloyd, EK; Wilson, RJ (1976), Graph Theory 1736–1936 , Oxford University Press.
• Garbano, ML; Malerba, JF; Lewinter, M. (2003), "Hipercubos y triángulo de Pascal: una historia de dos demostraciones", Mathematics Magazine , 76 (3): 216–217, doi :10.2307/3219324, JSTOR  3219324.
• Joshi, Mark (2015), "Conteo doble", Patrones de prueba , Springer International Publishing, págs. 11-17, doi :10.1007/978-3-319-16250-8_2, ISBN 978-3-319-16249-2
• Klavžar, Sandi (2006), "Contar hipercubos en hipercubos", Matemáticas discretas , 306 (22): 2964–2967, doi : 10.1016/j.disc.2005.10.036.
• van Lint, Jacobus H.; Wilson, Richard M. (2001), Un curso de combinatoria , Cambridge University Press, pág. 4, ISBN 978-0-521-00601-9.