あみだくじ

質問

こんにちは
あみだくじに関連した問題を解きたいのですが
どうすればいいか分かりません。
とりあえず、あみだくじを数学的に表現したいと思っています。
あみだくじを数学的に表現する方法には
どのような物があるでしょうか。

回答No.3

stomachman · ベストアンサー

[1] あみだくじと互換の積
　あみだくじは平面に描かれますけれども、ここではもっと自由な、立体あみだくじを考えます。すなわち「n本のうんと長い縦棒に番号1,2,…,nが付いている。これらの縦棒がみんな鉛直に立っていて、その水平断面を見ると円周上に並んでいる。そして、いろんな高さにおいて、縦棒のうちの二つj, kを水平な線分で結んである」というものです。
　「j番目とk番目を入れ替える水平な線分」を意味する(j, k)は、数学では「互換」と呼ばれます。
　あみだくじを上から順に見て行ったとき、現れる互換を順に並べたものを「互換の積」と言います。たとえば
　(1,2)(1,3)(2,4)
のように水平な線分を順番に並べて行くことによって、あみだくじがどういう構造になってるのかを表現できるわけです。

[2] 置換
　既に出ている回答にも書かれている「置換」とは、たとえば（1,2,3,4)を(4,3,1,2)に置き換える、というような、番号の順番の入れ替えのことです。いちいち「（1,2,3,4)を」と断る必要はないので、置換は単に(4,3,1,2)のように表します。もちろん、互換も置換の一種ですし、互換の積もまた、ひとつの置換を表しています。というわけで、あみだくじ全体はひとつの置換である、と考えられる訳です。
　そればかりか、あらゆる置換は互換の積によって表すことができます。たとえば置換(4,3,1,2)は (1,2)(1,3)(2,4)と表せます。

[3]互換の積が持つ性質
　ある置換を表す互換の積は、一通りではない。これが重要なポイントです。互換の積が二つあって、どちらも同じ置換を表しているとき、両者を等号 = で結びます。つまり等号は、「表している置換が同じである」という意味です。
　「水平な線分がない（互換がない）」ということも一種の互換だと思って、φと表す事にします。すると、互換の性質として、
　(a,a) =φ
　φ(a,b) = (a,b)
　(a,b)φ = (a,b)
　(a,b) = (b,a)
　(a,b)(a,b) = φ
　(a,b)(b,c) = (a,c)(a,b)
　a≠c, a≠d, b≠c, b≠dのとき、(a,b)(c,d) = (c,d)(a,b)
などが成立つことは簡単に確認できるでしょう。つまり、これらの性質を使って互換の積を書き換えても、書き換える前後で、互換の積が表す置換は同じのままです。

　また、明らかに
　((a,b)(c,d))(e,f) = (a,b)((c,d)(e,f))
なので、互換の積の中の一連の部分だけに注目し、上記の性質を利用してその部分だけを書き換える、ということができます。たとえば
　　(1,2)(2,5)(1,3)(4,1)
という互換の積において、真ん中の(2,5)(1,3)の部分だけに注目して、これを(1,3)(2,5)に書き換えると
　　(1,2)(1,3)(2,5)(4,1)
となりますが、この互換の積が表す置換は元と同じですから、
　　(1,2)(2,5)(1,3)(4,1) = (1,2)(1,3)(2,5)(4,1)
です。

[4] 互換の積を書き換える
　あるあみだくじAについて、その一番下の所に新しく(a,b)という互換を追加することを考えます。これは、あみだくじAを表す互換の積
　　 (u,v)…(p,q)(r,s)
の右側に(a,b)を付け加えて
　　(u,v)…(p,q)(r,s)(a,b)
にするということです。
　この互換の積の右端にある(r,s)(a,b) の部分を、上記の性質をうまく使って
　　(u,v)…(p,q)(m,n)(r,s)
になるように書き換えます。書き換えによって、(r,s)(a,b)の(r,s)が右側に移動し、その代わりに(a,b)が(m,n)に変化したわけです。
　次に、(p,q)(m,n)の部分を、同様にして
　　(u,v)…(x,y)(p,q)(r,s)
になるように書き換えます。すると(p,q)が元通り右から2番目の位置になった代わりに、(m,n)が(x,y)に変化した。
　このような書き換えを繰り返して行くと、どこかで上記の(a,b)(a,b) = φの性質を使って二つの互換を消してしまえるかもしれません。もしそうできれば、「あるあみだくじAの一番下の所に新しく(a,b)という互換を追加したもの」という互換の積が表す置換（あみだくじ）は、「そのあみだくじAの中の互換をひとつ取り除いたもの」という互換の積としても表せる、ということです。そして、これは「元のあみだくじの中の、ある横線を消した」ということですね。

お礼

ご回答ありがとうございます。

回答No.2

trytobe

「群論」での「置換」とか「全単射」とかであらわせます。

イメージは、あみだくじというのは、横線のところで２本の糸を左右入れ替えているだけ（置換）、という考え方です。だから、上と同じ数だけ下にゴールがあり、重複するゴールやたどり着けないゴールができないのです（全単射）。

群論 集合 全単射 置換 あみだくじ - Google 検索
http://www.google.co.jp/search?q=%E7%BE%A4%E8%AB%96+%E9%9B%86%E5%90%88+%E5%85%A8%E5%8D%98%E5%B0%84+%E7%BD%AE%E6%8F%9B+%E3%81%82%E3%81%BF%E3%81%A0%E3%81%8F%E3%81%98

お礼

回答ありがとうございます。
群論、置き換え、全単射などについて
勉強してみます。

回答No.1

DJ-Potato

あみだくじは、上と下が必ず1対1で対応するので、横線を何本いれようと、横線が0本の状態と本質的には変わりません。

具体的にはどんな問題に取り組もうと考えているのですか？

お礼

回答ありがとうございます。
具体的には、
あみだくじがすでに用意されていて
そこから、決められた数だけ横線を消して
目的の場所に誘導（？）するという問題です。
答えが、１つだけではないと思っています。
（色々なパターンがあると思う、ということです。）