問題 1 (あみだくじの理論) n 人のあみだくじ X とは，平面上に n 本の縦線（柱）を描き，その隣り合う柱の間に
適当に水平な横線（横木）を入れたものである．ここでは，横木の高さはすべて異なるものとする．
（実際のあみだ
くじでは，同じ高さの横木も現れるが，その場合でも適当に横木の位置を微調整することにより，結果に影響を与
えずに上の形にすることはいつでも可能である．
）また，横木の間の相対的な位置関係（つまり，高低の関係）が同
じあみだくじは同じものとみなすことにする。柱の上端に置かれた文字 1, 2, . . . , n は，あみだくじを実行するこ
とにより，柱の下端でその順番が入れ替わる．従って，あみだくじは n 文字 {1, 2, . . . , n} の置換 σ を引き起こす．
(
)
1 2 3 4
このとき，X を置換 σ に属するあみだくじと言う．
（図を参照：この場合，n = 4 であり，σ =
4 1 3 2
となる．
）さて，図の様に左から数えて i 番目と i + 1 番目の柱をつなぐ横木の上に S の元 si を書く．
1
2
3
4
s1
s2
s3
s4
1
2
3
4
図 1：n = 4 の場合のあみだくじ
(i) X を置換 σ に属するあみだくじとする．X が k 個の横木を持つとして，各横木の上の sij を横木の高い順に
si1 , si2 , . . . , sik と並べる．
（図 1 の場合，s1 , s2 , s3 , s4 である．
）このとき，σ = si1 si2 · · · sik となることを
示せ．
(ii) χσ を σ に属するあみだくじ全体の集合とする．また，Φσ をその積が σ となる様な，si ∈ S の有限列全体の
集合とする．即ち，
{
}
Φσ = (si1 , si2 , . . . , sik ) σ = si1 si2 · · · sik , sij ∈ S, k ≥ 0 .
このとき，自然な対応で χσ ≃ Φσ （全単射）となることを示せ．
(iii) χσ に含まれるあみだくじ X で，その横木の個数が最小のものを無駄のないあみだくじと言う．(ii) の対応
により，χσ に含まれる無駄のないあみだくじの全体は σ の最短表示全体と 1 対 1 に対応することを示せ．
解答 (i) 置換に属するあみだくじの定義と互換の横木への割り振り方に注意すれば，主張は明らかな感じに思え
るが，このことの証明を詳細に与えてみる．n に関する数学的帰納法で証明する．まず，n = 2 の時は，主張の成
立は容易に分かる．
（横木の本数の偶奇について考えればすぐに分かる．
）次に，n 未満の各番号に対して，主張が成
立すると仮定する．σ を {1, 2, . . . , n} 上の任意の置換とする．n と別の番号を入れ替えるある互換を用いること
で，n が σ により動かないと仮定することができる．σ を {1, 2, . . . , n − 1} 上のある置換 σ
e と同一視することが
1
e の各横木の上に書かれている {1, 2, . . . , n − 1}
できる．このとき，仮定により，任意の σ
e に属するあみだくじ X
上の互換の，横木の高さの順による合成 sei1 sei2 · · · seik と σ
e が一致することが成り立つ．この式を {1, 2, . . . , n} 上
の置換の式としてみると，σ = si1 si2 · · · sik を得る．したがって，数学的帰納法により，主張の成立が得られた．
(ii) χσ から Φσ への自然な対応とは，任意の元 X ∈ χσ に対して，X の横木を高い順に si1 , si2 , . . . , sik ∈ S と
表すとき，この X に有限列 (si1 , si2 , . . . , sik ) を対応させるようなものである．ここで，(i) より σ = si1 si2 · · · sik
であることに注意されたい．この自然な対応を Σ とし，以下ではこれが全単射であることを証明する．
• 単射性：任意に X, Y ∈ χσ をとったときに，Σ (X) = Σ (Y ) を仮定し，
Σ (X) = (si1 , si2 , . . . , sik ) , Σ (Y ) = (tj1 , tj2 , . . . , tjℓ )
と表しておけば，有限列として，(si1 , si2 , . . . , sik ) = (tj1 , tj2 , . . . , tjℓ ) である．このとき，k = ℓ か
つ sim = tjm (1 ≤ m ≤ k) である．ゆえに，あみだくじの相当の定義により，X と Y は同一のもので
ある．よって，Σ は単射である．
• 全射性：任意に有限列 (si1 , si2 , . . . , sik ) ∈ Φσ を選び，sij = (rj rj + 1) と表しておく．この有限列に
対して，χσ の元 X0 を次の様に構成する．上端には左から番号が 1 から n まで番号付けられている，
n 本の平行に並んだ等しい長さの線分を与えておく．まず，これらのうちで上端に番号 r1 と r1 + 1
が番号付けられている 2 本の縦線の間に横木 T1 をつくり，T1 の上に si1 を書く．次に，番号 r2 と
r2 + 1 が番号付けられている 2 本の縦線の間に横木 T2 を，T1 よりも低い位置につくり，T2 の上に
si2 を書く．この様な操作を k 個の横木 T1 , T2 , . . . , Tk が全てつくられるまで行うと，ある 1 つのあ
みだくじが得られ，これを X0 とする．ところで，Φσ の定義により，σ = si1 si2 · · · sik であるから，
Σ (X0 ) = (si1 , si2 , . . . , sik ) が成り立つ．よって，Σ は全射である．
以上により，Σ は全単射であり，この対応によって χσ ≃ Φσ が成り立つ．
2
© Copyright 2024 ExpyDoc
