Numeron koostumus

Lukuteoriassa luonnollisen luvun koostumus tai hajotelma on sellainen esitys siitä luonnollisten lukujen summana, joka ottaa huomioon termien järjestyksen. Sävellykseen sisältyviä termejä kutsutaan osiksi , ja niiden numero on sävellyksen pituus .

Numeron jakaminen , toisin kuin kokoonpano, ei ota huomioon osien järjestystä. Siksi luvun osioiden määrä ei koskaan ylitä kokoonpanojen määrää.

Kiinteän pituuden sävellyksissä termit, jotka ovat yhtä suuria kuin 0, ovat joskus sallittuja.

Esimerkkejä

Numerolle 5 on 16 sävellystä:

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

Sävellysten lukumäärä

Yleisessä tapauksessa on luvun n koostumuksia , joiden pituus on täsmälleen k , missä on binomikerroin tai yhdistelmien lukumäärä . $2^{{n-1}}$ ${\tbinom {n-1}{k-1))$ ${\tbinom {n-1}{k-1))$

Todiste

Tämän väitteen todistamiseksi riittää, että konstruoidaan bijektio k -pituisten koostumusten n ja -elementtijoukon -elementtiosajoukkojen välille . Yhdistetään kokoonpano joukon osajoukkoon, joka koostuu osittaisista summista: . Ilmeisesti tällä kirjeenvaihdolla on päinvastainen: alijoukolla , jonka elementit on järjestetty nousevaan järjestykseen, voit palauttaa alkuperäisen sävellyksen: $(k-1)$ $(n-1)$ $n=n_{1}+\lpisteet +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}

, klo ja lopuksi .

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

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

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

Siten muodostettu kuvaus on bijektiivinen, ja siksi luvun n , jonka pituus on k , määrä on yhtä suuri kuin -elementtijoukon -alkio-osajoukkojen lukumäärä , eli binomikerroin . $(k-1)$ $(n-1)$ ${\tbinom {n-1}{k-1))$

Luvun n kokoonpanojen kokonaismäärän laskemiseksi riittää joko summaamalla nämä binomikertoimet tai käyttää samaa kartoitusta bijektion rakentamiseen luvun n kaikkien koostumusten ja -alkiojoukon kaikkien osajoukkojen välille . ■ $(n-1)$

Jos nolla osaa sallitaan koostumuksissa, joiden lukumäärä on n ja joiden pituus on k , niin tällaisten kokoonpanojen lukumäärä on yhtä suuri kuin , koska lisäämällä 1 jokaiseen osaan saadaan luvun n + k kokoonpano jo ilman nollaosia. Jos tarkastellaan luvun n koostumuksia, joissa on mahdollisia nollaosia, joiden pituus on täysin mikä tahansa, niin sävellysten lukumäärä on yleisesti ottaen ääretön. ${\tbinom {n+k-1}{k-1))$

Katso myös

Numeron jakaminen

Kirjallisuus

Sachkov VN Diskreetin matematiikan kombinatoriset menetelmät. - M .: Nauka, 1977. - S. 241. - 319 s.