2
$\begingroup$

(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)

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @nickpeterson...thanks but i cant find the soution $\endgroup$ – user293581 Oct 31 '16 at 4:21
0
$\begingroup$

$\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} enter image description here

$\endgroup$
  • $\begingroup$ ...Thanks lot nice slotuin $\endgroup$ – user293581 Oct 31 '16 at 4:39
  • $\begingroup$ @rajendra Thanks. $\endgroup$ – Felix Marin Oct 31 '16 at 6:01
  • $\begingroup$ @FelixMarin..its real nice explanation thanks very much..your rock $\endgroup$ – user271336 Oct 31 '16 at 14:14
  • $\begingroup$ @Psuresh Thanks. $\endgroup$ – Felix Marin Oct 31 '16 at 20:22
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy