How to approach this type of question in general?
- How to use binomial theorem?
- How to use multinomial theorem?
- Are there any other combinatorial arguments available to solve this type of question?
Asked
Active
Viewed 1,827 times
5
Andrés E. Caicedo
- 79,201
archangel89
- 903
-
See related problem. – Mhenni Benghorbal Jan 08 '15 at 05:20
-
What could be simpler than $6^4$ multiplications? – copper.hat Jan 08 '15 at 05:51
2 Answers
14
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}$$
4
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$.
Empiricist
- 7,933
-
1Put 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. – ReverseFlowControl Jan 08 '15 at 04:39
-
-
-
Right. It is not exactly the answer and partition is a correct description. – Empiricist Jan 08 '15 at 04:52