パーマネント (数学)
(相異なるとは限らない)S1, S2, ..., Sm は n元-集合の部分集合で、m ≤ n とする。この部分集合族の接続行列 A は m × n の (0, 1)-行列である。この族の完全代表系(英語版)(systems of distinct representatives; 相異なる代表系、個別代表系; SDR)総数は perm(A) である。
↑ Egoryčev, G. P. (1980) (Russian), Reshenie problemy van-der-Vardena dlya permanentov, Krasnoyarsk: Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., p. 12, MR602332 . Egorychev, G. P. (1981), “Proof of the van der Waerden conjecture for permanents” (Russian), Akademiya Nauk SSSR 22 (6): 65–71, 225, MR638007
↑ Egorychev, G. P. (1981), “The solution of van der Waerden's problem for permanents”, Advances in Mathematics 42 (3): 299-305, doi:10.1016/0001-8708(81)90044-X, MR642395 .
↑ Falikman, D. I. (1981), “Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix” (Russian), Akademiya Nauk Soyuza SSR 29 (6): 931-938, 957, MR625097 .
任意の正方行列 A ≔ (aij) は適当な重み付き有向グラフの隣接行列と見なすことができて、各 aij は頂点 i から j へ結ぶ弧の重み付けを表す。 重み付き有向グラフの閉路被覆(英語版)とは、その有向グラフの点素 (vertex-disjoint) な有向閉路の集まりで、グラフの全ての頂点を被覆するものをいう。このとき、有向グラフの各頂点 i は、その閉路被覆において一意的な「後続点」σ(i) を持ち、σ は {1, 2, ..., n}(n はグラフの頂点数)の置換となる。逆に、{1, 2, ..., n} 上の任意の置換 σ は、各 i に対して頂点 i から σ(i) へ結ぶ弧がある閉路被覆に対応する。
「閉路被覆の重み」を各閉路における重みの総乗と定めるならば、
A がクラス Ω(n,k) に属する巡回行列ならば、k > 3 のとき、perm(A) > |det (A)| であり、k = 3 のとき perm(A) = |det(A)| が成り立つ。さらには、k = 3 のとき、行および列を入れ替えて、A を行列 Z の e個のコピーの直和の形にすることができて、したがって n = 7e および perm(A) = 24 となる。
位置の制限(禁止)を含む置換の総数の計算にもパーマネント は利用できる。標準 n元-集合 {1, 2, ..., n} に対して、A = (aij) を、各 aij は素の置換で i → j と写せるならば 1, さもなくば 0 と定めて得られる (0, 1)-行列とするとき、perm(A) は標準 n-元集合上でこれらの制限を全て満たす置換の総数に等しい。このような例としてよく知られた特別の場合が、完全順列問題(不動点を全く持たない場合)とメナージュの問題(英語版)(problème des ménages: 複数の男女カップルがどの組もパートナー同士が隣り合うことなく円卓に着席する場合の数を求める)である。