ランダム順列統計

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

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

順列はラベル付きサイクルの集合である。フラジョレ・セジウィック基本定理のラベ​​ル付きケースを用いて、順列の集合と単集合 について書くと、次のようになる。${\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、つまり の 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のサイクルをub(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である順列の数とし、を位数が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 となります。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 個の壷を一列に並べます。それぞれの壷には囚人の名前が 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}.}$

ここで紹介した方法に非常によく当てはまる、関連した問題があります。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 から始まります。

仕様を生成関数に変換すると、2変量生成関数が得られる。

${\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 の計算も同様の方法で行われます。

この問題では、導入部で述べたように、2変量生成関数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のサイクルの期待数はゼロであることを意味します (当然)。長さが少なくとも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 をランダム順列の固定点の数とします。第 2 種のスターリング数を使用すると、 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}},}$

これは のときはゼロ、それ以外のときは1です。したがって、 の項のみが合計に寄与します。これは ${\displaystyle k>n}$${\displaystyle k<=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}$

(セクション 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}}}$

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

順列を二乗するとどうなるか考えてみましょう。固定点は固定点にマッピングされます。奇数サイクルは 1 対 1 で奇数サイクルにマッピングされます。たとえば、はになります。偶数サイクルは 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 によって研究された、いわゆる奇サイクル不変量の例です(外部リンクを参照)。奇サイクル不変量という用語は、それぞれの組み合わせクラスのメンバーシップが、順列で発生する奇サイクルのサイズと数に依存しないことを意味します。実際、すべての奇サイクル不変量は単純な再帰に従うことを証明できます。これを導出します。まず、奇サイクル不変量の例をいくつか示します。

このクラスの仕様は

${\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).}$

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

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

このクラスの仕様は

${\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}\,.}$

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

${\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を引いた値、 は固定点を表します。これを生成関数に翻訳すると、 ${\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]}

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

• ケン・フォード、整数とランダム順列の解剖学 - コース講義ノート
• Sung, Philip; Zhang, Yan (2003). 「順列計算における繰り返し」CiteSeerX  10.1.1.91.1088 .
• Marko Riedel 他「偶数順列と奇数順列のサイクル数の差」
• Marko Riedel 他「閉じた箱の中の鍵、確率に関する疑問」

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