Dupla contaxe

En combinatoria, a dupla contaxe, é unha técnica de proba combinatoria para demostrar que dúas expresións son iguais vendo que hai dous xeitos de contar o tamaño dun mesmo conxunto. Nesta técnica, que van Lint & Wilson (2001) chaman "unha das ferramentas máis importantes da combinatoria", descríbese un conxunto finito desde dúas perspectivas que conducen a dúas expresións distintas para o tamaño do conxunto. Dado que ambas as expresións son iguais ao tamaño do mesmo conxunto, son iguais entre si.

Exemplos

Formación de comités

Un exemplo do método de conta dupla conta o número de formas en que se pode formar un comité a partir de $n$ persoas, permitindo que calquera número de persoas (incluso cero delas) forme parte do comité. É dicir, cóntase o número de subconxuntos que un conxunto de n elementos pode ter. Un método para formar un comité é pedir a cada persoa que elixa se se une ou non a el. Cada persoa ten dúas opcións: si ou non, e estas opcións son independentes das opcións das outras persoas. Polo tanto hai $2\times 2\times \cdots 2=2^{n}$ posibilidades. Alternativamente, pódese observar que o tamaño do comité debe ser algún número entre 0 e $n$. Para cada tamaño posible $k$, o número de formas en que un comité de $k$ persoas se pode formar a partir $n$ persoas é o coeficiente binomial de n elementos tomados en grupos de k$${n \choose k}.$$Polo tanto, o número total de posibles comités é a suma dos coeficientes binomiais $k=0,1,2,\dots ,n$. Igualando as dúas expresións dá a identidade $$\sum _{k=0}^{n}{n \choose k}=2^{n},$$un caso especial do teorema binomial.

Pódese usar un método de dupla contaxe similar para probar a identidade máis xeral $$\sum _{k=d}^{n}{n \choose k}{k \choose d}=2^{n-d}{n \choose d}$$

Lema do apertón de mans

Outro teorema que se demostra habitualmente cun argumento de dupla contaxe afirma que cada gráfica non dirixida contén un número par de vértices de grao impar. É dicir, o número de vértices que teñen un número impar de arestas incidentes debe ser par. En termos máis coloquiais, nun grupo de persoas ás que algúns se dan a man, un número par debe ter apertado a man a un número impar de outras persoas; por este motivo, o resultado coñécese como lema do apertón de mans .

Para demostrar isto por contaxe dupla, imos ter $d(v)$ o grao do vértice $v$. O número de incidencias de vértices no grafo pódese contar de dúas formas diferentes: sumando os graos dos vértices ou contando dúas incidencias por cada aresta. Polo tanto $$\sum _{v}d(v)=2e$$onde $e$ é o número de arestas. A suma dos graos dos vértices é polo tanto un número par, o que non podería ocorrer se un número impar dos vértices tivese un grao impar. Este feito, con esta proba, aparece no artigo de 1736 de Leonhard Euler sobre as Sete Pontes de Königsberg que comezou o primeiro estudo da teoría de grafos.

Contando árbores

A fórmula de Cayley implica que hai 1 = 2^{2 − 2} árbores con dous vértices, 3 = 3^{3 − 2} árbores con tres vértices e 16 = 4^{4 − 2} árbores con catro vértices.

Engadindo unha aresta dirixida a un bosque con raíz

Cal é o número $T_{n}$ de diferentes árbores que se poden formar a partir dun conxunto de $n$ vértices distintos? A fórmula de Cayley dá a resposta $T_{n}=n^{n-2}$. Aigner & Ziegler (1998) enumeran catro probas deste feito; escriben sobre a cuarta, unha proba de dupla contaxe debida a Jim Pitman.

A proba de Pitman conta de dúas formas diferentes o número de secuencias diferentes de arestas dirixidas que se poden engadir a un grafo baleiro con $n$ vértices para formar a partir dela unha árbore con raíz. As arestas dirixidas apuntan para fóra da raíz. Unha forma de formar tal secuencia é comezar cunha das $T_{n}$ posibles árbores sen raíz, escoller un dos seus $n$ vértices como raíz e escoller unha das $(n-1)!$ posibles secuencias nas que engadir as súas $n-1$ arestas (dirixidas). Polo tanto, o número total de secuencias que se poden formar deste xeito é $T_{n}n(n-1)!=T_{n}n!$.

Outra forma de contar estas secuencias de arestas é considerar engadir as arestas unha a unha a un grafo baleiro, e contar o número de opcións dispoñibles en cada paso. Se xa temos engadidas unha colección de $n-k$ arestas, de xeito que o grafo formado por estas arestas é un bosque con raíz con $k$ árbores, daquela hai $n(k-1)$ opcións para engadir a seguinte aresta: o seu vértice inicial pode ser calquera dos $n$ vértices do grafo, e o seu vértice final pode ser calquera das $k-1$ raíces distintas da raíz da árbore que contén o vértice inicial. Polo tanto, se se multiplica o número de opcións do primeiro paso, do segundo paso, etc., o número total de opcións é $$\prod _{k=2}^{n}n(k-1)=n^{n-1}(n-1)!=n^{n-2}n!.$$Ao igualar estas dúas fórmulas para o número de secuencias de arestas dá como resultado a fórmula de Cayley: $$\displaystyle T_{n}n!=n^{n-2}n!$$ e $$\displaystyle T_{n}=n^{n-2}.$$Como describen Aigner e Ziegler, a fórmula e a proba pódense xeneralizar para contar o número de bosques con raíz con $k$ árbores, para calquera $k$.

Véxase tamén

Bibliografía

• Aigner, Martin; Ziegler, Günter M. (1998). Proofs from THE BOOK. Springer-Verlag. . Double counting is described as a general principle on page 126; Pitman's double counting proof of Cayley's formula is on pp. 145–146; Katona's double counting inequality for the Erdős–Ko–Rado theorem is pp. 214–215.
• Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis (PDF). Commentarii Academiae Scientiarum Imperialis Petropolitanae 8. pp. 128–140. . Reprinted and translated in Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976). Graph Theory 1736–1936. Oxford University Press. .
• Garbano, M. L.; Malerba, J. F.; Lewinter, M. (2003). Hypercubes and Pascal's triangle: a tale of two proofs. Mathematics Magazine 76. pp. 216–217. JSTOR 3219324. doi:10.2307/3219324. .
• Joshi, Mark (2015). "Double Counting". Proof Patterns. Springer International Publishing. pp. 11–17. ISBN 978-3-319-16249-2. doi:10.1007/978-3-319-16250-8_2. 
• Klavžar, Sandi (2006). Counting hypercubes in hypercubes. Discrete Mathematics 306. pp. 2964–2967. doi:10.1016/j.disc.2005.10.036. .
• van Lint, Jacobus H.; Wilson, Richard M. (2001). A Course in Combinatorics. Cambridge University Press. p. 4. ISBN 978-0-521-00601-9. .

Outros artigos

• Proba bixectiva.
• Principio de inclusión–exclusión