月刊組合せ論 Natori は面白そうな組合せ論のトピックを紹介していく企画です。今回はパフィアンを用いた数え上げを解説します。
2026 年、ようやく初 Natori です。今月号から毎月の連載を再開していこうと思います。
パフィアン
#
まずはパフィアンを紹介します。行列式と似たようなものです。
行列式は次のように定義されるものでした。
det ( A ) = ∑ σ ∈ S n sgn ( σ ) ∏ i = 1 n a i σ i
\det(A)=\sum_{\sigma\in S_n}\operatorname{sgn}(\sigma)\prod_{i=1}^n a_{i\sigma_i}
det ( A ) = σ ∈ S n ∑ sgn ( σ ) i = 1 ∏ n a i σ i 行列式は任意の正方行列 A A A A A A
偶数次の正方行列
歪対称行列（すなわち、a i j = − a j i a_{ij}=-a_{ji} a ij = − a ji
歪対称行列であることから特に対角成分は 0 です。
A A A 2 n 2n 2 n F n F_n F n 1 , 2 , … , 2 n 1,2,\ldots,2n 1 , 2 , … , 2 n σ \sigma σ
σ ( 1 ) < σ ( 3 ) < ⋯ < σ ( 2 n − 1 ) \sigma(1)<\sigma(3)<\cdots<\sigma(2n-1) σ ( 1 ) < σ ( 3 ) < ⋯ < σ ( 2 n − 1 ) σ ( 2 i − 1 ) < σ ( 2 i ) ( i = 1 , 2 , … , n ) \sigma(2i-1)<\sigma(2i) \ (i=1,2,\ldots,n) σ ( 2 i − 1 ) < σ ( 2 i ) ( i = 1 , 2 , … , n )
をみたすもの全体からなる集合とします。このとき A A A
pf ( A ) = ∑ σ ∈ F n sgn ( σ ) ∏ i = 1 n a σ ( 2 i − 1 ) σ ( 2 i )
\operatorname{pf}(A)=\sum_{\sigma\in F_n}\operatorname{sgn}(\sigma)\prod_{i=1}^n a_{\sigma(2i-1)\sigma(2i)}
pf ( A ) = σ ∈ F n ∑ sgn ( σ ) i = 1 ∏ n a σ ( 2 i − 1 ) σ ( 2 i ) により定義します。
例えば A A A
A = ( 0 a − a 0 )
A=\begin{pmatrix} 0 & a \\ -a & 0 \end{pmatrix}
A = ( 0 − a a 0 ) のとき、パフィアンは a a a A A A
A = ( 0 a b c − a 0 d e − b − d 0 f − c − e − f 0 )
A=\begin{pmatrix} 0 & a & b & c \\ -a & 0 & d & e \\ -b & -d & 0 & f \\ -c & -e & -f & 0 \end{pmatrix}
A = 0 − a − b − c a 0 − d − e b d 0 − f c e f 0 のとき、σ \sigma σ 1234 , 1324 , 1423 1234, 1324, 1423 1234 , 1324 , 1423 a f − b e + c d af-be+cd a f − b e + c d
パフィアンのもつ重要な性質として
det ( A ) = ( p f ( A ) ) 2
\det(A)=(\mathrm{pf}(A))^2
det ( A ) = ( pf ( A ) ) 2 があります。
パフィアンは行列式と同様、時間計算量 O ( n 3 ) O(n^3) O ( n 3 )
このパフィアンを数え上げに応用していきます。
完全マッチング
#
マッチングとは
#
パフィアンの定義で用いた F n F_n F n
グラフのマッチング とは、頂点がダブらないように辺をいくつか選ぶことです。すべての頂点が選んだある辺の端点であるとき、完全マッチング といいます。
2 n 2n 2 n ( 1 , 3 ) , ( 2 , 5 ) , ( 4 , 6 ) (1,3),(2,5),(4,6) ( 1 , 3 ) , ( 2 , 5 ) , ( 4 , 6 ) 132546 132546 132546 F 3 F_3 F 3
辺の並べ方をうまく決めることで、一意的な表記としたいです。そのための条件が、定義で登場した
σ ( 1 ) < σ ( 3 ) < ⋯ < σ ( 2 n − 1 ) \sigma(1)<\sigma(3)<\cdots<\sigma(2n-1) σ ( 1 ) < σ ( 3 ) < ⋯ < σ ( 2 n − 1 ) σ ( 2 i − 1 ) < σ ( 2 i ) ( i = 1 , 2 , … , n ) \sigma(2i-1)<\sigma(2i) \ (i=1,2,\ldots,n) σ ( 2 i − 1 ) < σ ( 2 i ) ( i = 1 , 2 , … , n )
ということです。つまり、F n F_n F n
なお、行列式では通常の置換 σ ∈ S n \sigma \in S_n σ ∈ S n K n , n K_{n,n} K n , n
完全マッチングの数え上げ
#
完全マッチングとパフィアンはさらに関係があります。
頂点が 2 n 2n 2 n K = ( K i j ) K=(K_{ij}) K = ( K ij )
K i j = { + 1 ( v i , v j ) ∈ E − 1 ( v j , v i ) ∈ E 0 o t h e r w i s e
K_{ij}=\begin{cases}
+1 & (v_i,v_j) \in E \\
-1 & (v_j,v_i) \in E \\
0 & \mathrm{otherwise}
\end{cases}
K ij = ⎩ ⎨ ⎧ + 1 − 1 0 ( v i , v j ) ∈ E ( v j , v i ) ∈ E otherwise この行列のパフィアンは
pf ( K ) = ∑ σ ∈ F n sgn ( σ ) ∏ i = 1 n K σ ( 2 i − 1 ) σ ( 2 i )
\operatorname{pf}(K)=\sum_{\sigma\in F_n}\operatorname{sgn}(\sigma)\prod_{i=1}^n K_{\sigma(2i-1)\sigma(2i)}
pf ( K ) = σ ∈ F n ∑ sgn ( σ ) i = 1 ∏ n K σ ( 2 i − 1 ) σ ( 2 i ) ですが、辺がないと 0 になって無視できるので、和の範囲はグラフの完全マッチング全体を動くことになります。
pf ( K ) = ∑ M : m a t c h i n g sgn ( σ M ) ε ( M )
\operatorname{pf}(K)=\sum_{M:\mathrm{matching}}\operatorname{sgn}(\sigma_M)\varepsilon(M)
pf ( K ) = M : matching ∑ sgn ( σ M ) ε ( M ) ここで σ M \sigma_M σ M M M M ε ( M ) \varepsilon(M) ε ( M ) M M M ( v i , v j ) (v_i,v_j) ( v i , v j ) K i j K_{ij} K ij
いま、sgn ( σ M ) ε ( M ) \operatorname{sgn}(\sigma_M)\varepsilon(M) sgn ( σ M ) ε ( M ) M M M + 1 +1 + 1 − 1 -1 − 1 pf ( K ) \operatorname{pf}(K) pf ( K )
問題となるのは上記の仮定をみたすように辺に向きをつけられるかということです。残念ながらすべてのグラフではできません。一方で、平面グラフでは可能であることが知られています。
パフィアンの絶対値が完全マッチングの個数と等しくなるような向き付けを Pfaffian orientation といいます。
平面グラフでこのような向き付けを求めるアルゴリズムとして、Fisher–Kasteleyn–Temperley algorithm が知られています。
非交差経路
#
行列式
#
行列式を用いた数え上げといえば LGV 公式と行列木定理ですね。ここでは LGV 公式を扱います。
Γ = ( V , E ) \Gamma=(V,E) Γ = ( V , E ) e ∈ E e\in E e ∈ E w ( e ) ∈ Z w(e)\in \mathbb{Z} w ( e ) ∈ Z P = ( v 1 , … , v n ) P=(v_1,\ldots,v_n) P = ( v 1 , … , v n ) w ( P ) = w ( v 1 , v 2 ) w ( v 2 , v 3 ) ⋯ w ( v n − 1 , v n ) w(P)=w(v_1,v_2)w(v_2,v_3)\cdots w(v_{n-1},v_n) w ( P ) = w ( v 1 , v 2 ) w ( v 2 , v 3 ) ⋯ w ( v n − 1 , v n ) a 1 , … , a n , b 1 , … , b n ∈ V a_1,\ldots,a_n,b_1,\ldots,b_n\in V a 1 , … , a n , b 1 , … , b n ∈ V n × n n\times n n × n
M ( a , b ) = ( ∑ P : a i → b j w ( P ) ) 1 ≤ i , j ≤ n
M(a,b)=\left(\sum_{P\colon a_i\to b_j}w(P)\right)_{1\le i,j\le n}
M ( a , b ) = P : a i → b j ∑ w ( P ) 1 ≤ i , j ≤ n を定めます。ただし和において P P P a i a_i a i b j b_j b j
定理 (LGV)
条件「i 1 < i 2 , j 1 > j 2 i_1<i_2, j_1>j_2 i 1 < i 2 , j 1 > j 2 a i 1 a_{i_1} a i 1 b j 1 b_{j_1} b j 1 a i 2 a_{i_2} a i 2 b j 2 b_{j_2} b j 2
det M ( a , b ) = ∑ ( P 1 , … , P n ) w ( P 1 ) ⋯ w ( P n )
\det M(a,b)=\sum_{(P_1,\ldots,P_n)}w(P_1)\cdots w(P_n)
det M ( a , b ) = ( P 1 , … , P n ) ∑ w ( P 1 ) ⋯ w ( P n ) が成り立つ。ここで和は P i P_i P i a i a_i a i b i b_i b i
パフィアン
#
LGV 公式は始点と終点が決まっている場合しか扱えません。始点のみ決まっていて、終点が決まっていない場合を考えます。
n n n i i i a i a_i a i b j ( j ∈ Z ) b_j \ (j \in \mathbb{Z}) b j ( j ∈ Z )
定理 (岡田, Stembridge)
条件「i 1 < i 2 , j 1 > j 2 i_1<i_2, j_1>j_2 i 1 < i 2 , j 1 > j 2 a i 1 a_{i_1} a i 1 b j 1 b_{j_1} b j 1 a i 2 a_{i_2} a i 2 b j 2 b_{j_2} b j 2 1 ≤ i < j ≤ n 1\le i<j\le n 1 ≤ i < j ≤ n M M M ( i , j ) (i,j) ( i , j )
∑ ( P 1 , P 2 ) w ( P 1 ) w ( P 2 )
\sum_{(P_1,P_2)}w(P_1)w(P_2)
( P 1 , P 2 ) ∑ w ( P 1 ) w ( P 2 ) とおく。ここで P 1 P_1 P 1 a i a_i a i b i ′ b_{i'} b i ′ P 2 P_2 P 2 a j a_j a j b j ′ b_{j'} b j ′
p f ( M ) = ∑ ( P 1 , … , P n ) w ( P 1 ) ⋯ w ( P n )
\mathrm{pf}(M)=\sum_{(P_1,\ldots,P_n)}w(P_1)\cdots w(P_n)
pf ( M ) = ( P 1 , … , P n ) ∑ w ( P 1 ) ⋯ w ( P n ) が成り立つ。ここで和は P i P_i P i a i a_i a i b i ′ b_{i'} b i ′
n n n
パフィアンは偶数次の行列に対して定義されるので、n n n
使用例
#
AtCoder Beginner Contest 216 H - Random Robots をパフィアンを用いて解くことができます。
公式解説にあるように、終点が固定されていない非交差経路の数え上げに帰着されます。パフィアンを用いることで、想定解よりもよい計算量で解くことができます。
関連する話題
#
行列式を用いた数え上げは、LGV 公式の他に行列木定理もあります。
パフィアン版の行列木定理もあるようです。いつか解説記事を書くかもしれません。
おわりに
#
行列式を使った数え上げはそれなりに知名度がありますが、パフィアンはまだまだだと思うので、布教していきたいです。
今後も月刊組合せ論 Natori では組合せ論の面白いトピックを紹介していきたいので、応援のほどよろしくお願いします。
参考文献
#
Shane Chern; Theresia Eisenkölbl; Ilse Fischer; Moritz Gangl; Mona Gatzweiler; Álvaro Gutiérrez; Christian Krattenthaler; Nishu Kumari; Markus Reibnegger; Marcus Schönfelder; Atsuro Yoshida. More minor summation formulae. arXiv:2603.21021, https://arxiv.org/abs/2603.21021
Okada, Soichi. On the generating functions for certain classes of plane partitions. J. Comb. Theory, Ser. A 51, No. 1, 1-23 (1989).
Stembridge, John R. Nonintersecting paths, pfaffians, and plane partitions. Adv. Math. 83, No. 1, 96-113 (1990).
