ランダム順列統計

ランダム順列の統計、たとえばランダム順列のサイクル構造は、アルゴリズム、特にランダム順列を操作するソート アルゴリズムの解析において基本的に重要です。たとえば、ランダム順列のランダムな要素を選択するためにクイックセレクト(クイックソートの親戚) を使用するとします。クイックセレクトは、ピボットに従って配列を分割するため、配列の部分的なソートを実行します。したがって、クイックセレクトの実行後は順列の無秩序性が低くなります。残る無秩序性の量は、生成関数を使用して分析できます。これらの生成関数は、基本的にランダム順列統計の生成関数に依存します。したがって、これらの生成関数を計算することは極めて重要です。

ランダム順列に関する記事には、ランダム順列の概要が記載されています。

基本的な関係

順列はラベル付き閉路の集合である。フラジョレ・セジウィック基本定理のラベ​​ル付きの場合を用いて、順列の集合と単集合について書くと、 ${\displaystyle \scriptstyle {\mathcal {P}}}$ ${\displaystyle \scriptstyle {\mathcal {Z}}}$

${\displaystyle \operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}}))={\mathcal {P}}.}$

指数生成関数（EGF） に翻訳すると、

${\displaystyle \exp \left(\log {\frac {1}{1-z}}\right)={\frac {1}{1-z}}}$

ここで、順列の組み合わせ種（n個の要素のn !個の順列がある） のEGFは

${\displaystyle \sum _{n\geq 0}{\frac {n!}{n!}}z^{n}={\frac {1}{1-z}}.}$

この1つの方程式から、多数の順列統計量を導くことができます。まず、 から項、つまり exp を省くことで、順列に含まれるサイクルの数を制限できます。例えば、EGF を に制限することで、2つのサイクルを含む順列が得られます。次に、ラベル付きサイクルの EGF、つまり の は、 ラベル付きサイクルがk ! /  k 個あるため、 となることに注意してください。つまり、この生成関数から項を省くことで、順列に発生するサイクルのサイズを制限し、特定のサイズのサイクルのみを含む順列の EGF を得ることができます。 ${\displaystyle \scriptstyle \operatorname {SET} }$ ${\displaystyle \scriptstyle \operatorname {SET} _{2}}$ ${\displaystyle \scriptstyle \operatorname {CYC} ({\mathcal {Z}})}$ $${\displaystyle \sum _{k\geq 1}{\frac {(k-1)!z^{k}}{k!}}=\sum _{k\geq 1}{\frac {z^{k}}{k}}=\log {\frac {1}{1-z}}}$$

サイクルを除去・選択する代わりに、異なるサイズのサイクルに異なる重みを与えることもできます。サイクルの サイズkのみに依存する重み関数を とすると、簡潔に次のように書きます。${\displaystyle b:\mathbb {N} \rightarrow \mathbb {R} }$

${\displaystyle b(\sigma )=\sum _{c\in \sigma }b(c),}$

順列のbの値をサイクル上の値の合計と定義すると、長さkのサイクルをu ^{b ( k )}でマークし、2変数生成関数を得る ことができる。${\displaystyle \sigma }$

${\displaystyle g(z,u)=1+\sum _{n\geq 1}\left(\sum _{\sigma \in S_{n}}u^{b(\sigma )}\right){\frac {z^{n}}{n!}}=\exp \sum _{k\geq 1}u^{b(k)}{\frac {z^{k}}{k}}}$

これは「混合」母関数である。つまり、 zについては指数母関数であり、二次パラメータuについては通常の母関数である。u  = 1 で微分して評価すると、次のようになる。

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}}=\sum _{n\geq 1}\left(\sum _{\sigma \in S_{n}}b(\sigma )\right){\frac {z^{n}}{n!}}}$

これはbの期待値の確率生成関数です。言い換えれば、このべき級数における の係数は、 の各順列が同じ確率 で選択されると仮定した場合の、における順列におけるbの期待値です。 ${\displaystyle z^{n}}$ ${\displaystyle S_{n}}$ ${\displaystyle 1/n!}$

この記事では、形式的冪級数のページで説明されている係数抽出演算子 [ z ⁿ ] を使用します。

反転順列の数

反転とは、σ の置換であり、置換合成のもとで σ ² = 1 となる。したがって、σ は長さ 1 または 2 の閉路のみを含むことができる。つまり、これらの置換の指数生成関数 g ( z ) は^{[1]である。}

${\displaystyle g(z)=\exp \left(z+{\frac {1}{2}}z^{2}\right).}$

_{これは、順列}σ∈Sn間の反転の 総数を表す明示的な式を与える：^[1]${\displaystyle I(n)}$

${\displaystyle I(n)=n![z^{n}]g(z)=n!\sum _{a+2b=n}{\frac {1}{a!\;2^{b}\;b!}}=n!\sum _{b=0}^{\lfloor n/2\rfloor }{\frac {1}{(n-2b)!\;2^{b}\;b!}}.}$

n !で割ると、ランダム順列が反転である確率が得られます。これらの数は電話番号として知られています。

順列の数メートル統一の根源

これは反転の概念を一般化したものである。m乗根はσの置換であり、置換合成においてσ ^m = 1となる。σを適用するたびに、そのすべてのサイクルに沿って1ステップずつ並行に進む。長さdのサイクルをd回適用すると、 d個の元（d個の固定点）上の恒等置換が生成され、 dはそれを実現する最小の値である。したがって、mはすべてのサイクルサイズdの倍数でなければならない。つまり、可能なサイクルは長さdがmの約数となるものだけである。したがって、これらの置換の EGF g ( x )は

${\displaystyle g(z)=\exp \left(\sum _{d\mid m}{\frac {z^{d}}{d}}\right).}$

m = p （pは素数）のとき、これは次のように単純化される。

${\displaystyle n![z^{n}]g(z)=n!\sum _{a+pb=n}{\frac {1}{a!\;p^{b}\;b!}}=n!\sum _{b=0}^{\lfloor n/p\rfloor }{\frac {1}{(n-pb)!\;p^{b}\;b!}}.}$

正確に順序の順列の数け

これはメビウス反転によって行うことができます。前回と同じ概念を用いると、kを割り切る順列の組み合わせ種は次のように与えられます。 ${\displaystyle {\mathcal {Q}}}$

${\displaystyle {\mathcal {Q}}=\operatorname {SET} \left(\sum _{d\mid k}\operatorname {CYC} _{=d}({\mathcal {Z}})\right).}$

指数生成関数に翻訳すると、 kを割り切る順序を持つ順列のEGFが得られる。これは

${\displaystyle Q_{k}(z)=\exp \left(\sum _{d\mid k}{\frac {z^{d}}{d}}\right).}$

この生成関数を使って、ちょうどkの位数の順列を数えることができます。をn上の順列のうち、位数がちょうどdである順列の数とし、をn上の順列のうち、位数がkを割り切る順列の数とします。すると、 ${\displaystyle p_{n,d}}$ ${\displaystyle q_{n,k}}$

${\displaystyle \sum _{d|k}p_{n,d}=q_{n,k}.}$

メビウス反転により、

${\displaystyle \sum _{d|k}q_{n,d}\times \mu (k/d)=p_{n,k}.}$

そのため、EGF

${\displaystyle Q(z)=\sum _{d\mid k}\mu (k/d)\times Q_{d}(z)=\sum _{d\mid k}\mu (k/d)\exp \left(\sum _{m\mid d}{\frac {z^{m}}{m}}\right).}$

必要なカウントは次のように与えられる。

${\displaystyle n![z^{n}]Q(z).}$

この式は、例えばk  = 6の場合にはEGF

${\displaystyle Q(z)={\rm {e}}^{z}-{\rm {e}}^{z+1/2\,z^{2}}-{\rm {e}}^{z+1/3\,z^{3}}+{\rm {e}}^{z+1/2\,z^{2}+1/3\,z^{3}+1/6\,z^{6}}}$

n  = 5 から始まる値のシーケンス

${\displaystyle 20,240,1470,10640,83160,584640,4496030,42658440,371762820,3594871280,\ldots }$ （ OEISの配列A061121）

