Find the coefficient of $x^{13}$ in the convolution of two generating functions

Question

Four thiefs have stolen a collection of 13 identical diamonds. After the theft, they decided how to distribute them.

3 of them have special requests:

1. One of them doesn't want more than 2 diamonds ($\leq2$).

2. The other one only wants a number of diamonds that's a multiple of 3.

3. And the other one wants an odd number of diamonds greater or equal than 3.

Find in how many ways they can distribute the diamonds.

My first thought was to use generating functions to find the coefficient of $x^{13}$, for this problem it would be:

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

and that would be equivalent to finding the coefficient of $x^{10}$ in $\frac{1}{(1-x)^{2}}\frac{1}{(1-x^2)}$.

I know that I could use the binomial theorem, but the solution I have says I should be using convolution of these two generating functions, but I have no idea how to use it to find the coefficient of $x^{10}$.

Answer 1

It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.

We obtain \begin{align*} \color{blue}{[x^{13}]\frac{x^3}{(1-x)^2(1-x^2)}} &=[x^{10}]\frac{1}{(1-x)^2(1-x^2)}\tag{1}\\ &=[x^{10}]\sum_{j=0}^5 x^{2j}\sum_{k=0}^\infty \binom{-2}{k}(-x)^k\tag{2}\\ &=\sum_{j=0}^5[x^{10-2j}]\sum_{k=0}^\infty\binom{k+1}{k}x^k\tag{3}\\ &=\sum_{j=0}^5[x^{2j}]\sum_{k=0}^\infty(k+1)x^k\tag{4}\\ &=\sum_{j=0}^5(2j+1)\tag{5}\\ &=2\left(\frac{5\cdot6}{2}\right)+6\\ &\,\,\color{blue}{=36} \end{align*}

Comment:

• In (1) we apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

• In (2) we do a geometric and a binomial series expansion.

• In (3) we select the coefficient of $x^{2j}$ and restrict the upper limit of the outer sum to $5$ since other values do not contribute to $[x^{10}]$. We also use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (4) we change the order of summation $j\to 5-j$ and use $\binom{k+1}{k}=\binom{k+1}{1}=k+1$.

• In (5) we select the coefficient of $x^{2j}$.

• In (6) we apply the formula $\sum_{j=0}^n j=\frac{n(n+1)}{2}$.

Answer 2

It is a laborious work.

$$\frac{d^n}{dx^n}\frac{1}{(1-x)^2(1-x^2)}=-\frac{1}{2}(-2-n)_n(-1+x)^{-3-n}+\frac{1}{4}(-1-n)_n(-1+x)^{-2-n}+\frac{1}{8}(-n)_n(1+x)^{-1-n}-\frac{1}{8}(-n)_n(-1+x)^{-1-n}$$

The bracket symbol is the Pochhammer symbol.

$$f^{(10)}(x)=\frac{d^{10}}{dx^{10}}\frac{1}{(1-x)^2(1-x^2)}=$$

$$\frac{-7257600(143x^{10}+715x^9+2574x^8+5148x^7+7722x^6+7722x^5+5720x^4+2860x^3+975x^2+195x+18)}{(x+1)^{11}(x-1)^{13}}$$

$$c_{10}=\frac{f^{(10)}(0)}{10!}=36$$

Or collect together all coefficients of $x^{13}$ from your series representation in your question, e.g. by a computer program.

Answer 3

Hint: $$\begin{align} \frac{1}{(1-x)^2} \frac{1}{1-x^2} &= (1-x)^{-2} (1-x^2)^{-1} \\ &= \sum_{i=0}^{\infty}\binom{2+i-1}{i} x^i\cdot \sum_{j=0}^{\infty}x^{2j} \end{align}$$ Combinations of $(i,j)$ satisfying $i+2j=10$ are $(10,0),(8,1),(6,2),(4,3),(2,4),(0,5)$.

[The above list of combinations was corrected in an edit on 3/10/2019. It just goes to show that I should not attempt to write an answer just before I rush out the door. My apologies.]

Can you take it from there?

Answer 4

Do you have to use generating functions? This problem seems quite simple just using simple logic. It will at least help you verify your answer.

Consider thieves 2 and 3 get allocated their diamonds first, leaving some number $k$ for thieves 0 and 1. Thief 1 has no minimum and thief 0 is easy, so any number of diamonds left over has at least one satisfactory allocation. If $k\ge2$, there are three valid allocations, if $k=1$ there's two, if $k=0$ just one (each depending on whether thief 1 does/can take 0,1 or 2 diamonds.

Thief 2 only wants $t_2=0, 3, 6, 9, 12$ diamonds. Thief 3 only wants $t_3 = 3, 5, 7, 9, 11 ,13$. The cross of this is tractable while imposing the 13 limit, giving

• $t_2=0$, $t_3 = 3, 5, 7, 9, 11, 13$
• $t_2=3$, $t_3 = 3, 5, 7, 9$
• $t_2=6$, $t_3 = 3, 5, 7$
• $t_2=9$, $t_3 = 3$

Of these cases, $(t_2,t_3) = (0,13), (6,7)$ have no remaining diamond, and $(t_2,t_3) = (3,9), (9,3)$ have one remaining. The other 10 cases have two or more remaining.

Combining this with the requirements of thieves 0 and 1 gives $10\cdot3 + 2\cdot2+ 2\cdot 1 = 36$ allocations.