Calculating amount of possible combinations

274 Views Asked by At

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

1

There are 1 best solutions below

1
On BEST ANSWER

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.