出会いの番号

組み合わせ論において、rencontres 数は、特定の数の固定点を持つ集合 { 1, ..., n }の順列を列挙する整数の三角形配列です。言い換えれば、部分的な順列です。（Rencontreはフランス語で「出会い」を意味します。この問題は、ソリティアゲームにちなんで名付けられたという説もあります。）n ≥ 0 かつ 0 ≤ k ≤ nの場合、rencontres 数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 ≤ nの場合、i番目のモーメントはi番目のベル数、つまりサイズiの集合の分割数です。       

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

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