Consider the letters {a, b, c, d}. How many 5-letter sequences containing an even number of b's and odd d's exist?
How to approach this problem using generating functions?
Anagrams with Generating Functions
combinationscombinatoricsdiscrete mathematicsgenerating-functions
Related Question
- [Math] Number of anagrams of ‘AABBCCDD’ that have no repeated letters.
- Generating function for the number of strings following a certain pattern.
- Generating Function Approach giving wrong combination count while normal brute force casework approach giving correct answer
- Combinatorics – Number of Ways to Form Sequence of 10 Letters with Constraints
Best Answer
Hint
A five letter word is given by partitioning $\{1,2,3,4,5\}$ into four parts, an $a$, $b$, $c$ and $d$ part, and filling the corresponding letter in the spaces in the part. This corresponds exactly to the action of multiplying exponential generating functions.
The EGF for the $a$ part is just $\sum_{n\ge 0}\frac{x^n}{n!}$, since there is exactly one way to fill $n$ given spots with $a$, for all $n\ge 0$. The same goes for the $c$ part. However, the EGF for the $b$ part is $\sum_{n\ge 0}\frac{x^{2n}}{(2n)!}=(e^x+e^{-x})/2$, since there is $1$ way to fill an even number of spots with $b$'s, and zero ways to fill and odd number of spots.
I leave you to find the EGF for the $c$ parts. Once you have all four EGF's, you need to multiply them all together, extract the coefficient of $x^5$, then multiply by $5!$.
Addendum: You should get that the number of sequences is $4^4$, and in general the number of $n$ letter sequences is $4^{n-1}$, for all $n\ge 1$. This is begging for a simple bijective proof; here is one. To choose a sequence of length $n$ with an even number of $b$'s and an odd number of $a$'s, choose the first $n-1$ symbols arbitrarily, then...
If there are an even number of $d$'s and an even number of $b$'s, make the last symbol $d$.
If there are an odd number of $d$'s and an odd number of $b$'s, make the last symbol $b$.
If there are an odd number of $d$'s and an even number of $b$'s, make the last symbol $a$.
If there are an even number of $d$'s and an odd number of $b$'s, make the last symbol $c$, and then replace all $d$'s with $b$'s and all $b$'s with $d'$s.