概要

全体から, 重複している集合を取り除く原理。最も基本的な包除原理の形への変換として次式を与える。

$\displaystyle |\bigcap_{i=1}^{n} A_i| = |\overline{\bigcup_{i=1}^{n} \overline{A_i}}|$

$A_i$ が何らかの条件を表している。 つまり全ての条件 $A_i$ を満たす集合を数え上げたい時に, $\overline{A_i}$ の和集合を数え上げる形に変形することにより包除原理を使える形に落とせることを示している。条件 $A_i$ の部分集合を指定したときに条件を全て違反するようなものの個数(指定した条件以外の条件については満たしていても満たしていなくてもよい) を求めてそれらを部分集合の条件の個数の偶奇に応じて足し引きすればよい。条件は DP などによって個数によってまとめられることがあり, その場合は計算量を落とすことが可能で有用である。

完全順列

長さ $N$ の順列 $\{a_i\}$ で, すべての $i$ について $a_i \ne i$ を満たすものの個数

  • もとの条件: $a_1 \ne 1$ and $a_2 \ne 2$ and … $a_N \ne N$
  • 条件の否定: $a_1 = 1$ or $a_2 = 2$ or … $a_N = N$

愚直な解法: 条件の部分集合 $B$ をとってきたとき, それらを満たす順列の個数は $(N-|B|)!$ である。$B$ で選ばれた要素以外は自由に決めて良いので, 残りの要素数の階乗通りある。

効率的解法: $(N-|B|)!$ は条件の個数のみに依存している。条件が $k$ 個の部分集合の個数は $C(N, K)$ である。よって条件を否定する順列の個数は $\displaystyle \sum_{k=1}^{N} (-1)^{k+1} (N-k)! C(N, k)$ であり, これを全体の $N!$ から引いたものが答えである。$O(N)$。

$|a_i - i| \ne K$ の順列(AGC005 D ~K Perm Counting)

長さ $N$ の順列 $\{a_i\}$ で, すべての $i$ について $|a_i - i| \ne K$ を満たすものの個数

  • もとの条件: $a_1 - 1 \ne K$ and $a_2 - 2 \ne K$ and … $a_N - N \ne K$ and $a_1 + 1 \ne K$ and $a_2 + 2 \ne K$ and … $a_N + N \ne K$
  • 条件の否定: $a_1 - 1 = K$ or $a_2 - 2 = K$ or … $a_N - N = K$ or $a_1 + 1 = K$ or $a_2 + 2 = K$ or … $a_N + N = K$

愚直な解法: 条件の部分集合 $B$ をとってきたとき, それらを満たす順列の個数は $0$ または $(N-|B|)!$ である。$B$ のそれぞれの要素から, 実際に割り当てる値 $a_i = K + i$ または $a_i = K - i$ に辺をはる。ここで次数が $2$ 以上の頂点が生まれたら, そのような割り当て方は存在しないので $0$ である。それ以外は指定した要素以外を自由に決められるため $(N-|B|)!$ である。

効率的解法: 次数が $1$ 以下というのは, つまり二部グラフのマッチングの一例である。$a_i = K + i$ または $a_i = K - i$ に辺をはったグラフを考えると, これは $\bmod K$ で $K$ 個の直線グラフに分けられる。長さ $M$ の直線グラフについて $K$ 個マッチさせる個数は $C(M-k, k)$ らしいので, これを $K$ 個の直線の各個数について求めて DP で数え上げる。DPテーブルは dp[$k$] := $K$ 個の直線グラフから $k$ 個マッチングさせる組み合わせとすればよい。

自分以外の連結成分に移動する順列 (ARC087 F - Squirrel Migration)

長さ $N$ の順列 $\{a_i\}$ で, それぞれの要素には色 $c_i$ が塗られている。すべての $i$ について $c_i \ne c_{a_i}$ を満たすものの個数

  • もとの条件: $c_1 \ne c_{a_1}$ and $c_2 \ne c_{a_2}$ and … $c_N \ne c_{a_N}$
  • 条件の否定: $c_1 = c_{a_1}$ or $c_2 = c_{a_2}$ or … $c_N = c_{a_N}$

愚直な解法: 条件の部分集合 $B$ をとってきたとき, それらを満たす順列の個数を考える。まず $B$ で指定された以外の要素は自由に決めて良いため $(N-|B|)!$ が全体に掛かる。 $B$ で指定された要素のみを考える。$T_k$ を色 $k$ の個数, $S_k$ を $B$ 内での色 $k$ の要素の個数と定義する。それぞれの色について, 自分の色に移動するような順列の個数は $P(T_k, S_k)$ である。よって $\displaystyle (N-|B|)! \prod_{k} P(T_k, S_k)$ となる。

効率的解法: 色を順番に追加していく DP を考える。DP テーブルを dp[$k$] := ($k$ 個の要素を部分集合 $B$ に含めたときの順列の個数) $÷ (N-|B|)!$ とする。 $x$ 個の同じ色を追加するときその選び方は $C(T_k, x)$ である。これに $P(T_k, x)$ を掛けたものが組み合わせの数である。あとは普通に遷移させればよくて $O(N^2)$。