# Point out my Fallacy, in combinatorics problem, please.

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 comment if you don't understand what I want to say. – mnulb Feb 23 '17 at 16:36
• You start by stating "There are $4!$ without any restriction." How do you get this? – Tim Thayer Feb 23 '17 at 16:40
• 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? – Steve Kass Feb 23 '17 at 16:41
• Does the child in front have the child in the back as his "companion"? – The Count Feb 23 '17 at 16:41
• @TimThayer concept of circular permutations. – mnulb Feb 23 '17 at 16:41

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

• 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...... – mnulb Mar 7 '17 at 7:41

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

• 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. – Dario Feb 23 '17 at 20:23

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$

• The solution for all n is here oeis.org/A167760 – Coolwater Feb 23 '17 at 17:26
• 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$. – Dario Feb 23 '17 at 17:26
• 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. – Dario Feb 23 '17 at 17:40

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

• 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!$? – mnulb Feb 24 '17 at 2:54
• 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$. – mnulb Feb 24 '17 at 3:16
• @Ayushakj please check the edit.I hope it is clear now. – Navin Feb 24 '17 at 4:37
• See this: artofproblemsolving.com/community/… – mnulb Feb 24 '17 at 7:15
• @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. – Navin Feb 24 '17 at 9:01