代数学の問題です。

質問

x,y∈Sn
xとyがSnで共役⇔xとyは同じ巡回置換型をもつ
を証明せよ。

それと、S11の共役類の数はいくつでしょうか。説明もお願いします。

よろしくお願いします。

回答No.1

ramayana · ベストアンサー

（⇒について）

xとyが共役で、

　　x=a1・a2・…・ak

だとします。ただし、各aiは、長さがliの巡回置換であり、i≠jなるiとjに対してaiとajは共通の要素を含まないものとします。また、

　　l1≧l2≧…≧lk

とします。

xとyが共役であることから、ある置換zが存在し、y=z^(-1)xzと書けます。すると、

　　y=z^(-1) a1z・z^(-1) a2z・…・z^(-1) akz

であって、各z^(-1) aizは、長さがliの巡回置換であり、i≠jなるiとjに対してz^(-1) aizとz^(-1) ajzは共通の要素を含みません。これは、xとyが同じ巡回置換型を持つことを意味します。

（⇐について）

逆に、xとyが同じ巡回置換型を持つとします。すると、

　　y=b1・b2・…・bk

と書けます。各biは、長さがliの巡回置換であり、i≠jなるiとjに対してbiとbjは共通の要素を含みません。そこで、次のような対応で定義される置換をzとします。

「b1の第1要素にa1の第1要素を対応、b1の第2要素にa1の第2要素を対応、…、b1の第l1要素にa1の第l1要素を対応

b2の第1要素にa2の第1要素を対応、b2の第2要素にa2の第2要素を対応、…、b2の第l2要素にa2の第l2要素を対応

・・・

bkの第1要素にakの第1要素を対応、bkの第2要素にakの第2要素を対応、…、bkの第lk要素にakの第lk要素を対応」

すると、y=z^(-1)xzなので、xとyは共役です。

（共役類の個数について）

S11の共役類の個数を計算してみると、56になりました。次の通り。

上の命題により、Snの共役類の個数は、

　　l1+l2+…+lk＝n
　　l1≧l2≧…≧lk

となるようなk及びl1, l2, …, lkの選び方の個数に等しくなります。これをC(n)とします。また、これらの選び方のうち、l1 = rとなるものの個数をB(n, r)とすれば、

　　C(n )= B(n, 1) + B(n, 2) + … + B(n, n)

であって、さらに、次の漸化式が成り立ちます。

　　B(n, r) = B(n-r, r) + B(n-r, r-1) + … + B(n-r,1)
　　B(n, 1) = 1
　　B(n, r) = 0 for r>n

なお、一般に、

　　B(n, 2) = n/2 (nが偶数のとき) or (n-1)/2 (nが奇数のとき)
　　B(n, n) = B(n, n-1) =1
　　B(n, n-2) = 2 (n≧4のとき)

です。

これらを使ってC(11)を計算すると、次のようにります。

B(11, 1) = 1

B(11, 2) = 5

B(11, 3) = B(8, 3) + B(8, 2) + B(8, 1) = B(5, 3) + B(5, 2) + B(5, 1) + B(8, 2) + B(8, 1) = B(2, 2) + B(2, 1) + B(5, 2) + B(5, 1) + B(8, 2) + B(8, 1) = 1 + 1 + 2 + 1 + 4 + 1 = 10

B(11, 4) = B(7, 4) + B(7, 3) + B(7, 2) + B(7,1) = B(3, 3) + B(3, 2) + B(3, 1) + B(4, 3) + B(4, 2) + B(4, 1) + B(7, 2) + B(7,1) = 1 + 1 + 1 + 1 + 2 + 1 + 3 + 1 = 11

B(11, 5) = B(6, 5) + B(6, 4) +B(6, 3) + B(6, 2) + B(6, 1) = B(6, 5) + B(6, 4) +B(3, 3) + B(3, 2) + B(3, 1) + B(6, 2) + B(6, 1) = 1 + 2 + 1 + 1 + 1 + 3 + 1 = 10

B(11, 6) = B(5, 5) + B(5, 4) + B(5, 3) + B(5, 2) + B(5, 1) = 1 + 1 + 2 + 2 + 1 = 7

B(11, 7) = B(4, 4) + B(4, 3) + B(4, 2) + B(4, 1) = 1 + 1 + 2 + 1 = 5

B(11, 8) = B(3, 3) + B(3, 2) + B(3, 1) = 3

B(11, 9) =2

B(11, 10) = 1

B(11, 11) = 1

C(11) = 1 + 5 + 10 + 11 + 10 + 7 + 5 + 3 + 2 + 1 + 1 = 56

