Rozklady na součet

Úloha číslo: 4323

Spočítejte, kolik existuje rozkladů čísla \(n\) na součet celých kladných sčítanců. Například pro \(n=3\) to jsou \(1+1+1\), \(1+2\), \(2+1\) a \(2\).
  • 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.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
	Zaslat komentář k úloze