Partition the set $\{1,2,\ldots, 2n\}$ into $n$ subsets of size 2, such that each pair differs by 1 or $n$.

Question

Encountered this problem in a textbook - find the number of ways to partition the set $\{1,2,\ldots, 2n\}$ into $n$ subsets of size 2, such that each pair differs by 1 or $n$. I wasn't too sure how to proceed - initially, I tried to count all the ways to partition $2n$ elements into $n$ subsets of size 2, and subtract the cases that don't differ by 1 or $n$. This proved to be very tedious/basically impossible to calculate. Any ideas?

Answer 1

Imagine a $2 \times n$ rectangular grid, filled with the numbers $\{1,2,...2n\}$ as shown below:

$$ \begin{array}{|c|c|c|c|c|c|} \hline 1 & 2 & 3 & \cdots & n-1 & n \\ \hline n+1 & n+2 & n+3 & \cdots & 2n-1 & 2n \\ \hline \end{array} $$

Notice that numbers that differ by $n$ are vertically aligned. Thus the subsets being chosen have to consist of either a horizontally adjacent or vertically adjacent pair. The problem then is akin (almost! see note at the end) to tiling a $2 \times n$ rectangular grid with dominoes; this is a well-known problem for which the solutions are the Fibonacci numbers.

Seeing why this is the case is easy by induction. Let the number of tilings for a $2 \times n$ rectangle be $t_n$. Clearly when $n=1$ and $n=2$, there are only one and two ways to tile the rectangle, respectively; so $t_1 = 1$ and $t_2 = 2$.

Now take a $2 \times n$ rectangle, $n>2$, and consider the rightmost squares. They can only be covered two ways, either with one vertical domino or two horizontal dominoes. In the former case, the remaining $2 \times (n-1)$ rectangle can, by the induction hypothesis, be covered in $t_{n-1}$ ways; and in the latter, the remaining $2 \times (n-2)$ rectangle can, by the induction hypothesis, be covered in $t_{n-2}$ ways. So $t_n = t_{n-1} + t_{n-2}$. Combining this with the base cases proves $t_n = F_n$ (if you start at $F_{\small 0} = 1$) or $F_{n+1}$ (if you start at $F_{\small 0} = 0$).

However, there is one situation (thanks @Zoe H for noticing) that is not covered by the rectangular grid scenario. If $n$ is odd, it is possible for $n$ and $n+1$ to be paired; luckily (and this is easy to see by checking the grid) this forces all pairs to be ones that differ by $1$, so it only adds a single additional case (except when $n = 1$, for which they're the same)(thanks @BrianHopkins).

Thus the final answer is: $F_1$ when $n=1$, $F_n$, if $n$ is even, and $F_n+1$, if $n \ge 3$ is odd.