Full article: The 2 x n seating derangements

Formulae display: $MathJax Logo$ ?Mathematical formulae have been encoded as MathML and are displayed in this HTML version using MathJax in order to improve their display. Uncheck the box to turn MathJax off. This feature requires Javascript. Click on a formula to zoom.

Abstract

In this paper, we study the derangement of 2n persons sitting 2 rows and n columns. In how many ways can the $2 n$ persons rearrange their seating in accordance with the following condition. Each seat is located by one person and reoccupied by another person and each person moves to a horizontal or a vertical or a diagonal neighboring seat. We establish the system of recurrence relations for the solution of this problem and provide the solution of the system of recurrence relations.

Keywords:

AMS Mathematics subject classifications:

PUBLIC INTEREST STATEMENT

A 2 x n seating derangement is any movement of persons among the 2n seats, arranged in 2 rows and n columns, so that each seat is located by one person and reoccupied by another person and each person moves to a horizontal or a vertical or a diagonal neighboring seat. How many ways can the directive in a 2 x n seating derangement be carried out? What is the number of ways that this can be done? The objective of this paper is to solve a 2 x n seating derangement. The system of recurrence relations for the solution of this problem is established and the solution of the system of recurrence relations is obtained.

1. Introduction

Kennedy and Cooper (Citation1993) are interested in the following problem.

“A $m \times n$ classroom has $m$ rows of $n$ desks per row. The teacher requests each pupil to change his seat by going either to the seat in front, the one behind, the one to his left, on to the one on his right (of course not all these options are possible for all students). How many ways can this direcitve be carried out?” (p. 60)

The answer to the $2 \times n$ classroom is $F_{n + 1}^{2},$ where $F_{n}$ is the $n$ th Fibonacci number (Honsberger, Citation1997; Kennedy & Cooper, Citation1993; Otake, Kennedy, & Cooper, Citation1996). The following problem, which were raised in Kennedy and Cooper (Citation1993) and still remain open, as follows:

“A $2 \times n$ classroom has $2$ rows of $n$ desks per row. The teacher requests each pupil to change his seat by going either to the seat in front or behind, the one to the left or the right, or to one of the diagonal seats (of course, not all these options are possible for all students). How may ways can this directive be carried out?”

The purpose of this paper is to study derangement for the $2 \times n$ classroom problem. We can restate the $2 \times n$ classroom problem as follows: Consider $2 n$ person seated at the 2 rows of n seats per row; in how many ways, the $2 n$ person can be derangement such that each seat can located by one person and reoccupied by another person and each person moves to a horizontal or a vertical or a diagonal neighboring seat.

2. Main results

For any positive integer $n$ , suppose that $2 n$ persons are seated at the 2 rows of $n$ seats per row.

Definition 1. Let $n$ be a positive integer.

A $2 \times n$ seating derangement is any movement of person among the $2 n$ seats, arranged in 2 rows and $n$ columns, so that each seat is located by one person and reoccupied by another person and each person moves to a horizontal or a vertical or a diagonal neighboring seat.

For example, the figure of $2 \times 4$ seating derangement and $2 \times 5$ seating derangement are shown in Figure (a) and (b), respectively.

Figure 1. $2 \times 4$ and $2 \times 5$ seating derangements.

Figure 1. 2×4 and 2×5 seating derangements.

In Figure , Ↄ denotes a seat and $\to$ denotes the movement of a person from one seat to another.

Next, we are interested in the problem of a $2 \times n$ seating derangement, in how many ways the seats can be derangement? What is the number of ways that this can be done?

We may find that it is not easy to get a direct answer to the problem. Let us consider some special cases. When $n = 1$ , it is clear that there is one and only one way to interchange the two seats in a $2 \times 1$ seating derangement as shown in Figure .

Figure 2. $2 \times 1$ seating derangement.

When $n = 2,$ there are exactly 9 ways to rearrange the 4 seats in a $2 \times 2$ seating derangement as shown in Figure .

Figure 3. $2 \times 2$ seating derangement.

When $n = 3,$ there are 33 different ways to rearrange the 6 seats on a $2 \times 3$ seating derangement as shown in Figure .

Figure 4. $2 \times 3$ seating derangement.

We observed that each figure in the $2 \times 3$ seating derangement(Figure ) are ended by $2 \times 1$ and the $2 \times 2$ seating derangements. These exhibit endings that may be classified into 13 types, call type $A$ , type $B$ , type $C$ , type $D$ , type $E$ , type $F$ , type $G$ , type $H$ , type $I$ , type $J$ , type $K$ , type $L$ , type $M$ as shown in Figure .

Figure 5. Type $A$ , type $B$ , ..., type $M$ .

Type $B$ may be further subdivided into five kinds shown in Figure ; similarly for type $C$ , type $D$ and type $E$ .

