Kuličky a přihrádky

Mějme dáno $k$ uniformních kuliček, které chceme všechny rozdělit do $p$ přihrádek (uspořádaných zleva doprava). Kolika způsoby to lze učinit? Uvažujme tři možné varianty podle povoleného počtu kuliček v přihrádce:

1. V přihrádkách může být libovolný počet kuliček.
2. V každé přihrádce je nejvýše jedna kulička.
3. V každé přihrádce je aspoň jedna kulička.

Dále znovu uvažme část a. a b. s tím rozdílem, že nyní jsou kuličky očíslované postupně $1, 2, . . . , k$. Celkem máme tedy pět možných variant úlohy.

Počty součtů

1. Kolika způsoby lze nezáporné celé číslo $n \in \N$ napsat jako součet $s$ sčítanců? Předpokládejme, že každý sčítanec je také nezáporné celé číslo a že na pořadí sčítanců záleží. Například pro $n = 4$ a $s = 2$ máme pět možností: $4 = 0 + 4,\ 4 = 1 + 3,\ 4 = 2 + 2,\ 4 = 3 + 1,\ 4 = 4 + 0$.
2. Jak se změní předchozí výsledek, jestliže budeme požadovat, aby všechny sčítance byly kladné?

Kombinatorické identity

Rozmyslete si, že platí následující identity ($n,k\in \N$):

1. ${n \choose k} = {n \choose n-k}$
2. ${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$ pro $n\ge 1$.
3. $\sum_{0\le k \le n}{n \choose k} = 2^n$
4. $\sum_{0\le k \le n} k{n \choose k} = n2^{n-1}$
5. $\sum_{0\le k \le n} (-1)^k{n \choose k} = 0$ pro $n\ge 1$.
   Lehčí varianta: $n$ je liché.

Náhodné úlohy

1. Mějme šachovnici o rozměrech $2^n \times 2^n$ pro $n \in \N$, na níž chybí jedno rohové políčko. Dokažte, že ji jde celou vydláždit dlaždicemi tvaru L velikosti $2\times 2$.
2. Máme osm kuliček, které vypadají úplně stejně, jen jedna je o trochu těžší než ostatní. Dokážete s pomocí pouhých dvou vážení na rovnoramenných vahách najít tu těžší?