あみだくじの横線の本数について

質問

あみだくじの定理で「全ての順列を生み出すには最低{ｎ(ｎ－１)/２}本の横線が必要」とあるのですがこれは一体どういうことなのでしょうか。証明できるんでしょうか？

あみだくじをテーマに研究発表をしようと思うのですが「ああみだくじ」そのものについての文献ってないんですね。数学の線型代数の置換という分野に関係があるということはわかったのですが数学を学んでいる者ではないので数学書は理解に苦しみました（^^；
ですのでできればわかりやすく説明して頂けるとありがたいです。

回答No.11

aiueo95240

あみだくじをテーマに研究発表とのことですが、僕自身の現在のまとめを考えました。

強引ですが、幾何的・代数的・解析的の３つの側面として比較しました。

●分類
(1)幾何的
(2)代数的
(3)解析的

●表現
(1)具体的なあみだの絵の上と下のつながりだけを見たもの
(2)置換を具体的に表現したもの。たとえば、
(1 2 3 4)
(3 2 4 1)
(3)置換を数値的に表現したもの。No.8を参照。たとえば、
3*3!+0*2!+1*1!

●恒等あみだ
(1)あみだの絵の上と下のつながりが同じ
(2)恒等置換。たとえば、
(1 2 3 4)
(1 2 3 4)
(3)たとえば、
0*3!+0*2!+0*1!

●鏡像あみだ
(1)あみだの絵の上と下のつながりが左右逆。
(2)たとえば、
(1 2 3 4)
(4 3 2 1)
(3)たとえば、
3*3!+2*2!+1*1!

●構成の要素
(1)あみだの絵の横線一本
(2)隣接互換
(3)置換を数値的に表現した
c(3)*3!+c(2)*2!+c(1)*1!
の係数が１増えるか１減るか。

●構成の要素の間の関係
(1)あみだの絵の横線複数。つまり普通のあみだの絵。
(2)隣接互換の合成
(3)置換を数値的に表現した
c(3)*3!+c(2)*2!+c(1)*1!
の係数が１増えるか１減るかを繰り返したもの。

●既約とか極小とかの概念
(1)あみだの絵を実際にひもで作ってみて、そのひもを上下にひっぱり、その交点のみを横線として表現しなおせば、一意的に(?)簡約化できる。
(2)基本変換or公理系を使って一意的に(?)簡約化できる。
(3)これは何を意味するのか僕は知りません。

●合成とか積の概念
(1)あみだの絵の上下のつながりだけをみたものが２つあったとして、それを合体すること。
(2)置換の合成。並べ替えという作業を経由する。たとえば、
(1 2 3 4)(1 2 3 4)=(1 2 3 4)(3 2 4 1)=(1 2 3 4)
(3 2 4 1)(1 2 4 3) (3 2 4 1)(4 2 3 1) (4 2 3 1)
(3)これは何を意味するのか僕は知りません。

●高さの概念
(1)あみだの絵の上下のつながりだけをみたものがあったとして、それを作るために最低限必要な横線の個数は、高さを意味する。
(2)置換の表現で、上段の２つの数が下段では大小関係が逆になっている組の個数は、高さを意味する。
(3)c(3)*3!+c(2)*2!+c(1)*1!において、係数の和つまり、c(3)+c(2)+c(1)は高さを意味する。

●高さの最大の求め方
(1)高さの最大は幾何的に考えて、？？？。
(2)高さの最大は組み合わせ的に考えて、
nC2=n(n-1)/2
(3)高さの最大は解析的に考えて、
Σ[k=1,n-1]k=n(n-1)/2

#いくつか不備があります。ご了承ください。

回答No.10

stomachman

しまった。「既約」と同じ概念をあらわす用語「極小」を既にNo.7で導入してました…
ま、どっちも同じ意味ということで。

回答No.9

stomachman

No.8でaiueo95240さんがご指摘になったことを、ちょっとフォーマルっぽくまとめてみますと、以下のようになります。
　あみだくじをNo.3の記法で表現することにします。
　あみだくじaの表す置換をP(a)と書くことにします。
　あみだくじa,bが置換として同値であること（つまりP(a)=P(b)）を a≡b　と書くことにします。
　あみだくじaの高さをH(a), 横線の数（つまりNo.3の記法で書いたときの互換の列の長さ）をL(a)と書くことにします。
　どんなあみだくじでも、H(a)≦L(a)　ですが、特に
H(a)=L(a)
であるようなあみだくじを「既約」と呼ぶことにします。
　すると、

あみだくじで作りたい置換をp= (p[1],…,p[n]) とするとき、
q ← (1,2,…,n) 恒等置換
a ← φ …　あみだくじ
k ← n-1
（b[k] (k=1,2,…,n-1)はあみだくじ）
while (k＞0）
　　　　　j ← ( q[j]=p[k]を満たすj)
　　　　　b[k] ← (j)(j+1)…(k)
　　　　　q ← q b[k]
　　　　　a ← a b[k]
　　　　　k ← k-1
end while

というアルゴリズムで生成したあみだくじaは
(1) P(a) = p
(2) aは既約あみだくじである。
という性質を持っている。
さらに、b[k]　(k=1,2,…,n-1)の横線の数をc(k)とするとき、
(3) Σc(k) = H(a)
U(p) = Σk! c(k)
とすると、任意の置換 s,tについて
(4) U(s)=U(t)はs=tの必要十分条件である。

　証明はそれほど難しくないと思います。ですが、しかしU(p)の右辺なんて、よく思いつくもんです。すごいですね。

　ところでこのアルゴリズムは「バブルソート」にほかなりません。というのは、pから同じaを作るのに、以下のようにすることもできるからです：

inv(a)をあみだくじaを上下逆さまにしたものとするとき、
q ← p
a ← φ
k ← 1
while (k＜ n-1)
　　　　　j ← (q[j] = kを満たすj)
　　　　　b[k] ← (k)(k+1)…(j-1)
　　　　　q ← q inv(b[k])
　　　　　a ← ab[k]
　　　　　k ← k+1
end while
このアルゴリズムが終了したとき、
q = (1,2,…, n)
になっています。これは、最初バラバラに並んでいたものpを、小さい順にソートしたことになっている訳です。

　バブルソートで生成したあみだくじaは、(1)(2)の性質を持っていますが、他にも(1)(2)を満たすあみだくじxが存在します。（あみだくじxについてはc(k)が定義できないから、(3)(4)も定義されません。）
　一方、任意のあみだくじxが与えられたとき、その置換P(x)を計算し、バブルソートでP(a)=P(x)となる既約あみだくじaを生成しなおせば、x≡aかつ既約であるあみだくじaが得られる訳です。

　あみだくじの置換としての同値性(≡)だけに注目するならそれで十分ですけれども、しかしね、あみだくじを部分的に書き換える（横線を追加するなど）ことの意味が見えないのでは、あみだくじ理論としては寂しい。やっぱり、次の定理を証明しておくのがいいかなあ？
●あみだくじa,bがa≡bであるとき、以下の規則だけを使ってaからbへ変換できる。
基本変換：
[1] (j)(j)≡φ
[2] (j)(j+k)≡(j+k)(j) (k＞1)
[3] (j)(j+1)≡(j+1)(j)(j+1)(j)
[4] (j+1)(j)≡(j)(j+1)(j)(j+1)

回答No.8

aiueo95240

あみだくじの高さの概念で、ご質問の「全ての順列を生み出すには最低{ｎ(ｎ－１)/２}本の横線が必要」が証明できるのですが、ちょっと別の考えをします。

一般論を表記するのは面倒なので、
http://www004.upp.so-net.ne.jp/s_honma/amida/amida.htm
にある下のあみだくじの図を見ながら書きます。

あみだくじの結果があったとして、横線を引いてそれを作ることを考えます。
まず、１２３４５６の３を一番右に持っていくのに、
３本の横線を引いています。
次に、１を右から二番目に持っていくために、４本の横線を引いています。
同様に、次には１本、２本、０本。

これらの横線の数から、
3*5!+4*4!+1*3!+2*2!+0*1!
を対応させます。
こういった対応は、
恒等あみだくじの
0*5!+0*4!+0*3!+0*2!+0*1!=0
から
鏡像あみだくじの
5*5!+4*4!+3*3!+2*2!+1*1!=6!-1
まで、合計6!種類あります。

逆に、0から6!-1の数があったとして、それを、
c(5)*5!+c(4)*4!+c(3)*3!+c(2)*2!+c(1)*1!
(ただし、c(1)=0～1,c(2)=0～2,c(3)=0～3,c(4)=0～4,c(5)=0～5の整数)
と表記すると、あみだくじの結果が定まります。

高さという概念は、No.6のstomachmanさんが定義されてますが、それは
c(5)+c(4)+c(3)+c(2)+c(1)
と同値です。

あみだくじの横線があったとして、それから結果を導くのに、stomachmanさんは公理系を使用されていますが、それを上記の数の表記を用いて、なにかしら規則を表現できればいいことがあるかもしれません。

回答No.7

stomachman

あみだくじに関する研究発表の題材として、未解決のまま放置されている質問No.195687がご参考になるかもしれません。

　これは、平面をn本の直線（互いに平行でない）で分割したときに出来る三角形の個数を問う問題です。
　（不完全な）回答の中で示されている通り、平面の分割の仕方は、隣り合う要素に関する互換の積、すなわちあみだくじとして表現できます。
　従って、平面の分割の仕方はn本の縦線を持つ鏡像あみだくじと対応しています。さらに、鏡像あみだくじのうちで横棒の数がn(n-1)/2であるもの（これを「極小鏡像あみだくじ」とでも呼びましょう）は、平面の分割の仕方と1:1対応しています。
　このように、一見全然違う問題とあみだくじとが等価であるというのは、面白いんじゃないでしょうか。
　直感的には、鏡像あみだくじのひとつの出発点とその到着点を持ってぐいと引っ張ってまっすぐにする。全ての出発点についてこれをやると、縦線が全部直線になり、横棒は交点になる、という訳です。

　平面の分割における三角形は、互換の列で表したあみだくじにおいて、(k)(k+1)(k) または(k+1)(k)(k+1)という並びと対応しています。
　一方、回答No3に示す規則aとbから、
規則d: (k)(k+1)(k) = (k+1)(k)(k+1)
が成り立つことが分かります。規則dで極小鏡像あみだくじを変形しても、それによって互換の個数も変化しませんし、対応する平面の分割に於ける三角形の個数は変化しません。
　また、これらの(k)と(k+1)の間の２箇所の隙間に別の互換（ただし(k),(k+1),(k-1)以外のもの）が挟まっていても、規則cを使って移動することができ、それによって互換の個数も変化しませんし、平面の分割に於ける三角形の個数は変化しません。
　ですから、ある極小鏡像あみだくじAに対応する平面の分割が持つ三角形の個数は、少なくとも、Aを規則cとdだけで変型して得られる極小鏡像あみだくじBに含まれる(k)(k+1)(k) という並びの個数だけあることになります。

　質問No.195687の元々の問いである「三角形の個数を最小にするような平面の分割」に対応する極小鏡像あみだくじは、従って、(k)(k+1)(k) という並びの個数が最小であるようなものです。
　これについても、もし『高さ』のような保存量が見つけられれば、一挙に解決するかもしれません。

回答No.6

stomachman

回答No.5は簡単明瞭なすばらしい証明ですね。少なくともn(n-1)/2本の横線が必要であることの証明は、これで良いと思います。

　「あみだくじの一番下に横線1本を追加すると『高さ』が1だけ変化（増えるか減るか）する」はほとんど自明です。
　　縦線をn本持つ或るあみだくじが置換(p[1], p[2], …,p[k],p[k+1],…, p[n])を表しているとします。（つまり、出発点の1番左を到着点の左からp[1]番目に、出発点の左から2番目を到着点の左からp[2]番目に、…とつなぐあみだくじです。）このあみだくじの『高さ』hとはすなわち、「 i＜j かつ p[i]＞p[j]」が成り立つ<i,j>の組の個数です。
　このあみだくじの下に横線(k)（ただし1≦k＜n)を追加してできるあみだくじは、置換(q[1], q[2], …,q[k],q[k+1],…, q[n])を表しています。ただし、
q[k]=p[k+1],q[k+1]=p[k]
であり、その他の要素に付いては
q[1]=p[1], q[2]=p[2], ……, q[n]=p[n]
になっています。
<k,k+1>以外の<i,j>については、「 i＜j かつ q[i]＞q[j]」と「 i＜j かつ p[i]＞p[j]」とは同値（一方が真なら他方も真、一方が偽なら他方も偽）です。
i=k, j=k+1については、
p[k]＞p[k+1]の場合には「 i＜j かつ p[i]＞p[j]」は真で、「 i＜j かつ q[i]＞q[j]」は偽ですから、『高さ』が1減ってh-1になります。
p[k]＜p[k+1]の場合には「 i＜j かつ p[i]＞p[j]」は偽で、「 i＜j かつ q[i]＞q[j]」は真ですから、『高さ』が１増えてh+1になります。
従って、確かに　「あみだくじの一番下に横線1本を追加すると『高さ』が1だけ変化（増えるか減るか）する」ことが分かります。

