資 料
円形のあみだくじ
内村桂輔 （昭和60年8月30日受理）
Circular Amida Lots
KeisukeUCHIMURA Abstract We define a circular Amida lot and evaluate the number of vertices of it needed to represent apermutation． 1． まえがき あみだくじの数学的な解析はいろいろ行なわれてい る。森口繁一教授1）は，あみだくじの確率論的な解析を して次のことを明らかにした。「1からnまでを出発点 とするあみだくじにおいて，その段数が少ないと，各 出発点パ1《i《κ）に対して，それの到達点の分布は 一様でない。」すなわち，1から出発した時は，その真 下の1に到達する確率が高く，nに到達する確率が低 い。［n／2］から出発した時は［n／2］に到達する確率が 高く，1やnに到達する確率は低く，その分布は正規分 布に似ている。 そこで森口教授1）はあみだくじの公平さを得るため に，「十字路」を許すことを提案している。これに関連 して，東工大の渡辺治氏2）はくもの巣状のあみだくじ を提案している。 ここでは，あみだくじの一つの変形として，円形の あみだくじを提案する。そしてこのあみだくじと置換 との関係をしらべる。 あみだくじと置換に関しても，岩堀長慶教授3），木村 良夫氏4）等いろいろな研究がある。任意の置換はあみ だくじで実現できることは良く知られている。彼らは 置換をあみだくじであらわす時の横線の数の最小値を 求めている。 本論は，置換を円形のあみだくじであらわす時の点 の数の上界と下界を求める。そして，円形のあみだく じをあらわす平面グラフの，複雑度（complexity）を グラフの点の数で評価した。 なお，置換とは，有限集合MからMへの単射のこ とである。 2．円形のあみだくじ 円形のあみだくじを次のように定義する。出発点と 到達点を兼ねる①から⑭までのn個の点を円周上に ならべる。その円の内部にm個の点をとり，それらm 個の点と円周上のn個の点とを合わせて適当に交差 しないように線で結び，平面グラフを作る。ただし， 円周の線は含まれない。線の結び方は，円周上の点の 次数（degree，枝分れの数）は1，または0になるよう にし，円内の点の次数は3となるようにする。このと き，円内のm個の点については，t’正の方向”か’ρ負 の方向”のどちらかの方向をつける（図一1参照。そこ では正の方向を＋，負の方向を一であらわす）。 そして，円周上の各点⑦（ただし，次数が1）を出発 した道は，円内の点にゆくと道が二つに分かれる。こ のとき，各点につけられた方向にしたがい，どちらか の道を選択して進む。そして最終的に，点⑦から始っ 十 ＊計算機科学科，Department of Computer Science． 図一1 点の向きづけ Fig．1 0rientation of vertices
一126一
円形のあみだくじ た道は円周上の点⑦に到達する。これは次のように示 される。点⑦から出た道が，円周内の点だけからなる サイクルになることはない。もし，点⑦から出た道が サイクルVl， v2，……， Vhに入ってしまうと仮定する。 v→Vlをサイクルに入る枝とする。すると， v→Vl→ V2， Vh→Vl→V2となり矛盾をひきおこす。故に，点⑦ から始った道は円周上の点⑦に到達する。 このように，各点②に対してその到達点⑦，∫＝σ（i） が決る。前と同様に，写像σは単射であることがわか る。故に，写像σは置換となる。 このことより，円形のあみだくじは置換をあらわす ことがわかる。 ここで一つの単純な例として，図一2を考えよう。こ の図において①から出た枝は，円内の点にゆくとその 点につけられた負の方向により，②に続く枝に移り， ①から出た道は②に到達する。同様に，②を出発した 道は③に行き，③を出発した道は①に到達する。故に， 図一2の円形のあみだくじは置換（1，2，3）を表す。 〔定理1〕 ｛1，2，…，n｝の任意の置換は，円の内 部に高々0（n2）個の点を持つ円形のあみだくじで実現 される。 （証明） まず｛1，2，…，n｝の任意の置換を普通の あみだくじで実現する。このとき次のことが知られて いる（岩堀3），木村4）参照）。 ある置換をあらわすあみだくじの横線の数の最小値 は，その置換の転位の数と一致する。 （”転位の数”については例えば，佐藤，永井5）を参 照のこと。） 転位の数は高々0（n2）であるので，｛1，2，…， n｝ の置換は高々0（n2）個の横線のあみだくじで実現され ることがわかる。次にこのあみだくじを円形のあみだ くじに変形してゆく。その手続きをまず例で示そう。 図一3のあみだくじは図一4の円形のあみだくじに変形 図一2 円形のあみだくじ Fig．2 A circular Amida lot 1 2 3 図一3 置換（1，2，3） Fig．3 A permutation（1，2，3） 図一4 置換（1，2，3） Fig．4 A permutation（1，2，3） される。 一般の場合は次のようにする。あみだくじは1から nまでのn本のたて線と高々0（n2）個の横線でできて いるものとする。これを次の三つのステップで円形の あみだくじに変形してゆく。 Step 1． iが0からn−1まで動くとして，次のこと を実行する。 あみだくじのn−i番目のたて線の上と下を伸ばし て，円内に一つの閉路C。．iを作る。その際，疹1の時 は，n−i＋1番目のたて線から作った閉路C。．i＋1の外 f則にCn＿，を作る。 Step 2．円周上の点⑭，（1＜ん《η），をとる。∫＝k， k−1，…，2として，次の手線きを考える。閉路C上 の，点⑧の近くの所に，二つの点V＋（R，ノ，1）とV＋ （fe，元， r）をとる。 V＋（k，∫，1）は点⑫より見て左 側，V＋（k，∫， r）は点⑫より見て右側にとる。
一127一
昭和60年12月 山梨大学工学部研究報告 第36号 この二点に対応して，閉路G−、上に二点v−（k，∫− 1，1）とv−（k，元Ll， r）をとる。そして， v＋（ん， ノ，1）とv−（fe，ノ’−1，1），zノ＋（k，ノ， r）とv−（k， ∫−1，r）を結ぶ（この二本の線分は交わらない）。 ノ〉．3ならば，v−（k，∫−1，1）とv−（k，∫−1， r） の中間に，v＋（k，ノー1，1）とv＋（fe，∫−1， r）をと る。この二点に上の手続きを再び適用する。 まず∫＝kとして上の手続きを次々とくり返し，最 後にv−（k，1，1）とv−（le，1， r）ができたら，そ の二点の中間に一つの点v＋（k，1，c）をとる。そし て，v＋（k，1， c）と点⑫を結ぶ。 Step 3．元からあるあみだくじの点については横線 の左側の点は負の方向をつけ，右側の点は正の方向を つける。また，点v＋（k，∫，i），（i＝1， r， c）には正 の方向をつけ，点V−（k，∫，i），（i＝1， r， C）には負 の方向をつける。 このようにすると，任意のあみだくじを円形のあみ だくじに変形することができる。この際，何本かの枝 を新たにつけ加えなければいけない。新しくつけ加え られた枝の数は点⑲に関して，2k−1である。kを1か らnまで動かすと合計n2になる。 ゆえに，円形のあみだくじの全体の枝の数は0（n2） になる。各点の次数が3であることを考えれば，円の 内部の点の数は0（n2）個になる。ゆえに｛1，2，…， n｝の任意の置換は，円の内部に高々0（n2）の点を持 つ円のあみだくじで実現される。 （証明終） 定理1で，任意の置換は高々0（n2）の点を持つ円形 のあみだくじで実現されることが示せたが，次に円形 のあみだくじで実現するためには，0（n2）個の点が必 要な置換が存在することを示す。 〔定理2〕 ｛1，2，…，n｝の置換の中には，それを 円形のあみだくじで実現するときに，どうしても0 （n2）個の点が必要なものがある。 （証明） まずnが偶数の場合を考える。そこで次の 置換を考える。 1，2，…tn／2，n／2十1，…，n σ＝ n／2十1，n／2一ト2，… ， n ， ＊ ，… ， ＊ この置換σを円形のあみだくじで実現することを 考える。そこで1→n／2＋1，2→n／2＋2，…，n／2→ nを線で結ぶ（図一5参照）。するとその交点の数は，1＋ 2十…十（n／2−1）となり0（n2）個となる。ここでで きた交点の次数は4である。このままでは円形のあみ だくじにはならない。 これを次数3の点に直しても基本的には，次数4の 場合と同じである。 まず，次の三つの性質が成り立つことに注意する。 図一5 置換σ Fig．5 A permutationσ （a）一本の枝は高々二本の道Pi， p2で（逆向きに）し か使用されない。なぜならば，第三の道p3がその枝を Piと同じ向きにとおるとすると，Piとp3の到達点は一 致するはずである。これは矛盾である。
（b）⑦から◎への道を，別の⑦から◆
の道が横切るときは，各点の次数が3であるから，少 なくとも一本枝を共有しなければならない。 （c）①から（葱≡）への道を，他のn／2−1本の，⑦から◎（念2），への道が劔らなけitc9“な
らない。②から㊨への道を，他のn／2−1本の道が横切
らなければいけない。以下同様にして，⑦から⇔への道を池のn／2一体の道力横切
らなければならない。 この（a），（b？，（c）より，最低1十2十…十（n／2−1） 個の点が必要となることがわかる。 ゆえに，置換σを円形のあみだくじで実現するため には，少なくとも0（n2）個の点が必要になる。 nが奇数の時も同様の置換を考えれば良い。 （証明終） 3． ま と め 本論は，円形のあみだくじと呼ばれる平面グラフを 定義して，それで任意の置換が定義できることを示し た。そして，その時に必要となるグラフの点の数は上 界，下界ともに0（n2）であることを示した。点の数 でグラフの複雑度（complexity）を計った。一128一
円形のあみだくじ 参考文献 1）森口繁一：あみだくじと酔歩の問題数学セミナー，1984年 9月号，pp．16−21（1984） 2）渡辺 治：くもの巣くじ，数学セミナー，1984年12月号，p， 112 （1984） 3）岩堀長慶：あみだくじと置換群，数学セミナー，1964年2月 号，pp．8−13（1964） 4）木村良夫：エレガントな解答を求む，数学セミナー，1985年 7月号，pp．106−108（1985） 5）佐藤正次，永井 治：線型代数学，p．10，学術図書（昭51）
