I had 2 questions about using the inclusion-exclusion method to solve arrangements:
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"?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?
-
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}$
-
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!
Best Answer
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.