5
$\begingroup$

How to approach this type of question in general?

  1. How to use binomial theorem?
  2. How to use multinomial theorem?
  3. Are there any other combinatorial arguments available to solve this type of question?
$\endgroup$
2

2 Answers 2

14
$\begingroup$

We really seek the coefficient of $x^{14}$, factoring out an $x$ from each term in the generating function. Then observe that:

$(1 + x + x^{2} + x^{3} + x^{4} + x^{5}) = \frac{1-x^{6}}{1-x}$

Now raise this to the fourth to get: $f(x) = \left(\frac{1-x^{6}}{1-x}\right)^{4}$.

We have the identities:

$$(1-x^{m})^{n} = \sum_{i=0}^{n} \binom{n}{i} (-1)^{i} x^{mi}$$

And:

$$\frac{1}{(1-x)^{n}} = \sum_{i=0}^{\infty} \binom{i + n - 1}{i} x^{i}$$

So we expand out the numerator and denominator, picking terms of $x^{14}$. Note that we are multiplying the numerator expansion by the denominator expansion.

$$\binom{14 + 4 - 1}{14}x^{14} - \binom{4}{1} \binom{8 + 4 - 1}{8} x^{14} + \binom{4}{2} \binom{2 + 4 - 1}{2} x^{14}$$

$\endgroup$
1
  • $\begingroup$ @aes Thanks for the catch! Sorry for the careless mistake. :-) $\endgroup$
    – ml0105
    Jan 8, 2015 at 5:45
4
$\begingroup$

Hint: the coefficient of $x^{18}$ should be exactly the number of partitions $(i, j, k, l)$ of 18 with $1 \leq i,j,k,l \leq 6$.

$\endgroup$
4
  • 1
    $\begingroup$ Put another way, the answer is: the number of partitions of 18 into 4 parts where each part can come from $\{1,2,3,4,5,6\}$ and repetitions are allowed. In general you can think of them like this, with some minor tweaks depending on the powers. $\endgroup$ Jan 8, 2015 at 4:39
  • $\begingroup$ Partitions, perhaps? $\endgroup$ Jan 8, 2015 at 4:47
  • $\begingroup$ Multi-index :-) $\endgroup$
    – copper.hat
    Jan 8, 2015 at 4:48
  • $\begingroup$ Right. It is not exactly the answer and partition is a correct description. $\endgroup$
    – Empiricist
    Jan 8, 2015 at 4:52

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.