What to do after finding products for coefficients in generating functions?

159 Views Asked by At

The problem is as follows:

$\text{Determine the coef. of } x^{10} \text{ in } (x^3 + x^5 + x^6)(x^4 + x^5 + x^7)(1+x^5+x^{10}+x^{15}+...)$

With this, there are three ways to get $x^{10}$.
1) $x^3\cdot x^7\cdot1$
2) $x^5\cdot x^5\cdot1$
3) $x^6\cdot x^4\cdot 1$

But then what? I don't understand where to go on from here.

1

There are 1 best solutions below

7
On BEST ANSWER

$$\sum_i x_i \sum_j y_j \sum_k z_k = \sum_{i,j,k} x_i y_j z_k$$

Suppose we wanted to multiply $(x_1 + x_2)(y_1 + y_2 + y_3)$. We take every combination of $x_iy_j$ and sum them together. In every possible way, we choose one term from the first bracket, either $x_1$ or $x_2$ and then multiply it by one term from the second bracket, either $y_1$, $y_2$ or $y_3$. Let's look at a picture.

enter image description here

So how do we multiply $(x^3 + x^5 + x^6) (x^4 + x^5 + x^7) (1 + x^5 + x^{10})$. Doing the same as above, we will get $27$ terms, which is unwieldy. Instead let's just pick out the ones that contribute to $x^{10}$.

$$ (x^3 + x^5 + x^6) (x^4 + x^5 + x^7) (1 + x^5 + x^{10}) \\ \; \\ \begin{array} ( &= &... &+& (x^3) (x^7)(1) &+& ... &+& (x^5)(x^5)(1) &+& ... &+& (x^6)(x^4)(1) &+& ... \\ &= &... &+& x^{10} &+& ... &+& x^{10} &+& ... &+& x^{10} &+& ...\\ &=& ... &+& 3x^{10} &+& ...\\ \end{array} $$ There is nothing fancy about this calculation; all we are doing is standard multiplication.


You linked this post. Let's take a look at the product.

$$ (\;)_1 \;\; (\;)_2\;\; (\;)_3\;\; (\;)_4\;\; (\;)_5 = \\ \left(x^{31}\right) \left(1-x^{16}\right) \left(1-x^{15}\right) (1-x^{26}) \left(\sum_{i\geq 0} {k+2 \choose k} x^k \right) $$

Now we want to find the coefficient of $x^{52}$. I want you to carry it out yourself so you understand. Here is your first exercise: How can we choose one term from each $()_i$ such that their combined product results in $x^{52}$ (ignoring coefficients)? You should find that there are only three ways to do this.