6
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Compositions are generally taken to require positive summands, not just non-negative (otherwise there would be infinitely many, as you could insert as many $0$'s as you wish). $\endgroup$ – Robert Israel Sep 4 '12 at 22:20
  • $\begingroup$ My mistake, I meant positive of course. $\endgroup$ – Quintofron Sep 4 '12 at 22:22
5
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Before I posted the question, I had been thinking of a similar approach, but got stuck when trying to handle the possibility of multiple $3$s appearing within a ($k$-term) composition. I didn't come up with the idea of counting these separately, basing on the position of a $3$ in arrangements of the given length (they indeed sum up to the desired number). I also like the argument that lets us skip considering the occurrence of $3$ at consecutive positions and multiply by $k$ right away. Nicely done, thank you! $\endgroup$ – Quintofron Sep 5 '12 at 0:19
3
$\begingroup$

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?

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ This argument generalizes nicely to show that the number of $k$’s appearing in compositions of $n\ge k+1$ is $(n-k+3)2^{n-k-2}$. Equivalently, and perhaps more neatly, the number of $k$’s appearing in compositions of $k+n$ for $n\ge 1$ is $(n+3)2^{n-2}$: it’s the same sequence, $\langle 2,5,12,28,\dots\rangle$ for every $k$. $\endgroup$ – Brian M. Scott Sep 4 '12 at 23:59
  • $\begingroup$ @Michael Lugo: Yes, I know of this approach :) I explained the difficulties I had had with completing this line of reasoning in my comment to Robert Israel's answer. Apparently the difficult part is done by now, thanks for help. :) $\endgroup$ – Quintofron Sep 5 '12 at 0:25
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$

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.