# 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...

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

• @ Will Orrick,First of all thank you so much for your work (+1),I have some questions,do these couples sit around a circular table? besides does Lucas give a full explanation about how to derive the formula $$\lambda_{n+1}=(n-2)\lambda_n+(n-1)\mu_n+\nu_n+\rho_n.$$? I tried to understand,but it looks difficult
– user771003
May 18 '20 at 7:47
• Yes, it's a circular table. (So the last blank is adjacent to both $W_n$ and $W_1$.) I wouldn't say Lucas's explanation is "full", but it is more detailed than what I've included. Did you follow where the $(n-2)\lambda_n$ term comes from on the right? The explanation of the other three terms is similar. I can try to add it if needed. May 18 '20 at 12:08
• Well if you do that then it would be so nice :)
– user771003
May 18 '20 at 12:29