Proving an equality involving compositions of an integer

Solution 1:

The number of $k$-term compositions of $n$ is ${n-1} \choose {k-1}$, for $k \le n$.
There will be ${n-4} \choose {k-2}$ occurrences of $3$ as the first term of a $k$-term composition (namely the number of $k-1$-term compositions of $n-3$). But since any permutation of a composition is a composition, for $1 \le j \le k$ the number of occurrences of $3$ as the $j$'th term of a $k$-term composition of $n$ is also ${n-4} \choose {k-2}$. So the total number of occurrences of $3$ in $k$-term compositions of $n$ is $k {{n-4} \choose {k-2}}$. Now sum this from $k = 1$ to $n-2$.

Solution 2:

Although it's possible to do this using generating functions, that's not the best method. (Unless you've specifically been asked to do this using generating functions!)

If you've learned about compositions there's a good chance you've learned about the dots-and-bars representation of them. A composition of $n$ can be represented by $n$ dots, with bars separating the parts. For example, we can represent the composition $10 = 2 + 4 + 3 + 1$ as

$$ \cdot \cdot | \cdot \cdot \cdot \cdot | \cdot \cdot \cdot | \cdot $$

Any composition of 10 can be written as 10 $\cdot$s; each of the 9 positions between two dots can either contain a $|$ or not, giving a proof that there are $2^9$ compositions of $10$. (Of course this generalizes; in general there are $2^{n-1}$ compositions of $n$.)

This composition can be written as (some parts which add up to 6) + 3 + (some parts which add up to 1). How many such compositions are there? What about for the other positions in which the part $3$ could occur?

Solution 3:

It appears that the generating function approach is quite simple here. We have by inspection that the bivariate generating function of compositions with the number three marked is $$M(z, u) = \sum_{q\ge 1}\left(\frac{z}{1-z} - z^3 + uz^3\right)^q.$$ Therefore the generating function of the total number of ocurrences is $$\left.\frac{d}{du} M(z, u)\right|_{u=1} = \left. \sum_{q\ge 1} q \left(\frac{z}{1-z} - z^3 + uz^3\right)^{q-1} \times z^3 \right|_{u=1} \\= z^3 \sum_{q\ge 1} q \left(\frac{z}{1-z}\right)^{q-1} = z^3 \frac{1}{(1-z/(1-z))^2} = z^3 \frac{(1-z)^2}{(1-2z)^2} \\ = z^3 \left(\frac{1}{1-2z} + \frac{z^2}{(1-2z)^2}\right).$$ To conclude extract coefficients, getting $$[z^{n-3}] \left(\frac{1}{1-2z} + \frac{z^2}{(1-2z)^2}\right) = 2^{n-3} + [z^{n-5}] \frac{1}{(1-2z)^2} \\ = 2^{n-3} + (n-4) 2^{n-5} = 4 \times 2^{n-5} + (n-4) 2^{n-5} = n 2^{n-5}.$$