I want to understand how I would go about solving counting problems like this

Use exponential generating functions to determine the number $a_n$ of ordered choices of $n$ balls such that there are 2 or 4 red balls, an even number of green balls, and an arbitrary number of blue balls

I understand how I would start solving this type of problem, getting a multiplication that starts like: $(\dfrac{x^2}{2!} + \dfrac{x^4}{4!})(\dfrac{1}{2}(e^x + e^{-x}))(e^x)$

corresponding to the red, green, blue balls respectively.

I am aware of an existing question asking precisely this. However the answer there does not make sense to me question is here. Precisely speaking, I cannot understand how the multiplication of the generating functions is expanded in the first expansion in the answer there. Also please note that I cannot comment in the answer to the original question there, since I am a beginner and my reputation doesn't allow me to do that :)

  • 1
    $\begingroup$ you can study from this book how to solve this kind of problems $\endgroup$
    – Masacroso
    Nov 26 '19 at 12:30

If I understand your question correctly, you want to see the intermediate steps to show that if $$f(x)={\left(\frac{x^2}{2!}+\frac{x^4}{4!}\right)}{\frac12\left(e^x+e^{-x}\right)}{e^x}$$ then $$f(x)=\frac12\cdot\frac{x^2}{2!} + \frac12\cdot\frac{x^4}{4!} + \sum_{n=2}^\infty \frac1{16}2^nn(n-1)\frac{x^n}{n!} + \\\sum_{n=4}^\infty\frac1{768}2^nn(n-1)(n-2)(n-3)\frac{x^n}{n!}. \tag{1}$$ OK, here goes: $$\begin{align} f(x)&={\left(\frac{x^2}{2!}+\frac{x^4}{4!}\right)}{\frac12\left(e^x+e^{-x}\right)}{e^x} \\ &={\left(\frac{x^2}{2!}+\frac{x^4}{4!}\right)} \frac{1}{2}(e^{2x}+1) \\ &=\frac{1}{2}{\left(\frac{x^2}{2!}+\frac{x^4}{4!}\right)} + \frac{1}{2}{\left(\frac{x^2}{2!}+\frac{x^4}{4!}\right)}e^{2x} \\ &=\frac{1}{2}{\left(\frac{x^2}{2!}+\frac{x^4}{4!}\right)} + \frac{1}{2}{\left(\frac{x^2}{2!}+\frac{x^4}{4!}\right)} \sum_{n=0}^{\infty} \frac{1}{n!} 2^n x^n \tag{2} \\ &=\frac{1}{2}{\left(\frac{x^2}{2!}+\frac{x^4}{4!}\right)} + \frac{1}{2} \cdot \frac{x^2}{2!} \sum_{n=0}^{\infty} \frac{1}{n!} 2^n x^n + \frac{1}{2} \cdot \frac{x^4}{4!} \sum_{n=0}^{\infty} \frac{1}{n!} 2^n x^n \\ &=\frac{1}{2} \cdot \frac{x^2}{2!}+\frac{1}{2} \cdot \frac{x^4}{4!} + g(x) + h(x) \tag{3} \end{align}$$ where for the sake of keeping our equations short we define $$g(x) = \frac{1}{2} \cdot \frac{x^2}{2!} \sum_{n=0}^{\infty} \frac{1}{n!} 2^n x^n$$ and $$h(x) = \frac{1}{2} \cdot \frac{x^4}{4!} \sum_{n=0}^{\infty} \frac{1}{n!} 2^n x^n$$ Then $$\begin{align} g(x) &= \frac{1}{2} \cdot \frac{x^2}{2!} \sum_{n=0}^{\infty} \frac{1}{n!} 2^n x^n \\ &= \frac{1}{4} \sum_{n=0}^{\infty} \frac{1}{n!} 2^n x^{n+2}\\ &= \frac{1}{4} \sum_{i=2}^{\infty} \frac{1}{(i-2)!} 2^{i-2} x^i \tag{4}\\ &= \frac{1}{4} \sum_{i=2}^{\infty} \frac{1}{(i-2)!} \cdot \frac{i(i-1)}{i(i-1)} \frac{2^i}{4} x^i\\ &= \frac{1}{16} \sum_{i=2}^{\infty} \frac{i(i-1)}{i!} 2^i x^i \tag{5} \end{align}$$ and $$\begin{align} h(x) &= \frac{1}{2} \cdot \frac{x^4}{4!} \sum_{n=0}^{\infty} \frac{1}{n!} 2^n x^n\\ &= \frac{1}{48} \sum_{n=0}^{\infty} \frac{1}{n!} 2^n x^{n+4}\\ &= \frac{1}{48} \sum_{j=4}^{\infty} \frac{1}{(j-4)!} 2^{j-4} x^j \tag{6}\\ &= \frac{1}{48} \sum_{j=4}^{\infty} \frac{1}{(j-4)!} \cdot \frac{j(j-1)(j-2)(j-3)}{j(j-1)(j-2)(j-3)} \frac{2^j}{16} x^j\\ &= \frac{1}{768} \sum_{j=4}^{\infty} \frac{j(j-1)(j-2)(j-3)}{j!} 2^j x^j \tag{7} \end{align}$$ Now substitute $(5)$ and $(7)$ into equation $(3)$, change $i$ and $j$ to $n$, and we have the desired result $(1)$.


  • $(2)$ by use of the infinite series for $e^x$
  • $(4)$ shifting the index in the summation by letting $i = n+2$
  • $(6)$ shifting the index in the summation by letting $j = n+4$
  • $\begingroup$ Thanks for the perfectly detailed answer. However, I have a further question. As per my calculations, I concluded that, the coefficient in front of $\dfrac{x^4}{4!}$ (after taking this term "out" of the summation) is $(12 + \dfrac{1}{2})$, whereas in the answer it is supposed to be 13. Have I made a mistake? Or is it meant to be rounded up like that? $\endgroup$
    – d1861323
    Nov 26 '19 at 22:04
  • $\begingroup$ That is, in the answer of the original question which I linked to @awkward $\endgroup$
    – d1861323
    Nov 26 '19 at 22:20
  • $\begingroup$ @d1861323 $13 x^4 / 4!$ is correct. The second term in equation $(3)$ contributes $1/2$ to the coefficient of $x^4/4!$, then $g(x)$ contributes $12$, then $h(x)$ contributes $1/2$, for a total of $13$. $\endgroup$
    – awkward
    Nov 27 '19 at 13:37

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.