Permutations with restrictions

Question

Three ladies have each brought a child for admission to a school. The head of the school wishes to interview the six people one by one, taking care that no child is interviewed before its mother. In how many different ways can the interviews be arranged?

I tried to apply concept of balanced parenthesis so there can be 5 different permutations for balanced parenthesis with 6 strings

12 $\left \{ \left \{ \right \} \left \{ \right \} \right \}$
6 $\left \{ \right \} \left \{ \right \} \left \{ \right \}$
12 $\left \{ \right \} \left \{ \left \{ \right \} \right \} $
12 $ \left \{ \left \{ \right \} \right \} \left \{ \right \} $
36 $ \left \{ \left \{ \left \{ \right \} \right \} \right \} $

i'm getting 78 permutations but answer is 90 which permutations are missing?

Answer 1

One way to organize the count is to case it by the following pattern (where $\text{P}$ denotes one of the parents, and $\text{C}$ denotes one of the children):

• $\text{PPPCCC}:\;\;(3!)(3!)=36\;$ways
• $\text{PPCPCC}:\;\;(3)(2)(2)(1)(2)(1)=24\;$ways
• $\text{PPCCPC}:\;\;(3)(2)(2)(1)(1)(1)=12\;$ways
• $\text{PCPPCC}:\;\;(3)(1)(2)(1)(2)(1)=12\;$ways
• $\text{PCPCPC}:\;\;3!=6\;$ways

which yields a total of $$36+24+12+12+6=90$$

For an alternate, more sophisticated approach, you can argue as follows . . .

Label the parents-child pairs as$\;\;P_1,C_1,\;\;P_2,C_2,\;\;P_3,C_3$.

Place $P_1,C_1$ in the queue, but allow flexible space before them, after them, and between them, to allows for potential later insertions.

To place $P_2,C_2$, since there are $3$ available flexible spaces, there are ${\large{\binom{3}{1}}}$ ways to place $P_2,C_2$ in the same space, and ${\large{\binom{3}{2}}}$ ways to place $P_2,C_2$ in two distinct spaces.

As before, allow flexible space before the beginning of the queue, after the end of the queue, and between any two people in the queue, to allow for potential later insertions.

To place $P_3,C_3$, since there are $5$ available flexible spaces, there are ${\large{\binom{5}{1}}}$ ways to place $P_3,C_3$ in the same space, and ${\large{\binom{5}{2}}}$ ways to place $P_3,C_3$ in two distinct spaces.

It follows that the total number of ways is $$ \left( {\small{\binom{3}{1}}}+{\small{\binom{3}{2}}} \right) \left( {\small{\binom{5}{1}}}+{\small{\binom{5}{2}}} \right) =(6)(15) =90 $$ With the same reasoning, for $n$ parent-child pairs, the number of ways is \begin{align*} &\prod_{k=2}^n \left[{\small{\binom{2k-1}{1}}}+{\small{\binom{2k-1}{2}}}\right]\\[4pt] =\;&\prod_{k=2}^n k(2k-1)\\[4pt] =\;&\left(\prod_{k=2}^n k\right)\left(\prod_{k=2}^n (2k-1)\right)\\[4pt] =\;&n!\left(\prod_{k=2}^n (2k-1)\right)\\[4pt] =\;&n!\left(\frac{(2n-1)!}{2^{n-1}(n-1)!}\right)\\[4pt] =\;&\frac{n\Bigl((2n-1)!\Bigr)}{2^{n-1}}\\[4pt] =\;&\frac{(2n)!}{2^{n}}\\[4pt] \end{align*} which, for $n=3$, yields $$\frac{6!}{2^3}=\frac{720}{8}=90$$ matching our previously calculated result.

But there's an even easier way . . .

Start by placing the $2n$ people in the queue in any order, yielding $(2n)!$ ways.

But with that count, each parent-child pair can occur in two ways; once in an acceptable order, and once in an unacceptable order.

Thus, our count of $(2n)!$ is inflated by a factor of $(2)\cdots(2)$, with $n$ factors of $2$, one for each parent-child pair.

Hence, to correct the count, simply divide by $2^n$, yielding $$\frac{(2n)!}{2^{n}}$$ $$\text{Voila!}$$

Answer 2

Partial answer:

Let us start with one adult, followed by three children. One such example is $-A-a-b-c-$, where $A, B, C$ are the adults, and $a,b,c$ are the children. We now have to place the two adults $B$ and $C$ in the spaces.

There are $3$ ways to choose the adult, and $3!$ ways to order the children. There are also $5 \choose 2$ ways to arrange $B$ and $C$, which gives a total of $180$ — twice the original answer.

Of course, some combinations are not valid, because of the 'no child is interviewed before its mother' rule. For example, this methods counts $AabBcC$ when it breaks the rule.

Feel free to take this answer as inspiration for your solution.

Answer 3

I guess i have not correctly interpreted the question but I post the answer according to what I thought

Answer 1: No child is interviewed exactly before his mother

Let $M_1,M_2,M_3$ represent the mothers and $B_1,B_2,B_3$ represent the children.

Hence by inclusion exclusion principle we need to find the number of ways such that a word is formed from the letters $M_1,M_2,M_3,B_1,B_2,B_3$ with the restriction that the strings $B_1M_1$ or $B_2M_2$ or $B_3M_3$ do not occur in the word.

Let these events be represented by the events $A$(the string $B_1M_1$ occurs), $B$( the string $B_2M_2$ occurs) and $C$( the string $B_3M_3$ occurs) respectively. Hence we need to find by inclusion exclusion principle that $$\text {Answer}= 6!- [n(A)+n(B)+n(C)-n(A\cap B) -n(B\cap C) -n(A\cap C) +n(A\cap B\cap C) ]$$

$$\text {Answer}= 6!- [3.5!-3.4!+3!]=426$$

Answer 2: No child is interviewed at any point before his mother

The probability that the first child is not interviewed before his mother is simply $\frac 12$. The same goes for the second and third one. Now since these events are independent of each other hence the probabilities are multiplied

Hence the answer would be $$\frac 12\cdot \frac 12\cdot \frac 12\cdot (\text {Total permutations of 6 people})=\frac {6!}{8}=90$$

As for generalized answer as quasi suggested for $n$ parent child pairs, using the same reasoning above we get $$\frac12\cdot \frac 12\cdot \frac 12\cdot \frac 12\cdot....(\text {$n$ times})\cdot (\text {Total permutations of $2n$ people})=\frac {2n!}{2^n}$$

Answer 4

Consider the cases of three mothers followed by three children: $$3!\cdot 3!=36.$$ Consider the cases of the order $M_1,M_2,M_3$: $$\begin{align}&M_1M_2*M_3** \Rightarrow 2\cdot 2=4 \\ &M_1M_2**M_3* \Rightarrow 1\cdot 2=2 \\ &M_1*M_2M_3**\Rightarrow 1\cdot 2=2 \\ &M_1*M_2*M_3* \Rightarrow 1 \end{align}$$ Since there are $3!$ permutations of mothers, then: $$3!\cdot (4+2+2+1)=54.$$ Hence: $36+54=90$.