直線の配置の数え上げ(1)―6本の直線が作る43通りの形

　ある数え上げの問題. 言葉で説明するよりちょっと観察してみるのが早い.

　4本の直線を引く. どの2本も平行ではなく, どの3本も同じ点で交わることはないとしよう.

f:id:shironetsu:20190505023501p:plain:w600

すると, どう引いても直線で囲まれた領域の「形」はいつも同じになる. 1つの4角形が隣り合う2つの辺で2つの3角形とつながった形.

　5本ならどうか. 4本の直線を引いた後に, もう1本付け足すことを考えて, 慎重に数えると次の6通りがあることが分かる. ただし反転で移り合うものは1つとみなす.

f:id:shironetsu:20190505025204p:plain:w600

☆型が1つ, 左右対称なものが4つ, 自明な対称性しか持たないものが1つ. ここでいう「対称性」はグラフ的な意味で, 交点を頂点, 交点同士を結ぶ線分を辺とみなしている. それぞれ群としては位数10の2面体群 $D_5$ , 位数2の2面体群(というのは反転対称性のこと) $D_1$ , 自明な群 $E$ を自己同型群として持つ, と言える.

　この直線たちを6本, 7本……と増やしていったときにできる「形」のパターンを数えることがここでの興味である. つまり,

平面上に $n$ 本の直線を引く. どの2本も平行ではなく, どの3本も1つの点で交わらない. この条件を満たしつつ連続的に変形, または反転させたとき一致するものを同一視する. このとき, 何通りの直線の引き方が存在するか？

　さて, もう少し観察を続けよう……とペンと紙で $n=6$ の場合も引き続き調べようとするとかなり根気がいることがだんだん分かってくる. きわめて単純な観察から始まる割にこの問題は難しい. とはいえ $n=0$ から $n=5$ までは分かっている. $1,1,1,1,1,6,...$

　オンライン整数列辞典へ. 最初の6項と"line"の語を入れて調べてみると出てくる.
f:id:shironetsu:20190505032556p:plain:w600
A090338 - OEIS

"Number of ways of arranging n straight lines in general position in the (affine) plane." : 一般の位置にある $n$ 本の直線を（アフィン）平面上で並べる方法の数. $n=6$ では43通り. もう少し根気があれば自力で数えられる程度ではあった. コメントによると, このような直線の配置は"full $n-$ flups"と呼ばれていたらしい. "Old name"とされていることが気になるし, "flup"の訳語も分からないが, ここでもこの用語を使うことにする.

　実はこの検索結果の直下にもうひとつよく似た数列が出てくる(見ての通りナンバリングはA090388の直後であり,相互に参照もしている).
f:id:shironetsu:20190505033035p:plain:w600
A090339 - OEIS

"Number of full curvilinear flups with n curves." : $n$ 本の曲線からなる"full curvilinear flups"の数. コメントを読もう.

　 $a(n)$ (訳中:このA090339の数列のこと)は無限長のn本の曲線のトポロジー的に異なる配置の数で, どの曲線も他の曲線とちょうど1点で交わり, どの2つの交点が一致することもない. $n < 8$ では $a(n)$ は, 曲線を線分に制限した場合であるA090338 $(n)$ に一致する.
　しかし, $n=8$ において, 我々は $a(n)$ の中に線分で描けない3つの配置を発見した. 「無限長」の条件は, 他の曲線で囲まれた領域の中に端点があるような配置を許さない. A090338 $(n)$ と同様に, 鏡映対称な配置は異なるものとして数えない.

$n=8$ の直線では実現できない配置3つのうち1つが参考に挙げられている.

　いったいどうやって見つけたのか見当がつかないが, 「直線のなす配置」を仮定するとユークリッド幾何学による難しい制約が加わることが分かる. 現に直線の場合A90338では, 曲線の場合A90339では分かっている $n=9$ が確定していない. そこで, 純粋に組み合わせ的な問題に帰着できる後者A90339をまずは考える.

　方針はこう：

曲線によって平面は2つの領域に分割される. それぞれに0と1を割り当てる. 曲線も数でラベリングし, 各領域に長さ $n$ の符号を対応させる.

f:id:shironetsu:20190505042510p:plain:w500
平面は $n(n+1)/2+1$ 個の領域に分けられている. $(n-1)(n-2)/2$ 個の有限領域と $2n$ 個の無限領域.

$n=k+1$ の場合は, $n=k$ の場合に曲線を加えることで生成する. Full $k-$ flups に含まれる, 2つの無限領域(対応する符号はたがいに反転の関係にある)を結ぶ経路(両端を含んで長さ $(k+1)$ )は末尾に0と1を加えて2つの領域に分割. 直線で隔てられた2つの領域のそれぞれで末尾に0か1の異なる数を加える.

同型性の判定が難しい. 直線の入れ替え, 0と1の反転を行うことである「標準形」に持っていく.

このアイデアに従ってコードを書いたが... $n=5$ まではうまくいくものの, $n=6$ で重複や不可能な配置を生成してうまくいかない(おそらく実装の問題). しかし, 生成された配置から(マニュアルで)それらを除いていくと, 何とか43個のfull 6-flupsを確定させることができた. 自己同型群別に以下に並べる.

自己同型群 : 自明な群 $E$ (位数1)…34個
f:id:shironetsu:20190505050102p:plain:w800
f:id:shironetsu:20190505050202p:plain:w800
f:id:shironetsu:20190505050236p:plain:w800

自己同型群 : 1次の2面体群(反転対称性) $D_1$ (位数2)...6個
f:id:shironetsu:20190505045856p:plain:w800

自己同型群 : 3次の巡回群 $C_3$ (位数3)...2個
f:id:shironetsu:20190505050341p:plain:w300

自己同型群 : 3次の2面体群 $D_3$ (位数6)...1個
f:id:shironetsu:20190505050416p:plain:w200

曲線は色で分けた. 無限長を仮定しているが, 交点をすべて含むように両端点を打ち切り.

こうして並べるとなかなか美しい. ちなみにグラフはdotファイルを生成してgraphvizからsvgで出力したもの.
https://www.graphviz.org/www.graphviz.org

なお, 既に述べたようにこれらはすべて直線の配置として実現可能. これを判定する方法はやはり分からない.

$n=7$ でこれと同じように列挙するのが次の目標. しかし, 現時点で想定通りにコードが動かないうえ, 同型性の判定に非常に時間がかかる.

A09338からリンクされている以下の論文やこの研究に関するホームページ, また参照されている論文などを見ていけばよさそう.
Finschi, Lukas, A graph theoretical approach for reconstruction and generation of oriented matroids - Research Collection, (2001). Diss., Mathematische Wissenschaften ETH Zürich, Nr. 14335, 2001.
www.om.math.ethz.ch

尻切れになってしまった. うまくいったら次の記事で, 列挙アルゴリズムの中身について論じる予定.