お礼

ご回答ありがとうございます。

質問なのですが、
4行目の、長さがliの巡回置換とはどういうことなのでしょうか。

11行目の、これは、xとyが同じ巡回置換型を持つことを意味しますとありますが、なぜでしょうか。

27行目の、上の命題により、Snの共役類の個数は、

　　l1+l2+…+lk＝n
　　l1≧l2≧…≧lk

となるようなk及びl1, l2, …, lkの選び方の個数に等しくなります。　とありますがなぜでしょうか。

30行目の、また、これらの選び方のうち、l1 = rとなるものの個数をB(n, r)とすれば、

　　C(n )= B(n, 1) + B(n, 2) + … + B(n, n)

であって、さらに、次の漸化式が成り立ちます。

　　B(n, r) = B(n-r, r) + B(n-r, r-1) + … + B(n-r,1)
　　B(n, 1) = 1
　　B(n, r) = 0 for r>n
なお、一般に、

　　B(n, 2) = n/2 (nが偶数のとき) or (n-1)/2 (nが奇数のとき)
　　B(n, n) = B(n, n-1) =1
　　B(n, n-2) = 2 (n≧4のとき)

です。
とあるのですが、どうしたらC(n)の式が出るのか、漸化式の1行目はどうして成り立つのでしょうか。
よろしくお願いします。

回答No.3

ramayana

ANo.2の続きです。

補足質問３　「27行目の、上の命題により、Snの共役類の個数・・・」

（３－１）　共役類の個数＝巡回置換型の個数

命題によって、すべての共役類と、すべての巡回置換型との間に、１対１の対応関係があることが分かります。よって、共役類の個数＝巡回置換型の個数です。

また、上の（２－１）により、すべての巡回置換型は、l1+l2+…+lk＝n、l1≧l2≧…≧lkなる数字の組[l1,l2,...,lk]で表すことができます。反対に、このような数字の組を任意にもってきたとき、それを巡回置換型とする置換が必ず存在します（1からnまでの数字をl1個、l2個、…、lk個のk組に分けて、それぞれの組での巡回置換の積をとればよい）。

以上により、共役類の個数は、l1+l2+…+lk＝n、l1≧l2≧…≧lkなる数字の組の個数に等しくなります。

補足質問４　「C(n )= B(n, 1) + B(n, 2) + … + B(n, n)」

（４－１）　考え方

C(n )は、n個の要素を何組かに分ける分け方のパターンの数です。分け方における最大の組の要素の個数がいくつかによって、分け方を分類すれば、上の式が得られます。

（４－２）　例

n=6の場合を考えます。分け方のパターンは、[6]、[5,1]、[4,2]、[4,1,1]、[3,3]、[3,2,1]、[3,1,1,1]、[2,2,2]、[2,2,1,1]、[2,1,1,1,1]、[1,1,1,1,1,1]の11通りです。よってC(6)=11です。
このうち、最大の組が6のものは[6]だけなので、B(6,6)=1です。最大の組が5のものは[5,1]だけなので、B[6,5]=1です。最大の組が4のものは、[4,2]、[4,1,1]なので、B[6,4]=2です。最大の組が3のものは、[3,3]、[3,2,1]、[3,1,1,1]なので、B[6,3]=3です。
最大の組が2のものは、[2,2,2]、[2,2,1,1]、[2,1,1,1,1]なので、B[6,2]=3です。最大の組が1のものは、[1,1,1,1,1,1]だけなので、B[6,1]=1です。

以上により、B(6,1)+B(6,2)+B(6,3)+B(6,4)+B(6,5)+B(6,6)=1+3+3+2+1+1=11=C(6)となります。

補足質問５　「B(n, r) = B(n-r, r) + B(n-r, r-1) + … + B(n-r,1)」

（５－１）　考え方

B(n, r)は、n個の要素を分ける分け方のうち、最大の組の要素の個数がrになるパターンの数です。このパターンは、残りn-r個をどのように分けるかで決まります。また、このn-r個を分けるパターンでは、最大の組の要素の個数はrを超えることができません。つまり、「n個の要素を分ける分け方のうち、最大の組の要素の個数がrになるパターン」全体は、「n-r個の要素を分ける分け方のうち、最大の組の要素の個数がr-１以下になるパターン」全体と、１対１に対応します。これらにより、上の式が得られます。

（５－２）　例