　ところで、1～nのうちで、 i＜j となる<i,j>の組は n(n-1)/2通りですから、あみだくじの『高さ』はn(n-1)/2を越えることはできません。鏡像あみだくじは『高さ』が最大値になっているのです。逆に、『高さ』がn(n-1)/2であるあみだくじは全て鏡像あみだくじです。（これは『高さ』の定義から簡単に証明できます。）
　そこで、横線が１本もないあみだくじから出発して、横線を下に１本づつ加え、その際に常に『高さ』が増えるように横線を加える場所を選ぶことにすると、n(n-1)/2本目まではそのように場所を選ぶ事が常に可能です。そして、n(n-1)/2本目の横線を加えたときにできるあみだくじは必ず鏡像あみだくじになります。また、鏡像あみだくじにさらに横線を加えようとすると、どこに横線を加えても『高さ』が減ってしまいます。

　なお、ご回答No.2にある対称群とは、置換を元とし、置換をふたつ続けて行うことを積とする群です。この群の元は全て、互換（互換も置換の一種です）を繰り返し行うことだけで表すことができ、逆に、互換を繰り返し行って作れるあらゆる置換は、全ての置換を網羅します。
　さて、あみだくじ
(i)(i+1)…(j-2)(j-1)(j-2)…(i+1)(i)
は、i番目の要素とj番目の要素(i＜j)を入れ替え、他は変化させないあみだくじです。だから、全ての互換はあみだくじで表せる訳です。そして、互換を表す二つのあみだくじを縦に繋ぐことによって、二つの互換の積で表される置換が作れます。
　従って、あみだくじは（No.2のご回答の通り）確かに対称群になっています。言い換えれば、あみだくじによってあらゆる置換が可能であり、すなわち、n個の物の並べ替え方（n!通り）のどれについても、その並べ替えを実現するあみだくじ（縦線をn本持つ）が存在します。

