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?
Could you explain what does $$$1+x+x^2+x^3$$$, or generating function for each letter, mean?
Since the problem states that the words can be upto 3 letters long with letters being A, B, C, D or E. For example, for A the generating function (1+x+x^2+x^3) means we can take 0 letters of A or 1 letter of A or 2 letters of A or 3 letters of A. Similarly for other letters as well. Since the final output words contains A or B or C or D or E, i am multiplying the generating functions of all letters and finall adding the coefficients c0, c1, c2, c3.
OK, I've got it. As a hint, you can consider the strings 'AB' and 'BA' because they are regarded as the same string in the first approach but they are actually not.