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  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  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  posibilidades. Alternativamente, pódese observar que o tamaño do comité debe ser algún número entre 0 e . Para cada tamaño posible , o número de formas en que un comité de  persoas se pode formar a partir  persoas é o coeficiente binomial de n elementos tomados en grupos de kPolo tanto, o número total de posibles comités é a suma dos coeficientes binomiais . Igualando as dúas expresións dá a identidade un caso especial do teorema binomial. 

Pódese usar un método de dupla contaxe similar para probar a identidade máis xeral ; ). 

 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  o grao do vértice . 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 onde  é 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 
miniatura|297x297px| A fórmula de Cayley implica que hai  árbores con dous vértices,  árbores con tres vértices e  árbores con catro vértices.
miniatura| Engadindo unha aresta dirixida a un bosque con raíz
Cal é o número  de diferentes árbores que se poden formar a partir dun conxunto de  vértices distintos? A fórmula de Cayley dá a resposta .  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  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  posibles árbores sen raíz, escoller un dos seus  vértices como raíz e escoller unha das  posibles secuencias nas que engadir as súas  arestas (dirixidas). Polo tanto, o número total de secuencias que se poden formar deste xeito é .

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  arestas, de xeito que o grafo formado por estas arestas é un bosque con raíz con  árbores, daquela hai  opcións para engadir a seguinte aresta: o seu vértice inicial pode ser calquera dos  vértices do grafo, e o seu vértice final pode ser calquera das  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 é Ao igualar estas dúas fórmulas para o número de secuencias de arestas dá como resultado a fórmula de Cayley:  e 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  árbores, para calquera 
 Notas 


 Véxase tamén 

 Bibliografía 
. 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.
. Reprinted and translated in .
.

.
.
 Outros artigos 
 Proba bixectiva.
 Principio de inclusión–exclusión

Categoría:Combinatoria