1
$\begingroup$

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:

enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here

To be continued...

$\endgroup$
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ @ 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 $\endgroup$
    – user771003
    May 18 '20 at 7:47
  • $\begingroup$ 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. $\endgroup$ May 18 '20 at 12:08
  • $\begingroup$ Well if you do that then it would be so nice :) $\endgroup$
    – user771003
    May 18 '20 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy