家庭の問題

組み合わせ数学において、メナージュ問題（ménage problem）またはメナージュ問題（problème des ménages）とは、男女のカップルを円形の食卓に座らせる際に、男女が交互に座り、誰もパートナーの隣に座らないようにする方法の数を求める問題である。（メナージュはフランス語で「家族」を意味し、ここでは男女のカップルを指す。）この問題は、1891年にエドゥアール・リュカによって、そしてそれより数年前にピーター・ガスリー・テイトによって結び目理論に関連して独立に定式化された。^{[ 1 ]}カップルの数が3、4、5、…の場合、座席配置の数は

12、96、3120、115200、5836320、382072320、31488549120、... （ OEISの配列A059375）。

数学者たちは、これらの数や関連する数列を計算するための公式や漸化式を開発してきた。これらの数は、礼儀作法や結び目理論への応用だけでなく、グラフ理論的な解釈も持ち合わせている。つまり、特定のグラフ族におけるマッチングやハミルトン閉路の数を数えるのである。

M _nをn組のカップルの座席配置の数とする。Touchard (1934)は次の式を導出した。

${\displaystyle M_{n}=2\cdot n!\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(nk)!.}$

その後、この公式の別の証明や、この問題の様々な一般化バージョンに関する研究が数多く行われた。

第一種チェビシェフ多項式を含むM _nの異なる陰影公式は、 Wyman & Moser (1958)によって与えられた。

女性の座席配置方法は 2× n !通りあります。女性のために配置できる座席のセットは 2 組あり、特定の座席セットに女性を座らせる方法はn ! 通りあります。女性の各座席配置について、

${\displaystyle A_{n}=\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(nk)!}$

男性を座らせる方法。この式は、トゥシャールの式から 2× n ! の係数を単純に省略したものです。結果として得られるより小さな数 (ここでもn  =  3から開始)、

1、2、13、80、579、4738、43387、439792、... （ OEISのシーケンスA000179）

これらはメナージュ数と呼ばれます。${\displaystyle {\frac {2n}{2n-k}}{2n-k \choose k}}$は、隣接する座席のk組の重ならないペアを形成する方法の数、または同等に、 2 n個の頂点を持つサイクルグラフにおけるk個のエッジのマッチングの数です。 A _nの式は、マッチングの各エッジの端点に座る人がカップルである必要がある配置に包含排除の原理を適用することによって直接得られる結果です。

ボガートとドイル（1986）の研究までは、メナージュ問題の解決策は、まず女性のすべての座席配置を見つけ、次にこれらの部分的な座席配置のそれぞれについて、男性をパートナーから離して座らせることでそれを完成させる方法の数を数えるという形をとっていた。ボガートとドイルは、トゥシャールの公式は女性の参加を除外するのではなく、すべての座席配置を一度に考慮することによって直接導き出せると主張した。^{[ 2 ]}しかし、キロシスとコントゲオルギウ（2018）は、ボガートとドイルのアイデアをいくつか利用して（ただし、議論を性別にとらわれない言葉で書き直すことに注意を払って）、上記で説明したさらに単純な女性優先の解決策を見つけた。

メナージュ数は漸化式^{[ 3 ]を満たす。}

${\displaystyle A_{n}=nA_{n-1}+{\frac {n}{n-2}}A_{n-2}+{\frac {4(-1)^{n-1}}{n-2}}}$

そしてより単純な4項の漸化式^{[ 4 ]}

${\displaystyle \displaystyle A_{n}=nA_{n-1}+2A_{n-2}-(n-4)A_{n-3}-A_{n-4},}$

そこから、メナージュの数値自体を簡単に計算できる。

