三角形の個数

質問

平面にｎ本の直線をどの２本も平行でなく、また、
どの３本も１点で交わらないように引きます。
このとき、直線群は平面をいくつかの部分に分割します。
その分割された部分のうち、３角形になっている部分の個数を
問題にするのですが、その個数は直線群の配置によっては、異なったりします。
そこで、n本直線を引いたときできるそのような３角形の個数の最小値を
ｎの式で表してください。

何気なく作った問題ですが、いまだに解けていません。
（そういうもんかもしれないが…。）

回答No.17

stomachman

中間報告、続きです。
　まだ問題の核心には全然迫れていません。単に幾何を離れて離散数学の領域に問題を移して、探ってみているに過ぎないところです。
　前回(No.15)の話の[1]～[3]では、N本の直線からなる配置の「座標の回転を除いて位相同型」な同値類に一意的に対応する表現である「図形」を定義しました。そして図形に対して、もう一本の直線を「プローブ」として用い、プローブを平行移動させて行くことで飛び越え変換を定義して、飛び越え変換の列から図形Xを再構成できること、ならびに、<0,1,.....,N-1>の隣り合う要素を入れ替える操作をN(N-1)/2回行って<N-1,....,1,0>に並べ替えるsortの手順の集合が、可能な「飛び越え変換の列」の集合と一致し、従って図形と対応している、ということを述べました。これでなんとか、紙に変な図形を描き散らすことなく検討できるようになったかな、という所。
　なお、[4]は三角形の個数について雑多な事を並べてみたものに過ぎません。
　どのLemmaも完璧に証明できているか、と訊かれたらごめんなさいなんですけど…

　三角形とsortの手順（飛び越え変換の列）との関係をもう少し密接に表現することを試みます。

[5] 飛び越え変換の列と、三角形
　まず[3]において導入した「飛び越え変換の列」を記号化しておきましょう。
{0,1,....,N-1}から２個の元を選ぶ組み合わせの集合を、
Cmb={c| c⊂{0,1,....,N-1} ∧ |c|=2}
とする。Cmbの濃度はN(N-1)/2で、Cmbの元はいずれも２個の元からなる集合である。
ここで1:1対応 J : {1,....,N(N-1)/2}→Cmb
を考えると、Jは２個の元から成る集合cの列（列の要素はいずれもCmbの元である）を定める。これを
J[n] (n∈{1,....,N(N-1)/2})
と書いて「変換列」と呼ぶ。
Jが「飛び越え変換列」であるとは、Jが変換列であって、さらに以下のようなN-対の列X(N,0), X(N,1).....が存在して、
・X(N,0) = <0,1,.....,N-1>
・∀n∈{1,....,N(N-1)/2}について、J[n] = {a,b} (a>b)に対して、X(N,n-1)中でb,aがこの順で隣接している箇所が存在し、つまりX(N,n-1) = <......,b,a,......> である。さらに、X(N,n)はこのa,bを入れ替えたもの X(N,n) = <.....,a,b,.....> である。
を満たすことである。

(Lemma5-1)飛び越え変換列Jにおいて、
・{p,q,r}⊂{1,....,N(N-1)/2}、p<q<r
・J[p]∩J[q] ≠φ　（φは空集合）
・J[r]=(J[p]∪J[q])-(J[p]∩J[q])　（p≠qよりJ[p]≠J[q]なので、右辺は２個の元を持つ集合になる。）
・∀s(p<s<q→J[s]∩J[p]=φ)
・∀s(q<s<r→J[s]∩J[r]=φ)
を満たす集合{p,q,r}が存在するとき、そのときに限り、Jから再構成される図形には三角形J[p]∪J[q] （=J[p]∪J[q]∪J[r]）が存在する。この集合{p,q,r}をJにおける「三角index」と呼ぶ。

　さて、二つの飛び越え変換列K,Jを考え、Kから再構成される図形と、Jから再構成される図形とが同一であるとき、これらは「同値」であると言うことにして、
K～J
と書くことにします。（～は明らかに同値関係です。）ある飛び越え変換列Jが与えられたとき、これと同値の飛び越え変換列Kは以下のようにして得られます。

(Lemma5-2)飛び越え変換列Jについて、要素J[n-1]とJ[n]を入れ替えた変換列をKとする。変換列KがJと同値の飛び越え変換列であるための必要十分条件は
J[n-1]∩J[n]=φ
である。

　特定の飛び越え変換列Jを与えたとき、「(Lemma5-2)の入れ替えが不能である」という事を順序として表現すれば、Jの要素間に半順序関係が自然に決まります。この半順序を崩さない限り、随意に並べ替えても同値という訳です。従って、

(Lemma5-3)Jの任意のひとつの三角index {p,q,r}について、Jと同値の飛び越え変換列Kを構成して、その三角indexがKの引き続く３つの要素の添字{n-2,n-1,n}に対応するようにできる。すなわち
{J[p],J[q],J[r]}={K[n-2],K[n-1],K[n]}
を満たすようにKを構成できる。
（しかし、Jと同値のある一つの飛び越え変換列K上で、Jの全ての三角indexが同時にそれぞれ、引き続く３つの要素の添字になるように並べ替えることは一般にはできない。）

　任意の飛び越え変換列において、相異なる三角indexが(N-2)個以上存在することを示せば、元の問題が解決したことになります。つまり、図形と縁を切って、飛び越え変換列の性質だけの問題に落とせると思うんです。
　一方、単なる変換列であれば、ひとつも三角indexがないように構成することが実際可能です。だから、三角indexの数は飛び越え変換列であるということと分かちがたく関連しています。ある変換列Jが飛び越え変換列であるかどうかを、X(N)のsortに依らずに、J自体の特徴で表現する必要条件が欲しいところです。
　また、飛び越え変換列全体を～で同値類に分けて代表元を選ぶ。そうすると、代表元と図形が１：１に対応する。そこで代表元について三角indexが(N-2)個以上存在することを示せば良かろう、というのがもう一つのアイデアなんですが、代表元の選び方をどのように定めれば便利なのかまだ見当が付きません。

(Lamma5-4) Jが飛び越え変換列であるとき、
X(N,0) = <0,1,.....,N-1> すなわち X(N,0)[k] = k (k=0,1,....,N-1)
とし、
J[n] = {a,b}に対して、互換
・X(N,n)[b] = X(N,n-1)[a]
・X(N,n)[a] = X(N,n-1)[b]
・X(N,n)[k] = X(N,n-1)[k] (k∈{0,...,N-1}-J[n])
を対応させると、
X(N,N(N-1)/2) = <N-1,.....,0> すなわちX(N,N(N-1)/2)[k] = N-1-k (k=0,1,....,N-1)
である。（つまりX(N,0)がsortされる。）
　これはあんまり使い途はなさそうです。