$2n$ students want to sit in $n$ fixed school desks such that no one sits with their previous partner

Question

A classroom has $n$ fixed school desks with exactly $2$ chairs each. There are $2n$ students sitting in the classroom and then they go on a break. After the break they're coming back into the classroom and want to sit such that no one sits with their previous partner. What's the number of ways to do that?

I was thinking either a recursion or the inclusion-exclusion formula. This seems similar to derangements problem, but I'm not sure if I can make a connection between the two.

My idea was to define $A_i = \{$person $i$ sits with their previous partner$\}$ for $i=1,...,n$ and then to use inclusion-exclusion but I'm not sure how to count $\lvert A_i \rvert$ and $\lvert A_I\rvert=\cap_{i\in I}A_i$ where $I\subset\{1,2,...,n\}$

Answer 1

Combinatronics has never come easy to me, but hopefully this is a sound approach:

We can fix the position of $n$ of the students, label these $A_1, \dots, A_n$ on desks $D_1, \dots, D_n$. Then we have the remaining students, $B_1, \dots, B_n$, and we assume that the initial arrangement matched them up: $(A_i, B_i)$ on desk $D_i$.

Now, we need to arrange the $B$'s, there are in total $n \times (n-1) \times \dots \times 1 = n!$ ways to do this, we want to discount the permutations in which the $i$'s line up, as these students already sat next to each other. That is, we want the number of derangements: $!n$

$$ !n = (n-1)(!(n-1) + !(n-2)) $$ Consider the case with $n=4$, then fixing the $A$'s, the remaining four students, call them $a,b,c,d$ can be seated in the following $24$ permutations:

('a', 'c', 'b', 'd')
('a', 'c', 'd', 'b')
('a', 'b', 'c', 'd')
('a', 'b', 'd', 'c')
('a', 'd', 'c', 'b')
('a', 'd', 'b', 'c')
('c', 'a', 'b', 'd')
('c', 'a', 'd', 'b')
('c', 'b', 'a', 'd')
('c', 'b', 'd', 'a')
('c', 'd', 'a', 'b')
('c', 'd', 'b', 'a')
('b', 'a', 'c', 'd')
('b', 'a', 'd', 'c')
('b', 'c', 'a', 'd')
('b', 'c', 'd', 'a')
('b', 'd', 'a', 'c')
('b', 'd', 'c', 'a')
('d', 'a', 'c', 'b')
('d', 'a', 'b', 'c')
('d', 'c', 'a', 'b')
('d', 'c', 'b', 'a')
('d', 'b', 'a', 'c')
('d', 'b', 'c', 'a')`

but of these, only the following $9$ are valid:

('c', 'a', 'd', 'b')
('c', 'd', 'a', 'b')
('c', 'd', 'b', 'a')
('b', 'a', 'd', 'c')
('b', 'c', 'd', 'a')
('b', 'd', 'a', 'c')
('d', 'a', 'b', 'c')
('d', 'c', 'a', 'b')
('d', 'c', 'b', 'a')

where we have $!0 = 1$, $!1 = 0$, $!2 = 1$, $!3 = 2$ and finally: $$ !4 = 3(!3 + !2) = 9$$