Nummersammansättning

I talteorin är en sammansättning , eller nedbrytning av ett naturligt tal, en sådan representation av det som en summa av naturliga tal som tar hänsyn till ordningen på termerna. Termerna som ingår i kompositionen kallas delar , och deras antal är längden på kompositionen.

Att dela upp ett nummer, till skillnad från komposition, tar inte hänsyn till ordningen på delarna. Därför överstiger antalet partitioner av ett antal aldrig antalet kompositioner.

Med en fast längd på kompositioner tillåts ibland termer lika med 0 i dem.

Exempel

Det finns 16 kompositioner för nummer 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}}$

Antal kompositioner

I det allmänna fallet finns det sammansättningar av antalet n , av vilka exakt har längden k , där är binomialkoefficienten , eller antalet kombinationer . $2^{{n-1}}$ ${\tbinom {n-1}{k-1))$ ${\tbinom {n-1}{k-1))$

Bevis

För att bevisa detta påstående räcker det med att konstruera en bijektion mellan sammansättningar n med längden k och -elementdelmängder av en -elementmängd. Låt oss associera sammansättningen med en delmängd av mängden som består av delsummor: . Uppenbarligen har denna korrespondens motsatsen: genom delmängd , vars element är ordnade i stigande ordning, kan du återställa den ursprungliga kompositionen: $(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}

, vid och slutligen .

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

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

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

Således är den konstruerade mappningen bijektiv, och därför är antalet sammansättningar av antalet n av längden k lika med antalet -elementdelmängder av -elementmängden, det vill säga den binomiala koefficienten . $(k-1)$ $(n-1)$ ${\tbinom {n-1}{k-1))$

För att beräkna det totala antalet sammansättningar av talet n räcker det att antingen summera dessa binomialkoefficienter, eller att använda samma avbildning för att konstruera en bijektion mellan alla sammansättningar av talet n och alla delmängder av -elementmängden. ■ $(n-1)$

Om noll delar är tillåtna i kompositioner med antalet n av längden k , kommer antalet sådana kompositioner att vara lika med , eftersom att lägga till 1 till varje del ger en sammansättning av antalet n + k redan utan noll delar. Om vi betraktar kompositioner av numret n med möjliga nolldelar av absolut vilken längd som helst, så kommer antalet kompositioner i allmänhet att vara oändligt. ${\tbinom {n+k-1}{k-1))$

Se även

Dela ett nummer

Litteratur

Sachkov VN Kombinatoriska metoder för diskret matematik. - M. : Nauka, 1977. - S. 241. - 319 sid.