26. («The Problem of Married Couples».) In how many ways can $n$ married couples ( $n \geqslant 3$ ) be seated at a round table so that men and women alternate, but spouses do not sit next to each other?
Solution. Let us assign numbers $1, \ldots, 2n$ (clockwise) to the seats around the table, and let a woman sit at seat 1 for definiteness. Let $A_k$ be the event that seats $k$ and $k+1$ are occupied by a certain married couple ($1 \leqslant k \leqslant 2n$ and seat $2n+1$ is identified with seat 1). Then the required probability that no spouses occupy adjacent seats is $\mathrm{P}\left(\bigcap_{k=1}^{2n} \bar{A}_{k}\right)$. By the inclusion-exclusion principle (see problem I.1.12(b))

$$
\mathrm{P}\left(\bigcap_{k=1}^{2n} \bar{A}_{k}\right)=1-\mathrm{P}\left(\bigcup_{k=1}^{2n} A_{k}\right)=1-\sum_{i} \mathrm{P}\left(A_{i}\right)+\sum_{i<j} \mathrm{P}\left(A_{i} \cap A_{j}\right)-\ldots
$$

Calculations show that for $1 \leqslant i \leqslant 2n$ we have

$$
\mathrm{P}\left(A_{i}\right)=n\left(\frac{(n-1)!}{n!}\right)^{2}
$$

for $1 \leqslant i<j \leqslant 2n$ the equality holds

$$
\mathrm{P}\left(A_{i} \cap A_{j}\right)= \begin{cases}n(n-1)\left(\frac{(n-2)!}{n!}\right)^{2}, & \text { if }|i-j| \neq 1 \\ 0, & \text { if }|i-j|=1\end{cases}
$$

where $\mathrm{P}\left(A_{1} \cap A_{2n}\right)=0$, and generally for $i_{1}<\ldots<i_{k}$ we have

$$
\begin{aligned}
& \mathrm{P}\left(A_{i_{1}} \cap \ldots \cap A_{i_{k}}\right)= \\
& = \begin{cases}\frac{n!}{(n-k)!}\left(\frac{(n-k)!}{n!}\right)^{2}, & \text { if }\left|i_{j+1}-i_{j}\right| \geqslant 2 \text { for } 1 \leqslant k \leqslant k \\
0 & \text { and } 2n+i_{1}-i_{k} \geqslant 2, \\
0 & \text { in other cases. }\end{cases}
\end{aligned}
$$

Thus, the required probability is

$$
\mathrm{P}\left(\bigcap_{k=1}^{2n} \bar{A}_{k}\right)=\sum_{k=0}^{n}(-1)^{k} \frac{(n-k)!}{n!} d_{n}^{k}
$$

where $d_{n}^{k}$ is the number of ways to choose $k$ different pairs of seats, i.e., such that if $\left(i_{1}, i_{2}\right)$ and $\left(i_{3}, i_{4}\right)$ are any two pairs, they have no common elements $\left(\left\{i_{1}, i_{2}\right\} \cap\left\{i_{3}, i_{4}\right\}=\varnothing\right)$. Let us calculate $d_{n}^{k}$.

Suppose in the sequence $1, \ldots, 2n$, where 1 and $2n$ are considered neighbors, $k$ pairs of neighbors are fixed. Replace these pairs with blue balls, and the remaining elements with white balls. We get $k$ blue and $2n-2k$ white balls. Let us count the number of ways to arrange $k$ blue and $2n-2k$ white balls in a circle.

Arrange $2n-2k$ white balls in a circle and choose one white ball as the first. Blue balls can be placed between the white balls in any number. By problem I.1.6(c), this can be done in $C_{(2n-2k)+k-1}^{k}=C_{2n-k-1}^{k}$ ways.

Since the white balls are indistinguishable and we have fixed one of them, each arrangement is counted $2n-2k$ times, so the total number of circular arrangements of $k$ blue and $2n-2k$ white balls is

$$
C_{2n-k-1}^{k} \frac{1}{2n-2k}=C_{2n-k}^{k} \frac{1}{2n-k}
$$

Perform the reverse transformation: replace the blue balls with a pair of elements, the white balls with one element, and choose one element to be considered the first (this can be done in $2n$ ways). We get

$$
d_{n}^{k}=C_{2n-k}^{k} \frac{2n}{2n-k}
$$

Substituting the obtained value of $d_{n}^{k}$ into formula (*), we get that the probability that no married couple occupies adjacent seats is

$$
\frac{1}{n!} \sum_{k=0}^{n}(-1)^{k}(n-k)!\frac{2n}{2n-k} C_{2n-k}^{k}
$$