Variace, kombinace,
Pro každé reálné číslo r a každé nezáporné celé číslo k definujeme klesající faktoriál
M
k
1 pokud k = 0,
r\r - l)-(r - 2).....(r - k + 1)   pokud /c> 0
a rostoucí faktoriál
1 pokud k = 0,
r-(r + l)-(r + 2).....(r + k - 1)   pokud k> 0.
Zejména pak pro každé nezáporné celé číslo a? máme definován jeho faktoriál n\ = [n]n.
Pro každé reálné číslo r a každé nezáporné celé číslo k definujeme binomický koeficient
r\ = [j]k k J      k\ '
Pro tyto binomické koeficienty máme následující poznatky.
Pro libovolné reálné číslo r a libovolné nezáporné celé číslo k platí vztahy
0)
— r\     ,  .,k i r + k — 1
= (-i)'
oo
r + l k + 1
Důkaz.
Podle definic klesajících a rostoucích faktoriálů a binomických koeficientů dostáváme:
{-l)k\r]k_ = {_l)k^r + k-l
(i)
—r k
[-r]
k\
k\
(")
(r + l)-[r]k
(k+iy.
[r]k ,   [r]k+1      (k + l)-[r]k + [r]kir-k)
k\ + (k + 1)1 [r + l]fc+i
r + l /c + 1
□
Poznamenejme, že pro každé reálné číslo r podle definice binomických koeficientů platí (o) = 1, zejména (§) = 1, a pro každé kladné celé číslo k platí (£) =0. Tyto hraniční podmínky spolu s rekurentní formulí v části (ii) předchozího tvrzení umožňují postupně počítat všechny hodnoty (£) pro jakákoliv nezáporná celá čísla a?, k.
V následujících definicích a tvrzeních nechť a?, /cjsou libovolná nezáporná celá čísla a nechť /W je libovolná konečná množina mající n prvků.
Uspořádané /c-tice (mi,..., trik) vzájemně různých prvků mi,..., m^ £ M se nazývají variace k-té třídy v množině M. Lze je také popsat jako prostá zobrazení {l,...,/c} M.
Tvrzení.
Počet všech možných variací k-té třídy v množině M je roven číslu [n]k-
Zejména tedy počet všech permutací množiny M je roven číslu n\.
Uspořádané /c-tice (mi,..., m^) libovolných prvků /r?i...., m^ G M se nazývají variace k-té třídy v množině M s opakováním. Lze je také popsat jako libovolná zobrazení {1,..., k} —>► M.
Počet všech variací k-té třídy v množině M s opakováním je roven číslu n (klademe-li 0° = 1). □
Libovolné /c-prvkové podmnožiny L C M se nazývají kombinace k-té třídy v množině M. Je možné je také popsat jako libovolná zobrazení f : M —>► {0,1} splňující J2meM f(m) — ^- Zobrazení f odpovídající podmnožině L C M je takzvané charakteristické zobrazení podmnožiny L
Tvrzení.
Počet všech možných kombinací k-té třídy v množině M je roven číslu (nk)
Důkaz
Plyne z předminulého tvrzení, neboť z jedné /c-prvkové podmnožiny L C M, tedy z jedné kombinace /c-té třídy v množině M lze vytvořit celkem k\ variací k-té třídy v množině M. Tyto variace se dostanou jako libovolné permutace prvků podmnožiny L. □
Uvažme nyní libovolná zobrazení g : M —>* {0,1, 2,... } splňující podmínku ^2meM s(m) — k. Tato zobrazení nazýváme kombinace k-té třídy v množině /W s opakováním. Lze si je představit tak, že pro každý prvek m £ M udává hodnota g(m) počet výskytů prvku m v dané kombinaci.
Tvrzení.
Počet všech kombinací k-té třídy v množině M s opakováním je roven číslu
Důkaz.
Bez jakékoliv újmy můžeme předpokládat, že M = {1, 2,..., n}. Je-li k = 0, je uvedený počet kombinací roven 1. Je-li k > 0, ale n = 0, je tento počet roven 0. Jestliže k > 0 a n > 0, vezměme dále množinu M = {1, 2,..., n + /c — 1}. Na obou množinách M i /W uvažme obvyklé uspořádání čísel. Při tomto uspořádání lze libovolné kombinace k-té třídy zapisovat jako vzestupně uspořádané /c-tice čísel; v případě kombinací s opakováním jde o vzestupně uspořádané /c-tice ne nutně různých čísel.
Při tomto zápisu kombinací je předpisem
(A77i, m2. A773, . . . , mk) ^ (A77i, A772 + 1, A773 + 2, . . . , mk + /c - 1)
očividně dána vzájemně jednoznačná korespondence mezi kombinacemi s opakováním k-té třídy v množině M a obyčejnými kombinacemi k-té třídy v množině M. Množina M má n + /c — 1 prvků a zbývá už jen se odvolat na předchozí tvrzení. □
V okruhu Z[x,y] všech polynomů dvou proměnných x,y nad okruhem Z všech celých čísel pro libovolné kladné celé číslo n platí
Nyní následuje binomická věta.
Věta.
6/11
Důkaz.
Po roznásobení mocniny (x + y)n vznikne pro každou hodnotu k celkem (JJ) sčítanců tvaru xkyn~k, neboť podle předminulého tvrzení právě tolika způsoby je možno vybrat /c-prvkovou podmnožinu těch závorek (x + y), z nichž se při tvorbě součinu xkyn~k uplatní proměnná x. □
Důsledek.
Pro libovolné nezáporné celé číslo n platí rovnosti
k=o v 7
n
k=Q
1 pro n = 0. 0 pro n > 0.
Důkaz.
Obě tvrzení (i) i (ii) jsou pro n = 0 zřejmá a pro n > 0 plynou z binomické věty dosazením 1 za x i y, respektive —1 za x a 1 za y. □
Pro libovolné kladné celé číslo £ a pro libovolná nezáporná celá čísla a? a /ci,... splňující k\ + • • • + ku = n definujeme polynomický koeficient
n     \ _ n'
ki,...,kej ~ ki\.....ktV
V následujícím tvrzení ozřejmíme kombinatorický význam polynomických koeficientů. Půjde o zobecnění předminulého tvrzení týkajícího se binomických koeficientů. Buď opět M libovolná konečná množina mající n prvků.
Tvrzení.
Necht /ci,..., ku jsou nezáporná celá čísla taková, že je splněno k\ + • • • + ku = n. Pak počet všech zobrazení h : M —>► {1,..., £} splňujících podmínky = k\
pro všechna i = 1,..., í je roven číslu (kx"..M ) ■
Důkaz
Postupujeme indukcí vzhledem k číslu i. Pro £ = 1 je tvrzení zřejmé. Nechť dále £ je přirozené číslo takové, že £ > 1. Uvažme libovolné zobrazení h : M —>► {1,... ,£} splňující dané požadavky. Položme L = h~ľ(£). Podle předminulého tvrzení existuje (k£) možností, jak může vypadat tato podmnožina L množiny M. Uvažme dále zúžení Ii\m-l zobrazení h na podmnožinu M — L. Podle indukčního předpokladu je možno toto zúžení Ii\m-l vytvořit (kxn~ki-x) způsoby.
Odtud pro celkový počet všech možných zobrazení h splňujících dané požadavky vychází
n\   í    n - kt    \ _        n\              (n - ki)\     _( n kí)   \ki,..., kz-i)     ke\-(n-ke)\   kľ\.....k£_ľ\
k\*..., kÁ
i
V kontextu tohoto kombinatorického významu polynomických koeficientů bývá někdy také řeč o takzvaných permutacích s opakováním. Jde o libovolné uspořádané n-tice vytvořené z £ prvků, v nichž pro každé / = 1,.. .£ má /-tý prvek celkem k\ výskytů.
Pro polynomické koeficienty máme následující rekurentní formuli.
Tvrzení.
Necht í je kladné celé číslo, necht /ci,..., ku jsou nezáporná celá čísla a necht n = ki + • • • + ku. Je-li n > 0, pak platí
n      \     >r-^ / n — 1
ku...,kil ~ 2^
/ci,..., kj—i, kj    1, /cy"_|_i,..., kg
kde suma je přes všechna j = 1,..., í taková, že kj > 0,
Přímým výpočtem vyjde
n-1
/ci,..., kj—i, kj — 1, /cy"_|_i,..., ku
(n-1)!
= E
kx\.....kj-x\ ■ {kj - 1)! • kJ+i\.....kt\
ki\.....^'-í- • kj\ • kj+i\.....k^\
(n-l)!-E*/ = n-(n-!)! =/ n ( Q /ej...../c^!      /ej.....kt\     \k\,..., kt
Dostáváme se nakonec k následujícímu zobecnění binomické věty.
Pro libovolná kladná celá čísla naiv okruhu Z[xi,..., x^] všech polynomů £ proměnných nad okruhem Z platí
(« + -+*)" = E(*1,.".
/ / xl
ki
x
ke í '
kde suma je přes všechny uspořádané í-tice (/ci,..., km) nezáporných celých čísel splňujícík\ + • • • + ku = n.
Vede se analogická úvaha jako v důkazu binomické věty s odkazem na kombinatorický význam polynomických koeficientů.
Důsledek.
Pro libovolné nezáporné celé číslo n a pro libovolné kladné celé číslo í platí rovnost
kde suma je přes všechny uspořádané í-tice (/ci,..., k$) nezáporných celých čísel splňujícík\ + • • • + ku = n.
Důkaz.
Pro n = 0 je tvrzení zřejmé a pro n > 0 plyne z předchozí věty dosazením 1 za všechny proměnné xi,..., X£.
□