2
$\begingroup$

Having a string of length $N$ with $M$ different letters, and knowing how many times each letter appears on the string, how can one calculate the amount of possible strings?

For example:

  • $N=10$

  • $M=2$

  • Characters $=\{A, B\}$

  • Amounts: $A=\{6, 4\}$

Possibilities:

  • AAAAAABBBB

  • BBBBAAAAAA

  • ABABABABAA

  • ...

How can I calculate the amount of possibilities?

Edit, trying the answer provided in the comments

For these data:

  • $N=10$

  • $M=3$

  • Amounts $=\{2,5,3\}$

Would the solution be this one?

$$S={10\choose2}{8\choose5}{3\choose3}=45\times56\times1=2520$$

$\endgroup$
10
  • $\begingroup$ @Taroccoesbrocco My teacher told me to think it as an empty N-long string, and get the amount of possible places of the first character, then calculate the possibilities of the second character in the left places and so on. I think that would be multiplying the "choose" operator M times. But I don't really know its usage. $\endgroup$
    – Iaka Noe
    May 14, 2018 at 12:09
  • $\begingroup$ Should $M$ be 2 because you only have 2 characters? $\endgroup$
    – green frog
    May 14, 2018 at 12:30
  • $\begingroup$ @伽罗瓦 yeah I'm sorry, I'll edit that away $\endgroup$
    – Iaka Noe
    May 14, 2018 at 13:11
  • $\begingroup$ So in the case of $M = 2$ it is simple. Let us say you're trying to fill 10 holes with red or blue balls. You want 6 red and 4 blue. It suffices to count the number of ways to fill in 6 red in 10 holes. This is because the remaining spaces are automatically filled with blues. If you can see this, you can see that the answer should be 10 choose 6. $\endgroup$
    – green frog
    May 14, 2018 at 13:14
  • $\begingroup$ @伽罗瓦 but what about $M>2$ $\endgroup$
    – Iaka Noe
    May 14, 2018 at 13:14

1 Answer 1

1
$\begingroup$

It looks like your solution is good. You have the right idea.

Now, if we calculate a bit more:

$${10 \choose 2}{8 \choose 5}{3 \choose 3} = \frac{10!}{2!8!}\frac{8!}{5!3!}\frac{3!}{3!0!} = \frac{10!}{2!5!3!}.$$

This is called a multinomial. Note that the factorials in the denominator match the numbers of each kind of letter you need. This holds in general, for any number of characters.

$\endgroup$
1
  • $\begingroup$ Excellent! Thanks $\endgroup$
    – Iaka Noe
    May 14, 2018 at 13:42

You must log in to answer this question.

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