出会いの番号

組合せ論において、ランコントル数は、指定された数の固定点 を持つ集合 { 1, ...,  n } の順列、つまり部分的な混同を列挙する整数の三角形配列です。(ランコントルはフランス語で出会いを意味します。一説によると、この問題はソリティアゲームにちなんで名付けられています。) n  ≥ 0 および 0 ≤ k  ≤  nの場合、ランコントル数D _{n ,  k}は、正確にk 個の固定点 を持つ{ 1, ...,  n } の順列の数です。

たとえば、7 つのプレゼントが 7 人の異なる人に贈られ、正しいプレゼントを受け取る運命にあるのは 2 人だけの場合、この状況が発生する可能性はD _{7, 2}  = 924 通りあります。よく引用される別の例は、7 組のカップルがいるダンス スクールで、ティーブレイク後に参加者に、続けるパートナーをランダムに見つけるように指示すると、再び、以前の 2 組のカップルが偶然に再会する可能性はD _{7, 2}  = 924 通りあります。

この配列の始まりは次のとおりです ( OEISのシーケンスA008290 )。

k  = 0の列の数字は異常を列挙する。つまり

${\displaystyle D_{0,0}=1,\!}$

${\displaystyle D_{1,0}=0,\!}$

${\displaystyle D_{n+2,0}=(n+1)(D_{n+1,0}+D_{n,0})\!}$

負でないnに対しては、

${\displaystyle D_{n,0}=\left\lceil {\frac {n!}{e}}\right\rfloor ,}$

ここで、比率はn が偶数の場合は切り上げられ、 nが奇数の場合は切り捨てられます。n  ≥ 1 の場合、最も近い整数が得られます。

より一般的には、任意の に対して、 ${\displaystyle k\geq 0}$

${\displaystyle D_{n,k}={n \choose k}\cdot D_{nk,0}.}$

乱れを列挙する方法がわかれば、証明は簡単です。n から k 個の固定点を選択し、次に他のn  −  k個の点の乱れを選択します。

数D _{n ,0} /( n !)は、 e ^{− z} /(1 − z )のべき級数によって生成される。したがって、 D _{n ,  m}の明示的な式は次のように導出できる。

${\displaystyle D_{n,m}={\frac {n!}{m!}}[z^{nm}]{\frac {e^{-z}}{1-z}}={\frac {n!}{m!}}\sum _{k=0}^{nm}{\frac {(-1)^{k}}{k!}}.}$

これは、

${\displaystyle D_{n,m}={n \choose m}D_{nm,0}\;\;{\mbox{ および }}\;\;{\frac {D_{n,m}}{n!}}\approx {\frac {e^{-1}}{m!}}}$

nは大きく、m は固定です。

「数値」の表の各行のエントリの合計は、{1, ..., n }の順列の総数であり  、したがってn ! です。n行目のエントリすべてをn ! で割ると、{1, ..., n }の 一様分布ランダム順列の固定点の数の確率分布が得られます 。固定点の数がkである確率は、

${\displaystyle {D_{n,k} \over n!}.}$

n ≥ 1の場合 、固定点の期待数は 1 です (期待値の線形性から導かれる事実)。

より一般的には、i  ≤  nの場合、この確率分布のi番目のモーメントは、期待値が 1 であるポアソン分布のi番目のモーメントです。 ^[1] i  >  n の場合、i番目のモーメントはそのポアソン分布の i 番目のモーメントよりも小さくなります。具体的には、i  ≤  nの場合、i番目のモーメントはi番目のベル数、つまりサイズiの集合の分割数です。

順列集合のサイズが大きくなるにつれて、

${\displaystyle \lim _{n\to \infty}{D_{n,k} \over n!}={e^{-1} \over k!}.}$

これは、期待値が 1 であるポアソン分布のランダム変数がkに等しい確率です。言い換えると、n が大きくなるにつれて、サイズnのセットのランダム順列の固定点の数の確率分布は、期待値が 1 であるポアソン分布に近づきます。

• オーバーヴォルフアッハ問題、テーブルに食事をする人の配置に関する別の数学の問題
• Problème des ménages、部分的な錯乱を伴う同様の問題

• リオダン、ジョン、「組合せ分析入門」、ニューヨーク、ワイリー、1958年、57、58、65ページ。
• ワイスタイン、エリック・W.「部分的錯乱」。マスワールド。