ganesh_6's blog

Generating Function Approach gives wrong combination count while casework gives correct answer
By ganesh_6, history, 11 months ago, In English

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?

 
 
 
 
  • Vote: I like it
  • -9
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you explain what does $$$1+x+x^2+x^3$$$, or generating function for each letter, mean?

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        11 months ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        It is covered by the generating function approach right. See the Simple Exercises problem here: https://artofproblemsolving.com/wiki/index.php/Generating_function at the end of the page which is similar to this problem. The similar approach is followed by me.

        → Reply
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Now I get it, you are right. The Generating function approach does not take the order into account i.e; it calculates the combinations but not the permutation. So for calculating the permutations, it is not useful. Thanks! today i learned something.

        → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Exponential generating functions can be used to calculate the permutations: https://math.stackexchange.com/questions/4434822/generating-function-approach-giving-wrong-combination-count-while-normal-brute-f

→ Reply