1
$\begingroup$

Find the number of ways to arrange the letter in "FAMILY" for which F is before A or A is before M or M is before I.

("Before" means to be on the left, may not be adjacent.)

I still have no idea, please suggest.

$\endgroup$
  • 1
    $\begingroup$ Count all permutations, and then subtract the ones that have I M A F in exactly the backwards order. (For checking your work, there should be 30 of the latter). $\endgroup$ – Henning Makholm Mar 13 '17 at 11:47
  • $\begingroup$ Thank you. My answer is $6! - \binom{5+2-1}{2}\cdot2! = 720-30= 690$. $\endgroup$ – carat Mar 13 '17 at 15:53
3
$\begingroup$

Let Set $A$ be the set where $F$ is before $A$

Let Set $B$ be the set where $A$ is before $M$.

Let Set $C$ be the set where $M$ is before $I$

Suppose we have _$F$__$A$_. Then we have 4 other letters $(M,I,L,Y)$ to slot into the 3 boxes. We first treat the 4 letters as identical, and using distribution, we distribute the 4 letters into the 3 spaces. We have that ${4+3-1 \choose 4}=15$. However, we can arrange the letters $(M,I,L,Y)$ amongst themselves, which gives $4!$

Now, with similar argument, $|A|=|B|=|C|=15\times 4!=360$

Now we find $|A \cap B|$. This means $F$ is before $A$ is before $M$. Now it should look something like this;

_F_A_M_. Then we have 3 other letters $(I,L,Y)$ to slot into the 4 boxes. We first treat the 3 letters as identical, then apply distribution to the question. Then we will have ${3+4-1 \choose 3}=20$. However, we can arrange the letters $(I,L,Y)$ amongst themselves, which gives $3!$.

Now, with similar argument, $|A\cap B|=|B\cap C|=20 \times 3!=120$

But this is extremely different for $|A \cap C|$. Because it just states that $F$ is before $A$ and $M$ is before $I$. Hence, it does not mean _F_A_M_I. It can also mean _MF_A_I. (Which is also correct). So to deal with this question, we just arrange _F_A_ together, and we slot in the 4 remaining letters $(M,I,L,Y)$ and permute them later. But since $M$ must come before $I$, then there are only $\frac {4!}{2!}$ ways to arrange these letters.

Hence, $|A \cap C|={4+3-1 \choose 4}=15 \times \frac{4!}{2!} =180$

Now, finally, we find $|A \cap B \cap C|$, again, we can visualize it to be;

_F_A_M_I_. Now we only have 2 letters; $(L,Y)$ to slot into 5 spaces. We treat them as identical, and distribute them into 5 spaces. We have ${2+5-1 \choose 2}=15$ ways to slot the 2 letters. Next, we can arrange $(L,Y)$ among themselves, which gives $2!$.

Hence, $|A \cap B \cap C|=15 \times 2!=30$

By the Principle of Inclusion and Exclusion,

$|A \cup B \cup C| = 360 + 360 + 360 - 120 - 120 - 180 + 30 = 690$

I believe this is the answer you are looking for? Do let me know if I'm wrong or mis-read the question!

Therefore, this method of P-I-E is quite long but be careful if you are using this way.

$\endgroup$
  • $\begingroup$ Your explanation is very clear. Thank you all. $\endgroup$ – carat Mar 14 '17 at 13:35
3
$\begingroup$

Form the sets

$$A_{\text{fa}}=\text{set of arrangements with f preceding a}$$ $$A_{\text{am}}=\text{set of arrangements with a preceding m}$$ $$A_{\text{mi}}=\text{set of arrangements with m preceding i}$$

Then PIE says that, to count all elements belonging to these sets, you take the alternating sum

$$\begin{align}\text{desired count}\; =\; &|A_{\text{fa}}\cup A_{\text{am}}\cup A_{\text{mi}}|\\ =\; &\left(|A_{\text{fa}}|+|A_{\text{am}}|+|A_{\text{mi}}|\right)\\ &-\left(|A_{\text{fa}}\cap A_{\text{am}}| + |A_{\text{fa}}\cap A_{\text{mi}}|+|A_{\text{am}}\cap A_{\text{mi}}|\right)+|A_{\text{fa}}\cap A_{\text{am}}\cap A_{\text{mi}}|\end{align}$$

So what are the sizes of our sets and their intersections? Well our first is

$$|A_{\text{fa}}|=\frac{6!}{2!}$$

because we treat "f" and "a" as if they are identical (say "x") and then for every arrangement of the letters x,x,m,i,l,y we replace the "x"s with "f" and "i" in the left-to-right order that they appear. We can use a similar reasoning for the other sets

$$|A_{\text{fa}}|=|A_{\text{am}}|=|A_{\text{mi}}|=\frac{6!}{2!}$$

For the intersection $|A_{\text{fa}}\cap A_{\text{am}}|$ we can use a similar argument with 3 "x"s replacing "f","a" and "m" so that we count arrangements of x,x,x,i,l,y. We may argue similarly for the intersection $|A_{\text{am}}\cap A_{\text{mi}}|$

$$|A_{\text{fa}}\cap A_{\text{am}}|=|A_{\text{am}}\cap A_{\text{mi}}|=\frac{6!}{3!}$$

But in the case of $|A_{\text{fa}}\cap A_{\text{mi}}|$ we can replace "f" and "a" with "x"s and "m" and "i" with "z"s so that we arrange of x,x,z,z,l,y then for each arrangement the "x"s are replaced left-to-right with "f" and "a" and the "z"s are replaced left-to-right with "m" and "i", hence

$$|A_{\text{fa}}\cap A_{\text{mi}}|=\frac{6!}{2!^2}$$

Lastly $|A_{\text{fa}}\cap A_{\text{am}}\cap A_{\text{mi}}|$ can be determined by replacing "f","a","m" and "i" with "x"s so that we arrange the letters x,x,x,x,l,y and for each arrangement replace the "x"s left-to-right with f,a,m and i, hence

$$|A_{\text{fa}}\cap A_{\text{am}}\cap A_{\text{mi}}|=\frac{6!}{4!}$$

So we have

$$\begin{align}\text{desired count}\; =\; &|A_{\text{fa}}\cup A_{\text{am}}\cup A_{\text{mi}}|\\ =\; &3\cdot \frac{6!}{2!}-\left(2\cdot \frac{6!}{3!}+\frac{6!}{2!^2}\right)+\frac{6!}{4!} =690\tag{Answer}\end{align}$$

$\endgroup$
1
$\begingroup$

Basically the solution is the same as another question

What you do instead is to consider the "F", "A", "M", "I" similar, consider them placeholders where you later put the letters. That is what you're to rearrange is "____LY" and then put the letters "F", "A", "M" and "I" at the underscores.

That is the number of orderings considering the underscores distinct would be $6!$ and the number of ways you can reorder the underscores (in ways that should be considered equal are $4!$ So the result becomes

$$6!/4! = 6\times 5 = 30$$

Another way of reasoning is to place the "L" which can be done in six ways, and from the remaining five positions you can place "Y" in five ways. After that it's given how "F", "A", "M" and "I" would have to be placed.

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