Five children sitting one behind the other in a five seater merry go round, decide to switch seats so that each child has a new companion in front. In how many ways can this be done?
My tries:
I try using IEP but didn't work, please point out a fallacy.
There are $4!$ without any restriction.
Let $p_1$ be the property such that one of them has the same companion in front, similarly for other properties, $p_2,p_3,p_4,p_5$, as well.
No. of way in which $p_1$ occur,
I used tie method, tie 1st one and the 2nd one, we remain with $3$, which along with tied one can be arranged in $3!$ (circular permutations). Similarly for other properties as well.
No of ways in which $p_1\cup p_2$ occur:
Now tie three consecutive people, so we remain with $2$, which along with tied peoples can be permuted in $2!$, similarly for other as well. Total results in $5\cdot 2!$. (need to tie consecutive from $5$, not any hence factor with $2$ is not ${{5}\choose{2}}$)
No. of ways in which $p_1\cup p_2\cup p_3$ occur:
Now, four consecutive people, we remain with $1$, which along with tied can be permuted in $1!$. Total results in $5\cdot 1!=5$
No. of ways in which $p_1\cup p_2\cup p_3\cup p_4$ occur:
Now we'll tie $5$ consecutive, so one way.
No. of ways in which $p_1\cup p_2\cup p_3\cup p_4\cup p_5$ occur:
will be same as No. of ways in which $p_1\cup_2\cup p_3\cup p_4$ occur $=1$
Exploiting IEP: $$4!-(5\cdot 3!)+(5\cdot 2!)-(5\cdot 1!)+1-1=-1$$
Where I over substracted !!!
Please Help.
We have actually two different problems here. Given $n$ children and $n$ seats, the number of ways the children can be seated is notoriously $n!$, the number of permutations on $n$ objects, or, if you prefer, the order of the symmetric group $S_n$. However, if the seats are on a merry-go-round and are not distinguishable from each other, we can turn the merry-go-round and have, say, child number $1$ at the fixed position we want. For instance, this means that $(34512)$ and $(51234)$ are both equivalent to $(12345)$, and we are only considering the relative positions of the children. In this case we speak of circular permutations and their number is clearly $(n-1)!$ With a more advanced terminology, we can say that we are not working in the symmetric group $S_n$, but in $S_n/C_n$, its quotient group modulo the cyclic group $C_n$.
It is clear that, if we label the seats and start distinguishing among them, for every circular permutation we have only $n$ different seat choices for the first child, and all others are forced to their respective seats with no other choice. In the following I will talk about circular permutations and indistinguishable seats, but if you want the results for distinguishable seats, it will be enough to multiply my results by $n$ and they will be valid for regular permutations as well.
Let’s define $f_0(n)$ to be the number of circular permutations of $n$ objects: $$ f_0(n) = \left\{ \begin{array}{ll} 1 & \mbox{if } n = 0 \\ (n-1)! & \mbox{if } n > 0 \end{array} \right. $$
The degenerate case $f_0(0)$ is needed by the following. It’s the only case where $n!\ne n\cdot f_0(n)$, and its interpretation is analogous to that of $0!$ in the case of permutations: no seats, no children, no fun, only one possible situation.
Then, we define $f_1(n) \mbox{ for } n>1$ to be the number of permutations of $n$ objects not containing the sequence $12$, and, in general, we define $f_k(n) \mbox{ for } n\ge k$ to be the number of circular permutations of $n$ objects not containing any sequence $i(i+1) \mbox{ for } i\le k$. For instance, $f_3(4) = 2$ is the number of elements of the set $\left\{ (1432), (1324) \right\}$, i.e., the set of all circular permutations of $4$ objects containing neither $12$, nor $23$, nor $34$. Note that it still contains one element with the sequence $41$, $(1324) \approx (4132)$, but we don’t care: we’ll discard it when we compute $f_4(4)$.
I hope all is clear up to this point. Our problem is how to compute $f_5(5)$ and we can do it by induction, starting with the definition of $f_0$ above and by observing that
$$\begin{array}{lr} f_{k+1}(n) = f_k(n) - f_k(n-1) & \forall k \ge 0, n>k \end{array} $$
The proof is rather simple. By definition, $f_k(n)$ is the number of circular permutations of $n$ objects not containing sequences $i(i+1)\mbox{ for }i\le k$; to compute $f_{k+1}(n)$ we need to subtract the number of such circular permutations which contain the sequence $(k+1)(k+2)$. In fact, they are $f_k(n-1)$. For each of the permutations of $(n-1)$ objects counted by $f_k(n-1)$, we find where the element $(k+1)$ is, place a new element next to it naming it $(k+2)$, renumber all subsequent elements, and we get one of the circular permutations of $n$ objects that we want to discard. If there is no $(k+1)$, we are in the case $k=n-1$ and it is enough to concatenate $(k+1)$ at the end. For instance, for $k=3, n=4$, from $(132)$ we get $(1324)$. Conversely, if we have a circular permutation with the sequence $(k+1)(k+2)$, it is enough to delete the element $(k+2)$ and renumber all subsequent elements: we get one of the circular permutations of $n-1$ objects counted by $f_k(n-1)$. Again, if there is no $(k+2)$ because we want to discard the sequence $(k+1)1$, it is enough to delete $(k+1)$. For instance, $(1324)\mapsto(132)$. Q.E.D.
Let me give another example: we have already seen the set $E = \left\{ (1432), (1324) \right\}$. It has $f_3(4)$ elements. From each of its elements we can generate a circular permutation of $5$ objects containing the sequence $45$ but not “smaller” ones: $(1432)\mapsto(14532)\mbox{ and }(1324)\mapsto(13245)$. Conversely, for every circular permutation of $5$ elements containing the sequence $45$ but no “smaller” ones, we can delete the element $5$ and get one of the elements of $E$.
We can now tabulate:
$$ \begin{array}{lrrrrrr} & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline f_0: & 1 & 1 & 1 & 2 & 6 & 24 \\ f_1: & & 0 & 0 & 1 & 4 & 18 \\ f_2: & & & 0 & 1 & 3 & 14 \\ f_3: & & & & 1 & 2 & 11 \\ f_4: & & & & & 1 & 9 \\ f_5: & & & & & & 8 \end{array} $$
As expected, we see that the values of $f_n(n)$ in the diagonal of the above table form the sequence OEIS A000757. This answer is based on the literature cited at that link.
We see that $f_5(5)=8$, as already shown in Coolwater’s answer. Let’s recompute: $$ \begin{array}{rl} 24 & \mbox{# All possible circular permutations of 5 children}\\ -6 & \mbox{# permutations containing }12:(12abc),\,6\mbox{ possible permutations of }abc\\ -4 & \mbox{# }remaining\mbox{ permutations containing }23:(1a23b)\mbox{ or }(1ab23),\mbox{ with }a,b\in\{4,5\}\\ -3 & \mbox{# }remaining\mbox{ permutations containing }34: (13425),(13452),(15342)\\ -2 & \mbox{# }remaining\mbox{ permutations containing }45: (14532),(13245)\\ -1 & \mbox{# }remaining\mbox{ permutation containing }51: (14325)\approx(51432)\\ \hline =8 \end{array} $$