Nummersammensætning

I talteorien er en sammensætning eller dekomponering af et naturligt tal en sådan repræsentation af det som en sum af naturlige tal, der tager hensyn til rækkefølgen af vilkårene. De udtryk, der indgår i sammensætningen, kaldes dele , og deres nummer er længden af sammensætningen.

At opdele et nummer, i modsætning til sammensætning, tager ikke hensyn til rækkefølgen af delene. Derfor overstiger antallet af partitioner af et nummer aldrig antallet af kompositioner.

Med en fast længde af kompositioner er termer lig med 0 nogle gange tilladt i dem.

Eksempler

Der er 16 kompositioner til 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{aligned}}$

Antal kompositioner

I det generelle tilfælde er der sammensætninger af antallet n , hvoraf nøjagtigt har længden k , hvor er den binomiale koefficient , eller antallet af kombinationer . $2^{{n-1}}$ ${\tbinom {n-1}{k-1))$ ${\tbinom {n-1}{k-1))$

Bevis

For at bevise denne påstand er det tilstrækkeligt at konstruere en bijektion mellem sammensætninger n af længden k og -elementdelmængder af en -elementmængde. Lad os forbinde sammensætningen med en delmængde af mængden bestående af delsummer: . Denne korrespondance har åbenbart det modsatte: ved undersæt , hvis elementer er ordnet i stigende rækkefølge, kan du gendanne den oprindelige sammensætning: $(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}

, ved og til sidst .

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

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

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

Den konstruerede mapping er således bijektiv, og derfor er antallet af sammensætninger af antallet n af længden k lig med antallet af -element-delmængder af -elementmængden, det vil sige den binomiale koefficient . $(k-1)$ $(n-1)$ ${\tbinom {n-1}{k-1))$

For at beregne det samlede antal sammensætninger af tallet n er det tilstrækkeligt enten at summere disse binomiale koefficienter eller at bruge den samme afbildning til at konstruere en bijektion mellem alle sammensætninger af tallet n og alle delmængder af -elementmængden. ■ $(n-1)$

Hvis nul dele er tilladt i sammensætninger af antallet n af længden k , så vil antallet af sådanne sammensætninger være lig med , da tilføjelse af 1 til hver del giver en sammensætning af antallet n + k allerede uden nul dele. Hvis vi betragter sammensætninger af tallet n med mulige nuldele af absolut enhver længde, så vil antallet af sammensætninger generelt være uendeligt. ${\tbinom {n+k-1}{k-1))$

Se også

Opdeling af et tal

Litteratur

Sachkov VN Kombinatoriske metoder til diskret matematik. - M. : Nauka, 1977. - S. 241. - 319 s.