数え上げのための半順序集合入門

StanleyのEnumerative Combinatoricsの半順序集合の章を輪読したので、競技プログラミングと直接関係があることだけまとめました。同じようなテイストの記事だと、maspyさん、convexineqさんがあります。

記号の準備

$[n]=\{1,2,\ldots, n\}$
$\boldsymbol{(n)}=1+q+\ldots+q^{n-1}$
$\boldsymbol{(n)!}=\boldsymbol{(1)}\boldsymbol{(2)}\cdots \boldsymbol{(n)}$
${\boldsymbol n \choose \boldsymbol i} = \frac{\boldsymbol{ (n)!}}{\boldsymbol{ (i)!\boldsymbol{ (n-i)!}}}$

半順序集合

集合 $P$ が次の３条件を満たす二項演算 $ < $ を備えているとき、半順序集合と呼びます。

$a \leq a$
$a \leq b$ かつ $b \leq c$ ならば $a \leq c$
$a \leq b$ かつ $b \leq a$ ならば $a = b$

以降、半順序集合（Partially Ordered Set）は基本的に $P$ と置きます。最小元と最大元を（存在するならば）$\hat 0, \hat 1$ と書きます。競技プログラミングで頻出する半順序集合には次のようなものがあります。

$[n]$ の各元に対して、通常の大小を入れた半順序集合を $\boldsymbol{n}$
任意の正整数に対して、通常の大小を入れた半順序集合を $\mathbb{N}$
$[n]$ の各部分集合 $S, T$ に対して、$S \subseteq T$ ならば $S \leq T$ と定めた半順序集合 $B_n$
正整数$n$ の約数 $i, j$ に対して、$i | j$ ならば $i \leq j$ と定めた半順序集合 $D_n$
素数冪 $q$ を取ります。$\mathbb{F}_q$ 係数 $n$ 次元ベクトル空間の部分空間全体に対して、包含関係で順序を定めた半順序集合 $B_n(q)$
$[n]$ の分割 $\pi, \rho$ について、$\pi$ の各元が $\rho$ のある元の部分集合であるとき、$\pi$ は $\rho $ の細分であるといいます。$\pi$ が $\rho$ の細分ならば $\pi \leq \rho$ と定めた半順序集合 $\Pi_n$

二つの半順序集合 $P, Q$ に対して、直積 $P \times Q$ を、 $\{(s ,t) : s \in P, t \in Q\}$ について、$P$ で $s \leq s’$ かつ $Q$ で $t \leq t’$ ならば $P \times Q$ で $(s, t) \leq (s’, t’)$ と定めた半順序集合とします。例えば、$B_n$ は $\overbrace{\boldsymbol{2} \times \boldsymbol{2} \times \cdots \times \boldsymbol{2}}^{\text{$n$ times} } = \boldsymbol{2}^n$ と同型です。$P$ に対して、同じ台集合で大小関係だけ反転させて $a \leq_P b \iff b \leq_{P^*} a$ とした半順序集合 $P^*$ を $P$ の双対と呼びます。

束

半順序集合 $P$ の要素 $x, y \in P$ について、 $x \leq a$ かつ $y \leq a$ を満たす極小な $a$ が一意に定まるとき、$x, y$ の結び $a$ と呼び、 $a = x \lor y$ と書きます。同様に、 $x \geq a$ かつ $y \geq a$ を満たす極大な $a$ が一意に定まるとき、$x, y$ の交わり $a$ と呼び、$a = x \land y$ と書きます。任意の2元に対して結びと交わりが定まるような半順序集合を束と呼びます。有限束 $P$ には、全ての元に関する結び $\hat 0 = \bigwedge_{x \in P} x$ と交わり $\hat 1 = \bigvee_{x \in P} x$ が定まります。以降、基本的には束（Lattice）を $L$ と置きます。

$\boldsymbol{n},B_{n},D_n,\Pi_{n},B_n(q)$ は全て束です。

$\boldsymbol{n}$ の場合、$s \lor t = \max(s, t), s \land t = \min(s, t)$
$B_{n}$ の場合、$s \lor t = s \cup t, s \land t = s \cap t$
$D_n$ の場合、$s \lor t = \mathrm{lcm}(s, t), s \land t = \gcd(s, t)$
$B_n(q)$の場合、$s \lor t = s + t, s \land t = s \cap t$

全ての元について交わりが定義される半順序集合を交わり半束、結びが定義される半順序集合を結び半束と呼びます。

$x_1, x_2, \ldots, x_n \in P$ が $x_1 < x_2 < \cdots < x_n$ を満たすとき、$x_1, x_2, \ldots, x_n$ からなる順序集合を長さ $n-1$ の鎖と呼びます。また、$<$ を $\leq$ に置き換えた列を多重鎖と呼びます。任意の極大鎖が同じ長さを持つ半順序集合を、階層的であるといいます。階層的な半順序集合の各元 $x$ に対して、$\hat 0, x$ を２端点とする極大鎖の長さを $x$ のランクと呼び、$\rho(x)$ と置きます。$\boldsymbol{n},B_{n},D_n,\Pi_{n},B_n(q)$ は全て階層的です。

$\boldsymbol{n}$ の場合、$\rho(x) = x-1$
$B_{n}$ の場合、$\rho(x) = |x|$
$D_n$ の場合、$\rho(x)$ は $x$ の素因数の個数（重複も数える）
$B_n(q)$の場合、$\rho(x) = \mathrm{dim}(x)$

束 $L$ の任意の $x, y \in L$ に対して、$\rho(x)+\rho(y)=\rho(x \land y) + \rho(x \lor y)$ が成り立つとき、$L$ をモジュラー束と呼びます。$\boldsymbol{n},B_{n},D_n,B_n(q)$ はモジュラー束です。

半順序集合 $P$ の部分集合 $I$ について、$t \in I$ かつ $s \leq t$ ならば $s \in I$ を満たすとき、順序イデアルと呼びます。$P$ の順序イデアル全体を包含関係で順序付けた束を $J(P)$ と書きます。半順序集合 $P$ の有限順序イデアル全体を包含関係で順序付けた束を $J_f(P)$ と書きます。

隣接代数

$s \leq t$ なる2元 $s, t \in P$ に対して、部分半順序集合 $\{x : s \leq x \leq t\}$ を区間 $[s, t]$ と呼びます。半順序集合 P の区間（Interval）全体を Int(P) と置きます。任意の区間が有限であるような半順序集合を、局所有限であるといいます。体 $K$ を取ります（競技プログラミングだと、$\mathbb{R}, \mathbb{C}, \mathbb{F}_p$ がほとんど）。局所有限な半順序集合 $P$ の関数 $\mathrm{Int}(P) \to K$ 全体に対して $K$ 係数ベクトル空間の構造と乗算 $$fg(s, t) = \sum_{s \leq x \leq t} f(s, x)g(x, t)$$ を定めたものを隣接代数 $I(P, K)$ と呼びます。ただし、$f([s, t])$ を $f(s, t)$ と略記しています。関数 $f : P \to K$ に対する $\alpha \in I(P, K)$ の左作用・右作用を $$(\alpha f)(x) = \sum_{x \leq y}\alpha(x, y)f(y)$$および$$(f \alpha)(x) = \sum_{y \leq x}f(y)\alpha(y, x)$$ とします。$P$ の元を、相対的な順序を保ったまま適当に全順序にして $t_1, t_2, \ldots, t_{|P|}$ と置きます（競技プログラミングのトポロジカルソート）。$f \in \mathrm{Int}(P)$ に対して、$A_{ij} = \begin{eqnarray}
\left\{
\begin{array}{l}
f(t_i, t_j) & (t_i \leq t_j) \\
0 & (\text{otherwise})\\
\end{array}
\right.
\end{eqnarray}$ で定まる上三角行列 $A$ を対応付けると、$I(P, K)$ はこれらの行列がなす $K$ 上の代数と同型です。また、$f : P \to K$ への作用は、行列のベクトルへの作用に対応しています。$f, g : P \to K$ の積を $(fg)(x)=\sum_{x} f(x)g(x)$ とします。$f \in \mathrm{Int}(P)$ を $f_P$ と書くことがあります。

ゼータ関数

ゼータ関数 $\zeta \in \mathrm{Int}(P)$ を $\zeta(x, y) = \begin{eqnarray}
\left\{
\begin{array}{l}
1 & (x \leq y)\\
0 & (\text{otherwise})
\end{array}\right.\end{eqnarray}$ で定めます。$I(P, K)$ の単位元 $\delta$ を $\delta(x, y) = \begin{eqnarray}
\left\{
\begin{array}{l}
1 & (x = y)\\
0 & (\text{otherwise})
\end{array}\right.\end{eqnarray}$ と定めます。誤解がない場合は、$1$ と略記します。

\begin{align}
\zeta^k(x, y) =& \sum_{x = s_0 \leq s_1 \leq \cdots \leq s_{k+1} = y} \zeta(s_0, s_1)\zeta(s_1, s_2) \cdots \zeta(s_k, s_{k+1}) \\ =& \sum_{x = s_0 \leq s_1 \leq \cdots \leq s_{k+1} = y} 1 \end{align} は $x, y$ を端点とする長さ $k+1$ の多重鎖 $s_0 \leq s_1 \leq \cdots \leq s_k$ の個数に等しいです。また、\begin{align}
(\zeta-1)^k(x, y) =& \sum_{x = s_0 < s_1 < \cdots < s_{k+1} = y} 1 \end{align} は $x, y$ を端点とする長さ $k+1$ の鎖の個数に等しいです。$\sum_{k \geq 0} (\zeta-1)^k (x, y) = (2-\zeta)^{-1}(x, y)$ は $x, y$ を端点とする鎖の個数に等しいです。

直積 $P \times Q$ に対して、$\zeta_{P \times Q} = \zeta_P \otimes \zeta_Q = (\zeta_P \otimes 1_Q)(1_P \otimes \zeta_Q)$ が成り立ちます。

$\boldsymbol{n} \times \boldsymbol{m} \times \boldsymbol{k}$ の $\hat 0, \hat 1$ を2端点とする鎖の個数を求めよ（yukicoder940, maspyさん）。

メビウス関数

メビウス関数 $\mu \in $ を $\zeta \mu = \mu \zeta = \delta$ を満たす一意な関数として定めます。$ (\zeta \mu)( x, y) = \delta(x, y)$ は $$ \sum_{x \leq z \leq y} \mu(z, y) = \begin{eqnarray}
\left\{
\begin{array}{l}
1 & (x = y)\\
0 & (\text{otherwise})
\end{array}\right.\end{eqnarray}$$
と同値なので、この式を用いると、$\mu(\hat 0, x)$ を $x$ の昇順に求めることができます。未知のメビウス関数を、手計算で求める際に便利です。
$\hat 0, \hat 1$ を端点とする長さ $k$ の鎖の個数を $c_k$ と置くと、
\begin{align}
\mu(\hat 0, \hat 1) &= (1+(\zeta-1))^{-1}(\hat 0, \hat 1) \\
&=\sum_{k \geq 0} (-1)^k(\zeta-1)^k (\hat 0, \hat 1)\\
&=\sum_{k \geq 0} (-1)^kc_k(\hat 0, \hat 1)
\end{align}が成り立ちます（Hallの公式）。球面上の平面グラフの頂点数、辺数、面数を $V, E, F$ としたときに、$-1 = 1-V+E-F$ (簡約オイラー標数) が成り立つことと関連があります。$f=\zeta g$ とすると $g = f-(\zeta-1)g$ が成り立つことを用いて $f$ から $g$ を計算することが、競技プログラミングでは、除原理と呼ばれています（競プロフレンズ）。除原理を繰り返し用いても Hall の公式が得られます。

$f, g : K \to P$ に対して、$$f = \zeta g \iff \zeta^{-1} g$$ および $$f = g\zeta \iff f \zeta^{-1} = g$$ が成り立つことをメビウスの反転公式と呼びます（下位集合のゼータ・メビウス変換では $\{s : s \leq t\}$ の有限性を課す必要があります。上位集合でも同様）。

直積 $P \times Q$ のゼータ関数は定義より $\zeta_{P \times Q} ((s, t), (s’,t’))= \zeta_P(s, s’) \zeta_Q(t, t’)$ が成り立ちます。同様に、メビウス関数は $\mu_{P \times Q} ((s, t), (s’,t’))= \mu_P(s, s’) \mu_Q(t, t’)$ が成り立ちます。具体的には、次のような式変形に基づきます。

\begin{align}
(\zeta_{P \times Q} \mu_{P \times Q}) ((s, t), (s’,t’)) &= \sum_{s \leq s” \leq s’, t \leq t” \leq t’}\mu_{P \times Q}((s”, t”),(s’,t’)) \\
&= \sum_{s \leq s” \leq s’}\mu_{P}(s”,s’) \sum_{t \leq t” \leq t’}\mu_{P}(t”,t’) \\
&=\delta_P(s, s’)\delta_Q(t,t’)\\
&=\delta_{P \times Q}((s, t), (s,t’))
\end{align}

$\mu_{P \times Q}= (\zeta_P \otimes 1_Q)^{-1}(1_P \otimes \zeta_Q)^{-1} = (\mu_P \otimes 1_Q)(1_P \otimes \mu_Q) = \mu_P \otimes \mu_Q$ と思ってもよいです。

$\boldsymbol{n}$ のメビウス関数

$\boldsymbol{n}$ において $[a, b] \cong \boldsymbol{b-a+1}$ なので、$\mu_\boldsymbol{n}(\hat 0, \hat 1)$ の形に全て帰着できます。$(1+x+x^2+\cdots)^{-1} = 1-x$ より $\mu_{\boldsymbol n}(\hat 0, \hat 1) = \begin{eqnarray}
\left\{
\begin{array}{l}
1 & (n = 1)\\
-1 & (n = 2) \\
0 & (\text{otherwise})
\end{array}
\right.
\end{eqnarray}$ です。

$B_n$ のメビウス関数

$B_n \cong \boldsymbol{2}^n$ より $\mu_{B_n}(S, T) = (-1)^{\#T-\#S}$ です。$\mu(S, T) = \left[\frac{x^n}{(\#T-\#S)!}\right]\exp(x)^{-1}$ からも分かります。

$D_n$ のメビウス関数

$D_n$ において、$[a, b] \cong [1, b/a]$ なので $\mu_{D_n}(\hat 0, \hat 1)$ の形に全て帰着できます。素因数分解すると $n = \prod p_i^{e_i}$ となるとき、$D_n \cong \prod (\boldsymbol{e_i+1})$ なので $\mu_{\boldsymbol n}(\hat 0, \hat 1) = \begin{eqnarray}
\left\{
\begin{array}{l}
(-1)^{e_i} & (\text{$n$ is square free}) \\
0 & (\text{otherwise})
\end{array}
\right.
\end{eqnarray}$ です。
$\mu_{D_n}(\hat 0, \hat 1)=[n^{-s}](\sum_i i^{-s})^{-1} = [n^{-s}] \prod_i(1-p_i^{-s})$ からも分かります（maspyさん）。
$\mu_{P \times Q} = \mu_P \otimes \mu_Q$ を利用して、$\mu_{D_{{p_i}^{e_i}}}$ を個別に作用させると $O( \log\log n)$ で $\mu_{D_n}f$ が得られます。競技プログラミングでは高速メビウス変換と呼ばれています。

$\Pi_n$ のメビウス関数

区間 $[\rho , \pi]$ はいくつかの分割束の直積になります。例えば、$\rho =\{\{1,2\},\{3,5\},\{4\},\{6\}, \{7\}\} , \pi = \{\{1,2,3,5,6\}, \{4, 7\}\}$ ならば $[\rho, \pi] \cong \Pi_3 \times \Pi_{2}$ です。従って、全て $\mu_{\Pi_n}(\hat 0, \hat 1)$ の形の直積に帰着できます。
$\exp(f)-1 = x \iff f = \log(1+x)$ より $\mu_{\Pi_n}(\hat 0, \hat 1) = \left[\frac{x^n}{n!}\right]f = (-1)^{n-1}(n-1)!$ です。

特定のランク全体のゼータ・メビウス変換

$\hat 0$ が存在する有限半順序集合 $P$ に対して、特性多項式を $\chi_P(x) = \sum_{t \in P}\mu(\hat 0, t) x^{n-\rho(t)}$ と置きます。

$B_n$ では、$[a, b] \cong B_{\rho(b)-\rho(a)}$ という関係が成り立ちます。このことから、$g(S) = \sum_{S \subseteq T} f(T)$ に対して、
\begin{align}
\sum_S f(S)x^{\rho(S)} &=\sum_{S} x^S \sum_{S \leq T} \mu(S, T)g(T) \\
&=\sum_T g(T) \sum_{S \leq T} \mu_{B_{\rho(T)-\rho(S)}}(\hat 0, \hat 1)x^S \\
&= \sum \chi_{B_{k}}(x)\sum_{\rho(T) = k} g(T)
\end{align} を得ます。$B_n(q)$ でも同様の式が成り立ちます。

メビウス関数を代入して具体的に計算すれば、$\chi_{B_n}(x)=(x-1)^n, \chi_{B_n(q)}=(x-1)(x-q)\cdots(x-q^{n-1})$ を得ます。$\chi_{B_n(q)}$ では q-2項定理を使いました。$G(k) = \sum_{\rho(S)=k} g(k)$、$F(k) = \sum_{\rho(S)=k} f(k)$ とすると、$B_n$ において、$G$ と $F$ の変換は polynomial taylor shift により、$O(n \log n)$ でできます。$B_n(q)$ においても、q類似の式により同じ計算量で変換できます。polynomial taylor shift は $B_n \cong B_n^*$ や $B_n(q) \cong B_n(q)^*$ を用いて、簡約隣接代数の掛け算に帰着しています。

$t \in B_n$ に対して、$f(t)x^{\#t} = f(t)\#[x]^t$ と読み替えます。$\sum F(k)x^k = \sum G(k)(x-1)^k$ の右辺は $[x]^{t}$ のうち、像が $[x-1]$ に含まれる値域のサイズ $k$ 毎に分けて数えています。要素数 $x$ の $\mathbb{F}_q$ 係数線形空間を $V(x)$ と置きます。$t \in B_n(q)$ に対して、$f(t)x^{\dim t} = f(t)\# \hom_{\mathbb{F}_q}(t, V(x))$ と読み替えます。$\sum F(k)x^k = \sum G(k)(x-1)(x-q)\cdots(x-q^{k-1})$ の右辺は $\phi \in \hom_{\mathbb{F}_q}(t, V(x)) $ について、$k = \dim \operatorname{im}(\phi)$ 毎に分けて数えています。$t’=t/\ker \phi$ 毎に単射 $t’ \to W$ の取り方が $(x-1)(x-q)\cdots(x-q^{k-1})$ 通りあります。

$\Pi_n$ の下位集合に対するメビウス変換は、同じランクをまとめて計算すると、$$G(j) = \sum_{i=0}^{n-1} {n-i \brace n-j} F(i) \Longleftrightarrow F(j) = \sum_{i=0}^{n-1} (-1)^{j-i} {n-i \brack n-j} G(i)$$ となります（かならいさん）。

$\boldsymbol n, B_n, B_n(q)$ の下位集合に対するゼータ・メビウス変換を、同じランクをまとめて計算するのは、簡約隣接代数で説明できるので、後の章に回します。

メビウス代数

$f, g : P \to K$ の各点積 $f\odot$ を $(f\odot g)(x)= f(x)g(x)$ で定義します。$h(x) = \sum_{y \lor z = x} f(y)g(z)$ とすると、$\sum_{x \leq y} h(y) = \sum_{x \leq y} f(x) \sum_{x \leq z} g(z)$ なので $h = \zeta^{-1}(\zeta f \odot \zeta g)$ が成り立ちます。
$a \in P$ に対して $\delta_a, \delta_{\leq a}, 1′ : L \to K$ を $\delta_a(x) = [x=a], \delta_{\leq a} = [x \leq a], 1′(x) = 1$ で定義します。$\zeta \delta_a = \delta_{\leq a}$ です。$1′ \odot f = f \odot 1′ = f$ です。

Weisnerの定理

次の式をWeisnerの定理と呼びます。

\begin{align}
&\sum_{t : t \land a = \hat 0} \mu(t, \hat 1) \\
=& \delta_{\hat 0}\zeta(\zeta\zeta^{-1} \delta_{\hat 1} \odot \zeta\delta_a) \\
=& \delta_{\hat 0}\zeta(\delta_{\hat 1} \odot \delta_{\leq a})\\
=& 0
\end{align}

次のような導出もあります。$\hat 1′ \in P$ に対して、$x \mapsto x \land \hat {1′}$ は $P$ から $P’=[\hat 0, \hat 1′]$ への写像です。$g : P \to K$ に対して $g’:P’ \to K$ を $g'(x) = \sum_{y \land \hat {1′} = x} g(y)$ で定義します。すると、
\begin{align}
&\sum_{x \leq y \leq \hat {1′}} g'(y)= \sum_{x \leq y} g(y) \\
\iff & g'(x) = \sum_{x \leq y \leq \hat {1′}} \mu(x,y)\sum_{y \leq z}g(z)
\end{align}
を得ます。$g(x) = \mu(x, \hat 1)$ とすると Weisner の定理になります。この式変形は競技プログラミングで何度か出題されています。

$f, g : B_n \to K$ が与えられる。$h(k) = \sum_i f(i)g(i \cap k)$で定義される関数 $h$ を求めよ（yukicoder 1503）。
$S \subseteq [n]$ が与えられる。$S$ の要素 $s$ であって $j=\gcd(i, s)$ を満たすものが存在するか、全ての $j|i$ について求めよ（ARC155D）。
$\omega$ を $1$ の原始 $n$ 乗根とする。$\sum_{0 \leq i < n, \gcd(i, n) = k} \frac{1}{\omega^{ij}}$ を求めよ（ARC145F）

Weisner の定理により、半束のメビウス関数が計算できます。

$a$ をある $n-1$ 次元線形部分空間として固定します。$B_n(q)$ のうち、一次元部分空間は $\boldsymbol{{n \choose 1}}$ 個あり、そのうち、$a$ の部分空間であるものは $\boldsymbol{{n-1 \choose 1}}$ 個です。従って $a \land t = \hat 0$ かつ $t \neq \emptyset$ であるものは $\boldsymbol{{n \choose 1}}-\boldsymbol{{n-1 \choose 1}} = q^n$ 個あります。$\mu_n=\mu_{B_n(q)}(\hat 0, \hat 1)$ と置くと、Weisner の定理より $\mu_{n} = -q^n\mu_{n-1}=q^{n \choose 2}(-1)^{n}$ です。
$\{1, 2, \ldots, n-1\}, \{n\}$ の2つのブロックからなる分割を $a$ と置きます。$t \land a = \hat 1$ となるのは、$t = \hat 0$ または $t$ が $n$ を含む一つのサイズ2のブロックと $n-2$ 個のサイズ $1$ のブロックからなるときのみです。後者のような元は $n-1$ 通りあるので、$\mu_n = \mu_{\Pi_n}(\hat 0, \hat 1)$ と置くとWeisnerの定理より $\mu_n = -(n-1)\mu_{n-1}= (n-1)!(-1)^{n-1}$ です。
$[n]$ の部分集合のうち、長さ $k$ 未満の極大連続整数列が存在しないもの全体を包含関係で順序付けた半順序集合を $B_{n, k}$ と置きます。$\mu_{B_{n, k}}$ を Weisner の定理で求めてください（AGC58D）

cross-cut定理

有限束 $L$ に対して、部分集合 $X$ が、$\hat 1 \not \in X$ かつ $s \in L$ について、$s \neq \hat 1$ ならばある $t \in X$ に対して、$s \leq t$ を満たすとします。$N_k$ を $X$ の $k$ 元部分集合のうち、交わりが $\hat 0$ であるものの個数とします。次が成り立ちます。

\begin{align}
&\sum_k N_k(-1)^k \\
=&\delta_{\hat 0}\zeta^{-1}\bigodot_{t \in X} (1′-\zeta\delta_{a_i}) \\
=&\delta_{\hat 0}\zeta^{-1}\bigodot_{t \in X} (1′-\delta_{\leq t}) \\
=&\delta_{\hat 0}\zeta^{-1}\bigodot_{t \in X} \delta_{\not\leq t} \\
=&\mu(\hat 0, \hat 1)
\end{align}

cross-cut定理より順序イデアルのメビウス関数が求まります：$\begin{eqnarray}
\mu_{J(P)}(s, t)
=
\begin{cases}
(-1)^{\#t-\#s} & ( \text{$t \setminus s$ is antichain of $P$} ) \\
0 & (\text{otherwise})
\end{cases}
\end{eqnarray}$
$\mu_{B_{n, k}}$ を cross-cut 定理で求めてください（AGC58D）

ランク付きゼータ・メビウス変換

モジュラー束では
$$\rho(s) + \rho(t) = \rho(s \lor t) \Leftrightarrow s \land t = \hat 0$$が成り立ちます。$B_n, D_n, B_n(q)$ は全てモ
ジュラー束です。従って、ランク付きで $h = \zeta^{-1}(\zeta f \odot \zeta g)$ を計算すると、$h(x) = \sum_{y \lor z = x, y\land z = \hat 0} f(y)g(z)$ が得られます（37zigen, maspyさん、ながたかなさん）。

相反定理

\begin{align}
&\Omega_P(n) = \#\{\phi : [n] \to P:a \leq_P b \Longrightarrow \phi(a) \leq \phi(b)\} \\
&\overline{\Omega}_P(n) = \#\{\phi : [n] \to P : a <_P b \Longrightarrow \phi(a) < \phi(b)\}
\end{align}
と置くと$(-1)^{\#P}\Omega_P(-n) = \overline{\Omega}_P(n)$が成り立ちます。

例えば、$P = \boldsymbol{d}$とすると
\begin{align}
\Omega_P(n) &= \left(\!\!{n \choose d}\!\!\right) \\
&=(-1)^d {-n \choose d} \\
& =(-1)^d\overline{\Omega}_P(-n)
\end{align}

(証明）：順序イデアル$J(P)$において$\Omega_P(n) = \zeta^n(\hat 0, \hat 1)$です。$J(P)$の区間$[s, t]$について、$t\setminus s$が反鎖でないときは$\mu(s, t) = 0$、反鎖であるときは$\mu(s, t)=(-1)^{|t\setminus s|}$です。従って、$\overline\Omega_P(n)=(-1)^{\#P}\Omega(-n)=(-1)^{\#P}\mu^n(\hat 0, \hat 1)$

彩色多項式と非巡回的向き付け

グラフ$G$の彩色多項式を$\lambda$で評価した値$\chi(\lambda)$は次の条件を満たす組$(\sigma, o)$の個数に等しいです。

$o$は$G$の辺の向き付けで閉路を持たない。
写像$\sigma : V \to [\lambda]$
$u$から$v$に向きづけられているならば、$\sigma(u) < \sigma(v)$

一方、$\sigma(u) < \sigma(v)$ を $\sigma(u) \leq \sigma(v)$ に取り換えた時の組の個数を $\overline \chi (\lambda)$ と置きます。$\chi$ は各向き付け $o$ に誘導される半順序集合の順序多項式の和で表せるから、$\chi(\lambda)=(-1)^n\overline\chi(-\lambda)$ です。$\lambda=1$ のとき1色だけだから、$\overline \chi(1)$ は非巡回的向き付け（有向サイクルが存在しない向き付け）の個数に等しいです。

二項半順序集合

次の3つの条件を満たす半順序集合Pを二項半順序集合と呼びます。

$\hat 0$ を持ち、局所有限で、無限鎖を持つ。
任意の区間 $[s, t]$ は階層的である。
長さ $n$ の区間の極大鎖の個数 $B(n)$ は $n$ だけで決まる。$B(n)$ を階乗関数と呼ぶ。

有名な二項半順序集合には次のようなものがあります。

$\mathbb{N}$に自然な大小関係を入れる。$B(n)=1$。
$\mathbb{N}$の任意の有限な部分集合に包含関係で大小を入れる。$\mathbb{B}$と置く。$B(n) = n!$。
$\mathbb{F}_q$係数無限次線形空間の任意の有限次部分空間に包含関係で大小を入れる。$\mathbb{B}(q)$と置く。$B(n) = \boldsymbol{(n)!}$

二項半順序集合 $P$ に対して、$n$-区間のランク$i$の要素の個数は $${n \choose i}_P := \frac{B(n)}{B(i)B(n-i)}$$と表せます。これは、分母を払って、${n \choose i}_PB(i)B(n-i) = B(n)$ とすると、$B(i)B(n-i)$ はある固定した要素ランク$i$の要素$u$ を通る極大鎖の個数であることから分かります。

$A(i) = {n \choose 1}_P$ と置くと、$n! = n (n-1) \cdots 1$ の類似物 $B(n) = A(n)A(n-1) \cdots A(1)$ が成り立ちます。

二項半順序集合 $P$ の隣接代数 $I(P, K)$ のうち、区間の長さだけに依存する関数全体を $R(P)$ と置きます。$f \in R(P)$ について、$l(s, t)=n$ ならば $f(n) = f(s,t)$ と置きます。このとき、$\phi : R(P) \to K[[x]]$ を $$\phi(f) = \sum_{n \geq 0} f(n) \frac{x^n}{B(n)}$$ で定めると代数の同型になります。

代数の同型とは$k \in K, f,g \in R(P)$について、$\phi(fg) = \phi(f)\phi(g), \phi(f+g)=\phi(f)+\phi(g), \phi(kf) = k\phi(f)$が成り立つこと。

（証明）$f, g \in R(P)$とします。$f + g \in R(P)$, $\phi(f)+\phi(g) = \phi(f+g)$は明らか。
\begin{align}
fg(s, t) &= \sum_{u \in [s, t]} f(s, u)g(u, t) \\
&= \sum_{i = 0}^n {n \choose i}_P f(i)g(n-i) \\
&= [x^n / B(n) ] \phi(f)\phi(g)
\end{align}（終わり）

長さ $n$ の区間$[s,t]$ に対して、$Z_n(\lambda) = \zeta^\lambda(s, t)$と置くと$$\sum_{n \geq 0} Z_n(\lambda) \frac{x^n}{B(n)}= \left(\sum_{n \geq 0} \frac{x^n}{B(n)}\right)^{\lambda}$$です。
$Z_n(\lambda)$は$s,t$を端点とする長さ$\lambda$の鎖の個数に等しい。$\lambda=2$とすると長さ $n$ の区間の要素数になります。

$\sum_{n \geq 0} 2^n \frac{x^n}{n!} = \exp(x)^2$
$\sum_{n \geq 0} (n+1) x^n = \left(1 + x + x^2 + \cdots\right)^2$

$\lambda = -1$とすると
$\sum_{n \geq 0} \mu(n) \frac{x^n}{B(n)} = \left(\sum_{n \geq 0} \frac{x^n}{B(n)}\right)^{-1}$となります。

q二項定理より$$\sum_{n \geq 0} \frac{(-1)^nq^{n \choose 2}x^n}{\boldsymbol{(n)!}}= \left(\sum_{n \geq 0} \frac{x^n}{\boldsymbol{(n)!}}\right)^{-1}$$となり、$\mu_{B_n(q)}=(-1)^n q^{n \choose 2}$。

$P = \mathbb{N}$ のとき、多重鎖 $a_0 \leq a_1 \leq \cdots \leq a_k = n$ と $n$ を $k$ 個の非負整数の足し算 $n = \sum_{i=1}^k b_i$ で表す方法が $b_i = a_{i}-a_{i-1}$ によって一対一対応します。$P=\mathbb{B}$ のとき、多重鎖 $\emptyset = S_0 \subseteq S_1 \subseteq \cdots \subseteq S_{k} = [n]$ と $[n]$ の順序付き $k$ 分割 $(V_1, V_2, \ldots, V_k)$ が $V_i = S_i \setminus S_{i-1}$ によって一対一対応します。ですが、$\mathbb{B}(q)$ の多重鎖に関しては、そのような分割との対応はないことに注意してください。

ABC278Ex

$g(t) = \sum_{s \leq t} f(s)$ となる $f, g$ に対して
$F = \sum_{i} \sum_{\rho(t)=i} B(i)B(n-i)f(i)\frac{x^{i}}{B(i)}$ 、$G = \sum_{i} \sum_{\rho(t)=i} B(i)B(n-i)g(i)\frac{x^{i}}{B(i)}$ とすると、$F(x) = \phi(\zeta)^{-1}G(x)$ となります。

ディリクレ級数

二項半順序集合 $P_1, P_2, \ldots, $ の直積（ただし、 $\hat 0$ でない要素は有限個の半順序集合からしか選べない）は多変数の簡約隣接代数になります。例えば、$P_i = \mathbb{N}$ とするとディリクレ級数になります（maspyさん）。

超平面配置の交差

$K$ 係数 $n$ 次元ベクトル空間 $V$ を取ります。$V$ のアフィン超平面とは、ある $V$ の非零ベクトル $\alpha, \beta$ を用いて $\{v : \alpha \cdot v = \beta\}$ と表せる $n-1$ 次元アフィン部分空間のことです。アフィン超平面の集合を超平面配置と呼びます。超平面配置 $A$ に対して、$L(A)$ を、$A$ の超平面の非空な交差全体を包含関係で順序付けた（$V$ の部分空間として $s \subseteq t$ ならば $L(A)$ で $s \geq t$）半順序集合とします。$V$ は $0$ 個の超平面の交差とみなすので、$L(A)$ に属します。

超平面配置 $A$ の特性多項式を $\chi_A(x) = \sum_{t \in L(A)} \mu(t, \hat 1)x^{\dim(t)}$ として定義します。このとき、以下のことが包除原理により示せます。

$K = \mathbb{R}$ のとき $(-1)^n\chi(-1)$ は $\mathbb{R}^n \setminus \bigcup_{t \in A} t$ の領域数と等しい
$K = \mathbb{R}$ のとき $(-1)^{\mathrm{rank(A)}}\chi(1)$ は $\mathbb{R}^n \setminus \bigcup_{H \in A} H$ の有界な領域数と等しい（$\mathrm{rank}(A)$ とは、$A$ の超平面の垂直ベクトルが張るベクトル空間の次元数）
$K = \mathbb{F}_q$ のとき、$\chi(q)$ は $\#\left(\mathbb{F}_q^n \setminus \bigcup_{H \in A}H\right)$ と等しい

一つ目の $\chi(-1)$ は $\mathbb{R}^n \setminus \bigcup_{H \in A} H$ のオイラー標数を包除原理で求めています。2つ目も似たようなものを求めています。3つ目は $H \in A$ 上に点が $q^{\dim(H)}$ 個あることを用いた包除です。

彩色多項式

頂点集合 $[n]$ 上の無向グラフ $G$ を一つ取ります。超平面配置 $A_G = \{x_i = x_j : \{i, j\} \in E(G)\}$ を考えます。$L(A)$ の各元は、$V$ の（順序なし）分割 $V = V_1 \amalg V_2 \amalg \cdots \amalg V_k$ であって、各誘導部分グラフ $G[V_i]$ が連結なものと一対一対応しています。各分割に対して色を割り当てると、包除原理により、$\chi_{A_G}$ は彩色多項式になることが分かります。$K=\mathbb{F}_q$ における $\chi_{A_G}(q)$ の解釈とも整合的です。非巡回的向き付けの個数が $\chi(-1)(-1)^n$ であることは、相反定理から得られましたが、$K = \mathbb{R}$ において、領域数と等しかったことからも分かります。各領域の点の座標同士の大小関係に従って向き付けする（$x_i < x_j$ ならば $x_i$ から $x_j$ に向きづける）と、非巡回的向き付けが得られます。 $h = \sum_S x^S$ と置きます。ただし、$S$ は $G$ の独立集合全体（空集合を含む）を渡るとし、$x^S:= \sum_{i \in S}x_i$ とします。$f = \sum \mu_{G[U]}(\hat 0, \hat 1) x^{U}$ と置きます。ただし、$U$ は誘導部分グラフ $G[U]$ が連結グラフとなる頂点集合全体を渡るとします。点素な二つの頂点集合 $U, W$ について、$\mu_{A_{G[U] + G[W]}}(\hat 0, \hat 1) = \mu_{A_{G[U]}}(\hat 0, \hat 1) \mu_{A_{G[W]}}(\hat 0, \hat 1)$ から、
$\exp(f) = h\pmod {(x_1^2, \ldots, x_n^2)}$ が成り立ちます。従って、$f = \log(h)$ です。$t$ 個の独立集合への分割と、$t$ 彩色を一対一対応させることで $\exp(tf) = f^t $ の $x^U$ の係数が $G[U]$ の彩色多項式になることが分かります（ABC294H）。$\log(h)$ や $[x^{[n]}] f^t$ は $O(n^2 2^n)$ で計算できます（Elegiaさん、maspyさん）。

高速に計算できる形

$S = \{x_1, x_2, \ldots, x_k\} \subseteq [n-1]$ (昇順) に対して、ある関数 $h$ を用いて $g_n$ が$$g_n(S) = \prod_{i = 1}^{k+1} h(x_{i}-x_{i-1})$$と書けるとします。ただし、$x_0=0,x_{k+1}=n$とします。
$H(x) = \sum_{i \geq 1} h(i)x^i$ と置くと、このような関数は$$\sum_{n = 1}^\infty x^{n}\sum_{S \subseteq [n-1]} g_n(S) = \frac{H}{1-H}$$が成り立ちます。もう一度、この式を用いることで、$\sum_{n = 1}^\infty x^{n}\sum_T (\sum_{T \subseteq S \subseteq [n-1]} g_n(S))^k$ のような式も有理式で表せます。

長さ $2n$ の順列 $A$ であって、$A_1 > A_2 < A_3 >
A_4 < \cdots > A_{2n}$ が成り立つものの個数が $\left[\frac{x^n}{n!}\right] \frac{1}{\cos(x)}$ であることを示せ（オイラー数）
長さ $n$ の順列 $A$ であって、$A_i > A_{i + 1}$ となる $i \in [n-1]$ が $m$ 個あるものの個数が $\left[\frac{x^n}{n!}t^{m+1}\right]\frac{1}{1-t(\exp(x(1-t))-1)/(1-t)}$ であることを示せ（オイラー多項式の指数型母関数）
オイラー多項式の指数型母関数の $\frac{x^n}{n!}t^{m+1}$ の係数を $O(n \log n)$ で求めよ（JOI2018春合宿D）
AGC60D
各 $i$ について、文字 $x_i$ が $e_i$ 個使われる文字列であって、同じ文字が連続しないものの個数が $\left[\prod x_i^{e_i}\right]\left(1-\sum\frac{x_i}{1+x_i}\right)^{-1}$ と表されることを示せ（かならいさん）。
$f = \sum_{n=k}^{\infty}\mu_{B_{n,k}}(\hat 0, \hat 1) x^n$ と置くと $\left(1-x-\frac{f}{1+f}\right)^{-1} = \sum_{i=0}^{k-1}x$ であることを示せ。

指数型母関数の合成と分割束

$E_f=\sum f(n)x^n/n!$と置く。$[\sigma, \pi] \cong \Pi_1^{a_1} \times \Pi_2^{a_2} \times \cdots \times \Pi_n^{a_n}$に対して、$f(\sigma, \pi) = f(1)^{a_1}f(2)^{a_2}\cdots f(n)^{a_n}$と書けるならば$f$を乗法的であるといいます。$f,g$が乗法的ならば$\Pi_n$において、
\begin{align}
fg(\hat 0, \hat 1)=&\sum_{\hat 0 \leq \pi \leq \hat 1} f(\hat 0, \pi) g(\pi, \hat 1)\\
=& \sum_{\{B_1,\ldots,B_k\}=\pi \leq \Pi_n} g(k)\prod_i f(\#B_i)\\
=& \left[\frac{x^n}{n!}\right]E_g\left(E_f(x)\right)
\end{align}
$E_\zeta=\exp(x)-1$, $E_{\zeta^{-1}}=\log(1+x)$となります。$\pi = \{B_1, \ldots, B_k\}$に対して、$f(\pi, \hat 1) = f(B_1)f(B_2)\cdots f(B_k)$ならば$f\zeta$は集合べき級数の exp で書けます。指数型母関数の合成を、$B_n(q)$ などに一般化したものも知られています。集合の分割ではなく、線形空間の直和を渡ります（Stanley）。