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 the 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 coffecients 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?