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  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 = 2n 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

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:
 
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:

(; ).

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
 
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  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

Hány különböző Tn fa alakítható ki n darab számozott csúcsból? A Cayley-formula megadja a választ: .  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 Tn 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  lehetséges sorozat egyikét, melyben hozzáadjuk az  (irányított) élet. Az így felmerülő sorozatok száma éppen .

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  élet, akkor az élek egy k fából álló gyökeres erdőt alkotnak, és a következő él hozzáadására  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  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:

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

and

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  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 , 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
. 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.
. Reprinted and translated in .
.
.
.

Kombinatorika
Matematikai bizonyítások
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 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árszemély is tagja lehetbizottsá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××\ . . . ×= lehetőség van . Egy másik módszer szerint megfigyeljük , hogy az egyes bizottságok taglétszáma mindigés n között van . Minden potenciális k létszámú bizottságot az n emberből éppen az binomiális együttható szerint lehet kiválasztani . Tehát a lehetséges bizottságok összesített száma a k =\... 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 : 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 : ( ; ) . 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 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 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 Hány különböző Tn fa alakítható ki n darab számozott csúcsból ? A Cayley-formula megadja a választ : \. 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 Tn 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 lehetséges sorozat egyikét , melyben hozzáadjuk az ( irányított ) élet . Az így felmerülő sorozatok száma éppen \ . 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 élet , akkor az élek egy k fából álló gyökeres erdőt alkotnak , és a következő él hozzáadására 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 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 : A két képletet egyenlővé téve megkapjuk a Cayley-formulában szereplő élsorozat-számot : and 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 darab p hosszúságú szó tartozik egy A jelből álló ábécét tekintve , ahol A legalább 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 , 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 . Double counting is described as a general principle on page Pitman's double counting proof of Cayley's formula is on pp. 145–146 . . Reprinted and translated in \ . . . . Kombinatorika Matematikai bizonyítások