Számösszetétel

A számelméletben a természetes szám összetétele vagy felbontása természetes számok összegeként való megjelenítése , amely figyelembe veszi a tagok sorrendjét. A kompozícióban szereplő kifejezéseket részeknek nevezzük , számuk pedig a kompozíció hossza .

A szám felosztása a kompozícióval ellentétben nem veszi figyelembe a részek sorrendjét. Ezért egy szám partícióinak száma soha nem haladja meg a kompozíciók számát.

Rögzített hosszúságú kompozíciók esetén néha megengedettek 0-val egyenlő kifejezések.

Példák

Az 5-ös számhoz 16 kompozíció tartozik:

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

Kompozíciók száma

Általános esetben vannak n számú összetételek , amelyeknek pontosan k hossza van , ahol a binomiális együttható , vagy a kombinációk száma . $2^{{n-1}}$ ${\tbinom {n-1}{k-1))$ ${\tbinom {n-1}{k-1))$

Bizonyíték

Ennek az állításnak a bizonyításához elegendő egy bijekciót létrehozni a k hosszúságú n kompozíciók és egy -elem halmaz -elem részhalmazai között . Társítsuk az összetételt a halmaz részösszegekből álló részhalmazához : . Nyilvánvaló, hogy ennek a megfelelésnek az ellenkezője van: a részhalmaz segítségével, amelynek elemei növekvő sorrendben vannak, visszaállíthatja az eredeti összetételt: $(k-1)$ $(n-1)$ $n=n_{1}+\lpont +n_{k}$ $\{1,\;\ldots ,\;n-1\}$ $\{n_{1},\;n_{1}+n_{2},\;\lpontok ,\;n_{1}+\lpontok +n_{{k-1}}\}$ $\{m_{1},\;\ldots ,\;m_{{k-1}}\}$

n_{1}=m_{1}

, és végül, .

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

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

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

Így a megszerkesztett leképezés bijektív, és ezért az n számú k hosszúságú összetételek száma megegyezik a -elem halmaz -elem részhalmazainak számával , vagyis a binomiális együtthatóval . $(k-1)$ $(n-1)$ ${\tbinom {n-1}{k-1))$

Az n szám kompozícióinak teljes számának kiszámításához elegendő vagy összegezni ezeket a binomiális együtthatókat, vagy ugyanazt a leképezést használni az n szám összes összetétele és az -elem halmaz összes részhalmaza közötti bijekció létrehozásához. ■ $(n-1)$

Ha a k hosszúságú n számú kompozíciókban megengedett a nulla rész , akkor az ilyen kompozíciók száma egyenlő lesz , mivel minden részhez 1-et adva n + k számú összetételt kapunk, már nulla részek nélkül. Ha figyelembe vesszük az n számú kompozíciókat, amelyekben lehetséges nulla részek teljesen tetszőleges hosszúságúak, akkor a kompozíciók száma általánosságban végtelen lesz. ${\tbinom {n+k-1}{k-1))$

Lásd még

Szám felosztása

Irodalom

Sachkov VN A diszkrét matematika kombinatorikus módszerei. - M. : Nauka, 1977. - S. 241. - 319 p.