Figure 6. Type $B$ .

There are 4 kinds of type $F$ shown in the Figure , similarly for type $G$ , type $H$ and type $I$ . It is easy to see that there is only one kind of type $A, J, K,$ and $L .$

Figure 7. Type $F$ .

For convenience, let $T_{n}$ be the set of all $2 \times n$ seating derangements and $t_{n}$ denote the number of the set $T_{n}$ . As shown before, we have

t_{1} = 1, t_{2} = 9, t_{3} = 33.

Next, we will find $t_{n}, n \geq 3.$

The set $T_{n}$ may be partitioned into 13 subsets $A_{n}, B_{n}, C_{n}, D_{n}, E_{n}, F_{n}, G_{n}, H_{n}, I_{n}, J_{n}, K_{n}, L_{n}$ and $M_{n}$ according to the 41 endings (Figure –1).

Figure 8. $A_{n}$ .

Figure 9. $B_{n}, C_{n}, D_{n}, E_{n}$ .

Figure 10. $F_{n}, G_{n}, H_{n}, I_{n}$ .

Figure 11. $J_{n}, K_{n}, L_{n}, M_{n}$ .

Let $a_{n}, b_{n}, c_{n}, d_{n}, e_{n}, f_{n}, g_{n}, h_{n}, i_{n}, j_{n}, k_{n}, l_{n}$ and $m_{n}$ be the cardinalities of $A_{n}, B_{n}, C_{n}, D_{n}, E_{n}, F_{n},$ $G_{n}, H_{n}, I_{n}, J_{n}, K_{n}, L_{n}$ and $M_{n},$ respectively.

Then, the number of the $2 \times n$ seating derangement is

t_{n} = a_{n} + b_{n} + c_{n} + d_{n} + e_{n} + f_{n} + g_{n} + h_{n} + i_{n} + j_{n} + k_{n} + l_{n} + m_{n} .

Theorem 2. The number of the $2 \times n$ seating derangement is

t_{n} = w_{n} + 4 x_{n} + 4 y_{n} + 4 z_{n},

where $w_{n}, x_{n}, y_{n}, z_{n}$ satisfy the recurrence matrix

(\begin{matrix} 1 & 4 & 4 & 4 \\ 1 & 2 & 2 & 0 \\ 0 & 2 & 2 & 0 \\ 1 & 0 & 0 & 0 \end{matrix}) (\begin{matrix} w_{n} \\ x_{n} \\ y_{n} \\ z_{n} \end{matrix}) = (\begin{matrix} w_{n + 1} \\ x_{n + 1} \\ y_{n + 1} \\ z_{n + 1} \end{matrix}),

and $w_{1} = 1, x_{1} = y_{1} = z_{1} = 0.$

Proof. It is clear that any member of $T_{n}$ becomes a member of $A_{n + 1}$ when an extra column (Figure ) is attached to the end, and conversely. Then,

a_{n + 1} = a_{n} + b_{n} + c_{n} + d_{n} + e_{n} + f_{n} + g_{n} + h_{n} + i_{n} + j_{n} + k_{n} + l_{n} + m_{n} .

Next, there is a 1–1 correspondences between $A_{n} \cup B_{n} \cup D_{n} \cup F_{n} \cup H_{n}$ and $B_{n + 1}$ , shown in Figure . Then,

b_{n + 1} = a_{n} + b_{n} + d_{n} + f_{n} + h_{n} .

Figure 12. 1–1 correspondence between $A_{n} \cup B_{n} \cup D_{n} \cup F_{n} \cup H_{n}$ and $B_{n + 1}$ .

Figure 12. 1–1 correspondence between An∪Bn∪Dn∪Fn∪Hn and Bn+1.

Similar correspondences, we have

c_{n + 1} = a_{n} + c_{n} + e_{n} + g_{n} + i_{n},

d_{n + 1} = a_{n} + c_{n} + e_{n} + g_{n} + i_{n},

e_{n + 1} = a_{n} + b_{n} + d_{n} + f_{n} + h_{n},

f_{n + 1} = b_{n} + c_{n} + f_{n} + h_{n},

g_{n + 1} = b_{n} + c_{n} + g_{n} + i_{n},

h_{n + 1} = b_{n} + c_{n} + f_{n} + h_{n}, a n d

i_{n + 1} = b_{n} + c_{n} + g_{n} + i_{n} .

Since $A_{n}$ is a one-to-one correspondence to $J_{n + 1},$ we have

j_{n + 1} = a_{n} .

Similarly, we have

k_{n + 1} = l_{n + 1} = m_{n + 1} = a_{n} .

