3
$\begingroup$

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)?

$\endgroup$
4
$\begingroup$

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} $$

$\endgroup$
  • $\begingroup$ (+1): What if $n<0$? (Kidding.) $\endgroup$ – Cameron Buie Mar 3 '13 at 6:11
  • $\begingroup$ Thank you!! What if the second part is 1 instead of the first part? Would it still be the same solution? $\endgroup$ – Wooooop Mar 3 '13 at 6:11
  • $\begingroup$ @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$). $\endgroup$ – Marc van Leeuwen Mar 3 '13 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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