Finding the correct exponential generating function for word counting problem

72 Views Asked by At

Find the number of five-letter words that use an odd number of $A$s, at least two $B$s, and at most two $C$s.

The given answer: $65.$

I use the expression $(A + \frac{A^3}{3!})(\frac{B^2}{2!} + \frac{B^3}{3!} + \frac{B^4}{4!})(1 + C + \frac{C^2}{2!}).$ We can't have the term $\frac{A^5}{5!}$ because we must have the term $\frac{B^2}{2!}.$ Everything else looks ok to me, yet I can't derive $65$. Either I am not setting up the g.f. correctly or I am multiplying polynomials incorrectly. Is the g.f. above incorrectly set up? If so, how can I fix it?

1

There are 1 best solutions below

2
On BEST ANSWER

We are looking for \begin{align*} 120[z^5]\left(z+\frac{z^3}{3!}+\frac{z^5}{5!}\right)\left(\frac{z^2}{2!}+\frac{z^3}{3!}+\frac{z^4}{4!}+\frac{z^5}{5!}\right) \left(1+z+\frac{z^2}{2!}\right) \end{align*}

... can you figure out why?

As you correctly noted, the term $\frac{A^5}{5!}$ does not contribute to the result. So, we can simplify the left-most factor to $\left(z+\frac{z^3}{3!}\right)$.