Find the generating function for the number of solutions

Question

(a) Find the generating function for the number of solutions to

$x_1+x_2+x_3+x_4+x_5+x_6=n$ where $x_1,x_2,x_3$ are even $x_4,x_5,x_6$ are odd

(b) Find the generating function for the number of solutions to

$x_1+x_2+x_3+x_4+x_5=n$

subject to the condition that $0\leq x_i \leq 12$. answer in the closed form..

As i know that the number solution for the equation $x_1+x_2+x_3+x_4+...+x_k=n$ is C(n+k-1 , k)

Answer 1

Hint: Start by finding the generating functions $O(z)$ and $E(z)$ that represent $$ [z^k]O(z)=\begin{cases}1 & \text{for $k$ odd}\\0 & \text{for $k$ even}\end{cases} $$ and $$ [z^k]E(z)=\begin{cases}0 & \text{ for $k$ odd}\\1 & \text{ for $k$ even}\end{cases}. $$ How could you write the generating function for the sums of two even numbers? Of three? What about odd numbers? How can you combine these results?

For the second, try to see how you could replace the even and odd conditions above with something more appropriate to the problem.

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{{#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}$

$\ds{\large\mathbf{\left. a\right)}}$

\begin{align} &\left.\sum_{x_{1} = 0}^{\infty}\sum_{x_{2} = 0}^{\infty} \sum_{x_{3} = 0}^{\infty}\sum_{x_{4} = 1}^{\infty} \sum_{x_{5} = 1}^{\infty}\sum_{x_{6} = 1}^{\infty} \bracks{\sum_{k = 1}^{6}x_{k} = n} \right\vert_{\ x_{1},x_{2},x_{3}\ \mrm{even} \atop x_{4},x_{5},x_{6}\ \mrm{odd}} \\[5mm] = &\ \left.\sum_{x_{1} = 0}^{\infty}\sum_{x_{2} = 0}^{\infty} \sum_{x_{3} = 0}^{\infty}\sum_{x_{4} = 1}^{\infty} \sum_{x_{5} = 1}^{\infty}\sum_{x_{6} = 1}^{\infty} \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n + 1 - \sum_{k = 1}^{6}x_{k}}}\, {\dd z \over 2\pi\ic} \right\vert_{\ x_{1},x_{2},x_{3}\ \mrm{even} \atop x_{4},x_{5},x_{6}\ \mrm{odd}} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n + 1}}\, \pars{\sum_{x = 0}^{\infty}z^{2x}}^{3}\pars{\sum_{y = 0}^{\infty}z^{2y + 1}}^{3} {\dd z \over 2\pi\ic} = \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n + 1}}\, \pars{1 \over 1 - z^{2}}^{3}\pars{z \over 1 - z^{2}}^{3} {\dd z \over 2\pi\ic} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n - 2}\pars{1 - z^{2}}^{6}}\, {\dd z \over 2\pi\ic} = \sum_{k = 0}^{\infty}{-6 \choose k}\pars{-1}^{k} \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n - 2k - 2}}\, {\dd z \over 2\pi\ic} \\[5mm] = &\ \sum_{k = 0}^{\infty}{k + 5 \choose 5} \bracks{n - 2k - 2 = 1} =\ \bbox[15px,#ffe,border:1px dotted navy]{\ds{% \left\{\begin{array}{lcl} \ds{0} & \mbox{if} & \ds{n}\ \mbox{is}\ even \\[2mm] \ds{\bracks{n + 7}/2 \choose 5} & \mbox{if} & \ds{n}\ \mbox{is}\ odd \end{array}\right.}} \end{align}

$\ds{\large\mathbf{\left. b\right)}}$ is quite similar to $\ds{\large\mathbf{\left. a\right)}}$.

