# counting compositions of an integer

A *composition ^{}* of a nonnegative integer $n$ is a sequence

^{}$({a}_{1},\mathrm{\dots},{a}_{k})$ of positive integers with $\sum {a}_{i}=n$. Denote by ${C}_{n}$ the number of compositions of $n$, and denote by ${S}_{n}$ the set of those compositions. (Note that this is a very different - and simpler - concept than the number of partitions

^{}of an integer; here the order (http://planetmath.org/PartialOrder) matters).

For some small values of $n$, we have

${C}_{0}$ | $=1$ | ||

${C}_{1}$ | $=1$ | ||

${C}_{2}$ | $=2\mathit{\hspace{1em}\hspace{1em}}(2),(1,1)$ | ||

${C}_{3}$ | $=4\mathit{\hspace{1em}\hspace{1em}}(3),(1,2),(2,1),(1,1,1)$ |

In fact, it is easy to see that ${C}_{n}=2{C}_{n-1}$ for $n>1$: each composition $({a}_{1},\mathrm{\dots},{a}_{k})$ of $n-1$ can be associated with two different compositions of $n$

$$({a}_{1},{a}_{2},\mathrm{\dots},{a}_{k},1)$$ | ||

$$({a}_{1},{a}_{2},\mathrm{\dots},{a}_{k}+1)$$ |

We thus get a map $\phi :{S}_{n-1}\times \{0,1\}\to {S}_{n}$ given by

$$\phi (({a}_{1},\mathrm{\dots},{a}_{k}),0)=({a}_{1},\mathrm{\dots},{a}_{k},1)$$ | ||

$$\phi (({a}_{1},\mathrm{\dots},{a}_{k}),1)=({a}_{1},\mathrm{\dots},{a}_{k}+1)$$ |

and this map is clearly injective^{}. But it is also clearly surjective^{}, for given $({a}_{1},\mathrm{\dots},{a}_{k})\in {S}_{n}$, if ${a}_{k}=1$ then the composition is the image of $(({a}_{1},\mathrm{\dots},{a}_{k-1}),0)$ while if ${a}_{k}>1$, then it is the image of $(({a}_{1},\mathrm{\dots},{a}_{k-1}),1)$. This proves that (for $n>1$) ${C}_{n}=2{C}_{n-1}$.

We can also figure out how many compositions there are of $n$ with $k$ parts. Think of a box with $n$ sections in it, with dividers between each pair of sections and a chip in each section; there are thus $n$ chips and $n-1$ dividers. If we leave $k-1$ of the dividers in place, the result is a composition of $n$ with $k$ parts; there are obviously $\left({\displaystyle \genfrac{}{}{0pt}{}{n-1}{k-1}}\right)$ ways to do this, so the number of compositions of $n$ into $k$ parts is simply $\left({\displaystyle \genfrac{}{}{0pt}{}{n-1}{k-1}}\right)$. Note that this gives even a simpler proof of the first result, since

$$\sum _{k=1}^{n}\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)=\sum _{k=0}^{n-1}\left(\genfrac{}{}{0pt}{}{n-1}{k}\right)={2}^{n-1}$$ |

Title | counting compositions of an integer |
---|---|

Canonical name | CountingCompositionsOfAnInteger |

Date of creation | 2013-03-22 17:37:55 |

Last modified on | 2013-03-22 17:37:55 |

Owner | rm50 (10146) |

Last modified by | rm50 (10146) |

Numerical id | 5 |

Author | rm50 (10146) |

Entry type | Result |

Classification | msc 05-00 |

Defines | composition |