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
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 '15 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$ – ReverseFlow Jan 8 '15 at 4:39
  • $\begingroup$ Partitions, perhaps? $\endgroup$ – Miguelgondu Jan 8 '15 at 4:47
  • $\begingroup$ Multi-index :-) $\endgroup$ – copper.hat Jan 8 '15 at 4:48
  • $\begingroup$ Right. It is not exactly the answer and partition is a correct description. $\endgroup$ – Empiricist Jan 8 '15 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.