\begin{align} &\oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n + 1}} \pars{\sum_{x = 0}^{12}z^{x}}^{5}\,{\dd z \over 2\pi\ic} = \oint_{\verts{z}\ =\ 1^{-}}{\pars{1 - z^{13}}^{5} \over z^{n + 1}\pars{1 - z}^{5}} \,{\dd z \over 2\pi\ic} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n + 1}} \sum_{k = 0}^{\infty}{k + 4 \choose 4}x^{k}\sum_{\ell = 0}^{5} {5 \choose \ell}\pars{-1}^{\ell}x^{13\ell}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \sum_{\ell = 0}^{5}{5 \choose \ell}\pars{-1}^{\ell}\sum_{k = 0}^{\infty} {k + 4 \choose 4}\bracks{k + 13\ell = n} = \sum_{\ell = 0}^{5}{5 \choose \ell}\pars{-1}^{\ell} {n - 13\ell + 4 \choose 4}\bracks{\ell \leq {n \over 13}} \\[5mm] = &\ \color{#f00}{% \sum_{\ell = 0}^{\left\lfloor n/13\right\rfloor}\pars{-1}^{\ell}{5 \choose \ell}{n - 13\ell + 4 \choose 4}} \\[5mm] = &\ \left\{\begin{array}{ll} \ds{n + 4 \choose 4} & \mbox{if} & \ds{0 \leq n \leq 12} \\[3mm] \ds{{n + 4 \choose 4} - 5{n - 9 \choose 4}} & \mbox{if} & \ds{13 \leq n \leq 25} \\[3mm] \ds{{n + 4 \choose 4} - 5{n - 9 \choose 4} + 10{n - 22 \choose 4}} & \mbox{if} & \ds{26 \leq n \leq 38} \\[3mm] \ds{{n + 4 \choose 4} - 5{n - 9 \choose 4} + 10{n - 22 \choose 4} - 10{n - 35 \choose 4}} & \mbox{if} & \ds{39 \leq n \leq 51} \\[3mm] \ds{{n + 4 \choose 4} - 5{n - 9 \choose 4} + 10{n - 22 \choose 4} - 10{n - 35 \choose 4} + 5{n - 48 \choose 4}} & \mbox{if} & \ds{52 \leq n \leq 60} \\[3mm] \ds{0} & \mbox{if} & \ds{n > 60} \end{array}\right. \end{align}

Answer 3

Here is a slightly different approach.

Ad Problem (a):

• Since even $x_j, 1\leq j\leq 3$ may have values $0,2,4,\ldots$ we encode candidates for even $x_j$ via $t^0+t^2+t^4+\cdots$

• Since odd $x_j, 4\leq j\leq 6$ may have values $1,3,5,\ldots$ we encode candidates for odd $x_j$ via $t^1+t^3+t^5+\cdots$

  The contribution of even $x_1,x_2,x_3$ is \begin{align*} (1+t^2+t^4+\cdots)^3=\frac{1}{\left(1-t^2\right)^3} \end{align*}

  The contribution of odd $x_4,x_5,x_6$is \begin{align*} (t^1+t^3+t^5+\cdots)^3=t^3(1+t^2+t^4+\cdots)^3=\frac{t^3}{\left(1-t^2\right)^3} \end{align*}

  Here we apply the geometric series expansion.

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

We conclude: A generating function $A(t)$ providing with $[t^n]A(t)$ the number of wanted solutions is \begin{align*} A(t)=\frac{t^3}{\left(1-t^2\right)^6} \end{align*}

$$ $$

Ad Problem (b):

• Since $x_j,1\leq j\leq 5$ may have values $0\leq x_j\leq 12$ we encode the contribution of $x_j$ via $t^0+t^1+t^2+\cdots+t^{12}$.

So, the contribution of each $x_j$ can be encoded as \begin{align*} 1+t^1+t^2+\cdots+t^{12}=\frac{1-t^{13}}{1-t} \end{align*}

Here we apply the formula for the finite geometric series.

We conclude: A generating function $B(t)$ providing with $[t^n]B(t)$ the number of wanted solutions is \begin{align*} B(t)=\left(\frac{1-t^{13}}{1-t}\right)^5 \end{align*}

Hint: If additionally the number of solutions, i.e. the coefficient of the generating functions $A(t)$, resp. $B(t)$ is to extract, it is again convenient to apply the coefficient of operator as well as the Iverson bracket.