• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q24E

Expert-verified Found in: Page 550 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # What is the generating function for $\left\{{a}_{k}\right\}$, where ${a}_{k}$ is the number of solutions of ${x}_{1}+{x}_{2}+{x}_{3}+{x}_{4}=k$ when ${x}_{1},{x}_{2},{x}_{3}$, and ${x}_{4}$are integers with ${x}_{1}\ge 3$, $1\le {x}_{2}\le 5,0\le {x}_{3}\le 4$, and ${x}_{4}\ge 1?$Use your answer to part (a) to find ${a}_{7}$.

(a)The total generating function is $\frac{{x}^{5}{\left(1+x+{x}^{2}+{x}^{3}+{x}^{4}\right)}^{2}}{{\left(1-x\right)}^{2}}$.

(b) ${a}_{7}=10$

See the step by step solution

## Step 1: Use Generating Function:

Generating function for the sequence ${{a}}_{{0}}{,}{{a}}_{{1}}{,}{\dots }{,}{{a}}_{{k}}{,}{\dots }$ of real numbers is the infinite series;

${G}{\left(}{x}{\right)}{=}{{a}}_{{0}}{+}{{a}}_{{1}}{x}{+}{{a}}_{{2}}{{x}}^{{2}}{+}{\dots }{+}{{a}}_{{k}}{{x}}^{{k}}{+}{\dots }{=}\sum _{k=0}^{+\infty }{{a}}_{{k}}{{x}}^{{k}}$

Extended binomial theorem;

role="math" localid="1668610635640" ${\left(1+x\right)}^{{u}}{=}\sum _{k=0}^{+\infty }\left(\begin{array}{c}u\\ k\end{array}\right){{x}}^{{k}}$

Since ${x}_{1}\ge 3$ the series representing ${x}_{1}$ should then contain only terms with a power of at least 3:

${x}^{3}+{x}^{4}+{x}^{5}+\dots$

Since $1\le {x}_{2}\le 5$ the series representing ${x}_{2}$ should then contain only terms with a power of at least 1 and at most 5:

$x+{x}^{2}+{x}^{3}+{x}^{4}+{x}^{5}$

Since $0\le {x}_{3}\le 4$ the series representing ${x}_{3}$ should then contain only terms with a power of at least 0 and at most 4

$1+x+{x}^{2}+{x}^{3}+{x}^{4}$

Since ${x}_{4}\ge 1$ the series representing ${x}_{4}$should then contain only terms with a power of at least 1:

$x+{x}^{2}+{x}^{3}+\dots$

## Step 2: The generating function is the product of the series for each variable:

$\left(1+x+{x}^{2}+{x}^{3}+{x}^{4}\right)\left(x+{x}^{2}+{x}^{3}+{x}^{4}+{x}^{5}\right)\left({x}^{3}+{x}^{4}+{x}^{5}+\dots \right)\phantom{\rule{0ex}{0ex}}=x{\left(1+x+{x}^{2}+{x}^{3}+{x}^{4}\right)}^{2}\left({x}^{3}\right)\left(x\right){\left(1+x+{x}^{2}+\dots \right)}^{2}\phantom{\rule{0ex}{0ex}}={x}^{5}{\left(1+x+{x}^{2}+{x}^{3}+{x}^{4}\right)}^{2}{\left(1+x+{x}^{2}+\dots \right)}^{2}\phantom{\rule{0ex}{0ex}}={x}^{5}{\left(1+x+{x}^{2}+{x}^{3}+{x}^{4}\right)}^{2}{\left(\sum _{k=0}^{+\infty }{x}^{k}\right)}^{2}\phantom{\rule{0ex}{0ex}}={x}^{5}{\left(1+x+{x}^{2}+{x}^{3}+{x}^{4}\right)}^{2}·{\left(\frac{1}{1-x}\right)}^{2}\phantom{\rule{0ex}{0ex}}=\frac{{x}^{5}{\left(1+x+{x}^{2}+{x}^{3}+{x}^{4}\right)}^{2}}{{\left(1-x\right)}^{2}}$

b).

## Step 3: Use Extended binomial theorem:

$\frac{{x}^{5}{\left(1+x+{x}^{2}+{x}^{3}+{x}^{4}\right)}^{2}}{{\left(1-x\right)}^{2}}={x}^{5}·{\left(\sum _{k=0}^{4}{x}^{k}\right)}^{2}·\frac{1}{{\left(1-x\right)}^{2}}\phantom{\rule{0ex}{0ex}}={x}^{5}·{\left(\frac{1-{x}^{5}}{1-x}\right)}^{2}·\frac{1}{{\left(1-x\right)}^{2}}\phantom{\rule{0ex}{0ex}}={x}^{5}·\frac{{\left(1-{x}^{5}\right)}^{2}}{{\left(1-x\right)}^{4}}\phantom{\rule{0ex}{0ex}}={x}^{5}·{\left(1+\left(-{x}^{5}\right)\right)}^{2}·\left(1+\left(-x\right){\right)}^{-4}$

By further simplification:

localid="1668668833805" $\frac{{x}^{5}{\left(1+x+{x}^{2}+{x}^{3}+{x}^{4}\right)}^{2}}{{\left(1-x\right)}^{2}}={x}^{5}·\sum _{m=0}^{\phantom{\rule{0ex}{0ex}}+\infty }\left(\begin{array}{c}2\\ m\end{array}\right){\left(-{x}^{5}\right)}^{m}.\sum _{k=0}^{\phantom{\rule{0ex}{0ex}}+\infty }\left(\begin{array}{c}-4\\ k\end{array}\right){\left(-x\right)}^{k}\phantom{\rule{0ex}{0ex}}={x}^{5}·\sum _{m=0}^{\phantom{\rule{0ex}{0ex}}+\infty }\left(\begin{array}{c}2\\ m\end{array}\right){\left(-1\right)}^{m}{x}^{5m}.\sum _{k=0}^{\phantom{\rule{0ex}{0ex}}+\infty }\left(\begin{array}{c}-4\\ k\end{array}\right){\left(-1\right)}^{k}{x}^{k}\phantom{\rule{0ex}{0ex}}={x}^{5}·\sum _{m=0}^{+\infty }{b}_{m}{x}^{5m}·\sum _{k=0}^{+\infty }{c}_{k}{x}^{k}$

Let localid="1668611635844" ${b}_{m}=\left(\begin{array}{c}2\\ m\end{array}\right)\left(-1{\right)}^{m}$ and ${c}_{k}=\left(\begin{array}{c}-4\\ k\end{array}\right)\left(-1{\right)}^{k}$

## Step 4: The coefficient of x7a7 if m=0 and k=2 :

The coefficient of ${x}^{7}$ is the sum of the coefficients for each possible combination of localid="1668612574555" $\mathrm{m}$ and $k$:

localid="1668612490312" ${a}_{7}={b}_{0}{c}_{2}\phantom{\rule{0ex}{0ex}}=\left(\begin{array}{c}2\\ 0\end{array}\right)\left(-1{\right)}^{0}\left(\begin{array}{c}-4\\ 2\end{array}\right)\left(-1{\right)}^{2}\phantom{\rule{0ex}{0ex}}=10$

Hence,${a}_{7}=10$. ### Want to see more solutions like these? 