n次対称群の要素を互換で表すときの最大個数

Question

n次対称群(置換群)の要素を、隣接互換で表すときの最大個数は、転倒数が最大のものあり、
C(n-1,2)=Σ[k=1,n-1]k=n(n-1)/2
ただし、Cは二項係数。

では、n次対称群(置換群)の要素を、(隣接とは限らない)互換で表すときの最大個数は何なのでしょうか。

stomachman · Accepted Answer

ANo.9はなんだか説明がへたくそな気がするので、改訂版を書きました。
　が、いやまだかなりへたくそな気がしますが、でもま、多少ましかと思いますんで、忘れないうちにとりあえず。

カードの組を(2,3,…,n, 1)という状態から(1,2,…,n)に整列を行う最短手順がK手であるとして、この最短手順を変形して、「n-1枚目にあるカードnを、n枚目の位置にあるカードn-1と入れ替える」という手が最後の一手になるようなK手の手順を構成する、という話です。

＝＝＝＝＝＝＝＝＝＝＝＝
　(x, n-1): x枚目と(n-1)枚目とを入れ替えよ
という互換が最短手順の中に少なくともひとつ存在します。そこで、このような互換がJ回現れるものとして、その互換を、現れる順に
　　(m[j],n-1) : m[j]枚目と(n-1)枚目とを入れ替えよ
であるとします。
　さて、最短手順を実行中に(m[j],n-1) という互換が出てきたら、これを実際には行わず、m[j]枚目のカードにエンピツで(n-1)枚目のカード(つまりカードn）に書いてある番号を写し、(n-1)枚目のカードにはm[j]枚目のカードの本来の番号を書く、という操作を行います。それ以外の場合は単に互換を実行するだけです。すると、K-J回の入れ替えが終わった時点では、
(1) カードnは一度も動かず、n-1枚目の位置にある。
(2) カードにエンピツ書きがあるならエンピツの番号を見るようにすれば、カードの組は番号順に整列している。
(3) エンピツ書きはカードn以外に、J枚のカードに書かれている。
　（もしJ枚以下のカードにしか書かれていないとすると、あるカードには複数のエンピツ書きがある。そのカードは、本来の最短手順の中で、位置n-1へ一旦移動しながら、そのあと別のところへ行き、また位置n-1へ移動したことになります。これは明らかに無駄な操作だから、この手順は最短ではない。ま、このあたりは、議論を整理すると不要になる部分かも知れません。）
　これらJ枚のカードを、エンピツ書きが行われた順に e[1], e[2],…,e[J]とし、カードe[j]に書かれているエンピツ書きの番号をf[j]とします。これは、「カードe[j]は本来の最短手順が終わった時点では、現在カードf[j]がある場所になくてはならない」ということを意味しており、そして、その場所とは、もちろん場所e[j]です。すると、
　　f[1] = n
　　f[j]=e[j-1] (1≦j≦J)
であることは明らかです。そして、カードnにはf[J]が書かれています。それぞれのカードe[j]の現在位置は従ってf[j] であり、また、カードnの現在位置はf[J]ですが、カードnは最初から一度も動いていないから
　　f[J]= n-1
です。

さてここで、手順を追加して、カードe[1]を位置f[2]へ、カードe[2]を位置f[3]へ、… 、カードe[J]を位置f[1]へと巡回移動させる。これは互換J-1回でできます。すると、カードの組は(1,2,…,n-2, n, n-1)という状態になる。これがK-1回の手順でできたことになります。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

なんか不要な枝葉が紛れ込んでる気がしますが、筋と辻褄は合ってると思います。

stomachman · Answer

互換じゃなくカードで考えたら、できたかな、と思います。

カードの組(2,…,n,1)の整列を最短手順において、手順の長さがK手であるとする。

この手順でカードnは少なくとも1度動くから、J回動くとして、手順中にその互換が現れる順に相手のカードをp[1], …, p[J]とする。

さて、この手順中にカードnとp[1]の交換が現れたら、実際には交換を行わず、代わりにカードp[1]にエンピツでnと書き、カードnにはp[1]と書く。カードnとp[j](j≧2)の交換が現れたら、実際には交換を行わず、代わりにカードp[j]にはカードnにエンピツで書いてある番号を書き、カードnは一度エンピツ書きを消して、p[j]と書き直す。
　すると、手順が終了したとき、実際の交換はK-J回行われ、カードはエンピツで書かれた番号順に整列している。そして、カードp[1],p[2],…,p[J]にはそれぞれn, p[1]. p[2], …, p{J-1]と書いてあり、カードnにはp[J]と書いてある。

明らかに、もしこの後続けて、カードnとp[J]，カードnとp[J-1]，… カードnとp[1]の交換をこの順で行えば、カードが本当に整列する。

しかし実際はそうはせず、代わりに、カードp[1]とp[2], カードp[2]とp[3], …, カードp[J-1]とp[J], カードP[J]とnの交換をこの順で行なう。こうやってもカードが本当に整列し、手数はK-J+J=K手である。

さて、最後の交換、すなわちカードp[J]とnの交換を行う直前の状態（K-1手が終わった時点）を考える。このとき、カードnはまだ一度も動いていない。従って、カードnは末尾から2番目の位置にある。
　　(…, n, x)
　最後の交換をするとカードnは末尾に移るのだから、p[J]は末尾にある。
　　(…, n, x) = (…, n, p[J])
そしてそれによって整列が完了するのだから、p[J] = n-1 でなくてはならない。
　　(…, n, x) = (1,2,..., n-2, n, n-1)

最後の交換を行う直前において、カードnと、末尾から2番目の位置は手順中これまで全く使われていない。故に、このK-1手の手順によって、カードの組(2,…,n-1,1)が整列できる。なぜなら、「末尾の位置と末尾から2番目の位置との中間に、仮想の位置があって、そこに仮想のカードnがある」と思って上記のK-1手の手順を行えば良いから。

まとめると、
●カードの組(2,…,n,1)を整列する最短手順がK手であるとすると、カードの組(2,…,n-1,1)を整列する最短手順はK-1手以下である。

ところがカードの組(2,1)を整列する最短手順は明らかに1手である。

だから、カードの組(2,…,n,1)を整列する最短手順は少なくとも(n-1)手である。

stomachman · Answer

ANo.5へのコメントについてです。

互換をアークとするグラフだと思ったとき、その直径はn-1かという話ですよね。どっかで見た事あるような気がするなあ。

バラバラのカードの話は、カードの通し番号を２進数で表して○とUに対応させるだけの、ごく簡単な仕掛けです。n個の穴で扱えるカードの枚数は、ですから最大2^n枚。
　また、カードを人に対応させ、いくつかの質問に対するその人の答をYESを○、NOをUに対応させて切れ込みを入れる。そうすると、「問AにYESと答え問BにNOと答えた人のカードを全部集めろ」のようなデータベース操作（関係データベースにおける射影演算）が棒を使って出来ます。コンピュータが普及する前は、実務にも使われていました。いや、今でも使っているかも。

eclipse2maven · Answer

>No.６

たしかに　n-1 でおさえられますね。

ただ　n-1 の　例は　あるのでしょうか？　これが　best possible?

stomachman · Answer

失礼。変なのアゲてしまいました。

> 一方、逆順になってるものを入れ替えだけで並べ直すのには少なくともn-1手掛かる。
>  （ → http://oshiete.goo.ne.jp/qa/3177493.html )

の部分は消し忘れです。（互換が先頭との入れ替えになってるものに限る、という条件付きの話なので、この場合にはあてはまらない。）

stomachman · Answer

(n-1)でしょ。

> n枚のバラバラの数字カードを、2枚のイレカエ(ソート)だけで元の順番に戻そうとすると

(step 1) 全体のうち、最小のものを先頭と入れ替える。（たまたま先頭が最小なら入れ替えない）
(step 2) 先頭から2番目以降のうち、最小のものを先頭から2番目と入れ替える。（たまたま先頭から2番目が最小なら入れ替えない）
…
(step (n-1)) 最後から2番目以降のうち、最小のものを最後から2番目と入れ替える。（たまたま最後から2番目が最小なら入れ替えない）

でできるから、最大n-1手。
　一方、逆順になってるものを入れ替えだけで並べ直すのには少なくともn-1手掛かる。
（ → http://oshiete.goo.ne.jp/qa/3177493.html )

eclipse2maven · Answer

＞うまくすると、n(n-1)/2未満でできると思います。

ですよね。むずかしいですね

eclipse2maven · Answer

タイプミスです。

n(n-9>/2

＝＝＞

n(n-1>/2

eclipse2maven · Answer

その場合も 隣接互換のときと　同じ　n(n-9>/2 が　最大だと思います。

simple reflection というのは、　simple root に対してのreflection です。simple root は　正のroot の　選び方によって、変わります。　リー環の言葉になってしまうのですが　Weyl chamber　を取り替えることで、正ルートの選び方が変わります。　だから　必ずしも　隣接互換がsimple root でなくなります。この場合でも　新しく定められた正ルートを全部無駄なく1個ずつ負のルートに代えていくものが、最短表示のいちばん大きいものになります。　今回は1個ずつ変えるsimple reflection は隣接互換ではなくなっています。

eclipse2maven · Answer

問題設定がおかしいと思います。

例えば隣接互換の場合でも、置換群の要素、表し方はどれだけでも大きく出来ます。
置換群の元を隣接互換で表す際の一番短い表示の仕方が、その元の最短表示といわれ、隣接互換の要素の数を長さっていいます。

この長さの一番長い元の長さがn(n-1)/2です。これって　上三角行列の　対角成分を含まない部分の成分の数です。（別の言い方をすると、リー環論を知っていれば、正 root の数です。　置換群はワイル群、隣接互換は、simple reflection にあたります）

えっと　e_i- e_j  (i>j)  を　正のルート　e_i- e_j (i<j) を負のルート  って言います。　隣接互換は　ひとつだけ　　ルートの符号を入れ替えます　　正のルート、無駄なくすべて負のルートに代えてしまうやり方が最短のものです。　むだがあると　負のルートを　正に戻してしまいます。

隣接互換でないと　一度に何個もルートの符号を代えてしまいます。これで無駄なく　正のルート負に変える方法はおそら一番版大きな数字と小さな数字を入れ替えて次は2番目、3番目　　といく操作だと思うのですが。

n次対称群の要素を互換で表すときの最大個数

ANo.9はなんだか説明がへたくそな気がするので、改訂版を書きました。

互換じゃなくカードで考えたら、できたかな、と思います。

ANo.5へのコメントについてです。

>No.６

失礼。

(n-1)でしょ。

＞うまくすると、n(n-1)/2未満でできると思います。

タイプミスです。

その場合も 隣接互換のときと 同じ n(n-9>/2 が 最大だと思います。

問題設定がおかしいと思います。

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

その場合も隣接互換のときと　同じ　n(n-9>/2 が　最大だと思います。