0
$\begingroup$

Suppose 15 characters are generated one by one, what is the probability we can rearrange the characters to spell MISSISSIPPI?

My answer was

$${15\choose 11}\times{11! \over 4!4!2!1!}\times{26^{-15}}.$$

Just wanted to clarify if this was correct. This is because we have the multinomial coefficient corresponding to the number of ordered sequences associated with the multi-set of MISSISSIPPI and 15C11 different ways of selecting where to place these letters.

$\endgroup$
4
  • $\begingroup$ I think it's more complicated than that. What if you have more than one $M$, or more than two $P$'s? (Also, your $26^{-15}$ should be $26^{15}$ I think.) $\endgroup$ – TonyK May 17 '19 at 11:26
  • $\begingroup$ Corrected. Ahh I didn't think about that case, thanks! $\endgroup$ – jodeg May 17 '19 at 11:27
  • $\begingroup$ Where did this problem come from? If you came up with it yourself, good for you for trying to practice and expand upon your own knowledge, but sometimes slight tweaks to well-known problem variants will cause massive headaches and make the problem many times more difficult. I rather doubt that this would have been a problem from a book or a teacher. $\endgroup$ – JMoravitz May 17 '19 at 12:21
  • $\begingroup$ @JMoravitz was myself, so yeah i see your point $\endgroup$ – jodeg May 17 '19 at 12:58
1
$\begingroup$

I would approach this problem via inclusion-exclusion based on the events:

  • $M$: we have strictly fewer than $1$ M selected

  • $I$: we have strictly fewer than $4$ I's selected

  • $S$: we have strictly fewer than $4$ S's selected

  • $P$: we have strictly fewer than $2$ P's selected

The probability of failure then is $Pr(M\cup I\cup S\cup P) = Pr(M)+Pr(I)+Pr(S)+Pr(P)-Pr(M\cap I)-Pr(M\cap S)-Pr(M\cap P)-Pr(I\cap S)-\dots+\dots-Pr(M\cap I\cap S\cap P)$

You should be able to calculate each of $Pr(M),Pr(M\cap I),Pr(M\cap I\cap S),\dots$ and complete the calculations that way, though this will be rather tedious to do as you will have to potentially use case-work on the exact number of I's and S's appearing, etc...

For example, $Pr(M\cap I)$ is the probability no M's and at most $3$ I's were used. Breaking into cases based on the number of I's used we have $Pr(M\cap I) = \binom{15}{0}\left(\frac{24}{26}\right)^{15} + \binom{15}{1}\left(\frac{1}{26}\right)\left(\frac{24}{26}\right)^{14}+\dots+\binom{15}{3}\left(\frac{1}{26}\right)^{3}\left(\frac{24}{26}\right)^{12}$

Doing it like this though, you might be breaking $M\cap I\cap S\cap P$ into $32$ events, which is incredibly tedious.

$\endgroup$
0
$\begingroup$

This was supposed to be a comment but it got too long.

You (at least) also need to count the remaining 4 unknown letters which are allowed to be whatever. $26^4$ without respect to placement.

Then as Tony says also if you among these four unknown get an extra $M$ then switching placement of this random $M$ with a prescribed $M$ counts as two cases but should only count as one.

Maybe it is easier to allow any other letter than $MSPI$, $(26-4)^4=22^4$ for a first estimate and then treat the Tony cases separately.

$\endgroup$
0
$\begingroup$

The probability you want is the probability that your $15$ randomly chosen letters contain at least $4$ Is, at least $4$ Ss, at least $2$ Ps, and at least one M—that is, $$ \sum_\limits{j_1=1}^{5}\sum_\limits{j_2=2}^{7-j_1}\sum_\limits{j_3=4}^{11-j_1-j_2}\,\sum_\limits{j_4=4}^{15-\sum_\limits{i=1}^3 j_i}\frac{22^{15-\sum_\limits{i=1}^4 j_i}}{26^{15}}{15\choose j_1\,j_2\, j_3\, j_4\,(15-\sum_\limits{i=1}^4 j_i)\,}\ . $$

$\endgroup$

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.