Compositions and partitions · Definition
Integer composition
Before you start you need to know
Compositions are the first example of counting partitions with order and appear in many counting problems. To count them, it suffices to decide where to place separators between the units.
Definition
A composition of a positive integer n is a way of writing it as an ordered sum of positive integers, where the order of the summands matters.
The total number of compositions of \(n\) is \(2^{n-1}\), because each of the \(n-1\) gaps between the \(n\) units may or may not hold a separator. If one fixes that the composition has exactly \(k\) parts, the number of compositions is \(\binom{n-1}{k-1}\), since one chooses \(k-1\) separators among \(n-1\) possible gaps. These results follow directly from a bijective correspondence between compositions and sets of separators.
Take \(n=4\). The compositions with exactly 2 parts are \(1+3\), \(2+2\) and \(3+1\), that is, \(\binom{3}{1}=3\) cases. Each one corresponds to choosing a single separator among the three gaps of a chain of four units.
A typical mistake is confusing compositions with partitions, counting \(1+3\) and \(3+1\) as the same. In a composition order matters, so they are two distinct objects, and that is why the total is \(2^{n-1}\) rather than the number of partitions of \(n\).
Think about it
What would happen to the number of compositions of \(n\) if parts equal to \(0\) were allowed?
It would be infinite, since zeros could be inserted as many times as desired; the formula \(2^{n-1}\) requires positive parts.
Exercises 10
- How many compositions of n=3 exist in total?
- How many compositions of n=4 have exactly 1 part?
- If n=5, how many gaps between units are there?
- What is the binomial coefficient \(\binom{4}{2}\)?
- How many compositions of n=2 exist?
- How many compositions of n=5 have exactly 2 parts?
- How many compositions of n=6 have exactly 3 parts?
- How many compositions of n=4 have at least 3 parts?
- How many compositions of n=6 have all parts odd?
- Give a counterexample showing that the number of compositions of n into k parts does not always match the number of partitions of n into k parts. For which n and k do they differ?
What comes next
References
- Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
- Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.