Seating Derangements without Horizontal Displacement

Abstract

This paper investigates the permutations of seating arrangements where individuals can only move to adjacent seats, without any horizontal displacement. We consider a grid consisting of 𝑚 rows and 𝑛 columns, with each seat occupied by a single person. The allowed movements are restricted to vertical or diagonal shifts to neighboring seats. We establish recurrence relations to determine the number of possible seating derangements for given values of m and n. Solutions to these recurrence relations are provided. Additionally, we extend our analysis to larger grids of size 2𝑚 × 𝑛, subject to the same movement constraints.