Find the coefficient of $x^{25}$ in $(1+x^3+x^8)^{10}$ using ordinary generating functions?
Could someone help me figure out this problem using generating functions? My initial thought was to using a substituting variable (like $y=x^3$ and substituting accordingly), but I couldn't find a variable that would work. I would really appreciate some help! A detailed answer is always great! Thanks in advance!
On
$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\dd}{{\rm d}}% \newcommand{\isdiv}{{\,\left.\right\vert\,}}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\ic}{{\rm i}}% \newcommand{\imp}{\Longrightarrow}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert #1 \right\vert}% \newcommand{\yy}{\Longleftrightarrow}$
\begin{align} \pars{1 + x^{3} + x^{8}}^{10} &= \sum_{\ell = 0}^{10}{10 \choose \ell}\pars{x^{3} + x^{8}}^{\ell} =\sum_{\ell = 0}^{10}{10 \choose \ell}x^{3\ell}\sum_{\ell' = 0}^{\ell}{\ell \choose \ell'}x^{5\ell'}\sum_{n = 0}^{80}\delta_{n,3\ell + 5\ell'} \end{align}
$$ \pars{1 + x^{3} + x^{8}}^{10}= \sum_{n = 0}^{80}a_{n}x^{n} $$ where $$ a_{n} = \sum_{\ell = 0}^{10}{10 \choose \ell} \sum_{\ell' = 0}^{\ell}{\ell \choose \ell'}\delta_{5\ell',n - 3\ell} = \sum_{\ell = 0 \atop {\vphantom{\Huge A}0\ \leq\ {n - 3\ell \over 5}\ \leq\ \ell}}^{10} {10 \choose \ell}{\ell \choose {n - 3\ell \over 5}} \quad\mbox{and}\quad 5 \isdiv \pars{n - 3\ell} $$
$$ \color{#ff0000}{% a_{n} = \left\lbrace% \begin{array}{lcl} \quad\sum_{\ell = 0 \atop {\vphantom{\Huge A}{n \over 8}\ \leq\ \ell\ \leq\ {n \over 3}}}^{10} {10 \choose \ell}{\ell \choose {n - 3\ell \over 5}} \quad\mbox{and}\quad 5 \isdiv \pars{n - 3\ell}\,, & \color{#0000ff}{\mbox{if}} & 0 \leq n \leq 80 \\[3mm] \quad 0\,, && \mbox{otherwise} \end{array}\right.} $$
\begin{align} a_{25} &= \sum_{\ell = 0 \atop {\vphantom{\Huge A}{25 \over 8}\ \leq\ \ell\ \leq\ {25 \over 3}}}^{10} {10 \choose \ell}{\ell \choose {25 - 3\ell \over 5}} \quad\mbox{and}\quad 5 \isdiv \pars{25 - 3\ell} \\[3mm]&= \sum_{\ell = 4}^{8} {10 \choose \ell}{\ell \choose {25 - 3\ell \over 5}} \quad\mbox{and}\quad 5 \isdiv \pars{25 - 3\ell} \\[3mm]&= {10 \choose 5}{5 \choose {25 - 3\times 5 \over 5}} = {10 \choose 5}{5 \choose 2} = {10! \over 5!\,5!}\,{5! \over 2!\,3!} = {10 \times 9 \times 8 \times 7 \times 6 \over 1}\,{1 \over 2 \times 3 \times 2} \end{align}
$$ \color{#0000ff}{\large a_{25} = 2520} $$
I don't know how to use generating functions for this. You are looking for compositions of $25$ with up to $10$ parts of $8$ and $3$. You can use $25=8+8+3+3+3$, which is the only one. So now you want a series of $10$ items, with $5\ \ 0$'s, $3\ \ 3$'s, and $2\ \ 8$'s. How many is that?