2

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

Iaka Noe
  • 29
  • @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. – Iaka Noe May 14 '18 at 12:09
  • Should $M$ be 2 because you only have 2 characters? – green frog May 14 '18 at 12:30
  • @伽罗瓦 yeah I'm sorry, I'll edit that away – Iaka Noe May 14 '18 at 13:11
  • 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. – green frog May 14 '18 at 13:14
  • @伽罗瓦 but what about $M>2$ – Iaka Noe May 14 '18 at 13:14
  • You should be able to apply the same idea. Try $M = 3$ with this in mind. – green frog May 14 '18 at 13:15
  • @伽罗瓦 is the edit right?? – Iaka Noe May 14 '18 at 13:33
  • Yea it seems correct! – green frog May 14 '18 at 13:33
  • @伽罗瓦 how can I make a general formula for this (so as I can post it)? It's like two iterations into one another. – Iaka Noe May 14 '18 at 13:36
  • Try expanding out each term in the product. 10 choose 2 is really $\frac{10!}{2!8!}$. – green frog May 14 '18 at 13:38

1 Answers1

1

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.

John
  • 26,319