2
$\begingroup$

Beforehand, each person is assigned a seat (n seats). How many ways can they rearrange such that each person is in a new seat and no 2 people swap?

I'm guessing $(n-1)!$, but I have no idea on how to get the answer.

I was trying to get the answer to this problem:

A small class of nine boys are to change their seating arrangement by drawing their new seat numbers from a box. After the seat change, what is the probability that there is only one pair of boys who have switched seats with each other and only three boys who have unchanged seats?

where I got: $(9C3 * 6C2 *4!)/9!$ but I realized that none of the (4!) people should be on the same seat. And no pair of students swapped seats

The answer to this problem is $9C3*6C2*3!/9!$. I want to find a generalization, with n seats, how many ways can you arrange n people such that no 2 people swap and no one is in the same seat.

$\endgroup$
7
  • $\begingroup$ Please use derangement $\endgroup$ – Math Lover Feb 18 at 7:03
  • $\begingroup$ Count it yourself for 1, 2, 3 and 4 people. The answers are not 1, 1, 2, 6. $\endgroup$ – Arthur Feb 18 at 7:25
  • 1
    $\begingroup$ OK so now your question is different. Now for $4$ people - the first person A has a choice of $3$ seats. Say A takes C's seat. Now C has choice of only $2$ seats as C cannot take A's seat as that would be a swap. Say C takes B's seat. Now B has choice of only 1 seat - cannot take C's seat as that is a swap. Cannot take A's seat as that would mean D does not change seat. So B takes D's seat. Finally D has 1 choice which is take A's seat. $\endgroup$ – Math Lover Feb 18 at 8:07
  • 2
    $\begingroup$ This entry to OEIS gives the answer. No simple closed formula. They give a recurrence relation. Didn't check but likely the same or similar to Gribouillis's answer (+1). $\endgroup$ – Jyrki Lahtonen Feb 18 at 8:34
  • 1
    $\begingroup$ @JyrkiLahtonen: I did just now check, and it has both Gribouillis’s original summation and the nice recurrence derived from it. $\endgroup$ – Brian M. Scott Feb 18 at 17:51
4
$\begingroup$

I think there is a way to write a recurrence relation by the following reasoning: we are counting the permutations of $\left\{1 , \ldots , n\right\}$ which decomposition in cycles contains only cycles having at least $3$ elements. Let ${X}_{n}$ be that number. We can start with ${X}_{1} = {X}_{2} = 0$ and ${X}_{3} = 2$. Conventionally, we take ${X}_{0} = 1$.

Let $n \geqslant 3$. We choose $k \geqslant 2$ elements in $\left\{1 , \ldots , n-1\right\}$ to form a cycle with the element $n$. There are $\binom{n-1}{k}$ ways to find these elements and there are $k !$ ways to align them in a row to build the cycle with element $n$. For the remaining $n-k-1$ elements, we choose one of the ${X}_{n-k-1}$ valid permutations. Hence we obtain the relation

\begin{equation} {X}_{n} = \sum _{k = 2}^{n-1} \binom{n-1}{k} \ k ! \ {X}_{n-k-1} = (n-1)!\sum _{k = 2}^{n-1} \frac{{X}_{n-k-1}}{(n-k-1)!} \end{equation} This easily entails the relation $X_n = (n-1)X_{n-1} + (n-1)(n-2) X_{n-3}$.

Note that this order 3 relation can be shown directly by another way of counting the permutations:

Second reasoning We can separate the valid permutations between the permutations for which the number $n$ belongs to a 3-cycle (there are $(n-1)(n-2) X_{n-3}$ of them because there are $(n-1)(n-2)/2$ ways of choosing the two other elements of the 3-cycle and each choice gives two possible cycles) and the permutations for which the number $n$ belongs to a larger cycle. Those are obtained by inserting the number $n$ in one of the cycles of a valid permutation of the $n-1$ first elements. For a given such permutation, there are exactly $n-1$ places where to insert the $n$-th element, between one of the $n-1$ first numbers and its successor in a cycle. Hence there are $(n-1)X_{n-1}$ such permutations. This proves the order 3 relation.

Clearly, the same reasoning shows that if we generalize and we count instead the number $Y_n$ of permutations of $\{1,\cdots, n\}$ where all the cycles have a length $\ge p$, then we have the relation

\begin{equation} Y_n = (n-1) Y_{n-1} + (n-1)\cdots (n-p+1) Y_{n-p} \end{equation}

$\endgroup$
3
  • $\begingroup$ I see how you can use the summation equation to prove the order $3$ recurrence relation, but how on earth did you discover the order $3$ recurrence relation in the first place? $\endgroup$ – Mike Earnest Feb 18 at 16:49
  • 1
    $\begingroup$ @MikeEarnest In fact I discovered it by remarking that the summation was almost a simple relation for $X_n / n!$. However, it can be obtained directly, see my edit about the second reasoning above. $\endgroup$ – Gribouillis Feb 18 at 17:20
  • $\begingroup$ Very cool, thank you! $\endgroup$ – Mike Earnest Feb 18 at 17:32

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.