2
$\begingroup$

What is the generating function for ${a_k}$, where $a_k$ is the number of solutions of $x_1 + x_2 + x_3 = k$ when $x_1,x_2,x_3$ are integers with $x_1 \geq 2$, $0 \leq x_2 \leq 3$, and $2 \leq x_3 \leq 5$?

I know that the answer of this problem is $x^4(1+x+x^2+x^3)^2/(1-x)$. I want to know how to find the generating function in detail. Please help me!

$\endgroup$
0
$\begingroup$

Let me change the names of the variables in hopes of reducing confusion later: instead of $x_1,x_2$, and $x_3$, I’ll use $y_1,y_2$, and $y_3$. Eventually my generating function will use the indeterminate $x$, but temporarily I’m going to split it into three indeterminates $x_1,x_2$, and $x_3$: for $k=1,2,3$ the exponent on $x_k$ will keep track of a possible value of $y_k$. The possible values of $y_1$ are the integers greater than or equal to $2$, represented by

$$x_1^2+x_1^3+x_1^4+\ldots=\sum_{n\ge 2}x_1^n\;.$$

The only possible values of $y_2$ are $0,1,2$, and $3$, represented by

$$x_2^0+x_2^1+x_2^2+x_2^3\;.$$

And the only possible values of $y_3$ are $2,3,4$, and $5$, represented by

$$x_3^2+x_3^3+x_3^4+x_3^5\;.$$

Multiply these three expressions together to get

$$(x_1^2+x_1^3+x_1^4+\ldots)(x_2^0+x_2^1+x_2^2+x_2^3)(x_3^2+x_3^3+x_3^4+x_3^5)\;,$$

and imagine actually carrying out the multiplication. Each term of the product will have the form $x_1^kx_2^\ell x_3^m$, where $k\ge 2$, $0\le\ell\le 3$, and $2\le m\le 5$. Now drop the subscripts on $x_1,x_2$, and $x_3$, making them all simply $x$: each term of the product will have the form $x^{k+\ell+m}$ for some integers $k,\ell$, and $m$ such that $k\ge 2$, $0\le\ell\le 3$, and $2\le m\le 5$. Moreover, every possible combination of $k,\ell$, and $m$ satisfying those constraints will occur. Thus, when you collect like terms, you’ll have one copy of $x^n$ for each combination of $k,\ell$, and $m$ such that $k+\ell+m=n$, $k\ge 2$, $0\le\ell\le 3$, and $2\le m\le 5$. That is, the coefficient of $x^n$ will be the number of solutions to $y_1+y_2+y_3=n$ satisfying the given conditions.

This means that the desired generating function is

$$(x^2+x^3+x^4+\ldots)(x^0+x^1+x^2+x^3)(x^2+x^3+x^4+x^5)\;,$$

and we need only simplify it. First, $x^2+x^3+x^4+x^5=x^2(1+x+x^2+x^3)$, so

$$(x^0+x^1+x^2+x^3)(x^2+x^3+x^4+x^5)=x^2(1+x+x^2+x^3)^2\;.$$

Then

$$x^2+x^3+x^4+\ldots=\sum_{n\ge 2}x^n=x^2\sum_{n\ge 0}x^n=\frac{x^2}{1-x}$$

from the formula for a geometric series. Now just put the pieces togeter to get

$$\frac{x^2}{1-x}\cdot x^2(1+x+x^2+x^3)=\frac{x^4(1+x+x^2+x^3)}{1-x}\;.$$

$\endgroup$

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.