k = 8の場合、 EGFは次のようになる。

${\displaystyle Q(z)=-{\rm {e}}^{z+1/2\,z^{2}+1/4\,z^{4}}+{\rm {e}}^{z+1/2\,z^{2}+1/4\,z^{4}+1/8\,z^{8}}}$

n  = 8 から始まる値のシーケンス

${\displaystyle 5040,45360,453600,3326400,39916800,363242880,3874590720,34767532800,\ldots }$ （ OEISの配列A061122）

最後にk  = 12の場合にはEGFが得られる。

${\displaystyle Q(z)={\rm {e}}^{z+1/2\,z^{2}}-{\rm {e}}^{z+1/2\,z^{2}+1/4\,z^{4}}-{\rm {e}}^{z+1/2\,z^{2}+1/3\,{z}^{3}+1/6\,z^{6}}+{\rm {e}}^{z+1/2\,z^{2}+1/3\,z^{3}+1/4\,z^{4}+1/6\,z^{6}+1/12\,z^{12}}}$

n  = 7 から始まる値のシーケンス

${\displaystyle 420,3360,30240,403200,4019400,80166240,965284320,12173441280,162850287600,\ldots }$ （ OEISの配列A061125）

乱れとなる順列の数

パーティーにn人がいて、それぞれが傘を持ってきているとします。パーティーの終わりに、全員が傘の山から1本ずつ傘を取り、その場を去ります。誰も自分の傘を持って帰らない確率はどれくらいでしょうか？この問題は、固定点を持たない順列（いわゆる「乱れ」 ）を数えることに相当し、したがってEGF（基本関係式）は、 z項を基本関係式から 取り除くことで固定点（長さ1のサイクル）を減算します。

${\displaystyle \exp \left(-z+\sum _{k\geq 1}{\frac {z^{k}}{k}}\right)={\frac {e^{-z}}{1-z}}.}$

を で乗算すると の係数が合計されるので、異常の総数 は次のように求められます。 ${\displaystyle 1/(1-z)}$ ${\displaystyle e^{-z}}$ ${\displaystyle D(n)}$

${\displaystyle D(n)=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}\;\approx \;{\frac {n!}{e}}.}$

したがって、約 個の乱れがあり、ランダム順列が乱れである確率は${\displaystyle n!/e}$ ${\displaystyle 1/e.}$

この結果は包含排他性によっても証明できる。pを固定する順列の集合を とすると、 ${\displaystyle A_{p}}$ ${\displaystyle {\begin{matrix}1\leq p\leq n\end{matrix}}}$

${\displaystyle \left|\bigcup _{p}A_{p}\right|=\sum _{p}\left|A_{p}\right|\;-\;\sum _{p<q}\left|A_{p}\cap A_{q}\right|\;+\;\sum _{p<q<r}\left|A_{p}\cap A_{q}\cap A_{r}\right|\;-\;\cdots \;\pm \;\left|A_{p}\cap \;\cdots \;\cap A_{s}\right|.}$

この式は、少なくとも1つの固定点を持つ順列の数を数えます。基数は次のとおりです。

${\displaystyle \left|A_{p}\right|=(n-1)!\;,\;\;\left|A_{p}\cap A_{q}\right|=(n-2)!\;,\;\;\left|A_{p}\cap A_{q}\cap A_{r}\right|=(n-3)!\;,\;\ldots }$

したがって、固定点を持たない順列の数は

${\displaystyle n!\;\;-\;\;{n \choose 1}(n-1)!\;\;+\;\;{n \choose 2}(n-2)!\;\;-\;\;{n \choose 3}(n-3)!\;\;+\;\;\cdots \;\;\pm \;\;{n \choose n}(n-n)!}$

または

${\displaystyle n!\left(1-{\frac {1}{1!}}+{\frac {1}{2!}}-{\frac {1}{3!}}+\cdots \pm {\frac {1}{n!}}\right)=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$

そして私たちにはその主張がある。

これらの数には、ランコント数と呼ばれる一般化があり、これはm個の固定点を含む順列の個数である。対応するEGFは、サイズ1のサイクルを変数uでマークすることによって得られる。つまり、b ( k )を に対して1、それ以外の場合は0とすることで、順列の集合の固定点の数による 生成関数が得られる。${\displaystyle D(n,m)}$ ${\displaystyle [n]}$ ${\displaystyle k=1}$ ${\displaystyle g(z,u)}$

${\displaystyle g(z,u)=\exp \left(-z+uz+\sum _{k\geq 1}{\frac {z^{k}}{k}}\right)={\frac {e^{-z}}{1-z}}e^{uz}.}$

すると、

${\displaystyle [u^{m}]g(z,u)={\frac {e^{-z}}{1-z}}{\frac {z^{m}}{m!}}}$

そしてそれゆえ

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

これは、

${\displaystyle D(n,m)={n \choose m}D(n-m,0)\;\;{\text{ and }}\;\;{\frac {D(n,m)}{n!}}\approx {\frac {e^{-1}}{m!}}}$

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

ランダム順列の順序

Pが順列である場合、 Pの位数は、恒等順列となる最小の正の整数nである。これは、 Pの閉路の長さの最小公倍数である。 ${\displaystyle P^{n}}$

ゴーとシュムッツの定理^[2] によれば、 大きさnのランダム順列の期待順序が${\displaystyle \mu _{n}}$

${\displaystyle \log \mu _{n}\sim c{\sqrt {\frac {n}{\log n}}}}$

ここで定数cは

${\displaystyle 2{\sqrt {2\int _{0}^{\infty }\log \log \left({\frac {e}{1-e^{-t}}}\right)dt}}\approx 1.1178641511899}$

偶数サイクルと奇数サイクルを含む異常

前節と同じ構成を用いて、偶数個のサイクルを含む乱数の数と奇数個のサイクルを含む乱数の数を計算することができる。これを行うには、すべてのサイクルに印を付け、固定小数点を減算する必要がある。 ${\displaystyle D_{0}(n)}$ ${\displaystyle D_{1}(n)}$

${\displaystyle g(z,u)=\exp \left(-uz+u\log {\frac {1}{1-z}}\right)=\exp(-uz)\left({\frac {1}{1-z}}\right)^{u}.}$

さて、いくつかの非常に基本的な推論により、EGFは次のように与えられること がわかります。${\displaystyle q(z)}$ ${\displaystyle D_{0}(n)}$

${\displaystyle q(z)={\frac {1}{2}}\times g(z,-1)+{\frac {1}{2}}\times g(z,1)={\frac {1}{2}}\exp(-z){\frac {1}{1-z}}+{\frac {1}{2}}\exp(z)(1-z).}$

つまり、

${\displaystyle D_{0}(n)=n![z^{n}]q(z)={\frac {1}{2}}n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}+{\frac {1}{2}}n!{\frac {1}{n!}}-{\frac {1}{2}}n!{\frac {1}{(n-1)!}}}$

それは

${\displaystyle {\frac {1}{2}}n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}+{\frac {1}{2}}(1-n)\sim {\frac {1}{2e}}n!+{\frac {1}{2}}(1-n).}$

から引くと、 ${\displaystyle D_{0}(n)}$ ${\displaystyle D(n)}$

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

これら2つの（と）の差は${\displaystyle D_{0}(n)}$ ${\displaystyle D_{1}(n)}$ ${\displaystyle n-1.}$

100人の囚人

ある刑務所長は刑務所の空きスペースを確保しようと、100人の囚人を解放し、100の独房を解放することを検討しています。そこで100人の囚人を集め、次のようなゲームをするように指示します。100個の壺を一列に並べ、それぞれの壺に囚人の名前を1つずつ入れます。それぞれの壺には、同じ名前が1度だけ出てきます。ゲームの進め方は以下の通りです。囚人はそれぞれ50個の壺の中を見ることが許されます。もし自分の名前が50個の壺のどれにも見つからなければ、全員が即座に処刑されます。もし自分の名前が見つかったら、ゲームは続行されます。囚人たちは、ゲーム開始後は互いに意思疎通を図ったり、壺に印を付けたり、壺やその中の名前を動かしたりすることができなくなることを承知の上で、数分間戦略を決めます。壺をランダムに選んだ場合、生存率はほぼゼロです。しかし、名前が壺にランダムに割り当てられていると仮定した場合、生存率を30%に高める戦略があります。それは何でしょうか？

まず、ランダム選択による生存確率は

${\displaystyle \left({\frac {99 \choose 49}{100 \choose 50}}\right)^{100}={\frac {1}{2^{100}}},}$

したがって、これは決して実用的な戦略ではありません。

30% 生存戦略とは、壺の中身を囚人の順列とみなし、サイクルをたどることです。表記を単純にするために、各囚人に番号を割り当てます。たとえば、名前をアルファベット順に並べます。これ以降、壺には名前ではなく番号が入っていると見なすことができます。これで、壺の中身が順列を定義していることが明らかになります。最初の囚人が最初の壺を開けます。自分の名前が見つかれば完了して生き残ります。そうでない場合は、最初の壺で見つけた番号の壺を開けます。このプロセスが繰り返されます。囚人は壺を開け、自分の名前が見つかれば生き残り、そうでない場合は、取り出した番号の壺を開けます。これを 50 個の壺を上限として行います。2 番目の囚人は 2 番目の壺から、3 番目の囚人は 3 番目の壺から開始します。以下同様に続きます。この戦略は、壺によって表される順列のサイクルをたどることとまったく同じです。各囚人は自分の番号が刻まれた壺からスタートし、50個の壺まで自分のサイクルを巡り続ける。自分の番号が刻まれた壺の数は、その数の順列における原像である。したがって、順列のすべてのサイクルに最大50個の要素しか含まれていない場合、囚人は生き残る。この確率が少なくとも30%であることを示す必要がある。

これは、看守が順列をランダムに選択することを前提としていることに注意してください。看守がこの戦略を予測している場合は、単にサイクルの長さが 51 の順列を選択できます。これを克服するために、囚人は事前に自分の名前のランダムな順列に合意することができます。

囚人と壺が開けられるという一般的なケースを考えます。まず、相補確率、つまり要素数以上のサイクルが存在する確率を計算します。これを念頭に置いて、 ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle n}$

${\displaystyle g(z,u)=\exp \left(z+{\frac {z^{2}}{2}}+{\frac {z^{3}}{3}}+\cdots +u{\frac {z^{n+1}}{n+1}}+u{\frac {z^{n+2}}{n+2}}+\cdots \right)}$

または

${\displaystyle {\frac {1}{1-z}}\exp \left((u-1)\left({\frac {z^{n+1}}{n+1}}+{\frac {z^{n+2}}{n+2}}+\cdots \right)\right),}$

望ましい確率は

${\displaystyle [z^{2n}][u]g(z,u),}$

なぜなら、 個以上の要素から成る循環は必然的に一意となるからである。 という事実を用いて、 ${\displaystyle n}$ ${\displaystyle 2(n+1)>2n}$

${\displaystyle [z^{2n}][u]g(z,u)=[z^{2n}][u]{\frac {1}{1-z}}\left(1+(u-1)\left({\frac {z^{n+1}}{n+1}}+{\frac {z^{n+2}}{n+2}}+\cdots \right)\right),}$

その結果

${\displaystyle [z^{2n}][u]g(z,u)=[z^{2n}]{\frac {1}{1-z}}\left({\frac {z^{n+1}}{n+1}}+{\frac {z^{n+2}}{n+2}}+\cdots \right)=\sum _{k=n+1}^{2n}{\frac {1}{k}}=H_{2n}-H_{n}.}$

最後に、オイラー・マクローリン和などの積分推定、またはn次調和数の漸近展開を用いて、次式を得る。

${\displaystyle H_{2n}-H_{n}\sim \log 2-{\frac {1}{4n}}+{\frac {1}{16n^{2}}}-{\frac {1}{128n^{4}}}+{\frac {1}{256n^{6}}}-{\frac {17}{4096n^{8}}}+\cdots ,}$

となることによって

${\displaystyle [z^{2n}][u]g(z,u)<\log 2\quad {\mbox{and}}\quad 1-[z^{2n}][u]g(z,u)>1-\log 2=0.30685281,}$

あるいは少なくとも 30% と主張されています。

関連する結果として、漸近的に、最長サイクルの予想される長さはλn になります。ここで、 λ はゴロム・ディックマン定数で、約 0.62 です。

この例はAnna Gál氏とPeter Bro Miltersen氏によるものです。詳細についてはPeter Winkler氏の論文を参照し、Les-Mathematiques.netでの議論もご覧ください。これらの参考文献へのリンクについては、「100人の囚人」に関する参考文献を参照してください。

上記の計算は、次のように、より単純かつ直接的な方法で実行できます。まず、要素の順列には、長さが より大きい循環が最大で1つしか含まれないことに留意してください。したがって、 ${\displaystyle 2n}$ ${\displaystyle n}$

${\displaystyle p_{k}=\Pr[{\mbox{there is a cycle of length }}k],}$

それから

${\displaystyle \Pr[{\mbox{there is a cycle of length}}>n]=\sum _{k=n+1}^{2n}p_{k}.}$

の場合、長さ のサイクルを含む順列の数は、 ${\displaystyle k>n}$ ${\displaystyle k}$

${\displaystyle {{2n} \choose k}\cdot {\frac {k!}{k}}\cdot (2n-k)!.}$

説明： はサイクルを構成する要素の 選び方の数、 はサイクル内の要素 の並び方の数、 は残りの要素の順序を変える方法の数です。のとき、長さ のサイクルは最大で1つしかないため、ここでは重複カウントは発生しません。したがって、 ${\displaystyle {{2n} \choose k}}$ ${\displaystyle k}$ ${\displaystyle {\frac {k!}{k}}}$ ${\displaystyle k}$ ${\displaystyle (2n-k)!}$ ${\displaystyle k}$ ${\displaystyle k>n}$

${\displaystyle p_{k}={\frac {{{2n} \choose k}\cdot {\frac {k!}{k}}\cdot (2n-k)!}{(2n)!}}={\frac {1}{k}}.}$

我々は次のように結論づけた。

${\displaystyle \Pr[{\mbox{there is a cycle of length}}>n]=\sum _{k=n+1}^{2n}{\frac {1}{k}}=H_{2n}-H_{n}.}$

100人の囚人問題のバリエーション（鍵と箱）

ここで提示した方法に非常によく当てはまる、密接に関連する問題があります。n個の順序付けられた箱があるとします。それぞれの箱には、他の箱への鍵、あるいは箱自体への鍵が含まれており、鍵の順列が与えられている可能性があります。これらのn個の箱のうちk個を一度に選択し、同時に破壊することで、k個の鍵にアクセスすることができます。これらの鍵を使ってn個の箱すべてを開けられる確率はどれくらいでしょうか。この場合、見つかった鍵を使ってその鍵が属する箱を開け、これを繰り返します。

この問題の数学的な表現は次のとおりです。n個の要素と1からnまでの範囲のk個の値からなるランダムな順列をランダムに選び、これらをマークと呼びます。順列の各サイクルに少なくとも1つのマークがある確率はどれくらいでしょうか？この確率はk/nである、というのが主張です。

各サイクルの空でない部分集合がマークされているサイクルによる順列の 種は、 次の仕様を持つ。${\displaystyle {\mathcal {Q}}}$

${\displaystyle {\mathcal {Q}}=\operatorname {SET} \left(\sum _{q\geq 1}\operatorname {CYC} _{=q}({\mathcal {Z}})\times \sum _{p=1}^{q}{q \choose p}{\mathcal {U}}^{p}\right).}$

各サイクルに少なくとも 1 つのマークが必要なため、内部合計のインデックスは 1 から始まります。

仕様を生成関数に翻訳すると、二変数生成関数が得られる。

${\displaystyle G(z,u)=\exp \left(\sum _{q\geq 1}{\frac {z^{q}}{q}}\sum _{p=1}^{q}{q \choose p}u^{p}\right).}$

