Question: How many ways are there to form a sequence of 10 letters from four 'a's, four 'b's, four 'c's, and four 'd's if each letter must appear at least twice?
My Approach: I started out with the exponential generating function where:
- XA represents the number of 'A's,
- XB represents the number of 'B's,
- XC represents the number of 'C's,
- XD represents the number of 'D's,
and $XA + XB + XC + XD = 10$.
Here, $A(XA) = \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!}$, and
$A(X) = (A(XA))^4$.
My Problem: I am unable to solve or reduce it to a standard formula of $e^x$ from which I can easily calculate the coefficient of $ x^{10} $. Can I do it directly using permutation with limited repetition?
Best Answer
The original poster wanted a solution with generating functions. So here is my take on that:
I would use ordinary generating function instead of exponential one but still write:
$ A= \frac{x^{4}}{24} + \frac{x^{3}}{6} + \frac{x^{2}}{2} $
Where the motivation is: Since all the As are indistinguishable we have to divide by the number of permutations within those As. If e.g. $x³$ is choosen divide by 6.
The above kind of looks like an exponential generating function but the divisions are just to account for removing the permutation within the As.
$10! \cdot A^4 = \frac{175 x^{16}}{16} + 175 x^{15} + \ldots + 109200 x^{11} + 226800 x^{10} + 302400 x^{9} + 226800 x^{8}$
Where you can read off the solution at coefficient $x^{10}$
The original poster asked on how to find this. In the end generating functions only transform one combinatorial problem into another. The nice thing is that with that the one expressed in terms of generating functions can be handed of the a CAS system (I used sympy here).
Update The above is a bit of a hack as the multiplication by $10!$ only makes it correct for the 10 digit case. If the the function is indeed seen as an exponential generating functions we can read of all digits
$ \frac{x^{16}}{331776} + \frac{x^{15}}{20736} + \frac{x^{14}}{2304} + \frac{13 x^{13}}{5184} + \frac{107 x^{12}}{10368} + \frac{13 x^{11}}{432} + \frac{x^{10}}{16} + \frac{x^{9}}{12} + \frac{x^{8}}{16} $
Or:
$ A^4=63063000 \frac{x^{16}}{16!} + 63063000 \frac{x^{15}}{15!} + 37837800 \frac{x^{14}}{14!} + 15615600 \frac{x^{13}}{13!} + 4943400 \frac{x^{12}}{12!} + 1201200 \frac{x^{11}}{11!} + 226800 \frac{x^{10}}{10!} + 30240 \frac{x^{9}}{9!} + 2520 \frac{x^{8}}{8!} $