Užití principu inkluze a exkluze k dokazovaní kombinatorických identit
Naším úkolem je dokázat, že pro libovolná kladná celá čísla a?, k splňující k ^ n platí rovnost
i£ (k-l\ (n-£\ _ ín-k + 1 £   ) [n-kl ~\ k
£=0
K tomu účelu budeme dvěma způsoby řešit následující úlohu.
Je třeba určit, kolik existuje /c-prvkových podmnožin množiny čísel {1,2,..., n} neobsahujících žádnou dvojici po sobě jdoucích čísel.
Budeme postupovat přímou úvahou a také s použitím principu inkluze a exkluze. Porovnáním obou výsledků dostaneme potřebnou kombinatorickou identitu.
Zapisujeme /c-prvkové podmnožiny množiny {1,2,..., n} jako vzestupně uspořádané /c-tice čísel. Při tomto zápisu je předpisem
(A77i, m2. A773, . . . , IHk) ^ A772 - 1, A773 - 2, . . . , ATl/c - /C + 1)
dáno vzájemně jednoznačné zobrazení množiny všech /c-tic různých čísel z množiny {1,2,..., a?} neobsahujících žádnou dvojici po sobě jdoucích čísel na množinu všech /c-tic různých čísel z množiny {1, 2,..., n — k + 1}. Posledně jmenované /c-tice čísel jsou ale kombinacemi k-té třídy v množině {1, 2,..., n — k + 1} a jejich počet je tedy dán binomickým koeficientem
n
Tolik je pak i /c-prvkových podmnožin množiny {1,2,..., n}, které neobsahují žádnou dvojici po sobě jdoucích čísel.
Buď Q množina všech /c-prvkových podmnožin množiny {1,2,..., n}. Tyto podmnožiny si představujeme jako vzestupně zapsané /c-tice různých čísel. Označme dále / = {2, 3,..., k} množinu všech těch pozic v takových /c-ticích, na nichž se může objevit následník čísla z předchozí pozice. Pro každou pozici / G / označme A; množinu všech těch /c-tic z množiny Q, v nichž se na pozicích / — la/ vyskytují po sobě jdoucí čísla.
Takže /c-tice z množiny Q neobsahující žádná dvě po sobě jdoucí čísla vytvoří množinu k
A(0) = f](Q - A,).
i=2
Podle principu inkluze a exkluze tedy víme, že pro počet těchto /c-tic platí rovnost
4(0)| = ^(-i)|L|
LCI
n a-
Přitom pro libovolnou podmnožinu LCI pozůstává množina r)ieLA; ze yšech těch /c-tic z množiny Q, v nichž přinejmenším na pozicích z L leží následníci čísel z pozic jim předcházejících. Zjistíme počet takových /c-tic. Vypišme pozice množiny L ve vzestupném pořadí:
L = {/'i, /2, • • •, Ág}. Poté transformujme /c-tice z množiny H/fz. a' následovně:
Ol
, A77/:L_i,       , . . . , A77;2_i, A77/2,
5 mii-l, min
(at?!
/??/, _i, rriL — 1
, . . . , ,,,/:L_i, lílfl      1, . . . , A77/2_i      1, A77/2 2,
Tímto předpisem /c-ticím z množiny C\ieLA; vzájemně jednoznačně odpovídají vzestupně zapsané /c-tice čísel z množiny {1, 2,..., n — £}, v nichž právě na pozicích z množiny L dochází k opakování čísla z předchozí pozice. Vynecháme-li nyní v takových /c-ticích čísla ležící na pozicích z množiny /_, dostaneme tak libovolné vzestupně zapsané (k — £)-ť\ce různých čísel z množiny {1, 2,..., n — £}. To jsou ale kombinace (k — £)-té třídy v množině {1, 2,..., n — £}, jejichž počet je dán binomickým koeficientem (JJZ^)- Celkem tak dostáváme rovnost
n a
ieL
kde £ = \L\. Dosazením z této rovnosti do předchozího vztahu vychází
\A(0)
£=0
Poněvadž pro i ^ k je (k í 1) = 0, dostáváme nakonec rovnost
n
\A(0)\ = ^(-1)
£=0
Tolik je tedy všech /c-prvkových podmnožin množiny {1,2,..., n} neobsahujících žádná dvě po sobě jdoucí čísla.
Závěrem porovnáním tohoto posledního poznatku s předchozím výsledkem dostáváme dokazovanou kombinatorickou identitu.