これを単純化すると

${\displaystyle \exp \left(\sum _{q\geq 1}{\frac {z^{q}}{q}}(u+1)^{q}-\sum _{q\geq 1}{\frac {z^{q}}{q}}\right)}$

または

${\displaystyle \exp \left(\log {\frac {1}{1-(u+1)z}}-\log {\frac {1}{1-z}}\right)={\frac {1-z}{1-(u+1)z}}.}$

この書き直しから係数を抽出するには次のようにする。

${\displaystyle (1-z)\sum _{q\geq 0}(u+1)^{q}z^{q}.}$

すると、

${\displaystyle [z^{n}]G(z,u)=(u+1)^{n}-(u+1)^{n-1}}$

そしてそれゆえ

${\displaystyle [u^{k}][z^{n}]G(z,u)={n \choose k}-{n-1 \choose k}.}$

割って ${\displaystyle {n \choose k}}$

${\displaystyle 1-{\frac {(n-1)!}{k!(n-1-k)!}}{\frac {k!(n-k)!}{n!}}=1-{\frac {n-k}{n}}={\frac {k}{n}}.}$

はzの指数関数なので、n!で割る必要はありません。 ${\displaystyle G(z,u)}$

含む順列の数メートルサイクル

フラジョレ・セジウィック基本定理、すなわち のラベル付き列挙定理を集合に 適用すると、${\displaystyle G=S_{m}}$

${\displaystyle \operatorname {SET} _{=m}(\operatorname {CYC} ({\mathcal {Z}}))}$

生成関数を得る

${\displaystyle g_{m}(z)={\frac {1}{|S_{m}|}}\left(\log {\frac {1}{1-z}}\right)^{m}={\frac {1}{m!}}\left(\log {\frac {1}{1-z}}\right)^{m}.}$

用語

${\displaystyle (-1)^{n+m}n!\;[z^{n}]g_{m}(z)=s(n,m)}$

は第一種符号スターリング数 を与え、第一種符号なしスターリング数のEGFである。すなわち、 ${\displaystyle g_{m}(z)}$

${\displaystyle n![z^{n}]g_{m}(z)=\left[{\begin{matrix}n\\m\end{matrix}}\right].}$

nを固定した符号付きスターリング数のOGFを計算することができる。すなわち

${\displaystyle s_{n}(w)=\sum _{m=0}^{n}s(n,m)w^{m}.}$

まずは

${\displaystyle g_{m}(z)=\sum _{n\geq m}{\frac {(-1)^{n+m}}{n!}}s(n,m)z^{n}}$

その結果

${\displaystyle (-1)^{m}g_{m}(z)w^{m}=\sum _{n\geq m}{\frac {(-1)^{n}}{n!}}s(n,m)w^{m}z^{n}.}$

これを合計すると、

${\displaystyle \sum _{m\geq 0}(-1)^{m}g_{m}(z)w^{m}=\sum _{m\geq 0}\sum _{n\geq m}{\frac {(-1)^{n}}{n!}}s(n,m)w^{m}z^{n}=\sum _{n\geq 0}{\frac {(-1)^{n}}{n!}}z^{n}\sum _{m=0}^{n}s(n,m)w^{m}.}$

左辺の の対数、右辺の定義、二項定理を含む式を用いると、 ${\displaystyle g_{m}(z)}$ ${\displaystyle s_{n}(w)}$

${\displaystyle (1-z)^{w}=\sum _{n\geq 0}{w \choose n}(-1)^{n}z^{n}=\sum _{n\geq 0}{\frac {(-1)^{n}}{n!}}s_{n}(w)z^{n}.}$

の係数を比較し、二項係数の定義を用いると、最終的に次の式が得られる。 ${\displaystyle z^{n}}$

${\displaystyle s_{n}(w)=w\;(w-1)\;(w-2)\;\cdots \;(w-(n-1))=(w)_{n},}$

下降階乗。第一種符号なしスターリング数のOGFの計算も同様の方法で行われます。

与えられたサイズのサイクルの予想数メートル

この問題では、導入部で述べたように、二変数生成関数g ( z ,  u )を用いる。サイクルのサイズがmでない場合、 bの値は0 となり、サイズがmの場合、 b の値は 1 となる。

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}}={\frac {1}{1-z}}{\frac {z^{m}}{m}}}$

または

${\displaystyle {\frac {1}{m}}z^{m}\;+\;{\frac {1}{m}}z^{m+1}\;+\;{\frac {1}{m}}z^{m+2}\;+\;\cdots }$

これは、長さnがm未満の順列における、サイズmの循環の期待値は（当然ながら）0であることを意味します。長さm以上のランダム順列には、平均して 1/ m 個の長さmの循環が含まれます。特に、ランダム順列には約1つの固定点が含まれます。

したがって、 長さm以下の周期の期待値のOGFは

${\displaystyle {\frac {1}{1-z}}\sum _{k=1}^{m}{\frac {z^{k}}{k}}{\mbox{ and }}[z^{n}]{\frac {1}{1-z}}\sum _{k=1}^{m}{\frac {z^{k}}{k}}=H_{m}{\mbox{ for }}n\geq m}$

ここで、H _mはm番目の調和数です。したがって、ランダム順列における 長さm以下のサイクルの期待値は約 ln mです。

固定点のモーメント

不動点の数による順列集合の 混合GFは${\displaystyle g(z,u)}$

${\displaystyle g(z,u)=\exp \left(-z+uz+\log {\frac {1}{1-z}}\right)={\frac {1}{1-z}}\exp(-z+uz).}$

確率変数Xをランダム順列の不動点の数とする。第二種スターリング数を用いると、 Xのm次のモーメントは次の式で表される。

${\displaystyle E(X^{m})=E\left(\sum _{k=0}^{m}\left\{{\begin{matrix}m\\k\end{matrix}}\right\}(X)_{k}\right)=\sum _{k=0}^{m}\left\{{\begin{matrix}m\\k\end{matrix}}\right\}E((X)_{k}),}$

ここでは階乗降格である。を用いると、 ${\displaystyle (X)_{k}}$ ${\displaystyle g(z,u)}$

${\displaystyle E((X)_{k})=[z^{n}]\left({\frac {d}{du}}\right)^{k}g(z,u){\Bigg |}_{u=1}=[z^{n}]{\frac {z^{k}}{1-z}}\exp(-z+uz){\Bigg |}_{u=1}=[z^{n}]{\frac {z^{k}}{1-z}},}$

これは のときは0 、そうでないときは1である。したがって、 の項のみが和に寄与する。これは ${\displaystyle k>n}$ ${\displaystyle k\leq n}$

${\displaystyle E(X^{m})=\sum _{k=0}^{n}\left\{{\begin{matrix}m\\k\end{matrix}}\right\}.}$

ランダム順列における固定点の期待値の累乗け

ランダムな順列を （正の整数） 乗し、その結果に含まれる固定点の期待値を尋ねるとします。この値を と表記します。 ${\displaystyle \sigma }$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle E[F_{k}]}$

長さのサイクルの約数は、そのべき乗で固定点に分割される。したがって、これらのサイクルをマークする必要がある。これを説明するために、${\displaystyle d}$ ${\displaystyle k}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle k.}$ ${\displaystyle u^{d}.}$ ${\displaystyle E[F_{6}].}$

私たちは

${\displaystyle g(z,u)=\exp \left(uz-z+u^{2}{\frac {z^{2}}{2}}-{\frac {z^{2}}{2}}+u^{3}{\frac {z^{3}}{3}}-{\frac {z^{3}}{3}}+u^{6}{\frac {z^{6}}{6}}-{\frac {z^{6}}{6}}+\log {\frac {1}{1-z}}\right)}$

それは

${\displaystyle {\frac {1}{1-z}}\exp \left(uz-z+u^{2}{\frac {z^{2}}{2}}-{\frac {z^{2}}{2}}+u^{3}{\frac {z^{3}}{3}}-{\frac {z^{3}}{3}}+u^{6}{\frac {z^{6}}{6}}-{\frac {z^{6}}{6}}\right).}$

