Number composition

In number theory, the composition , or decomposition , of a natural number is its representation in the form of an ordered sum of natural terms. The terms included in the composition are called parts , and their number is called the length of the composition.

Unlike composition, splitting a number does not take into account the order of the parts. Therefore, the number of splits of the number never exceeds the number of compositions.

With a fixed length of compositions, zero parts are also sometimes allowed in them.

Content

Examples

There are 16 compositions of the number 5:

$5=5;$ ${\ displaystyle 5 = 5;}$
$5=4+1;$ ${\ displaystyle 5 = 4 + 1;}$
$5=3+2;$ ${\ displaystyle 5 = 3 + 2;}$
$5=3+1+1;$ ${\ displaystyle 5 = 3 + 1 + 1;}$
$5=2+3;$ ${\ displaystyle 5 = 2 + 3;}$
$5=2+2+1;$ ${\ displaystyle 5 = 2 + 2 + 1;}$
$5=2+1+2;$ ${\ displaystyle 5 = 2 + 1 + 2;}$
$5=2+1+1+1;$ ${\ displaystyle 5 = 2 + 1 + 1 + 1;}$
$5=1+4;$ ${\ displaystyle 5 = 1 + 4;}$
$5=1+3+1;$ ${\ displaystyle 5 = 1 + 3 + 1;}$
$5=1+2+2;$ ${\ displaystyle 5 = 1 + 2 + 2;}$
$5=1+2+1+1;$ ${\ displaystyle 5 = 1 + 2 + 1 + 1;}$
$5=1+1+3;$ ${\ displaystyle 5 = 1 + 1 + 3;}$
$5=1+1+2+1;$ ${\ displaystyle 5 = 1 + 1 + 2 + 1;}$
$5=1+1+1+2;$ ${\ displaystyle 5 = 1 + 1 + 1 + 2;}$
$5=1+1+1+1+1.$ ${\ displaystyle 5 = 1 + 1 + 1 + 1 + 1.}$

Number of Songs

In general, there is $2^{(n-1)}$ ${\ displaystyle 2 ^ {(n-1)}}$ compositions of n , of which exactly ${\tbinom {n-1}{k-1}}$ ${\ displaystyle {\ tbinom {n-1} {k-1}}}$ have length k .

Evidence

To prove this statement, it suffices to construct a bijection between compositions n of length k and $(k-1)$ ${\ displaystyle (k-1)}$ -element subsets $(n-1)$ ${\ displaystyle (n-1)}$ -element set. Match the composition $n=n_{1}+\ldots +n_{k}$ ${\ displaystyle n = n_ {1} + \ ldots + n_ {k}}$ subset of the set $\{1,\;\ldots ,\;n-1\}$ ${\ displaystyle \ {1, \; \ ldots, \; n-1 \}}$ consisting of partial amounts: $\{n_{1},\;n_{1}+n_{2},\;\ldots ,\;n_{1}+\ldots +n_{k-1}\}$ ${\ displaystyle \ {n_ {1}, \; n_ {1} + n_ {2}, \; \ ldots, \; n_ {1} + \ ldots + n_ {k-1} \}}$ . Obviously, this correspondence has the opposite: in a subset $\{m_{1},\;\ldots ,\;m_{k-1}\}$ ${\ displaystyle \ {m_ {1}, \; \ ldots, \; m_ {k-1} \}}$ , whose elements are ordered in increasing order, you can restore the original composition:

n_{1}=m_{1}

{\ displaystyle n_ {1} = m_ {1}}

,

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

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

at

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

{\ displaystyle i = 2, \; \ ldots, \; k-1}

and finally

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

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

.

Thus, the constructed mapping is bijective, and therefore the number of compositions of the number n of length k is equal to the number $(k-1)$ ${\ displaystyle (k-1)}$ -element subsets $(n-1)$ ${\ displaystyle (n-1)}$ -element set, i.e. binomial coefficient ${\tbinom {n-1}{k-1}}$ ${\ displaystyle {\ tbinom {n-1} {k-1}}}$ .

To calculate the total number of compositions of n, it is enough to either sum these binomial coefficients, or use the same map to construct a bijection between all compositions of n and all subsets $(n-1)$ ${\ displaystyle (n-1)}$ -element set. ■

If zero compositions are allowed in compositions of number n of length k , then the number of such compositions will be equal to ${\tbinom {n+k-1}{k-1}}$ ${\ displaystyle {\ tbinom {n + k-1} {k-1}}}$ , since adding 1 to each part gives the composition of the number n + k already without zero parts. The question of the total number of compositions of n with possible zero parts is meaningless, since it is infinite.

Literature

Sachkov V. N. Combinatorial methods of discrete mathematics. - M .: Nauka, 1977 .-- S. 241. - 319 p.

Number composition

Content

Examples

Number of Songs

See also

Literature

More articles: