分割束上のメビウス変換を用いて closed formula を導く方針をご紹介いたします。

分割束上の関数 \(f\) の定義

集合 \(\lbrace 1, \dots, N \rbrace\) を \(\lbrack N \rbrack\) と表します。\(\lbrack N \rbrack\) の集合分割 \(\mathcal A\) に対して、次の条件を満たす整数列 \(X = \lparen X _ 1, \dots X _ N \rparen\) の個数を \(f ( \mathcal A )\) と置きます。

• \( 1 \le X _ i \le M \ ( 1 \le i \le N )\)
• \(X _ i = X _ j \Leftrightarrow \exist A \in \mathcal A: i, j \in A \ (1 \le i \lt j \le N)\)
• \(D _ i \vert X_ i \ (1 \le i \le N )\)

このとき答えは \(\lbrack N \rbrack\) の最も細かい分割 \(0 = \lbrace \lbrace i \rbrace \vert i \in \lbrack N \rbrack \rbrace\) に対する \(f\) の値 \(f(0)\) です。

\(f(0)\) の計算

\(\lbrack N \rbrack\) 上の集合分割全体の集合に、\(\mathcal A \le \mathcal B\) が \(\mathcal A\) が \(\mathcal B\) の細分であることと同値であるように順序を入れた束を \(\Pi \) と置くと、\(0\) は \(\Pi\) の最小元です。このとき、任意の \(\mathcal A \in \Pi\) に対し、

\[ \sum _ { \mathcal B \ge \mathcal A } f ( \mathcal B ) = \prod _ { A \in \mathcal A } \left \lfloor \frac { M } { \mathop { \mathrm { lcm } } _ { i \in A } ( X _ i) } \right \rfloor \]

が成り立ちます。ところで \(\Pi\) 上のメビウス関数 \(\mu\) は

\[ \mu ( 0, \mathcal A) = \prod _ { A \in \mathcal A } ( -1 ) ^ { \# \mathcal A - 1 } ( \# \mathcal A - 1 ) ! \]

を満たしますから、\(\Pi\) 上メビウス変換することで、closed formula

\[ f ( 0 ) = \sum _ { \mathcal A \in \Pi } \prod _ { A \in \mathcal A } ( -1 ) ^ { \# \mathcal A - 1 } ( \# \mathcal A - 1 ) ! \left \lfloor \frac { M } { \mathop { \mathrm { lcm } } _ { i \in A } ( X _ i) } \right \rfloor \]

を得ます。これは、和因子が分割成分に関する積に分かれていることを利用した \(\lbrack N \rbrack\) の部分集合全体に関する動的計画法により \(O ( 3 ^ N )\) で計算することができます。