7
$\begingroup$

Is it possible to use exponential generating functions to solve problems where repetition is wanted?

For example, if I wanted to solve the following problem which wants distinct possibilities...

How many different 5-letter words can be formed from the letters from the word ABRACADABRA if duplicated letters are allowed but no letter can be used more times than it occurs in the word ABRACADABRA ?

5 distinct letters, A repeated five times, B twice, C once, D once, R twice.

Then, the function would be $$ F(x) = (1 + \frac {x}{1!} + \frac {x^2}{2!} + \frac {x^3}{3!} + \frac {x^4}{4!} + \frac {x^5}{5!}) (1 + \frac {x}{1!} + \frac {x^2}{2!})^2 (1 + \frac {x}{1!})^2 $$ $$ F(x) = \frac {x^{11}}{120} + \frac {3 x^{10}}{40} + \frac {2 x^9}{5} + \frac {19 x^8}{12}+ \frac{289 x^7}{60}+\frac{331 x^6}{30}+\frac{2221 x^5}{120}+\frac {545 x^4}{24} + \frac{121 x^3}{6}+\frac{25 x^2}{2}+5 x+1 $$

Therefore, the answer would be $5!(\frac {1271}{120})$

However, how would I be able to apply it to the following problem?

How many 5-card hands (from an ordinary deck) have at least one card of each suit?

4 suits, repeated 13 times

$ 52*51*50*49*48 = 311,875,200 $ total possibilities

$$ G(x) = (\frac {x^{13}}{13!} + \frac{x^{12}}{12!}+ \frac{x^{11}}{11!} + \frac{x^{10}}{10!} + \frac{x^9}{9!} + \frac{x^8}{8!} + \frac{x^7}{7!} + \frac{x^6}{6!} + \frac{x^5}{5!} + \frac{x^4}{4!} + \frac{x^3}{3!} + \frac{x^2}{2!} + \frac{x}{1!} + 1)^4 $$

Of course, this would just give me unique combinations, so it doesn't work. Is there an actual method to solve using exponential generating functions? Is it possible or even recommended?

$\endgroup$
3
$\begingroup$

"How many 5-card hands (from an ordinary deck) have at least one card of each suit?"

First, as a sanity check, a non-GF solution. There must be two cards of one suit and one each of the remaining three suits. There are 4 ways to choose the special suit, $\binom{13}{2}$ ways to choose its two cards, and 13 ways to choose the card from each of the remaining three suits. So the number of hands is $$4 \cdot \binom{13}{2} \cdot 13^3 = 685,464$$

Now let's try a solution using an ordinary power series generating function. Each suit can contribute 1 to 13 cards, and $n$ cards can be selected from a suit in $\binom{13}{n}$ ways, so the OPSGF is $$f(x) = \left[ \binom{13}{1}x + \binom{13}{2} x^2 + \binom{13}{3}x^3 + \dots + \binom{13}{13} x^{13} \right]^4$$ The coefficient of $x^n$ is the number of n-card hands. If all we are interested in is the coefficient of $x^5$, we can write $$f(x) = x^4 \left[ \binom{13}{1} + \binom{13}{2} x + O(x^2) \right]^4 = x^4 \left[ \binom{13}{1}^4 + \binom{4}{1} \binom{13}{1}^3 \binom{13}{2} x +O(x^2) \right]$$ so the coefficient of $x^5$ is $\binom{4}{1} \binom{13}{1}^3 \binom{13}{2}$, in agreement with our previous answer.

Now for the original question: the corresponding exponential generating function is $$g(x) = \left[ \binom{13}{1}x + \frac{1}{2!} 2! \binom{13}{2} x^2 + \frac{1}{3!} 3! \binom{13}{3}x^3 + \dots + \frac{1}{13!} 13! \binom{13}{13} x^{13} \right]^4$$ which is the same as our OPSGF, because now we are considering the order of the cards in the hand to be significant, and $n$ cards can be selected from 13 in $n! \binom{13}{n}$ ways taking order into account. The number of n-card hands, considering the order of the cards to be significant, is the coefficient of $\frac{1}{n!} x^n$. If you expand g(x) in the same way as we did for the OPSGF, the coefficient of $\frac{1}{5!} x^5$ is $5! \binom{4}{1} \binom{13}{1}^3 \binom{13}{2}$. But then if you do not want to consider the order of the cards to be significant, we have over-counted, and we must divide by 5! to compensate, leading us back to our original answer. The bottom line is that there is really not much difference between the two approaches, using an OPSGF or an EGF.

$\endgroup$
1
$\begingroup$

The generating function for the second problem will provide you with all possible 5-card hands. But we are interested in the case when we have at least one cord of each suit. So we need to make some restrictions. We already know the suit of 4 of the cards (because the conditon states they are different) and there are 4 options for the fifth card, so there are 4 different combinations if the cards were undistiguishable. But because they aren't, we need to multilply that number by the multinomial:

$$\binom{5}{2,1,1,1} = \frac{5!}{2!\cdot 1! \cdot 1! \cdot 1!} = 60$$

So the total number of combinations is:

$$60 \cdot 4 = 240 \text{ combinations}$$

This is actually the number of possible combinations with a pair of cards of the same suit. We can get the same exact result using the exponential generating function. Actually the exponential generating function is based on the same principle. You can read more about this here, especially on the $7^{th}$ page.

But before applying the exponential generating function, we need to limit the number of cards of one suit. From the condition we can obtain that the maximum number of cards per suit is 2 and the minimum number of cards per suit is 1. So the GF will be:

$$G(x) = \left(x + \frac {x^2}{2!}\right)^4 = x^4+2 x^5+\frac{3 x^6}{2}+\frac{x^7}{2}+\frac{x^8}{16}$$

The coefficient in fron to $x^5$ is 2. So the total number of combinations is:

$$2 \cdot 5! = 2 \cdot 120 = 240 \text{ combinations}$$

And we can see that we've obtained the same results using both methods. That's because, the exponetnial generating function is a more elegant, hidden and simplier version of the multinomial method.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.