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