French book translation related to Ménage problem I was reading about menage problem till I found the following formula:
$$M_n=2(n!)U_n$$
Where $M_n$ denotes the menage numbers and $U_n$ is the number of ways of seating men.
It's known that :
$$(n-2)U_n= n(n − 2)U_{n−1} + nU_{n−2} + 4(−1)^{n+1}\tag{I}$$
The formula $\text($I$)$ is proved in the book Théorie des nombres by Lucas, Edouard (1842-1891).
Unfortunately the book is in French and I could not find any English version of this book,on the other hand it looks that the only source that gives a proof of $\text($I$)$ is this book.
If someone has an English version please let me know,besides here are the pages that I'm going to learn,it would be highly appreciated if someone help me:






To be continued...
 A: Lucas sets the problem up by situating the wives in numerical order
$$
W_1\ \_\_\ W_2\ \_\_\ W_3\ \_\_\ \ldots\ W_n\ \_\_
$$
with the blanks to be filled by the husbands, $H_1,\ H_2,\ \ldots,\ H_n$. The last blank, of course, is considered to be adjacent to $W_1$.
Lucas defines four quantities:


*

*$\lambda_n$ is the number of ways of placing the husbands so that $H_j$ is not adjacent to $W_j$ for any $j$;

*$\mu_n$ is the number of ways of placing the husbands such that $H_1$ is in the last slot (and hence adjacent to $W_1$), but for all $j\ne1$ it is the case that $H_j$ is not adjacent to $W_j$;

*$\nu_n$ is the number of ways of placing the husbands so that exactly one husband is adjacent to his wife, but excluding placements where either $H_1$ or $H_n$ is in the last slot or $H_1$ is in the first slot;

*$\rho_n$ is the number of ways of placing the husbands so that $H_1$ is in the last slot (and hence adjacent to $W_1$) and exactly one other husband is also placed adjacent to his wife.


Lucas then derives the formula
$$
\lambda_{n+1}=(n-2)\lambda_n+(n-1)\mu_n+\nu_n+\rho_n.
$$
He does this by extending each of the placements counted by $\lambda_n$, $\mu_n$, $\nu_n$, and $\rho_n$ by putting newcomers $W_{n+1}$ and $H_{n+1}$ at the right,
$$
W_1\ \_\_\ W_2\ \_\_\ W_3\ \_\_\ \ldots\ W_n\ \_\_\ W_{n+1}\ H_{n+1}
$$
and then counting the ways of swapping $H_{n+1}$ with some other $H_j$ to produce a valid placement.


*

*The factor $n-2$ in front of $\lambda_n$ comes about by noticing that $H_{n+1}$ may be swapped with any husband except for $H_1$ or the husband to the right of $W_n$.

*The factor $n-1$ in front of $\mu_n$ arises because $H_{n+1}$ may be swapped with any husband except $H_1$.

*The term $\nu_n$ comes about, with coefficient $1$, because $H_{n+1}$ must be swapped with the husband who is next to his own wife.

*The term $\rho_n$ comes about similarly: $H_1$ is no longer adjacent to $W_1$ because $W_{n+1}$ and $H_{n+1}$ have been interposed. There was one other husband next to his own wife, who now gets swapped with $H_{n+1}$.


For this to be a proof one must argue that all valid arrangements are obtained in this way, exactly once. Lucas doesn't go into detail about this, but I think the way to argue it is to start with a valid arrangement of $n+1$ couples and have $W_{n+1}$ and $H_{n+1}$ depart, leaving two empty chairs. The husband in the chair to the right of the chair in which $W_{n+1}$ sat is moved to the chair in which $H_{n+1}$ sat, and the two now-empty chairs to the left of $W_1$ are removed. We must show that we inevitably get one of the arrangements counted by $\lambda_n$, $\mu_n$, $\nu_n$, or $\rho_n$. The insertion process described previously will then be the inverse of the deletion process just described.
I think this is clear, however. The only places in which possible defects might occur are in the chair to the left of $W_1$ and in the chair that previously contained $H_{n+1}$, which accords with the four cases describing $\lambda_n$, $\mu_n$, $\nu_n$, and $\rho_n$. The only thing that can go wrong in the chair to the left of $W_1$ is that $H_1$ might have been sitting there. (He would previously have been adjacent to $W_n$ and $W_{n+1}$ but would now be adjacent to $W_n$ and $W_1$.) The only slightly complicated thing to understand is the conditions placed on $\nu_n$. The condition that $H_1$ not occupy the chair to the left of $W_1$ is there so that the $\nu_n$ cases don't overlap with the $\mu_n$ cases. The condition that $H_n$ not occupy the chair to the left of $W_1$ (and hence to the right of $W_n$) would never arise as the result of removing $W_{n+1}$ and $H_{n+1}$ from a valid configuration in the manner described. Finally, the condition that $H_1$ not occupy the chair to the right of $W_1$ is needed because the defect is assumed to have arisen by moving the husband previously sitting to the left of $W_1$ in a valid arrangement, and this husband could not have been $H_1$.
Lucas then switches to the equivalent problem of placing $n$ non-attacking rooks on an $n\times n$ chessboard subject to the condition that no rook occupy certain excluded squares (marked with an $\times$):
$$
\begin{array}{cccccccc}
\cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \times & \times\\
\cdot & \cdot & \cdot & \cdot & \cdot & \times & \times & \cdot\\
\cdot & \cdot & \cdot & \cdot & \times & \times & \cdot & \cdot\\
\cdot & \cdot & \cdot & \times & \times & \cdot & \cdot & \cdot\\
\cdot & \cdot & \times & \times & \cdot & \cdot & \cdot & \cdot\\
\cdot & \times & \times & \cdot & \cdot & \cdot & \cdot & \cdot\\
\times & \times & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot\\
\times & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \times
\end{array}
$$
Placements counted by $\mu_n$, $\nu_n$, and $\rho_n$ correspond to boards in which rooks occupy particular disallowed squares.  By using the two operations of


*

*deleting a row and the corresponding column, and

*performing a cyclic permutation of rows and the corresponding cyclic permutation of columns,


Lucas relates certain sets of boards to one another so as to deduce the three relations
\begin{align*}
\mu_n&=\lambda_{n-1}+\mu_{n-1}\\
\nu_n&=(2n-3)\mu_n\\
\rho_n&=(2n-3)\mu_{n-1}+\rho_{n-1}.
\end{align*}
I have not checked this part in detail. The second of these equations may be used to eliminate $v_n$ from the equation for $\lambda_{n+1}$:
$$
\lambda_{n+1}=(n-2)\lambda_n+(3n-4)\mu_n+\rho_n.
$$
Subtracting from this equation the same equation with $n$ replaced by $n-1$ and using the equation for $\rho_n$ gives
$$
\lambda_{n+1}-\lambda_n=(n-2)\lambda_n-(n-3)\lambda_{n-1}+(3n-4)\mu_n-(3n-7)\mu_{n-1}+(2n-3)\mu_{n-1}.
$$
Simplifying, and using the equation for $\mu_n$ to eliminate $\mu_{n-1}$ gives
$$
\lambda_{n+1}=(n-1)\lambda_n-\lambda_{n-1}+2n\mu_n.
$$
Replace $n$ in this equation with $n-1$ and multiply the resulting equation by $n$ to get
$$
n\lambda_n=n(n-2)\lambda{n-1}-n\lambda_{n-2}+2n(n-1)\mu_{n-1}.
$$
Subtract this from the original equation multiplied by $n-1$ to get
$$
(n-1)\lambda_{n+1}-n\lambda_n=(n-1)^2\lambda_n-n(n-2)\lambda_{n-1}-(n-1)\lambda_{n-1}+n\lambda_{n-2}+2n(n-1)(\mu_n-\mu_{n-1}),
$$
which simplifies to
$$
(n-1)\lambda_{n+1}=(n^2-n+1)(\lambda_n+\lambda_{n-1})+n\lambda_{n-2}.
$$
This can be rewritten as
$$
(n-1)\lambda_{n+1}-(n-1)(n+1)\lambda_n-(n+1)\lambda_{n-1}=-[(n-2)\lambda_n-(n-2)n\lambda_{n-1}-n\lambda_{n-2}].
$$
This is a recurrence of the form $A_{n+1}=-A_n$, which has solution $A_{n+1}=K(-1)^n$ for some constant $K$. We obtain
$$
(n-1)\lambda_{n+1}-(n-1)(n+1)\lambda_n-(n+1)\lambda_{n-1}=K(-1)^n.
$$
Using the initial conditions $\lambda_2=0$, $\lambda_3=1$, $\lambda_4=2$, one finds that $K=4$.