導入部で述べたことをもう一度続けると、

${\displaystyle \left.{\frac {\partial }{\partial u}}g(z,u)\right|_{u=1}=\left.{\frac {z+z^{2}+z^{3}+z^{6}}{1-z}}\exp \left(uz-z+u^{2}{\frac {z^{2}}{2}}-{\frac {z^{2}}{2}}+u^{3}{\frac {z^{3}}{3}}-{\frac {z^{3}}{3}}+u^{6}{\frac {z^{6}}{6}}-{\frac {z^{6}}{6}}\right)\right|_{u=1}}$

それは

${\displaystyle {\frac {z+z^{2}+z^{3}+z^{6}}{1-z}}.}$

結論としては、の場合、平均して 4 つの不動点があるということです。 ${\displaystyle E[F_{6}]=4}$ ${\displaystyle n\geq 6}$

一般的な手順は

${\displaystyle g(z,u)=\exp \left(\sum _{d\mid k}\left(u^{d}{\frac {z^{d}}{d}}-{\frac {z^{d}}{d}}\right)+\log {\frac {1}{1-z}}\right)={\frac {1}{1-z}}\exp \left(\sum _{d\mid k}\left(u^{d}{\frac {z^{d}}{d}}-{\frac {z^{d}}{d}}\right)\right).}$

前回と同じように、

${\displaystyle \left.{\frac {\partial }{\partial u}}g(z,u)\right|_{u=1}=\left.{\frac {\sum _{d\mid k}z^{d}}{1-z}}\exp \left(\sum _{d\mid k}\left(u^{d}{\frac {z^{d}}{d}}-{\frac {z^{d}}{d}}\right)\right)\right|_{u=1}={\frac {\sum _{d\mid k}z^{d}}{1-z}}.}$

の値は、から始まるとすぐに(の約数の個数)に等しくなることを示しました。 はに対してから始まり、が の約数に達するたびに 1 ずつ増加し、その約数まで増加します。 ${\displaystyle E[F_{k}]}$ ${\displaystyle \tau (k)}$ ${\displaystyle k}$ ${\displaystyle n\geq k.}$ ${\displaystyle 1}$ ${\displaystyle n=1}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$

ランダム順列の任意の長さのサイクルの期待数

我々は、を使用して二変数生成関数を構築します。ここで、はすべてのサイクルに対して 1 です (すべてのサイクルがサイクルの合計数に 1 を加えます)。 ${\displaystyle g(z,u)}$ ${\displaystyle b(k)}$ ${\displaystyle b(k)}$

は閉じた形を持つ ことに注意${\displaystyle g(z,u)}$

${\displaystyle g(z,u)=\left({\frac {1}{1-z}}\right)^{u}}$

第一種符号なしスターリング数を生成します。

我々は持っています

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}}={\frac {1}{1-z}}\sum _{k\geq 1}{\frac {z^{k}}{k}}={\frac {1}{1-z}}\log {\frac {1}{1-z}}.}$

したがって、予想されるサイクル数は調和数 、つまり約 になります。 ${\displaystyle H_{n}}$ ${\displaystyle \log n}$

長さが次の値より大きい順列の数n/2

(セクション「100 人の囚人」にはまったく同じ問題と非常によく似た計算が含まれており、さらにより簡単な初等的証明も含まれていることに注意してください。)

もう一度、指数生成関数 から始めます。今回は、サイズに応じた順列のクラスで、長さが より大きいサイクルは変数 でマークされます。 ${\displaystyle g(z,u)}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle n/2}$ ${\displaystyle u}$

${\displaystyle g(z,u)=\exp \left(u\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}+\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {z^{k}}{k}}\right).}$

長さが より大きいサイクルは1つしか存在しないので、質問の答えは次のように与えられます。 ${\displaystyle {\frac {n}{2}}}$

${\displaystyle n![uz^{n}]g(z,u)=n![z^{n}]\exp \left(\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {z^{k}}{k}}\right)\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}}$

または

${\displaystyle n![z^{n}]\exp \left(\log {\frac {1}{1-z}}-\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}\right)\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}}$

それは

${\displaystyle n![z^{n}]{\frac {1}{1-z}}\exp \left(-\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}\right)\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}=n![z^{n}]{\frac {1}{1-z}}\sum _{m=0}^{\infty }{\frac {(-1)^{m}}{m!}}\left(\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}\right)^{m+1}}$

指数の項の指数はより大きいので、の値は寄与できない可能性がある。${\displaystyle z}$ ${\displaystyle m+1}$ ${\displaystyle \lfloor {\frac {n}{2}}\rfloor }$ ${\displaystyle m>0}$ ${\displaystyle [z^{n}].}$

答えは

${\displaystyle n![z^{n}]{\frac {1}{1-z}}\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}=n!\sum _{k=\lfloor {\frac {n}{2}}\rfloor +1}^{n}{\frac {1}{k}}.}$

合計には、例えば OEIS OEIS : A024167などで見られるような別の表現があります。

${\displaystyle \sum _{k=1}^{n}{\frac {1}{k}}-\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {1}{k}}=\sum _{k=1}^{n}{\frac {1}{k}}-2\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {1}{2k}}=\sum _{k=1 \atop k\;{\text{even}}}^{n}(1-2){\frac {1}{k}}+\sum _{k=1 \atop k\;{\text{odd}}}^{n}{\frac {1}{k}}}$

ついに与える

${\displaystyle n!\sum _{k=1}^{n}{\frac {(-1)^{k+1}}{k}}\sim n!\log 2.}$

ランダム順列の転置の期待回数

順列の分離サイクル分解を用いると、長さkのサイクルをk − 1個の 転置で置き換えることで、転置の積として因数分解することができます。例えば、サイクルは と因数分解されます。サイクルの関数は と等しく、以下の式を得ます 。${\displaystyle (1\;2\;34)}$ ${\displaystyle (1\;2)\;(2\;3)\;(3\;4)}$ ${\displaystyle b(k)}$ ${\displaystyle k-1}$

${\displaystyle g(z,u)=\left({\frac {1}{1-uz}}\right)^{1/u}}$

そして

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}(k-1){\frac {z^{k}}{k}}={\frac {z}{(1-z)^{2}}}-{\frac {1}{1-z}}\log {\frac {1}{1-z}}.}$

したがって、転置の期待数は ${\displaystyle T(n)}$

${\displaystyle T(n)=n-H_{n}}$

ここでは調和数です。転置の数は、すべてのサイクルの長さを加算してnとし、サイクルごとに1を減算して得られる（前のセクションで得られた）ことに注意することでも、この式を得ることができます。 ${\displaystyle H_{n}}$ ${\displaystyle n^{th}}$ ${\displaystyle \log n}$

再び第一種符号なしスターリング数を生成するが、順序は逆であることに 注意されたい。より正確には、${\displaystyle g(z,u)}$

${\displaystyle (-1)^{m}n!\;[z^{n}][u^{m}]g(z,u)=\left[{\begin{matrix}n\\n-m\end{matrix}}\right]}$

これを理解するには、上記は次の式と同等であることに注意してください。

${\displaystyle (-1)^{n+m}n!\;[z^{n}][u^{m}]g(z,u)|_{u=1/u}|_{z=uz}=\left[{\begin{matrix}n\\m\end{matrix}}\right]}$

そして

${\displaystyle [u^{m}]g(z,u)|_{u=1/u}|_{z=uz}=[u^{m}]\left({\frac {1}{1-z}}\right)^{u}={\frac {1}{m!}}\left(\log {\frac {1}{1-z}}\right)^{m},}$

これは、正確にm個のサイクルから成る順列に関するセクションで、第一種符号なしスターリング数の EGF であることが分かりました。

ランダム要素の期待サイクルサイズ

