この記事は Math Advent Calendar 2024 の 4 日目の記事です。
今回はランダム順列において固定点の個数の期待値を求めていきます。
問題
#
順列とは ( 1 , 2 , … , n ) (1,2,\ldots,n) ( 1 , 2 , … , n ) p p p p v = v p_v=v p v = v v v v p = ( 3 , 2 , 1 , 4 , 6 , 5 ) p=(3,2,1,4,6,5) p = ( 3 , 2 , 1 , 4 , 6 , 5 ) 2 , 4 2,4 2 , 4
今回考える問題は次のようなものです：n ! n! n !
小さい例で試してみましょう。n = 1 n=1 n = 1 p = ( 1 ) p=(1) p = ( 1 ) 1 1 1 n = 2 n=2 n = 2 p = ( 1 , 2 ) , ( 2 , 1 ) p=(1,2),(2,1) p = ( 1 , 2 ) , ( 2 , 1 ) 2 , 0 2,0 2 , 0 n = 3 n=3 n = 3
p = ( 1 , 2 , 3 ) p=(1,2,3) p = ( 1 , 2 , 3 ) p = ( 1 , 3 , 2 ) p=(1,3,2) p = ( 1 , 3 , 2 ) p = ( 2 , 1 , 3 ) p=(2,1,3) p = ( 2 , 1 , 3 ) p = ( 2 , 3 , 1 ) p=(2,3,1) p = ( 2 , 3 , 1 ) p = ( 3 , 1 , 2 ) p=(3,1,2) p = ( 3 , 1 , 2 ) p = ( 3 , 2 , 1 ) p=(3,2,1) p = ( 3 , 2 , 1 )
なので、期待値は 3 + 1 + 1 + 1 6 = 1 \frac{3+1+1+1}{6}=1 6 3 + 1 + 1 + 1 = 1 n n n
では実際に証明してみましょう。いろいろな証明方法がありますが、ここでは対称群の作用を考えます。
コーシー・フロベニウスの補題
#
群作用について簡単に紹介します。G G G X X X σ \sigma σ G G G X X X g ∈ G g\in G g ∈ G σ ( g ) \sigma(g) σ ( g ) X X X g g g σ ( g ) \sigma(g) σ ( g ) G G G X X X x ∈ X x\in X x ∈ X σ ( g ) ( x ) \sigma(g)(x) σ ( g ) ( x ) g . x g.x g . x
x ∈ X x\in X x ∈ X { g . x ∣ g ∈ G } \{g.x\mid g\in G\} { g . x ∣ g ∈ G } 軌道 といい、g ∈ G g\in G g ∈ G F i x ( g ) = { x ∈ X ∣ g . x = x } \mathrm{Fix}(g)=\{x\in X\mid g.x=x\} Fix ( g ) = { x ∈ X ∣ g . x = x } 固定点集合 といいます。
コーシー・フロベニウスの補題はバーンサイドの補題とも呼ばれ、軌道の個数を数える公式です。
補題 : 相異なる軌道の個数は
1 ∣ G ∣ ∑ g ∈ G ∣ F i x ( g ) ∣
\frac{1}{|G|}\sum_{g\in G}|\mathrm{Fix}(g)|
∣ G ∣ 1 g ∈ G ∑ ∣ Fix ( g ) ∣ に等しい。
この補題を使うことで期待値が計算できます。対称群 S n S_n S n X = { 1 , 2 , … , n } X=\{1,2,\ldots,n\} X = { 1 , 2 , … , n } g ∈ S n , x ∈ X g\in S_n, x\in X g ∈ S n , x ∈ X g . x g.x g . x g x g_x g x
1 n ! ∑ g ∈ S n ∣ F i x ( g ) ∣
\frac{1}{n!}\sum_{g\in S_n}|\mathrm{Fix}(g)|
n ! 1 g ∈ S n ∑ ∣ Fix ( g ) ∣ に等しいので、軌道の個数に等しいことになります。明らかに軌道は 1 本なので、期待値が 1 に等しいことがわかりました。
一般化
#
一般化して次の問題を考えます：n ! n! n ! k k k
つまり
1 n ! ∑ g ∈ S n ∣ F i x ( g ) ∣ k
\frac{1}{n!}\sum_{g\in S_n}|\mathrm{Fix}(g)|^k
n ! 1 g ∈ S n ∑ ∣ Fix ( g ) ∣ k を計算します。ぱっと見ではコーシー・フロベニウスの補題は使えないように見えますが、実は再びこの補題を使うことができます。
σ \sigma σ G G G X X X G G G X k X^k X k σ ′ \sigma^{\prime} σ ′
g . ( x 1 , … , x k ) = ( g . x 1 , … , g . x k )
g.(x_1,\ldots,x_k)=(g.x_1,\ldots,g.x_k)
g . ( x 1 , … , x k ) = ( g . x 1 , … , g . x k ) により定めます。すると F i x σ ′ ( g ) = F i x σ ( g ) k \mathrm{Fix} _ {\sigma^{\prime}}(g)=\mathrm{Fix}_{\sigma}(g)^k Fix σ ′ ( g ) = Fix σ ( g ) k
このことから、対称群 S n S_n S n { 1 , 2 , … , n } k \{1,2,\ldots,n\}^k { 1 , 2 , … , n } k
例えば ( 1 , 2 , 2 , 3 ) (1,2,2,3) ( 1 , 2 , 2 , 3 ) ( 2 , 3 , 3 , 1 ) (2,3,3,1) ( 2 , 3 , 3 , 1 ) ( 1 , 2 , 3 , 2 ) (1,2,3,2) ( 1 , 2 , 3 , 2 )
軌道の個数は、X 1 ∪ X 2 ∪ ⋯ ∪ X n = { 1 , 2 , … , k } X_1\cup X_2\cup\cdots\cup X_n=\{1,2,\ldots,k\} X 1 ∪ X 2 ∪ ⋯ ∪ X n = { 1 , 2 , … , k } X i X_i X i { X 1 , … , X n } \{X_1,\ldots,X_n\} { X 1 , … , X n } n ≥ k n\ge k n ≥ k
参考文献
#