回答No.5

aiueo95240

追加です。
置換に高さ、または重さなどと呼ばれるべき概念を導入すればよりいいと思います。

(1 2 3 4)
(2 1 4 3)

で考えます。下の数字に注目したとき、その左側にそれより大きい数字の個数を数えます。
上記の場合は、１の左に大きな２があります。
３の左に大きな２、１があります。
そのとき、高さを３とします。

隣接互換によって、その高さは１だけ変化します。

鏡像あみだくじの高さは数えれば、n(n-1)/2ですが、
それを隣接互換によって表そうとすると、n(n-1)/2個以上必要なことが分かります。

回答No.4

aiueo95240

「n(n-1)/2本の横線があれば鏡像あみだくじが作れる」ことは、以下の通り、容易に示せます。

最初に横線が一本も無いとすると、
(1 2 3 ・・・　n)
(1 2 3 ・・・　n)
の状態です。
まず、下の一番左にある１を一番右に持っていくことを考えます。
１と２の縦線の間に横線を一本引くと、
(1 2 3 ・・・　n)
(2 1 3 ・・・　n)
となり、１が一つ分右に移動します。
同様のことを合計n－１回繰り返すと、
(1 2 3 ・・・　n)
(2 3 4 ・・・　1)
となり、１を一番右に持っていくことが出来ます。
同様に２を一番右に持っていくことを考えると、横線が、n－２個必要なことがわかります。

結局、鏡像あみだくじには、
(n-1)+(n-2)+・・・+1=ｎ(ｎ－１)/２本の横線が必要