From the $2 \times 1$ seating derangement, we obtain that $a_{1} = 1,$ and $b_{1} = c_{1} = d_{1} = e_{1} = f_{1} = g_{1} = h_{1} = i_{1} = j_{1} = k_{1} = l_{1} = m_{1} = 0.$

For $n \geq 1,$ we derive $a_{n + 1}, b_{n + 1}, c_{n + 1}, d_{n + 1}, e_{n + 1}, f_{n + 1}, g_{n + 1}, h_{n + 1}, i_{n + 1}, j_{n + 1}, k_{n + 1},$ $l_{n + 1},$ and $m_{n + 1}$ form the following recurrence relation.

a_{n + 1} = a_{n} + b_{n} + c_{n} + d_{n} + e_{n} + f_{n} + g_{n} + h_{n} + i_{n} + j_{n} + k_{n} + l_{n} + m_{n},

b_{n + 1} = a_{n} + b_{n} + d_{n} + f_{n} + h_{n},

c_{n + 1} = a_{n} + c_{n} + e_{n} + g_{n} + i_{n},

d_{n + 1} = a_{n} + c_{n} + e_{n} + g_{n} + i_{n},

e_{n + 1} = a_{n} + b_{n} + d_{n} + f_{n} + h_{n},

f_{n + 1} = b_{n} + c_{n} + f_{n} + h_{n},

g_{n + 1} = b_{n} + c_{n} + g_{n} + i_{n},

h_{n + 1} = b_{n} + c_{n} + f_{n} + h_{n},

i_{n + 1} = b_{n} + c_{n} + g_{n} + i_{n},

j_{n + 1} = a_{n},

k_{n + 1} = a_{n},

l_{n + 1} = a_{n}, a n d

m_{n + 1} = a_{n} .

We notice that

b_{n + 1} = e_{n + 1},

c_{n + 1} = d_{n + 1},

f_{n + 1} = h_{n + 1},

g_{n + 1} = i_{n + 1}, a n d

j_{n + 1} = k_{n + 1} = l_{n + 1} = m_{n + 1} .

$b_{n + 1} = e_{n + 1}, c_{n + 1} = d_{n + 1}, f_{n + 1} = h_{n + 1}, g_{n + 1} = i_{n + 1}$ and $j_{n + 1} = k_{n + 1} = l_{n + 1} = m_{n + 1} .$ It follows that

a_{n + 1} = a_{n} + 2 b_{n} + 2 c_{n} + 2 f_{n} + 2 g_{n} + 4 j_{n} .

Since $f_{n + 1} - g_{n + 1} = 2 (f_{n} - g_{n})$ and $f_{1} = 0 = g_{1},$ we have $f_{n + 1} = g_{n + 1}$ and $b_{n + 1} = c_{n + 1} .$

Set $w_{n} = a_{n}, x_{n} = b_{n}, y_{n} = f_{n},$ and $z_{n} = j_{n} .$ Therefore, the number of the $2 \times n$ seating derangement is

t_{n} = w_{n} + 4 x_{n} + 4 y_{n} + 4 z_{n}

where

w_{n + 1} = w_{n} + 4 x_{n} + 4 y_{n} + 4 z_{n},

x_{n + 1} = w_{n} + 2 x_{n} + 2 y_{n},

y_{n + 1} = 2 x_{n} + 2 y_{n}, a n d

z_{n + 1} = w_{n},

and $w_{1} = 1, x_{1} = y_{1} = z_{1} = 0.$

These results are summarized in the matrix equation:

(\begin{matrix} 1 & 4 & 4 & 4 \\ 1 & 2 & 2 & 0 \\ 0 & 2 & 2 & 0 \\ 1 & 0 & 0 & 0 \end{matrix}) (\begin{matrix} w_{n} \\ x_{n} \\ y_{n} \\ z_{n} \end{matrix}) = (\begin{matrix} w_{n + 1} \\ x_{n + 1} \\ y_{n + 1} \\ z_{n + 1} \end{matrix}),

where

(\begin{matrix} w_{1} \\ x_{1} \\ y_{1} \\ z_{1} \end{matrix}) = (\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \end{matrix}) .

Ↄ

The following table shows the values of $w_{n}, x_{n}, y_{n}, z_{n},$ and $t_{n}$ in Theorem 2. when $n = 1, 2, \dots, 10.$

Table

Download CSV Display Table

Theorem 3. Let $n$ be a positive integer.

The number of the $2 \times n$ seating derangement is

t_{n} = (\frac{1}{2} α - 2) A α^{n + 2} + (\frac{1}{2} β - 2) B β^{n + 2} + (\frac{1}{2} γ - 2) C γ^{n + 2},

where

A = \frac{2}{α (α - β) (α - γ)}, B = \frac{2}{β (β - α) (β - γ)}, C = \frac{2}{γ (γ - α) (γ - β)},

