Kettős leszámlálás

A matematika, azon belül a kombinatorika területén a kettős leszámlálás (double counting) olyan kombinatorikus bizonyítási technika, ami annak demonstrálásával mutatja meg két kifejezés egyenlőségét, hogy azok ugyanannak a halmaznak az elemeit számolják meg két különböző módon. A (van Lint & Wilson 2001) szerint „a kombinatorika legfontosabb eszközei közé tartozó” technika alkalmazása során egy véges X halmazt két perspektívából írunk le, ami két különböző, a halmaz méretét meghatározó kifejezést eredményez. Mivel mindkét kifejezés a halmaz méretét írja le, egyenlőnek kell lenniük egymással.

Példák

Bizottságok alakítása

A kettős leszámlálás módszerére példa annak megszámlálása, hogy n személyből hányféleképpen alakítható bizottság, ha tetszőleges (akár 0) személy is tagja lehet 1-1 bizottságnak. Másként fogalmazva megszámoljuk egy n elemű halmaz lehetséges részhalmazainak a számát. Egy bizottság megalakításának egyik módja, hogy minden személyt megkérdezünk, szeretne-e tag lenni. Mindenkinek két választása van – igen vagy nem – és ezek a választások függetlenek a többi ember választásához. Ezért 2 × 2 × ... × 2 = 2ⁿ lehetőség van. Egy másik módszer szerint megfigyeljük, hogy az egyes bizottságok taglétszáma mindig 0 és n között van. Minden potenciális k létszámú bizottságot az n emberből éppen az

${n \choose k}$

binomiális együttható szerint lehet kiválasztani.

Tehát a lehetséges bizottságok összesített száma a k = 0, 1, 2, ... n-re kijövő binomiális együtthatók összege. A két kifejezést egyenlővé téve egymással a következő azonosságot kapjuk:

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

ami a binomiális tétel speciális esete. Hasonló kettős leszámlálással bizonyítható a következő általánosabb azonosság is:

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

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

Kézfogási lemma

Gyakran a kettős leszámlálási technikával bizonyítják azt az állítást, ami szerint minden irányítatlan gráf páros számú páratlan fokú csúcsot tartalmazhat. Tehát az olyan csúcsok száma, amelyből páratlan számú él indul ki, csak páros lehet. Egy köznapi életből vett példával, ha egy partin néhány ember kezet fog egymással, a páratlan számú emberrel kezet rázók száma páros – a tétel ezért kézfogási lemma néven terjedt el.

A kettős leszámláláshoz legyen d(v) a v csúcs fokszáma. A csúcs-él szomszédságok a gráfban kétféleképp is megszámolhatók: a csúcsok fokszámainak összeadásával vagy az élek két-két szomszédságainak összeadásával. Ezért

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

ahol e az élek száma. A csúcsok fokszám-összege ezért páros szám, ami nem lehetséges, ha páratlan számú csúcsnak lenne páratlan fokszáma. Ezt a tényt Leonhard Euler (1736) igazolta a königsbergi hidak problémáját vizsgáló híres elemzésében, ami a gráfelmélet megalapozásául szolgált.

Fák leszámlálása

A Cayley-formula szerint 1 = 2^{2 − 2} fa rajzolható két csúcsot összekötve, 3 = 3^{3 − 2} fa rendelkezik három csúccsal és 16 = 4^{4 − 2} fa négy csúccsal.

Gyökérrel rendelkező erdőhöz irányított él hozzáadása

Hány különböző T_n fa alakítható ki n darab számozott csúcsból? A Cayley-formula megadja a választ: T_n = n^{n − 2}. (Aigner & Ziegler 1998) a formula négy bizonyítását ismerteti, a negyediket, mely Jim Pitman kettős leszámláláson alapuló bizonyítása, a legszebbnek tartják mind közül.

Pitman bizonyítása kétféleképpen számolja meg az üres gráfhoz adható irányított élek olyan sorozatát, ami n csúcsú fenyőt (irányított fa, ahol a gyökérből minden csúcs elérhető) hoz létre. Az egyik szerint elindulunk a T_n lehetséges gyökér nélküli fák egyikével, az n csúcs egyikét gyökérnek választjuk, majd kiválasztjuk az (n − 1)! lehetséges sorozat egyikét, melyben hozzáadjuk az n − 1 (irányított) élet. Az így felmerülő sorozatok száma éppen T_nn(n − 1)! = T_nn!.

Az élsorozat megszámlálásának másik módja, hogy egy üres gráfhoz egyesével éleket adunk hozzá, és minden lépésben megvizsgáljuk, hány új él jöhet szóba. Ha egy ponton már hozzáadtunk n − k élet, akkor az élek egy k fából álló gyökeres erdőt alkotnak, és a következő él hozzáadására n(k − 1) lehetőségből lehet választani: a kezdő csúcs a gráf n csúcsának bármelyike lehet, a másik csúcs pedig a k − 1 gyökér bármelyike lehet, amelyik nem a kiinduló csúcs fájának gyökere. Ha összeszorozzuk az első, második stb. lépésben lehetséges választásokat, a következő produktumot kapjuk:

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

A két képletet egyenlővé téve megkapjuk a Cayley-formulában szereplő élsorozat-számot:

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

and

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

Aigner és Ziegler leírják, hogy a képlet és a bizonyítás általánosítható tetszőleges k fából álló fenyvesekre (fenyőkből álló erdőkre).

Kapcsolódó szócikkek

További példák

• Vandermonde-azonosság, kettős leszámlálással igazolható, a binomiális együtthatók összegére vonatkozó másik azonosság.
• Négyzetes piramisszámok. Az első n négyzetszám összege és egy harmadfokú polinom közötti egyenlőség megmutatható az olyan x, y, z számhármasok kettős leszámlálásával, ahol a z a legnagyobb.
• LYM-egyenlőtlenség. A halmazrendszerekre vonatkozó egyenlőtlenséget Lubell a permutációk kettős leszámlálásával bizonyítja (itt egyenlőtlenséget bizonyít egyenlőség helyett!).
• A kis Fermat-tétel bizonyításai. Egy oszthatósági bizonyítás kettős leszámlálással: bármely p prímhez és A természetes számhoz A^p − A darab p hosszúságú szó tartozik egy A jelből álló ábécét tekintve, ahol A legalább 2. Ezek olyan p szavakba csoportosíthatók, melyek egymásba körkörös eltolás műveletével átvihetők; az ilyen halmazokat nyakláncoknak nevezik. Ezért A^p − A = p × (a nyakláncok száma), ami osztható p-vel.
• a kvadratikus reciprocitás tételének egyik, Eisenstein által megadott bizonyítása fontos számelméleti tényt következtet egy háromszög rácspontjainak kettős leszámlálásából.

Kapcsolódó témák

• Bijektív bizonyítás. Míg a kettős leszámlálás során egy halmazt két különböző módon számlálunk le, a bijektív bizonyítás során két halmazt számlálunk le azonos módon, ezzel megmutatva az elemek közötti egy az egybeni megfeleltetést.
• A tartalmazás és kizárás elve (logikai szitaformula), egy képlet halmazok uniójának a méretére, ami az unióra vonatkozó másik képlettel együtt kettős leszámlálási bizonyításban is felhasználható.

Jegyzetek

• 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.
• Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis", Commentarii Academiae Scientiarum Imperialis Petropolitanae 8: 128–140, <http://math.dartmouth.edu/~euler/docs/originals/E053.pdf>. 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 (3): 216–217, DOI 10.2307/3219324.
• Klavžar, Sandi (2006), "Counting hypercubes in hypercubes", Discrete Mathematics 306 (22): 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.