ランダム順列のランダムな元qを選択し、 qを含むサイクルの期待サイズを尋ねます。ここで関数はに等しくなります。これは、長さkのサイクルは、長さkのサイクル上にあるk個の要素を寄与するからです。これまでの計算とは異なり、このパラメータは生成関数から抽出した後（ nで割る）、 平均化する必要があることに注意してください。${\displaystyle \sigma }$ ${\displaystyle b(k)}$ ${\displaystyle k^{2}}$

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}k^{2}{\frac {z^{k}}{k}}={\frac {1}{1-z}}{\frac {z}{(1-z)^{2}}}={\frac {z}{(1-z)^{3}}}.}$

したがって、 qを含むサイクルの期待長さは

${\displaystyle {\frac {1}{n}}[z^{n}]{\frac {z}{(1-z)^{3}}}={\frac {1}{n}}{\frac {1}{2}}n(n+1)={\frac {1}{2}}(n+1).}$

ランダム要素がサイズのサイクル上に存在する確率メートル

この平均パラメータは、ランダム順列の の元をランダムに選択したときに、その元がサイズmのサイクル上にある確率を表します。この関数はの場合は に等しく、それ以外の場合はゼロです。これは、長さmのサイクル、つまり長さmのサイクル上にあるm個の元のみが寄与するからです。 ${\displaystyle [n]}$ ${\displaystyle b(k)}$ ${\displaystyle m}$ ${\displaystyle m=k}$

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}}={\frac {1}{1-z}}\;m\;{\frac {z^{m}}{m}}={\frac {z^{m}}{1-z}}.}$

したがって、ランダム要素が長さmのサイクル上に存在する確率は

${\displaystyle {\frac {1}{n}}[z^{n}]{\frac {z^{m}}{1-z}}={\begin{cases}{\frac {1}{n}},&{\mbox{if }}n\geq m\\0,&{\mbox{otherwise.}}\end{cases}}}$

[のランダムな部分集合の確率n]は同じ周期にある

m個の要素とランダムな順列を含む [ n ]のランダムな部分集合Q を選択し、 Qのすべての要素が同じサイクル上にある確率を求めます。これは別の平均パラメータです。関数b ( k ) は に等しくなります。これは、長さkのサイクルはサイズmの部分集合を生成し、ここでk < mとなるためです。このことから、 ${\displaystyle {\begin{matrix}{k \choose m}\end{matrix}}}$ ${\displaystyle {\begin{matrix}{k \choose m}\end{matrix}}}$ ${\displaystyle {\begin{matrix}{k \choose m}=0\end{matrix}}}$

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq m}{k \choose m}{\frac {z^{k}}{k}}={\frac {1}{1-z}}{\frac {1}{m}}{\frac {z^{m}}{(1-z)^{m}}}={\frac {1}{m}}{\frac {z^{m}}{(1-z)^{m+1}}}.}$

平均すると、 Qの要素が同じサイクルにある確率は次のようになる。

${\displaystyle {n \choose m}^{-1}[z^{n}]{\frac {1}{m}}{\frac {z^{m}}{(1-z)^{m+1}}}={n \choose m}^{-1}{\frac {1}{m}}[z^{n-m}]{\frac {1}{(1-z)^{m+1}}}}$

または

${\displaystyle {\frac {1}{m}}{n \choose m}^{-1}{(n-m)\;+\;m \choose m}={\frac {1}{m}}.}$

特に、2 つの要素p < qが同じサイクル上にある確率は 1/2 です。

偶数個の偶数サイクルを含む順列の数

フラジョレ・セジウィック基本定理を直接用いて、より高度な順列統計を計算することもできる。（ここで用いる演算子の計算方法については、該当のページを参照のこと。）例えば、偶数個の偶数サイクルを含む順列の集合は、次のように表される。

${\displaystyle \operatorname {SET} (\operatorname {CYC} _{\operatorname {odd} }({\mathcal {Z}}))\operatorname {SET} _{\operatorname {even} }(\operatorname {CYC} _{\operatorname {even} }({\mathcal {Z}})).}$

これを指数生成関数（EGF） に置き換えると、

${\displaystyle \exp \left({\frac {1}{2}}\log {\frac {1+z}{1-z}}\right)\cosh \left({\frac {1}{2}}\log {\frac {1}{1-z^{2}}}\right)}$

または

${\displaystyle {\frac {1}{2}}\exp \left({\frac {1}{2}}\left(\log {\frac {1+z}{1-z}}+\log {\frac {1}{1-z^{2}}}\right)\right)+{\frac {1}{2}}\exp \left({\frac {1}{2}}\left(\log {\frac {1+z}{1-z}}-\log {\frac {1}{1-z^{2}}}\right)\right).}$

これを単純化すると

${\displaystyle {\frac {1}{2}}\exp \left({\frac {1}{2}}\log {\frac {1}{(1-z)^{2}}}\right)+{\frac {1}{2}}\exp \left({\frac {1}{2}}\log(1+z)^{2}\right)}$

または

${\displaystyle {\frac {1}{2}}{\frac {1}{1-z}}+{\frac {1}{2}}(1+z)=1+z+{\frac {1}{2}}{\frac {z^{2}}{1-z}}.}$

これは、偶数個の偶数サイクルを含むサイズ 0 の順列 (偶数長さのサイクルが 0 個含まれる空順列) が 1 つ存在し、そのようなサイズ 1 の順列 (同じく偶数長さのサイクルが 0 個含まれる固定点) が 1 つ存在し、 に対してそのような順列が存在することを示しています。 ${\displaystyle n\geq 2}$ ${\displaystyle n!/2}$

平方数の順列

順列を2乗するとどうなるか考えてみましょう。固定点は固定点に写像されます。奇数サイクルは奇数サイクルに1対1で写像されます。例えば、は になります。偶数サイクルは2つに分かれ、元のサイクルの半分のサイズのサイクルのペアを生成します。例えば、は になります。したがって、2乗である順列には、任意の数の奇数サイクル、サイズ2のサイクルが偶数個、サイズ4のサイクルが偶数個などが含まれる可能性があり、次のように表されます。 ${\displaystyle (1\;8\;9\;11\;13)}$ ${\displaystyle (1\;9\;13\;8\;11)}$ ${\displaystyle (5\;13\;6\;9)}$ ${\displaystyle (5\;6)\;(9\;13)}$

${\displaystyle \operatorname {SET} (\operatorname {CYC} _{\operatorname {odd} }({\mathcal {Z}}))\operatorname {SET} _{\operatorname {even} }(\operatorname {CYC} _{=2}({\mathcal {Z}}))\operatorname {SET} _{\operatorname {even} }(\operatorname {CYC} _{=4}({\mathcal {Z}}))\operatorname {SET} _{\operatorname {even} }(\operatorname {CYC} _{=6}({\mathcal {Z}}))\cdots }$

EGFを生成する

${\displaystyle \exp \left({\frac {1}{2}}\log {\frac {1+z}{1-z}}\right)\prod _{m\geq 1}\cosh {\frac {z^{2m}}{2m}}={\sqrt {\frac {1+z}{1-z}}}\prod _{m\geq 1}\cosh {\frac {z^{2m}}{2m}}.}$

奇数サイクル不変量

前の2つのセクションで示した順列の種類、すなわち偶数個の偶サイクルを含む順列と平方順列は、SungとZhang（外部リンクを参照）によって研究された、いわゆる奇サイクル不変量の例です。奇サイクル不変量とは、単に、それぞれの組合せクラスへの所属が、順列に含まれる奇サイクルの数とサイズに依存しないことを意味します。実際、すべての奇サイクル不変量は単純な回帰式に従うことが証明でき、これを導出します。まず、奇サイクル不変量の例をいくつか示します。

偶数サイクルの長さの合計が6となる順列

このクラスの仕様は

${\displaystyle \operatorname {SET} (\operatorname {CYC} _{\operatorname {odd} }({\mathcal {Z}}))\left(\operatorname {SET} _{=3}(\operatorname {CYC} _{=2}({\mathcal {Z}}))+\operatorname {CYC} _{=2}({\mathcal {Z}})\operatorname {CYC} _{=4}({\mathcal {Z}})+\operatorname {CYC} _{=6}({\mathcal {Z}})\right)}$

そして生成関数

