Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How many compositions of n has first part 1?

I've been trying to figure this out, if the number of compositions on n is 2^(n-1) then would the number of compositions of n with the first part 1 be 2^(n-2)?

share|cite|improve this question
up vote 4 down vote accepted

If you fix the first part of your composition of $n$, then the remaining parts give a composition of $n-1$. Therefore the formula you give is basically correct, though you should have some doubt about its validity for $n\leq1$. In fact the number of compositions of $n$ equals $2^{n-1}$ only if $n>0$ (and the number $0$ has one, empty, composition), so the number of composition of $n$ with first part $1$ is $2^{n-2}$ only if $n>1$. The full formula is $$ \#\{\text{compositions of $n$ with first part }1\} = \begin{cases} 0 & \text{if }n=0\\ 1 & \text{if }n=1\\ 2^{n-2} & \text{if }n>1 \end{cases} $$

share|cite|improve this answer
(+1): What if $n<0$? (Kidding.) – Cameron Buie Mar 3 '13 at 6:11
Thank you!! What if the second part is 1 instead of the first part? Would it still be the same solution? – Wooooop Mar 3 '13 at 6:11
@kevlar. Into every non-empty composition of $n-1$ one can insert a part $1$ after the first part, so as to obtain a composition of $n$ with second part $1$. So the answer for this case would be the same as the one for the first part except that that value for $n=1$ would be $0$ (there can be no second part for $n=1$). – Marc van Leeuwen Mar 3 '13 at 10:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.