4
$\begingroup$

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?

$\endgroup$
1

5 Answers 5

4
$\begingroup$

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!} $

$\endgroup$
3
$\begingroup$

Can I do it directly using permutation with limited repetition?

Sure. Every letter has to appear twice. That means $8$ out of the $10$ positions are already occupied and we have only $2$ positions left to fill. These $2$ positions can be filled using the same letter or two different letters. Let's consider these cases separately.

Case 1: Same letter

If we fill the two remaining places using the same letter, we can choose any of the four letters to fill with. And for every letter we choose, the number of permutations would be

$$\frac{10!}{2! \cdot 2! \cdot 2! \cdot 4!}$$

[There will be three letters repeated two times each and one letter repeated four times.]

So the total number of permutations for this case equals

$$\frac{4 \cdot 10!}{2! \cdot 2! \cdot 2! \cdot 4!}$$

Case 2: Different letters

We can pick two letters out of the four in ${4 \choose 2} = 6$ ways. And for every combination we choose, the number of permutations of the $10$ letters would be

$$\frac{10!}{2! \cdot 2! \cdot 3! \cdot 3!}$$

[There will be two letters repeated two times each and two repeated three times each.]

So the total number of permutations for this case equals

$$\frac{6 \cdot 10!}{2! \cdot 2! \cdot 3! \cdot 3!}$$

Adding the total number for the two cases, we get the required number

$$\frac{4 \cdot 10!}{2! \cdot 2! \cdot 2! \cdot 4!} + \frac{6 \cdot 10!}{2! \cdot 2! \cdot 3! \cdot 3!} = 226800$$

$\endgroup$
6
  • $\begingroup$ Interestingly we used the same method but arrived at a different number of possibilities for different letters; There are 6 possibilities, but a factor of 4 different ways of getting to it. $\endgroup$
    – yolo
    Feb 25 at 13:07
  • $\begingroup$ I don't see how you got $24$. the number of ways of choosing $2$ out of $4$ letters is $6$. Am I missing something? $\endgroup$
    – Haris
    Feb 25 at 13:09
  • $\begingroup$ We have 2 of each letter remaining. Probabilistically that makes no difference but I think it does combinatorially $\endgroup$
    – yolo
    Feb 25 at 13:10
  • 1
    $\begingroup$ @yolo You aren't choosing two from the set of 8 remaining letters, you are choosing two types of letters from the four types available. $\endgroup$ Feb 25 at 13:18
  • 1
    $\begingroup$ ah I see; thanks for the clarification $\endgroup$
    – yolo
    Feb 25 at 15:42
2
$\begingroup$

You can do it with basic combinatorial methods:

What you have are the letters aabbccdd?? with ?? representing wild card letters. There are $\frac{8!}{2!2!2!2!}$. There are 4 possibilities where the two ?? are the same, and $6$ where they are different. There are $\frac{10!}{2!2!4!2!}$ in the first case and $\frac{10!}{2!2!3!3!}$ in the second. Combining the possibilities we have $4\times \frac{10!}{2!2!4!2!}+6\times \frac{10!}{2!2!3!3!}$ which evaluates to 226800

$\endgroup$
1
$\begingroup$

Since two different answers have been posted, here is a mechanical way of computing as the product of two multinomial coefficients, viz.

$\mathtt{(Lay\;Down\;Pattern)\times(Permute\; pattern)}$

$ = \dbinom{10}{4,2,2,2}\dbinom{4}{1,3} + \dbinom{10}{3,3,2,2}\dbinom{4}{2,2} = 226800$

$\endgroup$
0
$\begingroup$

The exponential generating function for the number of acceptable sequences of length $r$ is $$f(x) = \left( \frac{1}{2!}x^2 + \frac{1}{3!}x^3 + \frac{1}{4!}x^4 \right)^4$$

Expand $f(x)$ by polynomial multiplication, with result $$f(x) = \frac{x^8}{16}+\frac{x^9}{12}+\frac{x^{10}}{16}+\frac{13 x^{11}}{432}+\frac{107 x^{12}}{10368}+\frac{13 x^{13}}{5184}+\frac{x^{14}}{2304}+\frac{x^{15}}{20736}+\frac{ x^{16}}{331776}$$ So the number of acceptable strings of length $10$ is $$10! \cdot \frac{1}{16} = 226800$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .