Compoziția numerelor

În teoria numerelor, o compoziție sau descompunerea unui număr natural este o astfel de reprezentare a acestuia ca o sumă de numere naturale care ia în considerare ordinea termenilor. Termenii incluși în compoziție se numesc părți , iar numărul lor este lungimea compoziției.

Împărțirea unui număr, spre deosebire de compoziție, nu ține cont de ordinea părților. Prin urmare, numărul de partiții ale unui număr nu depășește niciodată numărul de compoziții.

Cu o lungime fixă a compozițiilor, termenii egali cu 0 sunt uneori permisi în ele.

Exemple

Există 16 compoziții pentru numărul 5:

${\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}}$

Numărul de compoziții

În cazul general, există compoziții ale numărului n , dintre care exact lungimea k , unde este coeficientul binom , sau numărul de combinații . $2^{{n-1}}$ ${\tbinom {n-1}{k-1))$ ${\tbinom {n-1}{k-1))$

Dovada

Pentru a demonstra această aserțiune, este suficient să construim o bijecție între compozițiile n de lungime k și submulțimi de elemente ale unei mulțimi de elemente. Să asociem compoziția cu o submulțime a mulțimii formată din sume parțiale: . Evident, această corespondență are opusul: prin submulțime , ale cărui elemente sunt ordonate crescător, puteți restabili compoziția originală: $(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}

, la și, în sfârșit, .

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

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

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

Astfel, maparea construită este bijectivă și, prin urmare, numărul de compoziții ale numărului n de lungime k este egal cu numărul de submulțimi -element ale mulțimii -element, adică coeficientul binomial . $(k-1)$ $(n-1)$ ${\tbinom {n-1}{k-1))$

Pentru a calcula numărul total de compoziții ale numărului n , este suficient fie să însumăm acești coeficienți binomi, fie să folosim aceeași mapare pentru a construi o bijecție între toate compozițiile numărului n și toate submulțimile mulțimii de elemente. ■ $(n-1)$

Dacă sunt permise zero părți în compozițiile cu numărul n de lungime k , atunci numărul acestor compoziții va fi egal cu , deoarece adăugarea a 1 la fiecare parte dă o compoziție a numărului n + k deja fără zero părți. Dacă luăm în considerare compozițiile numărului n cu posibile părți zero de absolut orice lungime, atunci numărul compozițiilor, în general, va fi infinit. ${\tbinom {n+k-1}{k-1))$

Vezi și

Împărțirea unui număr

Literatură

Sachkov VN Metode combinatorii ale matematicii discrete. - M. : Nauka, 1977. - S. 241. - 319 p.