2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What do you want to know? The number of way to do so (do you count the position of each student, or just the couple by desk)? Why the desks need to be fixed? $\endgroup$ – Netchaiev Feb 1 '18 at 10:45
  • $\begingroup$ @Netchaiev yes that's what I want to know. I don't know why, the problems states so.. $\endgroup$ – Collapse Feb 1 '18 at 10:48
  • $\begingroup$ Does it matter if they are sitting on desk 1 or desk 2? do you count student A and student B sitting together on two different tests as different ? $\endgroup$ – dimebucker Feb 1 '18 at 10:50
  • $\begingroup$ @dimebucker91 I'm really not sure about that, it's a problem from an older test and I'm not sure myself, seeing as it says specifically that the desks are in fixed positions I would assume it matters and that if $A$ and $B$ were together on one desk before they can't be together on any desks now.. $\endgroup$ – Collapse Feb 1 '18 at 10:52
  • $\begingroup$ Just to be sure, if we count the different desks and sits, for 4 students, there are 4 ways to do so? $\endgroup$ – Netchaiev Feb 1 '18 at 10:52
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It is not a simple derangement, A(i) paired with A(j) is also a mismatch. $\endgroup$ – true blue anil Feb 1 '18 at 14:19
  • $\begingroup$ I'm not really sure that's it, the first step where you fix $A_1 ... A_n$ is what's bothering me. Those students might've been those who sat on the first $n/2$ desks before and therefore none of them sat with any $B_1,...,B_n$ before..? $\endgroup$ – Collapse Feb 1 '18 at 16:38

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.