${\displaystyle {\sqrt {\frac {1+z}{1-z}}}\left({\frac {1}{6}}\left({\frac {z^{2}}{2}}\right)^{3}+{\frac {z^{2}}{2}}{\frac {z^{4}}{4}}+{\frac {z^{6}}{6}}\right)={\frac {5}{16}}z^{6}{\sqrt {\frac {1+z}{1-z}}}.}$

最初のいくつかの値は

${\displaystyle 0,0,0,0,0,225,1575,6300,56700,425250,4677750,46777500,608107500,\ldots }$

すべての偶数サイクルの長さが同じになる順列

このクラスの仕様は

${\displaystyle \operatorname {SET} (\operatorname {CYC} _{\operatorname {odd} }({\mathcal {Z}}))\left(\operatorname {SET} _{\geq 1}(\operatorname {CYC} _{=2}({\mathcal {Z}}))+\operatorname {SET} _{\geq 1}(\operatorname {CYC} _{=4}({\mathcal {Z}}))+\operatorname {SET} _{\geq 1}(\operatorname {CYC} _{=6}({\mathcal {Z}}))+\cdots \right)}$

そして生成関数

${\displaystyle {\sqrt {\frac {1+z}{1-z}}}\left(\exp \left({\frac {z^{2}}{2}}\right)-1\,+\,\exp \left({\frac {z^{4}}{4}}\right)-1\,+\,\exp \left({\frac {z^{6}}{6}}\right)-1\,+\,\cdots \right).}$

ここには意味上のニュアンスがあります。0は偶数なので、偶数サイクルを含まない順列もこのクラスに属すると考えることができます。最初のいくつかの値は

${\displaystyle 0,1,3,15,75,405,2835,22155,199395,1828575,\ldots }$

偶数サイクルの最大長が4である順列

このクラスの仕様は

${\displaystyle \operatorname {SET} (\operatorname {CYC} _{\operatorname {odd} }({\mathcal {Z}}))\operatorname {SET} (\operatorname {CYC} _{=2}({\mathcal {Z}})+\operatorname {CYC} _{=4}({\mathcal {Z}}))}$

そして生成関数

${\displaystyle {\sqrt {\frac {1+z}{1-z}}}\exp \left({\frac {z^{2}}{2}}+{\frac {z^{4}}{4}}\right).}$

最初のいくつかの値は

${\displaystyle 1,2,6,24,120,600,4200,28560,257040,2207520,24282720,258128640,\ldots }$

再発

偶数サイクル構成要素の仕様がどのように構築されているか注意深く観察してください。構文木として考えるのが最適です。これらの木は3つのレベルを持ちます。最下層のノードは、シングルトンの偶数長サイクルの積の和を表します。中間層のノードは、集合演算子の制約を表します。最後に、最上層のノードは、中間層からの寄与の積の和です。集合演算子の制約は、偶数の生成関数に適用された場合、この特徴を保持します。つまり、別の偶数の生成関数を生成します。しかし、集合演算子への入力はすべて偶数です。なぜなら、それらは偶数長サイクルから生じるからです。結果として、関係するすべての生成関数は次の形式になります。 ${\displaystyle {\mathcal {Z}}}$

${\displaystyle g(z)=h(z){\sqrt {\frac {1+z}{1-z}}},}$

ここでは偶関数である。これはつまり ${\displaystyle h(z)}$

${\displaystyle {\frac {1}{1+z}}\;g(z)=h(z)\;{\frac {1}{\sqrt {1-z^{2}}}}}$

も偶数なので、

${\displaystyle {\frac {1}{1+z}}\;g(z)={\frac {1}{1-z}}\;g(-z)\quad {\mbox{ or }}\quad (1-z)\;g(z)=(1+z)\;g(-z).}$

係数を抽出して置くと、次の式が成り立つ。 ${\textstyle g_{n}=n![z^{n}]g(z)}$

${\displaystyle {\frac {g_{2m+1}}{(2m+1)!}}-{\frac {g_{2m}}{(2m)!}}=-{\frac {g_{2m+1}}{(2m+1)!}}+{\frac {g_{2m}}{(2m)!}}\quad {\mbox{ or }}\quad 2{\frac {g_{2m+1}}{(2m+1)!}}=2{\frac {g_{2m}}{(2m)!}}}$

これによって、

${\displaystyle g_{2m+1}=(2m+1)g_{2m}\,.}$

2005年のパトナム大会の問題

「外部リンク」セクションにパトナム・コンペティションのウェブサイトへのリンクがあります。問題では、

${\displaystyle \sum _{\pi \in S_{n}}{\frac {\sigma (\pi )}{\nu (\pi )+1}}=(-1)^{n+1}{\frac {n}{n+1}},}$

ここで、のすべての順列にわたって和は、 が偶数の 場合は、 が奇数の場合はの符号、 は の不動点の数です。 ${\displaystyle n!}$ ${\displaystyle [n]}$ ${\displaystyle \sigma (\pi )}$ ${\displaystyle \pi }$ ${\displaystyle \sigma (\pi )=1}$ ${\displaystyle \pi }$ ${\displaystyle \sigma (\pi )=-1}$ ${\displaystyle \pi }$ ${\displaystyle \nu (\pi )}$ ${\displaystyle \pi }$

の符号は次のように表される 。${\displaystyle \pi }$

${\displaystyle \sigma (\pi )=\prod _{c\in \pi }(-1)^{|c|-1},}$

ここで、積はのすべてのサイクルcにわたっており、これは例えば、偶数順列と奇数順列のページで説明されているとおりです。 ${\displaystyle \pi }$

そこで、組み合わせクラスを考える。

${\displaystyle \operatorname {SET} (-{\mathcal {Z}}+{\mathcal {V}}{\mathcal {Z}}+\operatorname {CYC} _{=1}({\mathcal {Z}})+{\mathcal {U}}\operatorname {CYC} _{=2}({\mathcal {Z}})+{\mathcal {U}}^{2}\operatorname {CYC} _{=3}({\mathcal {Z}})+{\mathcal {U}}^{3}\operatorname {CYC} _{=4}({\mathcal {Z}})+\cdots )}$

ここで、は寄与サイクルの長さの1-1を表し、 は固定点を表す。これを生成関数に置き換えると、 ${\displaystyle {\mathcal {U}}}$ ${\displaystyle {\mathcal {V}}}$

${\displaystyle g(z,u,v)=\exp \left(-z+vz+\sum _{k\geq 1}u^{k-1}{\frac {z^{k}}{k}}\right)}$

または

${\displaystyle \exp \left(-z+vz+{\frac {1}{u}}\log {\frac {1}{1-uz}}\right)=\exp(-z+vz)\left({\frac {1}{1-uz}}\right)^{1/u}.}$

今、私たちは

${\displaystyle n![z^{n}]g(z,-1,v)=n![z^{n}]\exp(-z+vz)(1+z)=\sum _{\pi \in S_{n}}\sigma (\pi )v^{\nu (\pi )}}$

したがって、望ましい量は次のように与えられる。

${\displaystyle n![z^{n}]\int _{0}^{1}g(z,-1,v)dv=\sum _{\pi \in S_{n}}{\frac {\sigma (\pi )}{\nu (\pi )+1}}.}$

計算すると、

${\displaystyle \int _{0}^{1}g(z,-1,v)dv=\exp(-z)(1+z)\left({\frac {1}{z}}\exp(z)-{\frac {1}{z}}\right)}$

または

${\displaystyle \left({\frac {1}{z}}+1\right)\left(1-\exp(-z)\right)={\frac {1}{z}}+1-\exp(-z)-{\frac {1}{z}}\exp(-z).}$

係数を抽出すると、係数はゼロであることがわかります。定数は1であり、式（ゼロであるべき）と一致しません。しかし、正の 場合には、${\displaystyle 1/z}$ ${\displaystyle n}$

${\displaystyle n![z^{n}]\left(-\exp(-z)-{\frac {1}{z}}\exp(-z)\right)=n!\left(-(-1)^{n}{\frac {1}{n!}}-(-1)^{n+1}{\frac {1}{(n+1)!}}\right)}$

