Nastínění problému "šatnářky"
Problém šatnářky: n-zákazníků a stejně tak i klobouků (které jsou stejné avšak rozlišitelné (nikoli však šatnářkou)).
Otázkou je v kolika případech žádný z hostů nedostane svůj klobouk (šatnářka klobouky nerozpozná a vydává je jak jí přijdou pod ruku)
Šatnářka vytváří zobrazení (zobrazení je relace) "klobouků" na "hosty" (či opačně - toto zobrazení je prosté a na, tkz. bijekce, jde jen o označení). Po jednoduché úpravě značení dostáváme f: X -> X, což je permutace. Celkový počet všech zobrazení je tedy počet všech permutací f, což je n! (kde n je počet prvků X (a zároveň stále i počet klobouků a hostů)).

Potřebujeme odhadnout kolik n! je, tj. jak je to vlastně "velké". K tomu je tu
Tvrzení(1) o omezenosti n! zhora ((n+1)/2)^n a zdola n^(n/2) pro každé n (předpokládám z N+{0}, aby n! mělo smysl).
Důkaz: použijeme trik (n!)^2 a při vhodném rozepsání celého výrazu dostaneme jednoduchý výraz pro hromadné násobení ((i)(n+1-i)) pro i z [1,n]. Takový výraz lehce dokážeme zdola omezit n, zhora pak složitěji ((n+1)/2)^2. Teď se můžeme vrátit k celému výrazu a provést tedy ono násobení přes i z [1,n]. Tím dostaneme, že (n!)^2 je zdola omezené n^n a zhora ((n+1)/2)^(2n). Výraz tedy již prakticky odpovídá výrazu z tvrzení s tím rozdílem, že má dvojnásobné exponenty. Protože n je vždy kladné, můžeme s klidem odmocnit, čímž se dostaneme přesně k hledanému výrazu.

Jiné nahlížení na ((i)(n+1-i)) nám umožní snadno dokázat horní odhad v důkazu Tvrzení(1). Stačí rozdělit tento výraz na dva pomyslné (X=i; Y=n+1-i). Součtem X+Y je vždy n+1. Jde vlastně jaké má být rozdělení tohoto součtu, aby násobek X a Y byl nějvětší (kvůli hornímu odhadu). (Jednoduchý příklad, součet dvou stran pravoúhlého čtyřúhelníku a,b je konst. (např. e) a při jakém rozdělení je obsah čtyřúhelníku největší - a to je právě jsou-li obě tyto strany stejně dlouhé, tedy a=b=e/2). Největší "výsledek" nám tedy vyjde při i=n/2, tj. úpravou získáme, že ((n+1)/2)^2 je horním odhadem (dosadíme za i právě ono n/2).

Zmíněn byl vzorec přesněji odhadující n!. Tím je Stirlingův vzorec.

Definice: X je konečná množina, jestliže existuje vzájemně jednoznačné zobrazení X -> {1, ..., n} (pak bude #X = |X| = n (mohutnost množiny X můžeme značit též #X))

Definice: je-li X množina; k číslo (přirozené), pak X nad k budeme rozumět množinu všech podmnožin množiny X s mohutností k; pojmem nad myslím klasický zápis do () zcela obdobně kombinatorickému zápisu "nad"

Tvrzení(2): počet prvků množiny X nad k (z definice výše), je kombinatorické číslo mohutnost množiny X nad k, tedy (hrubě asi takto):

|(	X	)| = (	|X|	)
	k		k

Princip ikluze a exkluze (PIE): mohutnost sjednocení množin A a B je součet mohutností množin A a B mínus mohutnost jejich průniku (pro dvě množiny). PIE je však obecnější, popisuje mohutnost sjednocení libovolného počtu množin. Celé by to mělo vypadat asi takhle:

Důkaz pak provádíme matematickou indukcí, nejprve ověřením pro n=1; následně pro n=2 čehož využijeme při ověřování n+1, kde si výraz rozdělíme na n, což předpokládáme a n+1 -ní, a využijeme toho, co jsme si dokázali pro dvě množiny.