# How to find number of solutions using generating functions

I need to find the number of solutions to the following equation

$x_1+x_2+x_3+x_4 = n$ where $x_1 = 2k, \space x_2 \in \{0,1,2\}, \space x_3=3q, \space x_4 \in \{0,1\}$

Using generating functions. The biggest problem I'm having with approaching this problem is the fact that the equation is being set equal to $n$ and not a specific number.

Thanks!

• Find the coefficient of the $x^n$ term in the expansion of the product of useful terms. What counts as useful in this case has to do with the number and types of options available for each term. For example, $(1+x)$ corresponds to an option of $0$ or $1$. Meanwhile $(1+x+x^2)$ corresponds to an option of $0$ or $1$ or $2$. Notice $(1+x+x^2)(1+x)=1+2x+2x^2+x^3$ corresponds with the number of ways of getting the totals $0,1,2,3$ respectively by adding $z_1$ and $z_2$ with $z_1\in\{0,1,2\}$ and $z_2\in \{0,1\}$. Any guesses as to how to represent $x_3$ needing to be multiples of $3$? – JMoravitz Dec 5 '16 at 1:17
• As an aside, Generatingfunctionology is a good free resource for information on all sorts of generating functions. – JMoravitz Dec 5 '16 at 1:24
• Funny, you accept an answer 4 hours after it is posted, although, according to a comment of yours, it is not what you wished for. Please explain. – Did Dec 5 '16 at 12:32

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ The solution is given by \begin{align} &\bracks{z^{n}}\braces{\pars{\sum_{x_{1} = 0}^{\infty}z^{2x_{1}}} \pars{z^{0} + z^{1} + z^{2}}\pars{\sum_{x_{3} = 0}^{\infty}z^{3x_{3}}} \pars{z^{0}+z^{1}}} \\[5mm] = &\ \bracks{z^{n}}\braces{{1 + z \over 1 - z^{2}}\,{1 + z + z^{2} \over 1 - z^{3}}} = \bracks{z^{n}}{1 \over \pars{1 - z}^{2}} = \bracks{z^{n}}\sum_{k = 0}^{\infty}{-2 \choose k}\pars{-z}^{k} \\[5mm] = &\ \bracks{z^{n}}\sum_{k = 0}^{\infty}{k + 1 \choose k}\pars{-1}^{k}\pars{-z}^{k} = \bracks{z^{n}}\sum_{k = 0}^{\infty}\pars{k + 1}z^{k} = \bbx{\ds{n + 1}} \end{align}