Složení čísla

V teorii čísel, složení nebo rozklad přirozeného čísla, je taková reprezentace toho jako suma přirozených čísel, která bere v úvahu pořadí požadavků. Termíny obsažené ve skladbě se nazývají části a jejich počet odpovídá délce skladby.

Rozdělení čísla na rozdíl od kompozice nebere v úvahu pořadí částí. Proto počet oddílů čísla nikdy nepřesáhne počet skladeb.

S pevnou délkou skladeb jsou v nich někdy povoleny výrazy rovné 0.

Příklady

Pro číslo 5 je 16 skladeb:

${\begin{alignedat}{2}5&=5=\\&=4+1=\\&=3+2=\\&=3+1+1=\\&=2+3= \\&=2+2+1=\\&=2+1+2=\\&=2+1+1+1=\\&=1+4=\\&=1+3+1= \\&=1+2+2=\\&=1+2+1+1=\\&=1+1+3=\\&=1+1+2+1=\\&=1+ 1+1+2=\\&=1+1+1+1+1.\end{alignedat}}$

Počet skladeb

V obecném případě existují složení čísla n , která mají přesně délku k , kde je binomický koeficient , nebo počet kombinací . $2^{{n-1}}$ ${\tbinom {n-1}{k-1))$ ${\tbinom {n-1}{k-1))$

Důkaz

K prokázání tohoto tvrzení stačí sestrojit bijekci mezi kompozicemi n délky k a -prvkovými podmnožinami -prvkové množiny. Spojme kompozici s podmnožinou množiny skládající se z dílčích součtů: . Tato korespondence má samozřejmě opak: pomocí podmnožiny , jejíž prvky jsou seřazeny ve vzestupném pořadí, můžete obnovit původní kompozici: $(k-1)$ $(n-1)$ $n=n_{1}+\ldots +n_{k}$ $\{1,\;\ldots ,\;n-1\}$ $\{n_{1},\;n_{1}+n_{2},\;\ldots ,\;n_{1}+\ldots +n_{{k-1}}\}$ $\{m_{1},\;\ldots ,\;m_{{k-1}}\}$

n_{1}=m_{1}

, v a nakonec .

n_{i}=m_{i}-m_{{i-1}}

i=2,\;\ldots ,\;k-1

n_{k}=n-m_{{k-1}}

Sestrojené zobrazení je tedy bijektivní, a proto je počet složení počtu n délky k roven počtu -prvkových podmnožin -prvkové množiny, tedy binomickému koeficientu . $(k-1)$ $(n-1)$ ${\tbinom {n-1}{k-1))$

Pro výpočet celkového počtu složení čísla n stačí buď sečíst tyto binomické koeficienty, nebo použít stejné zobrazení k sestrojení bijekce mezi všemi složeními čísla n a všemi podmnožinami -prvkové množiny. ■ $(n-1)$

Pokud jsou ve skladbách o počtu n délky k povoleny nula dílů , bude počet takových skladeb roven , protože přidáním 1 ke každému dílu vznikne skladba o počtu n + k již bez nulových dílů. Budeme-li uvažovat skladby čísla n s možnými nulovými částmi absolutně libovolné délky, pak bude počet skladeb, obecně řečeno, nekonečný. ${\tbinom {n+k-1}{k-1))$

Viz také

Rozdělení čísla

Literatura

Sachkov VN Kombinatorické metody diskrétní matematiky. - M. : Nauka, 1977. - S. 241. - 319 s.