0
$\begingroup$

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!

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$

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