I am solving a problem: How many words are less than four letters long and contain only the letters A, B, C, D, and E? Here, 'word' refers to any string of letters.
My Solution 1 uses Generating functions gives wrong answer
$(1+x+x^2+x^3)(1+x+x^2+x^3)(1+x+x^2+x^3)(1+x+x^2+x^3)(1+x+x^2+x^3)$
where $(1+x+x^2+x^3)$ is Generating function for each letter. This approach gave a wrong answer $(35+15+5+1)$ which is the sum of coefficients of $(x^3, x^2, x, 1)$ in $$x^{15} + 5 x^{14} + 15 x^{13} + 35 x^{12} + 65 x^{11} + 101 x^{10} + 135 x^9 + 155 x^8 + 155 x^7 + 135 x^6$$ $$+ 101 x^5 + 65 x^4 + 35 x^3 + 15 x^2 + 5 x + 1$$
Correct Approach using Case Work gives the correct answer
Case 1: The word is one letter long. Clearly, there are $5$ of these words.
Case 2: The word is two letters long. Constructing the set of these words, there are $5$ options for the first letter and $5$ options for the second letter, so there are $5^2 = 25$ of these words.
Case 3: The word is three letters long. By similar logic as above, we have $5$ options for the first letter, $5$ options for the second, and $5$ options for the third. Then there are $5^3 = 125$ of these letters.
Adding all our cases up, there are $5 + 25 + 125 = 155$ words that are less than four letters long and contain only the letters A, B, C, D, and E.
Could Someone help me in explaining why the Generating function approach failed here?
Best Answer
You will have to consider whether the e.g.f. (exponential generating function) approach is worth while here for such a short problem. However, the approach would stand you in good stead for more complex problems.
You will have to extract from the expansion of $(1+x+x^2/2!+x^3/3!)^5$,
(coefficient of $x$) + $2!$(coefficient of $x^2$) + $3!$(coefficient of $x^3$)
The factorials in the denominator of the exponential generating function effectively compensate the permutations for a letter occurring multiple times