当ブログは、自閉スペクトラム症の当事者である僕が、いつも見ている世界をできるだけ詳細に言葉にしていくことで、皆さんに他者の価値観を鑑賞していただく試みです。
前回は、あみだくじと置換について、特にあみだくじの横棒は隣接互換にあたるということを学んだね。まだ読んでない人はそちらから読んでね。
さて、どんな置換でも、あみだくじで表現できると証明したけれど、
図のような [3,1,4,2] という同じ置換であっても、別のあみだくじで表現することができるから、新たな疑問として、「横線の本数が最小のあみだくじを構成する方法はないだろうか？」という問いが生まれたね。
どんな方法を考えたところで、それが最小だと示すのはなかなか難しいね。
確かに、ただの一つもそれ以下の本数で作る方法はないと示さなくてはならないから、なかなか大変だよね。今回はそのあみだくじの構成方法を紹介するだけじゃなくて、しっかり最小性の証明もやってみよう。
クリハロ法の紹介
まずはじめに、最小あみだくじの作り方を紹介するね。
クリハロ法
- 上下に対応する数字を書いて同じ数字同士を結ぶ。
- Ｘ型の交点をＨ型に形を変える。
- あみだくじの形に整えて完成。
※命名に関して、僕の名前をつけているけれど、別に僕が見つけたわけじゃないよ。ただ、交点をＸ型からＨ型にするということで、Xmas Halloween…クリハロ法としていいんじゃないかと思ったの。
まず最小性の話は忘れて、これがちゃんと目的の置換を表したあみだくじになっているかを考えよう。
交点をＸ型からＨ型に変えるっていうことをしているね。このとき、Ｘ型のときは、左上から来たものを右下に、右上から来たものを左下にって流していて、あみだくじにおいては、Ｈ型が同じ性質を持つから、全体で見ても、最初に同じ番号同士を繋いでいたのなら、ちゃんと目的のあみだくじになっているとわかるよね。
なるほど。すべての交点の部分で向かう方向が変わらないから、全体で見ても変わっているはずがないよねって話だね。
準備ができたし、次に示したいのは、これが最小であるということだね。ただ、そのために使う用語があるから、一つ導入させてね。
転倒と転倒数
転倒
ｉ＜ｊかつ σ(ｉ)＞σ(ｊ)となる組 (σ(ｉ), σ(ｊ)) を置換σの転倒という
また、σ 全体における転倒の個数を転倒数といい、inv(σ) と書く
うーん…文字いっぱいでよくわかんないな〜
要するに、置換された先で「その数字より右側にあるのに小さい数字との組」は、順序が入れ替わっているから転倒と呼んで、それが置換全体で何組あるかを転倒数というんだと考えればいいよ。
〈例〉[3,1,4,2] の転倒数を求めよう。
3より右側にある数字で3より小さいものは、1, 2
1より右側にある数字で1より小さいものは、なし
4より右側にある数字で4より小さいものは、2
2より右側にある数字で2より小さいものは、なし
よって、[3,1,4,2] の転倒は、(3,1),(3,2),(4,2) の3つで
転倒数 inv([3,1,4,2]) = 3 である。
こんな風に順番に「ある数字」に注目して、右側に小さい数字が何組あるか数え上げ、あとで全部足し合わせれば転倒数を求めるのが楽そうだよね。
そこで、ある数字 σ(ｉ) よりも右側にあって σ(ｉ) より小さいものの数を inv(σ(ｉ)) と書くことにすると転倒数は、inv(σ(1))+inv(σ(2))+…+inv(σ(n)) で求められる。
これを使うとさっきの例題も
inv([3,4,1,2]) = inv(3)+inv(1)+inv(4)+inv(2) = 2+0+1+0 = 3
と、簡潔に示すことができるね。
クリハロ法の最小性
この「転倒数」を使って、クリハロ法で作るあみだくじが、目的の置換を表すために最小の横棒の本数を持つあみだくじであることを示していくよ。少し長い証明になるから、今、何をしているのか分からなくならないように、先に証明の概要を書いておくことにするね。
証明の概要
- あみだくじに横線を一本追加すること（隣接互換を掛けること）で転倒数がどう変わるか観察する。
- 初期状態から、最低でも必要な横線の数が転倒数だと導く。
- クリハロ法では、転倒数本の横線しか生まれないことを導く。
１．横棒を追加したときの転倒数
転倒数がｔであるようなある置換 [ h₁, h₂ , … , i , j , k₁ , k₂ , … ] に対して、新たにｉとｊをひっくり返す隣接互換を掛けることを考える。（これは適当なあみだくじに対して、ある場所に新たに一本の横線を追加することを意味している。）
つまりは、[ h₁, h₂ , … , i , j , k₁ , k₂ , … ] から
[ h₁, h₂ , … , j , i , k₁ , k₂ , … ] にすると、転倒数がどう変わるか調べよう。
〈ｉ＜ｊのとき〉
各ｈではｉとｊを交換しても右側にある数字は変わらず、inv(ｈ) は変化しない。
各ｋでもｉとｊを交換しても右側にある数字は変わらず、inv(ｋ) は変化しない。
ｉの右側からｊはなくなるが、ｉ＜ｊであるため、inv(ｉ)は変化しない。
ｊの右側にはｉだけが増えて、ｉ＜ｊであるため、inv(ｊ)は ＋1 される。
よって、合計の転倒数はｉとｊを交換する隣接互換によって、t+1 になる。
〈ｉ＞ｊのとき〉
各ｈではｉとｊを交換しても右側にある数字は変わらず、inv(ｈ) は変化しない。
各ｋでもｉとｊを交換しても右側にある数字は変わらず、inv(ｋ) は変化しない。
ｉの右側からｊがなくなって、ｉ＞ｊであるため、inv(ｉ)は－1 される。
ｊの右側にはｉが増えるが、ｉ＞ｊであるため、inv(ｊ)は 変化しない。
よって、合計の転倒数はｉとｊを交換する隣接互換によって、t－1 になる。
このことから、隣接互換を掛けると（あみだくじに新たな横線を一本加えると）必ず、転倒数が ±1 だけ変わるということが言える。
２．横棒の本数と転倒数の関係
すべての数字が変わらない置換（横線を一本も引いていないあみだくじ）の転倒数は０である。ここから、転倒数ｎの置換にするためには、新たに一本の横線を加えても転倒数は１しか変わらないので、少なくとも（転倒数が −1 になる隣接互換を一度もしなくても）ｎ本の横線は必要になる。
余談だが、このことから、あみだくじの横線の本数の偶奇と、そのあみだくじが表す置換の転倒数の偶奇は一致することがわかる。（転倒数ｎに達したのち、転倒数をｎのままにするには、+1 と −1 の横線は同数必要になる。つまりは、横線を余分に増やすにしても、2の倍数本増やすしかないため）
この性質から転倒数が偶数である置換を偶置換、奇数である置換を奇置換という。ちなみに、この偶置換・奇置換に関しては隣接互換に限らず、あらゆる互換の積で表すとしても、その個数の偶奇は一致する。余力があれば、任意の互換が奇数個の隣接互換の積で表せることを示して証明してみよう。
３．クリハロ法の横棒の本数
クリハロ法であみだくじを構成するとき、できる横線の本数はＸ型のときの交点の数に等しい。よって、この交点ができる条件を考えてみよう。
上のｉと下のｉを結んでできる線分と
上のｊと下のｊを結んでできる線分が交点を持つのは
上と下とで、ｉとｊの順序が入れ替わっているとき（上ではｊがｉの右側にあったのに、下では左側にあるとき。またはその逆のとき）である。
つまり、これは組( i, j )がこの置換において転倒であるときと言えるため、クリハロ法のＸ型でできる交点の数は転倒数個である。よって、クリハロ法では、転倒数本の横線が生まれる。
2で示したことより、これは目的の置換を表現するために必要な最低の横線の本数なので、クリハロ法によってできるあみだくじは、横線の本数が最小である。
わーい！証明完了だね。
でも、あみだくじってどこにいくか読めないように、たくさん線を引いた方が楽しいと思うんだけど…。
確かに…。無駄が多い方が楽しいかもしれない。でもそれなら、無駄に数学を楽しんでみてもいいんじゃないかな。それじゃあ、またね。