Conteo doble (técnica de prueba)

Tipo de técnica de prueba

En combinatoria , el conteo doble , también llamado conteo de dos formas , es una técnica de prueba combinatoria para mostrar que dos expresiones son iguales demostrando 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", 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í.

Ejemplos de

Multiplicación (de números naturales) conmuta

Este es un ejemplo simple de conteo doble, que se usa a menudo al enseñar multiplicación a niños pequeños. En este contexto, la multiplicación de números naturales se introduce como suma repetida, y luego se demuestra que es conmutativa contando, de dos formas diferentes, una serie de elementos dispuestos en una cuadrícula rectangular. Suponga que la cuadrícula tiene filas y columnas. En primer lugar, contamos los artículos sumando filas de elementos cada uno, luego una segunda vez sumando columnas de elementos cada una, lo que demuestra que, para estos valores particulares de y , . Si bien no es una prueba, muestra claramente que la multiplicación conmuta, para cualquier ejemplo (de tamaño práctico) que elijamos.${\displaystyle n}$${\displaystyle m}$${\displaystyle n}$${\displaystyle m}$${\displaystyle m}$${\displaystyle n}$${\displaystyle n}$${\displaystyle m}$${\displaystyle n\times m=m\times n}$

Formación de comités

Un ejemplo del método de conteo doble 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) formen 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 pedirle a cada persona que elija si desea unirse o no. Cada persona tiene dos opciones, sí o no, y estas opciones son independientes de las de las demás personas. Por 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${\displaystyle n}$${\displaystyle n}$${\displaystyle 2\times 2\times \cdots 2=2^{n}}$${\displaystyle n}$${\displaystyle k}$${\displaystyle k}$${\displaystyle n}$coeficiente binomial

$${\displaystyle {n \choose k}.}$$

Por lo tanto, el número total de posibles comités es la suma de los coeficientes binomiales . Igualar las dos expresiones da la identidad${\displaystyle k=0,1,2,\dots ,n}$

$${\displaystyle \sum _{k=0}^{n}{n \choose k}=2^{n},}$$

un caso especial del teorema del binomio . Se puede utilizar un método de doble recuento similar para probar la identidad más general

$${\displaystyle \sum _{k=d}^{n}{n \choose k}{k \choose d}=2^{n-d}{n \choose d}}$$

( Garbano, Malerba y Lewinter 2003 ; Klavžar 2006 ).

Lema de apretón de manos

Otro teorema que se demuestra comúnmente con un argumento de doble conteo establece que cada 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 probar esto contando dos veces, sea ​​el grado del vértice . El número de incidencias de borde de vértice en el gráfico se puede contar de dos formas diferentes: sumando los grados de los vértices o contando dos incidencias por cada borde. Por lo tanto${\displaystyle d(v)}$${\displaystyle v}$

$${\displaystyle \sum _{v}d(v)=2e}$$

donde es el número de aristas. La suma de los grados de los vértices es, por tanto, un número par , lo que no podría suceder si un número impar de los vértices tuviera un 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 .${\displaystyle e}$

Contando árboles

La fórmula de Cayley implica que hay 1 = 2 ^{2 - 2} árboles en dos vértices, 3 = 3 ^{3 - 2} árboles en tres vértices y 16 = 4 ^{4 - 2} árboles en cuatro vértices.

Agregar un borde dirigido a un bosque enraizado

¿Cuál es la cantidad 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 el cuarto, una prueba de doble conteo debida a Jim Pitman, que es "el más hermoso de todos".${\displaystyle T_{n}}$${\displaystyle n}$${\displaystyle 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 gráfico vacío en los vértices para formar a partir de él un árbol enraizado . Una forma de formar tal 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 bordes (dirigidos). Por tanto, el número total de secuencias que se pueden formar de esta forma es .${\displaystyle n}$${\displaystyle T_{n}}$${\displaystyle n}$${\displaystyle (n-1)!}$${\displaystyle n-1}$${\displaystyle T_{n}n(n-1)!=T_{n}n!}$

Otra forma de contar estas secuencias de bordes es considerar agregar los bordes uno por uno a un gráfico vacío y contar el número de opciones disponibles en cada paso. Si ya se ha agregado una colección de bordes, de modo que el gráfico formado por estos bordes sea un bosque enraizado con árboles, hay opciones para agregar el siguiente borde: su vértice inicial puede ser cualquiera de los vértices del gráfico, 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${\displaystyle n-k}$${\displaystyle k}$${\displaystyle n(k-1)}$${\displaystyle n}$${\displaystyle k-1}$

$${\displaystyle \prod _{k=2}^{n}n(k-1)=n^{n-1}(n-1)!=n^{n-2}n!.}$$

Igualar estas dos fórmulas para el número de secuencias de aristas da como resultado la fórmula de Cayley:

$${\displaystyle \displaystyle T_{n}n!=n^{n-2}n!}$$

y

$${\displaystyle \displaystyle T_{n}=n^{n-2}.}$$

Como describen Aigner y Ziegler, la fórmula y la demostración se pueden generalizar para contar el número de bosques enraizados con k árboles, para cualquier k .

Ver también

Ejemplos adicionales

• La identidad de Vandermonde , otra identidad en sumas de coeficientes binomiales que se puede probar mediante doble conteo.
• Número piramidal cuadrado . La igualdad entre la suma de los primeros números cuadrados y un polinomio cúbico se puede demostrar por recuento doble de los triples de números , y donde es más grande que cualquiera de los otros dos números.${\displaystyle n}$ ${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle z}$
• Desigualdad de Lubell-Yamamoto-Meshalkin . La prueba de Lubell de este resultado en familias de conjuntos es un argumento de doble recuento sobre permutaciones , utilizado para demostrar una desigualdad en lugar de una igualdad.
• Pruebas del pequeño teorema de Fermat . Una prueba de divisibilidad por conteo doble: para cualquier número primo y natural , hay palabras de longitud sobre un alfabeto de símbolo que tiene dos o más símbolos distintos. Estos pueden agruparse en conjuntos de palabras que pueden transformarse entre sí mediante turnos circulares ; estos conjuntos se llaman collares . Por lo tanto, (número de collares) y es divisible por .${\displaystyle p}$${\displaystyle A}$${\displaystyle A^{p}-A}$${\displaystyle p}$${\displaystyle A}$${\displaystyle p}$${\displaystyle A^{p}-A=p\cdot {}}$${\displaystyle p}$
• Pruebas de reciprocidad cuadrática . Una demostración de Eisenstein deriva otro hecho importante de la teoría de números contando dos veces los puntos reticulares de un triángulo.

Temas relacionados

• Prueba biyectiva . Cuando el conteo doble implica contar un conjunto de dos formas, las demostraciones biyectivas implican contar dos conjuntos de una forma, mostrando que sus elementos se corresponden uno por 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, usarse como parte de un argumento de doble recuento.

Referencias

• Aigner, Martin; Ziegler, Günter M. (1998), Pruebas de EL LIBRO , Springer-Verlag. La doble contabilización se describe como principio general en la página 126; La prueba de doble conteo de Pitman de la fórmula de Cayley se encuentra en las páginas 145-146.
• Euler, L. (1736), "Solutio problematis ad geometriam situs pertinente" (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 pruebas", Revista de matemáticas , 76 (3): 216-217, doi : 10.2307 / 3219324 , JSTOR  3219324.
• 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.