B(6,2)を考えます。上でみたように、6個の要素を分ける分け方のうち、最大の組の要素の個数が2のものは、[2,2,2]、[2,2,1,1]、[2,1,1,1,1]の3パターンです。これらから、左端の2を取り除いたパターン[2,2]、[2,1,1]、[1,1,1,1]は4個の要素を分ける分け方のうち、最大の組の要素が2以下のもの全体です。[2,2,2]と[2,2]、[2,2,1,1]と[2,1,1]、[2,1,1,1,1]と[1,1,1,1]を対応させることにより、「6個の要素を分ける分け方のうち、最大の組の要素の個数が2のもの」全体は、「4個の要素を分ける分け方のうち、最大の組の要素の個数が2以下のもの」全体と、１対１に対応します。前者のパターンの個数は、B(6,2)=3であり、後者のパターンの個数は、B(4,2)+B(4,1)=2+1=3で、両者は一致します。

回答No.2

ramayana

ANo.1です。

補足質問１　「長さがliの巡回置換とはどういうことなのでしょうか」

（１－１）　巡回置換、長さ

巡回置換というのは、一部分が玉突きのような置換で、他の部分が不変な置換をいいます。例えば、１から１１までの１１個の数字の置換aが、

　　a: (1,2,3,4,5,6,7,8,9,10,11) → (1,2,3,6,8,5,4,7,9,10,11)

だったとします。aによって、1→1、2→2、3→3、4→6、5→8、6→5、7→4、8→7、9→9、10→10、11→11と置換されます。このaでは、1,2,3,9,10,11が不変です。そして、残り4,5,6,7,8では、4→6→5→8→7→4 と順繰りに玉突きのような置換になっています。このaのような置換を「巡回置換」といいます。

また、巡回置換で、動く要素の個数を「長さ」といいます。上のaでは、動くのが4,5,6,7,8の5個なので、aの長さは5です。

特別なケースとして、どの要素も動かない置換（恒等置換）は、長さが1の巡回置換とみなします。動く要素がないのですが、長さを１とします。

上のaを(4→6→5→8→7)と表すことにします。以下、他の巡回置換も同様に表すことにします。恒等置換は、(1)、(2)、(5)などと表すことにします。表し方が違いますが、どれも同じ恒等置換です。

（１－２）　置換は互いに疎な巡回置換の積

すべての置換は、互いに疎な巡回置換の積で表すことができます。「互いに疎」とは、それぞれの巡回置換の間で、動く要素に重複が無いということです。また、この積は、可換（順序の入れ替えが可能）です。

例えば、次の置換xを考えます。

　　x : (1,2,3,4,5,6,7,8,9,10,11) → (2,1,11,3,5,7,8,9,6,4,10)

xによって、1→2、2→1、3→11、4→3、5→5、6→7、7→8、8→9、9→6、10→4、11→10となります。

1から始まる玉突きをみると、1→2→1となります。これに現れない数字、例えば、3から始まる玉突きをみると、3→11→10→4→3となります。まだ現れない数字、例えば、5から始まる玉突きをみると、5→5です。まだ現れない数字、例えば6から始まる玉突きをみると、6→7→8→9→6です。これですべての数字が現れました。

そこで、上の玉突きに対応する巡回置換を、長さの順に並べてa1、a2、a3、a4とします：

　　a1 = (3→11→10→4)
　　a2 = (6→7→8→9)
　　a3 = (1→2)
　　a4 = (5)

例えば、a1は、3→11、11→10、10→4、4→3と動かし、1、2、5、6、7、8、9を不変とする置換です。
すると、x = a1・a2・a3・a4 です。ここで、掛け算の順番は入れ替えても構いません。

補足質問２　「11行目の、これは、xとyが同じ巡回置換型・・・」

（２－１）　巡回置換型

置換の巡回置換型とは、その置換を互いに疎な巡回置換の積で表したときの、長さのパターンのことです。上のxでは、a1の長さが4、a2の長さが4、a3の長さが2、a4の長さが1ですから、その巡回置換型は[4,4,2,1]と表すことができます。積の順序を入れ替えても良いので、これを[2,4,1,4]と表しても構いません。しかし、同じ型に複数の表し方があると不便なので、ここでは、必ず長さが長いほうから順番で表すことと約束します。すると、巡回置換型の表し方は、[4,4,2,1]のようなものだけが許され、一通りに定まります。

4+4+2+1=11です。置換を互いに疎な巡回置換の積で表したとき、11個の要素のそれぞれは、どれかの巡回置換に必ず現れ、しかもただ１つだけに現れるので、巡回置換型の数字の和は、必ず要素の個数に一致します。

ご質問のケースでは、ｘとyが、同じ長さの互いに疎な巡回置換の積で表されるので、その長さのパターンが同じ、すなわち、同じ巡回置換型を持つことになります。