Two derangement problems are really confusing me a lot. Please help me.
First Problem
There are n people in the room and they are sitting on a round table. All of them went out the room and came back. When they are sitting on the same round table again, they are sitting in a certain way such that the person sitting on their right side is not the same person as before. How many ways are there to sit in this way?
To me, it sounded like Menage problem at first but found out that this is not the same problem.
At first, I thought there would be $D_n$ number of ways to sit them in the way the problem asks for. But I thought that since they are sitting on a round table, any rotations of a sitting will be counted as one case. So, I changed it to $D_{n-1}$ ways.
Am I on the right track?
Second Problem
There are $n$ pair of pieces for a necklace. For each pair, they have the same color but different letters are written on the pieces. How many ways are there to make the necklace such that any adjacent two pieces do not have the same color?
For this one, it really confuses me, but sounds really similar to the non-sexist Menage problem. How should I tackle with it?
Thank you!
Let’s get this off the unanswered list; the first problem in particular is not especially easy, so it would be nice to have an answer available.
For the first problem I will assume that we do not distinguish rotationally equivalent seating arrangements, and that the people are numbered $1$ through $n$ counterclockwise around the table in their initial arrangement. There is a bijection between possible arrangements and permutations of $\pi_1\pi_2\ldots\pi_n$ of $[n]$ such that $\pi_n=n$: we simply list the people in counterclockwise order around the table, starting with the person to the right of person $n$. Thus, we want to determine $g_n$, the number of permutations $\pi_1\pi_2\ldots\pi_n$ of $[n]$ such that $\pi_1\ne 1$, and $\pi_{k+1}\ne\pi_k+1$ for $k\in[n-1]$; I’ll call these the good permutations. It will also be useful to consider the almost good permutations, those such that $\pi_{k+1}\ne\pi_k+1$ for $k\in[n-1]$. Let $g_n$ be the number of good permutations of $[n]$ ending in $n$, $a_n$ the number of almost good permutations, and $b_n=a_n-g_n$ the number of almost good permutations such that $\pi_1=1$.
For $k\in[n-1]$ let $B_k$ be the set of bad permutations of $[n]$ ending in $n$ that are bad at position $k$, meaning that $k\in[n-1]$ and $\pi_{k+1}=\pi_k+1$. Now apply the inclusion-exclusion principle:
$$\begin{align*} \left|\bigcup_{k=1}^{n-1}B_k\right|&=\sum_{\varnothing\ne S\subseteq[n-1]}(-1)^{|J|+1}\left|\bigcap_{k\in S}B_k\right|\\ &=\sum_{k=1}^{n-1}\binom{n-1}k(-1)^{k+1}(n-1-k)!\\ &=(n-1)!\sum_{k=1}^{n-1}\frac{(-1)^{k+1}}{k!}\,, \end{align*}$$
so
$$\begin{align*} a_n&=(n-1)!-(n-1)!\sum_{k=1}^{n-1}\frac{(-1)^{k+1}}{k!}\\ &=(n-1)!\left(1+\sum_{k=1}^{n-1}\frac{(-1)^k}{k!}\right)\\ &=(n-1)!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}\\ &=D_{n-1}\,, \end{align*}$$
the $(n-1)$-st derangement number.
Suppose that $1\pi_2\ldots\pi_{n-1}n$ is an almost good permutation of $[n]$. For $k\in[n-1]$ let $\psi_k=\pi_{k+1}-1$; then $\psi_1\ldots\psi_{n-1}$ is a good permutation of $[n-1]$. Conversely, if $\psi_1\ldots\psi_{n-1}$ is a good permutation of $[n-1]$, and we set $\pi_1=1$ and $\pi_{k+1}=\psi_k+1$ for $k\in[n-1]$, then $\pi_1\ldots\pi_n$ is an almost good permutation of $[n]$ that begins with $1$. Thus, $b_n=g_{n-1}$, and
$$g_n=a_n-b_n=D_{n-1}-g_{n-1}\,.$$
By inspection $g_1=0$, so
$$\begin{align*} g_n&=D_{n-1}-b_{n-1}\\ &=D_{n-1}-D_{n-2}+g_{n-2}\\ &=D_{n-1}-D_{n-2}+D_{n-3}-g_{n-3}\\ &\;\;\vdots\\ &=\sum_{k=0}^{n-2}(-1)^kD_{n-1-k}+(-1)^{n-2}g_1\\ &=\sum_{k=0}^{n-2}(-1)^kD_{n-1-k}\\ &=(-1)^{n-1}\sum_{k=1}^{n-1}(-1)^kD_k\,.\tag{1} \end{align*}$$
(For the last step let $j=n-1-k$, so that $k=n-1-j$, rewrite the summation in terms of $j$, and then rename $j$ back to $k$.) And $D_k=k!\sum_{\ell=0}^k\frac{(-1)^\ell}{\ell!}$, so
$$\begin{align*} g_n&=(-1)^{n-1}\sum_{k=1}^{n-1}(-1)^kk!\sum_{\ell=0}^k\frac{(-1)^\ell}{\ell!}\\ &=(-1)^{n-1}\sum_{k=1}^{n-1}(-1)^k\sum_{\ell=0}^k\frac{(-1)^{k-\ell}k!}{(k-\ell)!}\\ &=(-1)^{n-1}\sum_{k=1}^{n-1}(-1)^k\sum_{\ell=0}^k(-1)^{k-\ell}k^{\underline\ell}\\ &=(-1)^{n-1}\sum_{k=1}^{n-1}\sum_{\ell=0}^k(-1)^\ell k^{\underline\ell}\\ &=(-1)^{n-1}\left(\sum_{k=0}^{n-1}\sum_{\ell=0}^k(-1)^\ell k^{\underline\ell}-1\right)\\ &=(-1)^{n-1}\sum_{\ell=0}^{n-1}\sum_{k=\ell}^{n-1}(-1)^\ell k^{\underline\ell}-(-1)^{n-1}\\ &=(-1)^{n-1}\sum_{\ell=0}^{n-1}\sum_{k=\ell}^{n-1}(-1)^\ell \frac{(k+1)^{\underline{\ell+1}}-k^{\underline{\ell+1}}}{\ell+1}+(-1)^n\\ &=(-1)^{n-1}\sum_{\ell=0}^{n-1}\frac{(-1)^\ell}{\ell+1}\sum_{k=\ell}^{n-1}\left((k+1)^{\underline{\ell+1}}-k^{\underline{\ell+1}}\right)+(-1)^n\\ &=(-1)^{n-1}\sum_{\ell=0}^{n-1}\frac{(-1)^\ell}{\ell+1}\left(n^{\underline{\ell+1}}-\ell^{\underline{\ell+1}}\right)+(-1)^n\\ &=(-1)^{n-1}\sum_{\ell=0}^{n-1}\frac{(-1)^\ell}{\ell+1}n^{\underline{\ell+1}}+(-1)^n\\ &=(-1)^{n-1}\sum_{\ell=0}^{n-1}\frac{(-1)^\ell n!}{(\ell+1)(n-1-\ell)!}+(-1)^n\\ &=(-1)^{n-1}n!\sum_{\ell=0}^{n-1}\frac{(-1)^{n-1-\ell}}{\ell!(n-\ell)}+(-1)^n\\ &=n!\sum_{\ell=0}^{n-1}\frac{(-1)^\ell}{\ell!(n-\ell)}+(-1)^n\\ &=\sum_{\ell=0}^{n-1}(-1)^{\ell}\binom{n}\ell(n-1-\ell)!+(-1)^n\,.\tag{2} \end{align*}$$
Here $k^{\underline\ell}$ is a falling factorial. Using $(1)$ or $(2)$ it is straightforward to calculate the first few values of $g_n$:
$$\begin{array}{rcc} n:&1&2&3&4&5&6&7&8&9\\ g_n:&0&0&1&1&8&36&229&1625&13208 \end{array}$$
Plugging them into OEIS, we find that this sequences is OEIS A000757. The entry also notes the following recurrences:
$$g_n=(n-3)g_{n-1}+(n-2)(2g_{n-2}+g_{n-3})\tag{3}$$
with initial values $g_0=1$ and $g_1=g_2=0$, and
$$g_n=(n-2)g_{n-1}+(n-1)g_{n-2}-(-1)^n\tag{4}$$
with $g_0=1$ and $g_1=0$. These are somewhat reminiscent of the derangement recurrences
$$D_n=(n-1)(D_{n-1}+D_{n-2})$$
and
$$D_n=nD_{n-1}+(-1)^n\,,$$
respectively.
$(3)$ can be proved as follows:
$$\begin{align*} 2g_{n-2}+g_{n-3}&=2\sum_{k=0}^{n-4}(-1)^kD_{n-3-k}+\sum_{k=0}^{n-5}(-1)^kD_{n-4-k}\\ &=2D_{n-3}+2\sum_{k=1}^{n-4}(-1)^kD_{n-3-k}+\sum_{k=0}^{n-5}(-1)^kD_{n-4-k}\\ &=2D_{n-3}-2\sum_{k=0}^{n-5}(-1)^kD_{n-4-k}+\sum_{k=0}^{n-5}(-1)^kD_{n-4-k}\\ &=D_{n-3}+\sum_{k=0}^{n-4}(-1)^kD_{n-3-k}\,, \end{align*}$$
so
$$\begin{align*} (n-3)g_{n-1}&+(n-2)(2g_{n-2}+g_{n-3})\\ &=(n-3)\sum_{k=0}^{n-3}(-1)^kD_{n-2-k}+(n-2)\left(D_{n-3}+\sum_{k=0}^{n-4}(-1)^kD_{n-3-k}\right)\\ &=(n-3)\left(\sum_{k=0}^{n-3}(-1)^kD_{n-2-k}+D_{n-3}+\sum_{k=0}^{n-4}(-1)^kD_{n-3-k}\right)\\ &\qquad+\left(D_{n-3}+\sum_{k=0}^{n-4}(-1)^kD_{n-3-k}+\right)\\ &=(n-3)\left(D_{n-2}-\sum_{k=0}^{n-4}(-1)^kD_{n-3-k}+D_{n-3}+\sum_{k=0}^{n-4}(-1)^kD_{n-3-k}\right)\\ &\qquad+\left(D_{n-3}+\sum_{k=0}^{n-4}(-1)^kD_{n-3-k}\right)\\ &=(n-3)(D_{n-2}+D_{n-3})+D_{n-3}+\sum_{k=0}^{n-4}(-1)^kD_{n-3-k}\\ &=(n-2)(D_{n-2}+D_{n-3})-D_{n-2}+\sum_{k=0}^{n-4}(-1)^kD_{n-3-k}\\ &=D_{n-1}-D_{n-2}+\sum_{k=0}^{n-4}(-1)^kD_{n-3-k}\\ &=\sum_{k=0}^{n-2}(-1)^kD_{n-1-k}\\ &=g_n\,. \end{align*}$$
And for $(4)$ we have
$$\begin{align*} (n-2)g_{n-1}&+(n-1)g_{n-2}\\ &=(n-2)\sum_{k=0}^{n-3}(-1)^kD_{n-2-k}+(n-1)\sum_{k=0}^{n-4}(-1)^kD_{n-3-k}\\ &=(n-2)D_{n-2}-(n-2)\sum_{k=0}^{n-4}(-1)^kD_{n-3-k}+(n-1)\sum_{k=0}^{n-4}(-1)^kD_{n-3-k}\\\\ &=(n-2)D_{n-2}+\sum_{k=0}^{n-4}(-1)^kD_{n-3-k}\\ &=(n-1)D_{n-2}-\sum_{k=0}^{n-3}(-1)^kD_{n-2-k}\\ &=D_{n-1}-(-1)^{n-1}-\sum_{k=0}^{n-3}(-1)^kD_{n-2-k}\\ &=(-1)^n+\sum_{k=0}^{n-2}(-1)^kD_{n-1-k}\\ &=(-1)^n+g_n\,. \end{align*}$$
The second problem is just a slightly disguised version of the relaxed ménage problem, which has a solution here. In that solution the justification of the formula
$$d_k=\frac{2n}{2n-k}\binom{2n-k}k\tag{5}$$
is left to the reader; the answer to this question gives one argument.
Alternatively, in the context of the version at the link one can avoid the computation in that argument by noting that there are $\binom{2n-k}k$ ways to line up $2n-k$ entities comprising $k$ couples and $2n-2k$ single individuals. There are then $2n$ ways to decide in which seat the first person in that line sits, so there are $2n\binom{2n-k}k$ ways to line up the $2n-k$ entities and then assign them to seats at the table. (Here we are not distinguishing the two members of a couple.) However, each possible seating can be broken open into a line at any of $2n-k$ places, so each possible seating is counted $2n-k$ times. The total number distinct seatings is therefore given by $(5)$.
Note that the linked solution distinguishes seatings that are equivalent under rotation; it must be divided by $2n$ if necklaces that are equivalent under rotation are considered identical.