3
$\begingroup$

I know how to count permutations of, say, p red balls and q white balls and r blue balls. I also know how to count permutations of part of a set of distinct objects. But I don't know an efficient way to count partial permutations with repetition.

To illustrate what I mean: suppose I have a supply of eight As, seven Bs and six Cs, and want to know how many sequences of length 12 can be made from these. I can do it by adding up the permutations of 8 As and 4 Bs, 8 As and 3 Bs and one C, ... but that's tedious (this example has 45 cases). Is there a better way?

Finally, is there a procedure to generate the nth such sequence in lexicographic order, without cranking out all of them?

$\endgroup$
2
$\begingroup$

We can count the number of different sequences with the help of exponential generating functions.

Using the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series we can calculate the wanted number of sequences as

\begin{align*} 12!&[z^{12}](1+\frac{z}{1!}+\frac{z^2}{2!}+\cdots+\frac{z^8}{8!})(1+\frac{z}{1!}+\frac{z^2}{2!}+\cdots+\ \frac{z^7}{7!})\\ &\qquad\cdot(1+\frac{z}{1!}+\frac{z^2}{2!}+\cdots+\frac{z^6}{6!})\\ &=484110 \end{align*}

The calculation was done with the help of Wolfram Alpha.

Note: The result coincides with the calculation of @N.F.Taussig. We obtain \begin{align*} \binom{12}{8}2^4&+\binom{12}{7}2^5+\binom{12}{6}2^6+\binom{12}{5}\left(2^7-1\right)\\ &+\binom{12}{4}\left[2^8-2\binom{8}{8}-\binom{8}{7}\right]\\ &+\binom{12}{3}\left[2^9-2\binom{9}{9}-2\binom{9}{8}-\binom{9}{7}\right]\\ &+\binom{12}{2}\left[2^{10}-2\binom{10}{10}-2\binom{10}{9}-2\binom{10}{8}-\binom{10}{7}\right]\\ &+\binom{12}{1}\left[\binom{11}{5}+\binom{11}{6}+\binom{11}{7}\right]\\ &+\binom{12}{0}\left[\binom{12}{6}+\binom{12}{7}\right]\\ &=7920+25344+59136+100584+121770\\ &\qquad+100320+52272+15048+1716\\ &=484110 \end{align*}

$\endgroup$
  • $\begingroup$ Your answer is elegant and demonstrates the power of generating functions. $\endgroup$ – N. F. Taussig Jul 4 '17 at 0:01
  • $\begingroup$ @N.F.Taussig:Thanks! :-) $\endgroup$ – Markus Scheuer Jul 4 '17 at 6:17
1
$\begingroup$

I assume your $45$ cases result from solving the equation $$a + b + c = 12$$ in the nonnegative integers subject to the restrictions that $a \leq 8$, $b \leq 7$, and $c \leq 6$.

We can reduce the number of cases by considering the number of A's in the sequence.

  1. $8$ A's: There are $\binom{12}{8}$ ways to choose the positions of the A's. Since we have $7$ B's and $6$ C's, we are free to fill each of the remaining four positions in $2$ ways. Hence, there are $$\binom{12}{8}2^4$$ such sequences.
  2. $7$ A's: By similar reasoning, there are $$\binom{12}{7}2^5$$ such sequences.
  3. $6$ A's: By similar reasoning, there are $$\binom{12}{6}2^6$$ such sequences.
  4. $5$ A's: There are $\binom{12}{5}$ ways to choose the positions of the A's. If we had at least $7$ B's and $7$ C's, we could fill the remaining seven positions in $2^7$ ways. However, we cannot have a sequence with $7$ C's. Hence, there are $$\binom{12}{5}(2^7 - 1)$$ such sequences.
  5. $4$ A's: There are $\binom{12}{4}$ ways to choose the positions of the A's. We cannot have a sequence with eight B's, eight C's, or seven C's. Hence, there are $$\binom{12}{4}\left[2^8 - 2\binom{8}{8} - \binom{8}{7}\right]$$ such sequences.
  6. $3$ A's: There are $\binom{12}{3}$ ways to choose the positions of the A's. We cannot have a sequence with nine B's, nine C's, eight B's, eight C's, or 7 C's. Hence, there are $$\binom{12}{3}\left[2^9 - 2\binom{9}{9} - 2\binom{9}{8} - \binom{9}{7}\right]$$ such sequences.
  7. $2$ A's: There are $\binom{12}{2}$ ways to choose the positions of the A's. Since we cannot have more than seven B's or six C's, there are $$\binom{12}{2}\left[2^{10} - 2\binom{10}{10} - 2\binom{10}{9} - 2\binom{10}{8} - \binom{10}{7}\right]$$ such sequences. Alternatively, we note that since we can fill at most six of the remaining ten positions with C's, we must use at least $10 - 6 = 4$ B's. Since we can use at most seven B's, there are $$\binom{12}{2}\left[\binom{10}{4} + \binom{10}{5} + \binom{10}{6} + \binom{10}{7}\right]$$ such sequences.
  8. $1$ A: There are $12$ ways to choose the position of the A. Since we can fill at most six of the remaining eleven positions with C's, we must use at least $11 - 6 = 5$ B's. Since we can use at most seven B's, there are $$\binom{12}{1}\left[\binom{11}{5} + \binom{11}{6} + \binom{11}{7}\right]$$ such sequences.
  9. $0$ A's: Since we can fill at most six of the twelve positions with C's, we must use at least $12 - 6 = 6$ B's. Since we can use at most seven B's, there are $$\binom{12}{6} + \binom{12}{7}$$ such sequences.

Since the above cases are disjoint, the total number of sequences is found by adding the above results.

Since the problem lacks symmetry, determining the position of a sequence in the lexicographic ordering is tedious. That said, it makes sense to pivot on the number of A's at the beginning of the sequence. Consider a sequence such as AABACBBAABCA. Any sequence with more than two A's at the beginning of the sequence precedes it. Add those cases. Since the next two letters are BA, it is not possible to introduce any more sequences before this sequence until we reach the fifth letter. At this point, we have to count how many sequences begin AABAA given that we have $8 - 4 = 4$ A's, $7 - 1 = 6$ B's, and $6$ C's left and how may sequences begin AABAB given that we have $8 - 3 = 5$ A's, $7 - 2 = 5$ B's, and $6$ C's left. Once, we have done that, we have to add the number of sequences that begin $AABACA$ given that we have $8 - 4 = 4$ A's, $7 - 1 = 6$ B's, and $6 - 1 = 5$ C's left. Continue from there.

$\endgroup$
  • 1
    $\begingroup$ @MarkusScheuer Thank you for alerting me to the error. $\endgroup$ – N. F. Taussig Jul 3 '17 at 22:43
  • 1
    $\begingroup$ @MarkusScheuer Thanks again. I thought you were alerting me to a different error in the next line. $\endgroup$ – N. F. Taussig Jul 3 '17 at 22:53

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.