Rozklady na součet
Úloha číslo: 4323
Odpověď
Číslo \(n\) má \(2^{n-1}\) rozkladů.Ř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\limits_{k=1}^n R_{n-k}\), tedy podle indukčního předpokladu \(R_n =R_0 + \sum\limits_{k=1}^{n-1} R_{n-k} = 1 + \sum\limits_{k=1}^{n-1} R_{k} = 1 + \sum\limits_{k=1}^{n-1} 2^{k-1} =1+\sum\limits_{k=0}^{n-2} 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.
