# Proving an equality involving compositions of an integer

Let’s consider various representations of a natural number $n \geq 4$ as a sum of positive integers, in which the order of summands is important (i.e. compositions). The task is to prove the number $3$ appears altogether $n2^{n-5}$ times in all of them.

I know there’re $2^{n-1}$ compositions of $n$. However, I have no clue as to how to count only those involving the number(s) $3$. I can’t think of any sensible generating function for this. Maybe there’s a nice combinatorial interpretation of the given formula, which I can’t figure out? Could anyone lend me a hand with handling this problem?

#### Solutions Collecting From Web of "Proving an equality involving compositions of an integer"

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

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?

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