回答No.3

stomachman

ご質問は、ここでちょこちょこっと証明してみせるにはいささか難しすぎる問題のようです。しかしご質問を見る限り、あみだくじの数学理論を本格的に研究するお積もりではないようにもお見受けします。だったら手始めに、あみだくじに関する基本的な性質について考えてみてはいかがでしょうか。

　あみだくじは、阿弥陀如来像の後光の形から来た名称だそうで、縦線は元々は放射状に並べられたものである、という話を聞いたことがあります。しかしイマドキのあみだくじでは、平行なn本の縦線を使います。

　stomachmanは小学生のとき、「あみだくじの全ての横線は、右から左へ、および、左から右へ、それぞれ丁度一度ずつたどられる」ということを不思議に思ったものです。けれども、あみだくじの横線は、「隣り合う2本の縦線を入れ替える」という操作を表している。このように考えれば、自明のことになります。

　ちょっと余談ですが、縦線を紐だと思えば（縄のれんみたいに紐がn本平行にぶら下がっているイメージですね）、横線に相当するところで隣り合う２本の紐が左右入れ替わって絡まっている訳です。ただし、紐の場合は「左右どちらの紐が交差点の手前側に来るか」を区別すると２通りの入れ替え方がありますが、あみだくじではこの区別がありません。左右どちらを手前側にするかを区別する紐を数学では「絡み目」と呼び、これを扱う数学である「組みひもの理論」は比較的新しい分野です。最近では「絡み目」が量子コンピュータ（未来の超高速コンピュータ）の基本原理になりうる事が発見されたために、注目されています。

　それはさておき、あみだくじは、要するに「出発点の並び順を到着点の並び順に並べ替えるもの」であり、このことに着目すれば、数学で言う「置換」で表せます。そして、あらゆる置換は、２つの要素（縦線）を入れ替える操作（これを「互換」という）を繰り返すことによって表せます。
　たとえば「5番目と8番目を入れ替える」という互換は(5,8)のように表します。「5番目と8番目を入れ替え、さらに7番目と8番目を入れ替える」という操作なら、二つの互換の積(5,8)(7,8)と表す訳です。ただし、普通のかけ算と違って、積の順番を入れ替えると別の置換になってしまいます。（こういうのを「非可換」と言い、一方、順番を入れ替えても常に同じである場合は「可換」と言います。）

　で、話をあみだくじに戻しますと、必ず隣り合った縦線同士を入れ替えますから、互換は(j,j+1)という形のものだけが許されている。なので、以下ではこれを省略して(j)と書くことにしましょう。つまり(7)と書いたら、これは互換(7,8)の意味だということにするわけです。たとえば、縦線が３本ある場合、(1)(2)というあみだくじは、横線が２本あって、上から順に、１本目と２本目を入れ替える横線、２本目と３本目を入れ替える横線、が描いてある、そういうあみだくじです。つまり、左端の縦線から出発すると右端へ、右端の縦線から出発すると真ん中の縦線に行くあみだくじですね。

　あみだくじの横線、すなわち隣り合う縦線同士の互換について、以下の定理が成り立ちます。
a: (j)(j) = φ　
φは「なにもしない」という意味であり、例えば「(1)(1)というあみだくじは、横線が一本もないあみだくじと同じ置換になっている」ということです。（群論の用語で言えば、「(j)は(j)の逆元である」。）
b: (j)(j+1) = (j+1)(j)(j+1)(j), (j+1)(j) = (j)(j+1)(j)(j+1)
横線(j)と横線(j+1)はどちらもj+1番目の縦線と繋がっています。bが成り立つ事は、縦線が3本あるあみだくじを描いて、
(1)(2)
と
(2)(1)(2)(1)
が同じ置換になることを確かめれば分かるでしょう。
c: (j)(j+k) = (j+k)(j) (k≧2)
横線(j)が繋がっている縦線と(j+k)が繋がっている縦線は共通ではない。ですから、（これら二つの横線の途中に他の横線がない限り）どっちが上にあっても置換としては同じ事だ、ということを表している定理です。

