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$
  • $\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 '18 at 12:09
  • $\begingroup$ Should $M$ be 2 because you only have 2 characters? $\endgroup$ – green frog May 14 '18 at 12:30
  • $\begingroup$ @伽罗瓦 yeah I'm sorry, I'll edit that away $\endgroup$ – Iaka Noe May 14 '18 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 '18 at 13:14
  • $\begingroup$ @伽罗瓦 but what about $M>2$ $\endgroup$ – Iaka Noe May 14 '18 at 13:14
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$
  • $\begingroup$ Excellent! Thanks $\endgroup$ – Iaka Noe May 14 '18 at 13:42

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.