分割と木の対応

多角形の分割方法は、以下の条件を全て満たす根付き木と一対一対応します。ただし、頂点にラベルはないが、子に順番はあるものとします。

• 葉がちょうど \(N - 1\) 個
• 葉でない頂点が根を含め \(k + 1\) 個
• 葉でない頂点の子の数を \(c\) としたとき、\(c + 1\) は \(S\) に含まれる

分割方法と木の対応は例えば以下のようにすれば良いです。ここで、線分 \(i\) を頂点 \(i\) と頂点 \(i + 1\) を結ぶ辺とします。ただし、線分 \(N\) は頂点 \(N\) と頂点 \(1\) を結ぶ辺であるとします。

• 分割された多角形 \(1\) つに対して、 \(1\) つの葉でない頂点を対応させる
• 線分 \(i (1\leq i\leq N - 1)\) に対して、葉である頂点を \(1\) つずつ対応させる
• \(2\) つの分割された多角形が同じ対角線を共有するときに限り、頂点同士を辺で結ぶ
• ある分割された多角形が線分 \(i (1\leq i\leq N - 1)\) を持つときに限り、それぞれに対応する頂点同士を辺で結ぶ。
• 線分 \(N\) を持つ多角形に対応する頂点を根とする。
• 子の順番は、葉が左から線分 \(1, 2, \dots , N - 1\) に対応する頂点の順になるようにする。

下の画像は、\(N = 5\) かつ \(k = 1\) であって、頂点 \(2\) と \(4\) を結ぶ対角線で分割する方法と木を対応させたものである。

木と数列の対応

上記の木は、根 \(1\) つのみからなる木から始めて以下の操作を \(N + k\) 回することで構築することができます。

• 行動 \(1, 2\) のいずれかを選んで行動する。ただし、行動 \(1\) は合計で \(N - 1\) 回行う
  • 行動 \(1\) : 一番左の葉を選び、その頂点を葉と確定させる。
  • 行動 \(2\) : \(s\in S\) を選び、葉のうち、葉だと確定していない頂点であって最も左の頂点から子を \(s - 1\) 個生やす。

例えば最初に示した五角形の分割と対応させた木は、以下のような操作で構築することができます。

上記の木を構築する操作列と数列 \(A\) を以下のようにして対応させます。

• \(A\) を空の状態から始めて、操作を前から見て \(A\) を次のように変更する。
  • 行動 \(1\) をしたときには \(-1\) を \(A\) の末尾に追加する。
  • 行動 \(2\) をしたときには \(s - 2\) を \(A\) の末尾に追加する。

例えば、画像の例だと \(A = (2, -1, 1, -1, -1)\) と対応する。

最終的にできる数列 \(A\) が以下の条件を全て満たすことが、操作列が valid であることの必要十分条件になります。

• \(|A| = N + k\)
• \(A\) に含まれる要素 \(a\) は \(a = -1\) もしくは \((a + 2)\in S\) を満たす
• \(A\) の総和は \(-1\) である
• 任意の \(1\leq i< N + k\) について、\(A_{1} + A_{2} + \cdots + A_{i} \geq 0\) が成り立つ

結局、上の条件を全て満たす数列 \(A\) の場合の数がそのまま答えになります。

数列の数え上げ

最後の条件を無視した数列の場合の数は \(\displaystyle f(x) = \sum_{s\in S}x^{s - 2}\) を用いて、 \(\binom{N + k}{k + 1}[x^{N - 2}] f(x)^{k + 1}\) となります。この値を \(C_{k}\) と定義します。

最後の条件を追加しても、Bertrand’s ballot theorem を用いると、\(\dfrac{C_{k}}{N + k}\) であることがわかります。

具体的には、以下の \(2\) つが一対一対応することから、\(A\) の場合の数が \(\dfrac{C_{k}}{N + k}\) であると示せます。

• 最後の条件も加えた数列 \(A\) と \(0\) 以上 \(N + k\) 未満の整数 \(x\) の組 \((A, x)\)
• 最後の条件を無視した数列 \(B\)

対応づけは \(A\) を左に \(x\) 回サイクリックシフトしたものを \(B\) とすれば良いです。例えば数列 \(A = (2, -1, 1, -1, -1)\) と \(x = 3\) の組は \(B = (-1, -1, 2, -1, 1)\) と対応されます。

よって、任意の \(0\leq k\leq N - 3\) に対して \(\dfrac{C_{k}}{N + k}\) を求めれば良いです。ボトルネックとなるのは、任意の \(0\leq k\leq N - 3\) に対して \(C_{k}\) を求める部分です。この問題は Power Projection と呼ばれており、時間計算量 \(O(N\log^{2}(N))\) で求められます。

よって、この問題の答えも同じ時間計算量で求めることができます。

Power Projection に関する参考記事

• noshi91 さんによる発見の記事
• maspy さんによる詳しい解説