　例えば、4本の縦線があるあみだくじ
(2)(3)(1)(2)(1)(3)
は、出発点と到着点が丁度左右裏返しになるような置換を表すあみだくじです。（確かめてみてください。）こういうのを「鏡像あみだくじ」と呼びましょうか。
(1)(2)(3)(2)(1)(2)
も「鏡像あみだくじ」です。（確かめてみてください。）
　両者が置換として等しいことは、上記a,b,cの定理を使って以下のように証明できます。
(2)(3)(1)(2)(1)(3)
= (2)(1)(3)(2)(3)(1) …なぜなら、cにより(3)(1) = (1)(3)だから。
=(1)(2)(1)(2)(3)(2)(3)(1)　…なぜなら、bにより(2)(1) = (1)(2)(1)(2)だから。
=(1)(2)(1)(3)(2)(1) …なぜなら、bにより(2)(3)(2)(3) = (3)(2)だから。
=(1)(2)(3)(1)(2)(1)　…なぜなら、cにより(1)(3) = (3)(1)だから。
=(1)(2)(3)(2)(1)(2)(1)(1)　…なぜなら、bにより(1)(2) = (2)(1)(2)(1)だから。
=(1)(2)(3)(2)(1)(2)　…なぜなら、aにより(1)(1) = φだから。
（この途中経過に出て来るあみだくじも描いて、確かめてみてください。）

　さらに、ふたつのあみだくじが同じ置換であるならば、これら3つの定理だけを使って、両者が等しいことが証明できる、という性質があります。（この性質が成り立つことを証明するのはさほど簡単じゃありません。数学の言葉で言えば、「a,b,cはあみだくじの公理系になっている」ということになります。）

　実は鏡像あみだくじは、どうしてもn(n-1)/2個以上の互換の積でないと作れません。つまり「少なくともn(n-1)/2本の横線が必要なあみだくじ」の例になっています。
　「n(n-1)/2本より少ない横線では鏡像あみだくじが作れない」ということの証明（これが示せればご質問の問題の解になる訳です）は易しくないですが、「n(n-1)/2本の横線があれば鏡像あみだくじが作れる」ことは、以下の通り、容易に示せます。

　縦線がn本あるあみだくじにおいて、
S[m] = (m)(m+1)(m+2)…(n-m-1)(n-m)(n-m-1)…(m+2)(m+1)(m)
という互換の積を考えます。すると、
S[1]は右端と左端の縦線を入れ替え、他の縦線は入れ替えないあみだくじです。
S[2]は右から2番目と左から2番目の縦線を入れ替え、他の縦線は入れ替えないあみだくじです。
S[m]は右からm番目と左からm番目の縦線を入れ替え、他の縦線は入れ替えないあみだくじです。

　ですから、これらの積（つまりこれらのあみだくじを順に縦につないだもの）
S[1]S[2]S[3]…S[K]
は鏡像あみだくじになります。ここにKはnが偶数ならn/2, nが奇数なら(n-1)/2です。

　S[m]は互換(2n-4m+1)個でできているから、S[1]S[2]S[3]…S[K]の互換の総数をtとすると
t = (2n-4×1+1)+(2n-4×2+1)+…+(2n-4K+1)
= 2Kn + K - 4(1+2+…+K)
= 2Kn + K - 4K(K+1)/2
= 2Kn + K - 2K(K+1)
= 2Kn - K - 2(K^2)
Kはnが偶数ならn/2, nが奇数なら(n-1)/2ですから、代入してみると
nが偶数のとき
t = 2(n^2)/2 - n/2 - 2(n^2)/4 = n(n-1)/2
nが奇数のとき
t = 2n(n-1)/2 - (n-1)/2 - 2((n-1)^2)/4 = n(n-1)/2
となって、確かに横線の本数tはn(n-1)/2本です。

　と、まあ、こんな感じではいかがでしょう？

回答No.2

yumisamisiidesu

あみだくじの数学的構造は対称群です.
線形代数では行列式の定義などで多少関係すると思いますが、本格的に学習するのは線形代数でなく代数学の群論です.ですから対称群の定義と基本的な性質を一通り調べてそれとあみだくじがどう関係しているのかを説明したらよいのではないでしょうか？特にどれを選んでも必ず途中で曲がるあみだくじは対称群において任意の置換は互換の積で表せることに対応していることを注目する必要があると思います.