0
$\begingroup$

Problem. A sequence of characters is comprised of characters from among $\{A,B,C,D\}$, and has length $n \geq 18$. How many sequences contain exactly $10$ A's, $5$ B's, and $3$ C's?


I'm not quite sure how to approach this, however here's where I am thus far.

The characters are indistinguishable, however the order of the sequence matters. Start with the A's... we have $n$ possible choices for the position of each $A$, so $_{n}C_{10}$ possible ways to insert the A's.

Now, for the B's. We now have $n-10$ possible choices for the position of each $B$, so there are $_{n-10}C_5$ possible ways to insert the B's.

Similarly for the C's, giving us $_nC_{10} \cdot _{n-10}C_5 \cdot _{n - 15}C_3$ possible sequences.


Is this a correct way to approach the problem?

$\endgroup$
2
  • $\begingroup$ @lulu Apologies. The set of characters includes $D$ as well. The string may have length greater than $18$. $\endgroup$
    – 10GeV
    Commented Sep 17, 2021 at 21:38
  • 3
    $\begingroup$ In that case, your approach looks good. $\endgroup$
    – lulu
    Commented Sep 17, 2021 at 21:39

1 Answer 1

1
$\begingroup$

Use the Tao of BOOKKEEPER: If you have a total of $n$ symbols, $k_1$ of type 1, $k_2$ of type 2, ..., $k_m$ of type $m$ (here $k_1 + k_2 + \dotsb + k_m = n$), the total number of strings made up of them is the multinomial coefficient:

$\begin{align*} \binom{n}{k_1, k_2, \dotsc, k_m} &= \frac{n!}{k_1! k_2! \dotsm k_m!} \end{align*}$

(If they are all different, you have $n!$ possible strings, each time you make $k_i$ symbols undistinguishable you are taking away a factor of $k_i!$ possibilities.)

$\endgroup$

You must log in to answer this question.

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