Number of compositions with sum N I was wondering if any of you folks could help me with this combinatorial problem. I need to show the exact number of compositions (c1, c2 , c3, ...) that have a sum of N is $2^{N-1}$.
For example, for $n=4$ we have $C_N = \{(4) , (3,1), (2,2), (1,3), (2,1,1), (1,2,1), (1,1,2), (1,1,1,1)\}$ with $|C_N| = 2^{4-1} = 8$
 A: For a given sum $N$, Consider a collection of $N$ objects laid out in a row. The problem of determining the number of compositions is equivalent to determining the number of ways we can group the objects in this row together. For example, the composition $(2,1,1)$ for $N=4$ would correspond to the grouping
$$**|*|*$$
For every object besides the first one there are two possibilities: $1)$ The object is in the same group as the previous object $2)$ The object is in a different group from the previous object. Compositions are uniquely determined by these $N-1$ choices. Thus, there are $2^{N-1}$ compositions.
Alternatively, you can formulate this problem as a stars and bars problem. In which case the total number of combinations becomes $$\sum_{k=1}^N \binom{N-1}{k-1}=2^{N-1}$$
A: I invite you to rewrite your example in a way that might a bit more helpful for seeing the combinatorics involved. For instance, write (1+1+1,1) instead of (3,1). Note that since $c_1,c_2,\cdots\in \mathbb{N}$, we then note that when writing an element of $C_N$ in the matter indicated above, the number 1 appears $n$ times. This is similar to noting that each element of $\mathbb{N}$ can be written as:
$$n=\underbrace{1+1+\cdots +1}_{\text{$n$ times}}$$
From here, we notice that each element of $C_N$ is simply a different way of replacing addition symbols with commas. In the example you gave, $4=1+1+1+1$, so there are 3 addition symbols that could be replaced with commas in some way. The number of ways this can be done is $2^3$. Can you see why?
Once you understand this, you should be able to use the same argument for any $N\in\mathbb{N}$.
