Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

## Kombinatorické počítání

Věta

Nechť je nějaká -prvková množina a je -prvková množina (). Potom počet všech zobrazení je .

Věta

Libovolná -prvková množina má právě podmnožin.

Věta

Nechť . Každá -prvková množina má právě podmnožin sudé velikosti a právě podmnožin liché velikosti.

Věta

Pro existuje právě prostých zobrazení -prvkové množiny do -prvkové množiny.

Definice

Prostá zobrazení množiny do sebe se nazývá permutace množiny . Tato zobrazení jsou zároveň na.

Permutace si můžeme představit jako přerovnání množiny - např. je permutací množiny . Jiný zápis permutací je pomocí jejich cyklů (cyklus v permutaci je pořadí prvků, kde začnu u nějakého prvku, pokračuji jeho obrazem v permutaci a toto opakuji, dokud nenarazím na první prvek). U cyklů znázorníme každý prvek množiny jako bod. Z každého bodu vychází a do každého vchází právě po jedné šipce. Šipka vycházející z prvního prvku množiny ukazuje na první prvek permutace, šipka z druhého prvku množiny na druhý prvek permutace atd. Zápis se pak provádí tak, že každou kružnici zapíšeme po řadě zvlášť (např. je zápis permutace .

Věta (Faktoriál)

Počet permutací na -prvkové množině je . Toto číslo pojmenujeme faktoriál a značíme .

Definice (Binomické koeficienty)

Nechť jsou nezáporná celá čísla. Binomický koeficient neboli kombinační číslo (čteme nad ) je funkce proměnných , , daná jako

nebo

Definice

Nechť je množina a je nezáporné celé číslo. Pak budeme značit množinu všech -prvkových podmnožin množiny .

Věta

Pro každou konečnou množinu je počet všech jejích -prvkových podmnožin roven .

Věta (Vlastnosti kombinačních čísel)

Platí:

Důkaz

První je zřejmé ze vzorce pro kombinační čísla, druhé se ukaže jednoduše pro použití komb. čísel - mějme množinu a v ní prvek . Kolik je podmnožin obsahujících, resp. neobsahujících ?

Důsledek

Z druhé vlastnosti plyne vzhled Pascalova trojúhelníku, tedy že v . řádku jsou vždy právě binomické koeficienty .

Věta (O počtu způsobů zápisu)

Nezáporné celé číslo lze zapsat jako součet nezáporných sčítanců právě způsoby.

Důkaz

Důkazem je onen pokus s rozdělováním kuliček mezi přihrádek (nebo spíš vkládání přihrádek mezi kuličky v řadě).

Věta (Binomická věta)

Pro nezáporné celé číslo a libovolná platí:

Věta (Multinomická věta)

Pro libovolná čísla a platí:

kde ta věc uprostřed v tom vzorci je multinomický koeficient, definovaný: