Esetszámítások

Esetszámítások a kombinatorika egyik alapmódszere, amelynek célja egy adott mennyiség meghatározása úgy, hogy a lehetőségeket több egymástól diszjunkt esetre bontják, majd minden esetben megszámlálják a kedvező kimenetek számát. A módszer akkor hatékony, ha a közvetlen számlálás nehéz vagy bonyolult a feltételek miatt, vagy amikor szimmetriák és strukturális minták révén egyszerűbb az egyes esetek megszámlálása. Az összegzett eredmény a külön-külön megszámlált kedvező kimenetek összegzése.

A módszer alkalmazása általában a következő lépésekből áll: először pontosan meg kell határozni az összes releváns esetet és azt, hogy ezek diszjunktak és teljes körűek-e; ezt követően minden esetben meg kell adni a kedvező kimenetek számát, végül az összegzéssel megkapni a kívánt mennyiséget. Ha az esetek átfednek vagy hiányoznak, szükség lehet az inklúzió-exklúzió elvének alkalmazására vagy a bontás további finomítására. Esetszámításokat széles körben használják a valószínűség-számításban és a kombinatorikában olyan problémáknál, ahol a feltételek egyszerűen lokálisan megadhatók, például meghatározható, hány n hosszú bináris sztringet tartalmaz tilos egymás utáni 1-esek nélkül; ennek esetében az első bit szerint lehet két fő ágat felállítani: ha az első bit 0, a maradék n−1 bitet számoljuk, ha az első bit 1, a második bitnek 0 kell lennie, és a maradék n−2 bitet számoljuk.