Rozklady na součet
Úloha číslo: 4323
Odpověď
\(2^{n-1}\)Řešení
Označme \(R_n\) počet rozkladů čísla \(n\). Ručně spočítáme \(R_0\)=1 (prázdný rozklad), \(R_1=1\), \(R_2=2\), \(R_3=4\). To naznačuje, že by mohlo platit \(R_n=2^{n-1}\) pro \(n>0\). To jde snadno dokázat indukcí: když rozklad začíná číslem \(k\), zbývající členy tvoří rozklad čísla \(n-k\). Takže \(R_n=\sum_{k=1}^n R_{n-k}\), tedy podle indukčního předpokladu \(R_n=1+\sum_{k=0}^{n-1} 2^k = 2^{n-1}\).
Nebo můžeme úlohu řešit kombinatorickou úvahou. Každý rozklad lze získat z \(1+1+1+\ldots+1\) tím, že některé sousedící jedničky spojíme do skupin. Rozklad na skupiny je jednoznačně určený tím, kterými jedničkami končí skupina. Prvními \(n-1\) jedničkami může, ale nemusí končit; poslední jedničkou vždy končí. Existuje \(2^{n-1}\) možností, jak skupiny ukončit.