メナージュ問題の解は、グラフ理論の観点から、クラウングラフにおける有向ハミルトン閉路として解釈できます。クラウングラフは、完全二部グラフK _n,nから完全マッチングを取り除くことによって形成されます。2 n個の頂点が2 色で表され、一方の色の頂点は、もう一方の色の頂点のうち 1 つを除くすべてに接続されています。メナージュ問題の場合、グラフの頂点は男性と女性を表し、辺は隣同士に座ることが許されている男性と女性のペアを表します。このグラフは、すべての男性とすべての女性を接続する完全二部グラフから、男性と女性のカップルによって形成される完全マッチングを取り除くことによって形成されます。有効な座席配置は、テーブルを囲む人々の順番によって記述でき、これはグラフ内でハミルトン閉路を形成します。しかし、2つのハミルトン閉路は、開始頂点に関係なく同じ頂点を同じ巡回順序で接続する場合、同等とみなされます。一方、メナージュ問題では開始位置が重要視されます。アリスのお茶会のように、すべての客が1席ずつ移動した場合、同じ閉路で記述されていても、異なる座席配置とみなされます。したがって、クラウングラフにおける向き付けられたハミルトン閉路の数は、座席配置の数より2n倍少なく^{[ 5 ]} 、メナージュ数より( n - 1)!倍多くなります。これらのグラフにおける閉路の数列（前述と同様にn = 3から開始）は次のようになります。    

2、12、312、9600、416880、23879520、1749363840、... （ OEISの配列A094047）。

この問題のグラフ理論的な記述は、もう 2 つ目の方法も可能です。女性が着席した後、残りの男性の可能な座席配置は、完全二部グラフから単一のハミルトン閉路を取り除いて形成されるグラフにおける完全マッチングとして記述できます。このグラフには、空席と男性を結ぶ辺があり、閉路の除去は、男性が妻の隣の空席のどちらにも座ることを禁じることに相当します。二部グラフにおけるマッチングの数え方の問題、したがって、メナージュ数を計算する問題は、特定の0-1 行列のパーマネントを使用して解決できます。メナージュ問題の場合、この問題のこの見方から生じる行列は、生成行の隣接する 2 つの要素を除くすべての要素が 1 に等しい巡回行列です。 ^{[ 6 ]}

テイトがメナージュ問題を研究する動機は、与えられた交点の数( nなど) を持つ数学的結び目の完全なリストを見つけようとしたことから生じた。結び目図のダウカー記法 (テイトが初期の形で使用)では、結び目が連続して自身と交差する2 n個の点に、 1 から 2 nまでの 2 n個の数字がラベル付けされる。縮小図では、交点の 2 つのラベルは連続できないため、結び目を表すためにダウカー記法で使用される各交点のラベルのペアのセットは、1 から 2 nまでの範囲のすべての数に対応する頂点と、パリティが異なり、法2 nに関して連続しないすべての数のペア間のエッジを持つグラフの完全マッチングとして解釈できる。このグラフは、完全な二部グラフ（偶奇性が異なるすべての数のペアを結ぶグラフ）からハミルトン閉路（連続する数を結ぶグラフ）を取り除くことによって形成されるため、マッチングの数はメナージュ数に等しくなります。交代結び目の場合、このマッチングだけで結び目図自体を記述できます。その他の結び目の場合、交差する2本の鎖のうちどちらがもう一方の鎖の上にあるかを判断するために、各交差ペアに追加の正または負の符号を指定する必要があります。

しかし、結び目リスト問題には、メナージュ問題にはない追加の対称性があります。異なる交点からラベル付けを開始すると、同じ結び目図に対して異なるダウカー表記が得られ、これらの異なる表記はすべて同じ図を表しているとみなされます。このため、巡回置換によって互いに異なる2つのマッチングは同等として扱われ、1回だけカウントされます。ギルバート（1956）はこの修正された列挙問題を解き、異なるマッチングの数は

1、2、5、20、87、616、4843、44128、444621、... （ OEISの配列A002484）。

• オーバーヴォルファッハ問題とは、食事をする人のテーブル配置に関する別の数学的問題である。
• Problème des rencontres、部分的な錯乱を伴う同様の問題

• ワイススタイン、エリック・W.、「夫婦問題」、MathWorld
• ワイススタイン、エリック・W.、「ライザントの漸化式」、MathWorld