6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please comment if you don't understand what I want to say. $\endgroup$ – mnulb Feb 23 '17 at 16:36
  • $\begingroup$ You start by stating "There are $4!$ without any restriction." How do you get this? $\endgroup$ – Tim Thayer Feb 23 '17 at 16:40
  • $\begingroup$ When two people have the same companion in front, it looks like you are assuming that those two people are consecutive. They don’t have to be, do they? $\endgroup$ – Steve Kass Feb 23 '17 at 16:41
  • $\begingroup$ Does the child in front have the child in the back as his "companion"? $\endgroup$ – The Count Feb 23 '17 at 16:41
  • $\begingroup$ @TimThayer concept of circular permutations. $\endgroup$ – mnulb Feb 23 '17 at 16:41
1
$\begingroup$

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} $$

$\endgroup$
  • $\begingroup$ Thanks in tons !!!. I think my fallacy was that I tied two and subtracted, then tied three and subtracted, so there may be that case that occurs in both, and I subtracted it twice. And you did it for $2-2$ peoples. Awesome...... $\endgroup$ – mnulb Mar 7 '17 at 7:41
1
$\begingroup$

I do not really understand what you are counting exactly. However, If $f(n)$ is the number of such rearrangements for $n$ children (counting those that can be transformed into another by rotating the merry go round), then we can find a recursion:

Let $n>3$ and the kids wear t-shirts numbered $1,\ldots,n$. In the original arrangement, the kids sit as $1\to 2\to\ldots\to n\to 1$. In the $f(n)$ other arrangements, there is no case of $k\to k+1$, nor os there $n\to 1$.

Now suppose $n$ puts a head on his successor and leaves, i.e., we convert $\ldots\to a\to n\to b\to \ldots$ into $\ldots\to a\to \hat b\to \ldots$. If $b\ne a+1$, this is one of $f(n-1)$ valid situations with $n-1$ kids (note that it is not possible to have $a=n-1$ and $b=1$); additionally, some kid that is neither $1$ nor the successor of $n-1$ has a hat.

But if $b=a+1$, $a$ leaves with $n$, takes of his shirt and kids $a+1,\ldots, n-1$ switch shirts so that each decreases by one, and shirt $n-1$ remains unused. In the end, we have $\ldots\to \hat a\to\ldots$ where $n$ and the now shirtless kid left. So this is one of $f(n-2)$ valid arrangements and a kid $\ne 1$ and $\ne n-2$ (note that these two exceptions are different!) has a hat.

Because of the hat, we can undo these steps: If there are $n-1$ kids on the merry go round, $n$ simply inserts himself behind the hat-kid. And if there are $n-2$ kids, then $n$ inserts behind the hat-kid with the shirtless kids behind him, the kids $\hat a,a+1,\ldots, n-2$ increase theri numbers while shirtless gets the then free $a$.

We conclude that $$\tag1 f(n) = (n-3)f(n-1)+(n-4)f(n-2)\qquad\text{if }n>3.$$ Clearly, $f(1)=f(2)=0$, $f(3)=1$. It is easy enough to use $(1)$ to find $f(5)$.

According to http://oeis.org/A000255, we have the surprising formula $$f(n+3)=\left\lfloor\frac{n!(n+2)}{e}+\frac12 \right\rfloor.$$

$\endgroup$
  • $\begingroup$ I think a permutation like $(14325)$ is included in your count, while it shouldn't, because in a merry-go-round $5$ would have $1$ in front again. $\endgroup$ – Dario Feb 23 '17 at 20:23
0
$\begingroup$

If you have one reordering so that each child has a new companion in front, then there are 4 similar solutions. Theses can be obtained by rotating the childs any number of times by $2\pi/5$ about the center of the merry-go-round. Hence the answer is a multiple of 5.

Now I think it's simplest to just list the solutions. Start by choosing a rotation by assigning child 1 to, say, the 3rd seat. Then put in front of him 3, 4 or 5. Then behind him any but 5, whoever is left.

Put the last two childs however it can validly be done (0, 1 or 2 ways (in fact at least 1))

$\{4,2,1,3,5\}\ ,\ \{5,2,1,4,3\}\ ,\ \{3,2,1,5,4\}$
$\{2,4,1,3,5\}\ ,\ \{5,3,1,4,2\}\ ,\ \{4,3,1,5,2\}$
$\{5,4,1,3,2\}\hspace{31.6mm}\{2,4,1,5,3\}$

There are 8 so the answer is $8\cdot5=40$

$\endgroup$
  • $\begingroup$ The solution for all n is here oeis.org/A167760 $\endgroup$ – Coolwater Feb 23 '17 at 17:26
  • $\begingroup$ We have to agree about what we want. I would say that $8$ is the correct solution. Each of those $8$ cases corresponds to $5$ equivalent positions of the merry-go-round, hence your $40$. $\endgroup$ – Dario Feb 23 '17 at 17:26
  • $\begingroup$ So, in my opinion, the correct answer is OEIS A000757, indistinguishable carousel horses. I upvoted your answer (distinguishable carousel horses) because OP’s requirements aren’t clear. $\endgroup$ – Dario Feb 23 '17 at 17:40
0
$\begingroup$

I think the main fallacy in your argument is that you wrongly choose the properties

Let us take $p_1$ be the property that exactly one person has the same companion. Number of ways in which this can be done is $\binom51*\binom21*3!$ Here there are $\binom21$ to choose companion(because in a round table each person has two companions and there are two ways to choose a companion who remains intact with the person.

Let us take $p_2$ be the property that exactly two person has the same companion.

It can be divided into cases

i)When the two persons are at adjacent places.Number of ways to choose the persons=5(if the round table goes as $A->B->C->D->E->A$ Then it can be clearly seen that two adjacent persons can be choosen in 5 ways.)

hence number of ways=$5*2!$(we have only one option for choosing companion in this case)

2)When the two persons are one place next to each other

Number of ways to choose the persons=$5$(Similar to argument in first case)

hence number of ways=$5*\binom32*2!$ Here there are $\binom32$ ways to choose companion(For example if round table is $A->B->C->D->E->A$ Then if $A$ and $C$ are choosen then possible choice of companions are $B,D,E$ of which any two is to be choosen.)One more thing here should be taken into consideration.When the two persons has same companion.It can be done in $5*2!$

3)Last case when the two persons are diagonally opposite to each other

CAUTION It is already counted in the second case.

Similarly when three persons has same companion=$2$(two rotations - clockwise or anticlockwise are possible)

Now apply IEP(which has none of the above properties) as $$4!-(\binom51*\binom21*3!)+(5*2!+5*\binom32*2!+5*2!)-2$$

$\endgroup$
  • $\begingroup$ In the third case, we picked diagonally so we have picked $4$ person (no companion overlapping), why that $2!$, it shouldn't be just $1!$? $\endgroup$ – mnulb Feb 24 '17 at 2:54
  • $\begingroup$ And why 3 persons can have just one way? like $A\rightarrow B\rightarrow C\rightarrow D$ , $B\rightarrow C\rightarrow D \rightarrow E$, $C\rightarrow D \rightarrow E\rightarrow A$. $\endgroup$ – mnulb Feb 24 '17 at 3:16
  • $\begingroup$ @Ayushakj please check the edit.I hope it is clear now. $\endgroup$ – Navin Feb 24 '17 at 4:37
  • $\begingroup$ See this: artofproblemsolving.com/community/… $\endgroup$ – mnulb Feb 24 '17 at 7:15
  • $\begingroup$ @Ayushakj Why you provided that link.There is no answer there as of now. Meanwhile it is of no use asking this question here.You can perhaps delete it from here. $\endgroup$ – Navin Feb 24 '17 at 9:01

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.