または

${\displaystyle (-1)^{n+1}\left(1-{\frac {1}{n+1}}\right)=(-1)^{n+1}{\frac {n}{n+1}},}$

これが望ましい結果です。

興味深い余談ですが、次の行列式を評価するために使用できることがわかります。 ${\displaystyle g(z,u,v)}$ ${\displaystyle n\times n}$

${\displaystyle d(n)=\det(A_{n})={\begin{vmatrix}a&&b&&b&&\cdots &&b\\b&&a&&b&&\cdots &&b\\b&&b&&a&&\cdots &&b\\\vdots &&\vdots &&\vdots &&\ddots &&\vdots \\b&&b&&b&&\cdots &&a\end{vmatrix}}.}$

ここで、行列式の公式を思い出してください。 ${\displaystyle a,b\neq 0}$

${\displaystyle \det(A)=\sum _{\pi \in S_{n}}\sigma (\pi )\prod _{i=1}^{n}A_{i,\pi (i)}.}$

ここで、順列の右側の積の値はであり、ここでfは の不動点の数である。したがって、 ${\displaystyle \pi }$ ${\displaystyle a^{f}b^{n-f}}$ ${\displaystyle \pi }$

${\displaystyle d(n)=b^{n}n![z^{n}]g\left(z,-1,{\frac {a}{b}}\right)=b^{n}n![z^{n}]\exp \left({\frac {a-b}{b}}z\right)(1+z)}$

その結果

${\displaystyle b^{n}\left({\frac {a-b}{b}}\right)^{n}+b^{n}n\left({\frac {a-b}{b}}\right)^{n-1}=(a-b)^{n}+nb(a-b)^{n-1}}$

そして最後に

${\displaystyle d(n)=(a+(n-1)b)(a-b)^{n-1}\,.}$

偶数順列と奇数順列の循環数の差

ここでは、この差が次のように表されることを示す。

${\displaystyle (-1)^{n}(n-2)!}$

順列の符号は次のように与えられる ことを思い出してください。${\displaystyle \sigma (\pi )}$ ${\displaystyle \pi }$

${\displaystyle \sigma (\pi )=\prod _{c\in \pi }(-1)^{|c|-1}}$

ここで、積は の分離サイクル構成からサイクルcにわたって変化します。 ${\displaystyle \pi }$

順列集合の符号と循環カウントを反映する 組み合わせ種は次のように与えられる。${\displaystyle {\mathcal {Q}}}$

${\displaystyle {\mathcal {Q}}=\operatorname {SET} ({\mathcal {V}}\operatorname {CYC} _{1}({\mathcal {Z}})+{\mathcal {U}}{\mathcal {V}}\operatorname {CYC} _{=2}({\mathcal {Z}}))+{\mathcal {U}}^{2}{\mathcal {V}}\operatorname {CYC} _{=3}({\mathcal {Z}})+{\mathcal {U}}^{3}{\mathcal {V}}\operatorname {CYC} _{=4}({\mathcal {Z}})+{\mathcal {U}}^{4}{\mathcal {V}}\operatorname {CYC} _{=5}({\mathcal {Z}})+\cdots )}$

ここでは標識をマークしたり、サイクルカウントに使用したりします。 ${\displaystyle {\mathcal {U}}}$ ${\displaystyle {\mathcal {V}}}$

生成関数に翻訳すると、

${\displaystyle Q(z,u,v)=\exp \left(v{\frac {z}{1}}+vu{\frac {z^{2}}{2}}+vu^{2}{\frac {z^{3}}{3}}+vu^{3}{\frac {z^{4}}{4}}+vu^{4}{\frac {z^{5}}{5}}+\cdots \right).}$

これを単純化すると

${\displaystyle Q(z,u,v)=\exp \left({\frac {v}{u}}\left({\frac {zu}{1}}+{\frac {z^{2}u^{2}}{2}}+{\frac {z^{3}u^{3}}{3}}+{\frac {z^{4}u^{4}}{4}}+{\frac {z^{5}u^{5}}{5}}+\cdots \right)\right)}$

それは

${\displaystyle \exp \left({\frac {v}{u}}\log {\frac {1}{1-uz}}\right)=\left({\frac {1}{1-uz}}\right)^{\frac {v}{u}}.}$

サイクルカウントによる偶数順列と奇数順列の 2つの生成関数とは次のようになる。${\displaystyle Q_{1}(z,v)}$ ${\displaystyle Q_{2}(z,v)}$

${\displaystyle Q_{1}(z,v)={\frac {1}{2}}Q(z,+1,v)+{\frac {1}{2}}Q(z,-1,v)={\frac {1}{2}}\left({\frac {1}{1-z}}\right)^{v}+{\frac {1}{2}}\left({\frac {1}{1+z}}\right)^{-v}}$

そして

${\displaystyle Q_{2}(z,v)={\frac {1}{2}}Q(z,+1,v)-{\frac {1}{2}}Q(z,-1,v)={\frac {1}{2}}\left({\frac {1}{1-z}}\right)^{v}-{\frac {1}{2}}\left({\frac {1}{1+z}}\right)^{-v}.}$

必要な数量

${\displaystyle G(z,v)=\left.{\frac {d}{dv}}(Q_{1}(z,v)-Q_{2}(z,v))\right|_{v=1}}$

それは

${\displaystyle \left.{\frac {d}{dv}}\left({\frac {1}{1+z}}\right)^{-v}\right|_{v=1}=-\left.\log {\frac {1}{1+z}}\left({\frac {1}{1+z}}\right)^{-v}\right|_{v=1}=-(1+z)\log {\frac {1}{1+z}}.}$

最後に、この生成関数から係数を抽出すると、

${\displaystyle -n\log {\frac {1}{1+z}}=-n!\left({\frac {(-1)^{n}}{n}}+{\frac {(-1)^{n-1}}{n-1}}\right)}$

それは

${\displaystyle -n!(-1)^{n-1}\left(-{\frac {1}{n}}+{\frac {1}{n-1}}\right)=n!(-1)^{n}{\frac {n-(n-1)}{n(n-1)}}}$

それは、

${\displaystyle n!(-1)^{n}{\frac {1}{n(n-1)}}=(-1)^{n}(n-2)!}$

これで証明は終わりです。

一般化

有限集合上のランダム自己準同型についても同様の統計が得られる。 ^{[3] [4]}

参照

• ゴロム・ディックマン定数

参考文献

1. Chowla, S. ; Herstein, IN ; Moore, WK (1951)「対称群に関連する再帰について. I」、Canadian Journal of Mathematics、3 : 328– 334、doi : 10.4153/CJM-1951-038-3、MR  0041849、S2CID  123802787
2. Goh, William MY; Schmutz, Eric (1991). 「ランダム順列の期待順序」. Bulletin of the London Mathematical Society . 23 (1): 34– 42. doi :10.1112/blms/23.1.34. 2020年2月25日時点のオリジナルよりアーカイブ。代替URL
3. バーナード・ハリス (1960). 「ランダムマッピングに関連する確率分布」. Ann. Math. Statist . 31 (4): 1045–1062 . doi : 10.1214/aoms/1177705677 .
4. フィリップ・フラジョレ、アンドリュー・M・オドリズコ (1989)。ランダム マッピング統計 (研究レポート RR-1114)。インリア。インリア-00075445。

外部リンク

• ケン・フォード「整数とランダム順列の解剖学」 - コース講義ノート
• 宋, フィリップ; 張, ヤン (2003). 「順列計算における反復的再帰」. CiteSeerX  10.1.1.91.1088 .
• Marko Riedel et al.,偶数順列と奇数順列の循環数の差
• Marko Riedel 他「閉じた箱の中の鍵、確率に関する疑問」

100人の囚人

• 様々な著者、n/2を超えるサイクルを持つ順列
• 様々な著者、混乱の特性
• 様々な著者、固定点の期待数
• ピーター・ウィンクラー『きっと正しく聞いていないと思う7つのパズル』
• 様々な著者、Les-Mathematiques.net。Cent prisonniers （フランス語）