Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

Suppose $n\ge4$. Show that in a list of all $2^{n-1}$ compositions of $n$, the integer $3$ occurs exactly $n2^{n-5}$ times.

[Hint: Look at ways of drawing lines between n dots.]

The number of k-term compositions of $n$ is $\binom{n−1}{k−1}$, for $k\le n$.

We have the two lines $3$ apart and then some combinations on the left of the lines and some combinations on the right of the lines to count but I can't figure out what they are.

Any help would be greatly appreciated!

share|improve this question

marked as duplicate by joriki, Gerry Myerson, 1015, Davide Giraudo, Henry T. Horton Feb 17 '13 at 23:19

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

add comment

1 Answer

There are $n-4$ ways to draw two lines $3$ apart. Each of those leaves $n-5$ other spaces between dots, spaces where you can either draw a line or not draw a line. So, for each way of drawing two lines $3$ apart, there are $2^{n-5}$ ways for it to occur in a composition.

But you could also draw a single line $3$ from the left end (or $3$ from the right end), leaving $n-4$ spaces where you can draw a line or not draw a line. So for each way to draw a line $3$ from an end, there are $2^{n-4}$ ways for it to occur in a composition.

Now add 'em all up.

share|improve this answer
add comment

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