and

α = \frac{5}{3} + \frac{2 \sqrt{37}}{3} cos (\frac{1}{3} arccos (\frac{- 1}{37 \sqrt{37}})),

β = \frac{5}{3} + \frac{\sqrt{37}}{3} (- cos (\frac{1}{3} arccos (\frac{- 1}{37 \sqrt{37}})) + \sqrt{3} sin (arccos (\frac{- 1}{37 \sqrt{37}}))),

γ = \frac{5}{3} - \frac{\sqrt{37}}{3} (cos (\frac{1}{3} arccos (\frac{- 1}{37 \sqrt{37}})) + \sqrt{3} sin (arccos (\frac{- 1}{37 \sqrt{37}}))) .

Proof. By Theorem 2, the number of the $2 \times n$ seating derangement is

(1) $t_{n} = w_{n} + 4 x_{n} + 4 y_{n} + 4 z_{n}$

where

(*) $\{\begin{matrix} w_{n + 1} & = w_{n} + 4 x_{n} + 4 y_{n} + 4 z_{n}, \\ x_{n + 1} & = w_{n} + 2 x_{n} + 2 y_{n}, \\ y_{n + 1} & = 2 x_{n} + 2 y_{n}, a n d \\ z_{n + 1} & = w_{n} . \end{matrix}$

for positive integer $n$ and $w_{1} = 1, x_{1} = y_{1} = z_{1} = 0.$

The system of equations in (*) are reduced to a single equation:

(2) $y_{n + 3} - 5 y_{n + 2} - 4 y_{n + 1} + 16 y_{n} = 0.$

The characteristic equation is $t^{3} - 5 t^{2} - 4 t + 16 = 0.$

The zeros of this polynomial are

α = \frac{5}{3} + \frac{2 \sqrt{37}}{3} cos (\frac{1}{3} arccos (\frac{- 1}{37 \sqrt{37}})),

β = \frac{5}{3} + \frac{\sqrt{37}}{3} (- cos (\frac{1}{3} arccos (\frac{- 1}{37 \sqrt{37}})) + \sqrt{3} sin (arccos (\frac{- 1}{37 \sqrt{37}}))),

γ = \frac{5}{3} - \frac{\sqrt{37}}{3} (cos (\frac{1}{3} arccos (\frac{- 1}{37 \sqrt{37}})) + \sqrt{3} sin (arccos (\frac{- 1}{37 \sqrt{37}}))) .

The general solution of Equation (2) is

(3) $y_{n} = A α^{n} + B β^{n} + C γ^{n},$

and using the initial conditions, $y_{1} = y_{2} = 0$ and $y_{3} = 2,$ we obtain

A = \frac{2}{α (α - β) (α - γ)},

B = \frac{2}{β (β - α) (β - γ)},

C = \frac{2}{γ (γ - α) (γ - β)} .

We substitute Equation (3) into $w_{n} = \frac{1}{2} y_{n + 2} - 2 y_{n + 1},$ which yields

w_{n} = (\frac{1}{2} α - 2) A α^{n + 1} + (\frac{1}{2} β - 2) B β^{n + 1} + (\frac{1}{2} γ - 2) C γ^{n + 1} .

Since $t_{n} = w_{n + 1}$ (by Theorem 2), we have

$t_{n} = (\frac{1}{2} α - 2) A α^{n + 2} + (\frac{1}{2} β - 2) B β^{n + 2} + (\frac{1}{2} γ - 2) C γ^{n + 2} .$

This completes the proof.

Additional information

Funding

The authors received no direct funding for this research.

Notes on contributors

Monrudee Sirivoravit

Monrudee Sirivoravit is a lecturer in the Department of Mathematics at Kasetsart University. She obtained her M.Sc. degree in Mathematics from Chulalongkorn University, Thailand, in 2004. Her research interests are Algebra, Number Theory and Combinatorics.

Utsanee Leerawat

Utsanee Leerawat is an associate professor in the Department of Mathematics at Kasetsart University. She received her Ph.D. degree in Mathematics in 1994 at Chulalongkorn University, Thailand. Her research interests are Ring Theory (derivations, commutativity conditions in rings), Universal algebra and Combinatorics.

References

Honsberger, R. (1997). In Polya’s footsteps: Miscellaneous problems and essays, Dolciani mathematical exposition number 19. MAA, New york, USA.
Google Scholar
Kennedy, R. E., & Cooper, C. (1993). Variation on a five - by - five seating rearrangement problem (pp. 59–67). Mathematics in College. Fall-Winter, New York.
Google Scholar
Otake, T., Kennedy, R. E., & Cooper, C. (1996). On a seating rearrangement problem. Mathematics and informatics quarterly, 52, 63–71.
Google Scholar

The 2 x n seating derangements