4
$\begingroup$

I had 2 questions about using the inclusion-exclusion method to solve arrangements:

  1. How many arrangements of the 26 different letters are there that

    a) Contain either the sequence "the" or the sequence "aid"
    b) Contain neither the sequence "the" or the sequence "math"?

  2. How many ways are there to arrange the letters in the word MISSISSIPPI so that either all the Is are consecutive or all the Ss are consecutive or all the Ps are consecutive

This is my guesses on the two questions, would someone be able to check my work on this and see if I'm right?

  1. a) There are 26 letters of the alphabet, therefore there are $26!$ possible arrangements that can be made. Thus $N(U)$ (which is the number of elements in the universe) is $26!$. By the same token, the number of sequences containing the word "the" ($N(A_{the}))$ is $23!$ because out of the 26 letters, you have taken out 3. Thus leaving a total of 23 letters to arrange. Also, $N(A_{aid})$ is $23!$ because again 3 letters of the 26 letter of the alphabet have been moved and already arranged. Therefore, when talking about the number of arrangements that contain either "the" or "aid" we have $N(A_{the} U A_{aid})$ = $N(A_{the}) + N(A_{aid}) - N(A_{the} intersect A_{aid})$ = $(23!) + (23!) -(20!) = 5.17*10^{22}$

    b) The universe, as said earlier is $26!$. In addition, $N(A_{the}) = 23!$ and $N(A_{math}) = 22!$. Therefore, the arrangement of the 6 letters in the 26 letter alphabet ($N(A_{the} U A_{math})$) is $20!$. Also, because In this particular context, we are trying to find $N(Not(A_{the}) intersect Not(A_{math})) = N -N(A_{the}) - N(A_{math}) + N(A_{the} U A_{math})$ which comes out to be $(26!) - (23!) - (22!) + (20!) = 4.03*10^{26}$

  2. The universe, or the arrangment of the 11 letters comes out to be $11!$. Therefore The arrangment of I's ($N(A_I)$) = $7!$, the arrangement of P's ($N(A_P)$) = $9!$ and the arrangment of S's ($N(A_S)$) = $7!$. Therefore $N(A_I U A_P U A_S) = N(A_I) + N(A_P) + N(A_S) - N(A_I intersect A_P) - N(A_I intersect A_S) - N(A_P intersect A_S) + N(A_I U A_P U A_S) = (7!) + (9!) + (7!) - (5!)-(3!)-(5!) + (1) = 372715$

Is my work or thought process correct? Thanks in advance for your help, it's greatly appreciated!

$\endgroup$
  • $\begingroup$ P.S. I wasn't sure how to do the intersect or "not" symbol - I apologize for any formatting issues. Thanks again for your help! $\endgroup$ – Billy Thorton Nov 26 '13 at 16:59
2
$\begingroup$

1a) The reasoning in the first part is right, though not all details are. Let $A$ be the set of sequences that include "the" and $B$ the set of sequences that include "aid." Then $$|A\cup B|=|A|+|B|-|A\cap B|.$$ For $|A|$, think of "the" as a superletter. Then we have $23$ ordinary letters and a superletter. They can be arranged in $24!$ ways.

A similar calculation deals with $|B|$ and $|A\cap B|$.

1b) We count the number of elements in the complement (either "the" or "math" or both), and subtract from the $26!$ permutations of the alphabet.

Let $P$ be the set of permutations that contain "the," and $Q$ the set of permutations that contain "math." By the reasoning of 1a), $|P|=24!$ and $|Q|=23!$. For $|P\cap Q|$, we need to have the sequence "mathe." There are $22!$ of these.

2) This is left to you for now. Your general strategy was basically OK. But note that for example the total number of permutations of our big word is not $11!$. That would be correct if the letters were all different. However, they are not, so we must divide by $4!4!2!$.

Alternately, there are $\binom{11}{4}$ ways to decide where the I's will go, and for each there are $\binom{7}{4}$ ways to decide where the S's will go, and for each there are $\binom{3}{2}$ ways to decide where the P's will go.

Similar considerations apply to the counting of sequences with restrictions.

You can if you wish colour the letters to make them all distinct, count, and then divide by $4!4!2!$ to deal with the fact they are not all distinct.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Wouldn't using the letters in words like "the" and "aid" remove those specific letters ('t', 'h','e' etc.) from arrangement? I'm not sure I understand why $24!$ ways over the way I had? $\endgroup$ – Billy Thorton Nov 26 '13 at 23:36
  • $\begingroup$ Using (say) the sequence "the" indeed removes $3$ letters from the game, leaving sort of $23$. Except it is $24$. because the block "the" acts as a letter, it can be moved around. So there are $24!$ sequences that have "the." $\endgroup$ – André Nicolas Nov 27 '13 at 0:13
  • $\begingroup$ If you like, consider the mini-alphabet a, b, c, d and the arrangements of the letters that have the substring ab. By listing you can find there are $6=3!$ of them. $\endgroup$ – André Nicolas Nov 27 '13 at 0:16
  • $\begingroup$ Okay, I think that makes sense... And above you used the word "mathe"; is that the combination of "the" and "math"? $\endgroup$ – Billy Thorton Nov 27 '13 at 4:06
  • $\begingroup$ Yes, all words that contain mathe would be double counted, once under math and once under the, so we need to count them and subtract that count from the sum. $\endgroup$ – André Nicolas Nov 27 '13 at 5:18

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.