連載しょぼんコーダー 6 一般化された包除原理と二項変換

第6回では, 一般化された包除原理について扱います. 包除原理は「条件を $1$ 個以上満たすものの個数」を数え上げるものです. これを一般化すると, 「条件を $K$ 個以上満たす」「条件をちょうど $K$ 個満たす」や「条件を $k$ 個満たすものは $k^2$ が答えに足される」などもふつうの包除原理と同じノリで解くことができます.

この一般化は, 「二項変換」と関連があるのでそれについても述べます.

（追記 2023.08.03）練習問題を追加

↓記事が長すぎる！「もう解ける問題たち」を先に覗いた方がいいかも

普通の包除原理
- 補題
- 包除原理の証明
問題1
問題2
一般化包除原理
二項変換の表示
もう解ける問題たち
- 問題3
- 問題4
- 問題5
- 問題6
練習問題
参考文献

普通の包除原理

有限集合 $S_1, S_2, \cdots, S_N$ があるとします. $[N] = \{1, 2, \cdots, N \}$ としたとき,

$\displaystyle |\cup_{i=1}^N S_i| = \sum^{N}_{i=1} (-1)^{i-1} \sum_{J \subset [N], |J| = i} |\cap_{j \in J} S_j|$

が成り立ちます. 小さい例として, $N=2$ のときは

$\displaystyle |S_1 \cup S_2| = |S_1| + |S_2| - |S_1 \cap S_2|$

, $N=3$ のときは

$\displaystyle |S_1 \cup S_2 \cup S_3|\\ = |S_1| + |S_2| + |S_3|\\ - |S_1 \cap S_2| - |S_2 \cap S_3| - |S_3 \cap S_1| + |S_1 \cap S_2 \cap S_3|$

となります.

補題

すべての正整数 $n$ に対して

$\displaystyle \sum^{n}_{i=1} \binom{n}{i} (-1)^{i-1} = 1$

が成り立ちます.（ $n=0$ の場合は $0$ ）

この補題がいつもの包除原理を支えています. この記事での包除原理の一般化は、ここの「補題」の式を変更するというイメージです.

証明目的の式の左辺を $A$ とします. 二項定理より

$\displaystyle -A+1 = \sum^{N}_{i=0} \binom{N}{i} (-1)^{i} = (1-1)^N = 0$

となるので, $A=1$ が従います.

包除原理の証明

$\cup_{i=1}^N S_i$ の要素 $x$ を任意にとります. $x$ に属する $S_i$ $(i=1,2,\cdots, N)$ の個数がちょうど $k$ 個 $(k \ge 1)$ とします. このとき, $i$ 個の共通部分のうち, $x$ が属するものの個数は $\binom{k}{i}$ 個である. よって,「 $i$ 個違反には $(-1)^i$ がかけられる」ことを考えて, $x$ の包除原理の式に対する寄与は

$\displaystyle \sum^{k}_{i=1} \binom{k}{i} (-1)^{i-1}$

となりますが, これは補題より $1$ に一致します. よって結局

$\displaystyle |\cup_{i=1}^N S_i| = \sum^{N}_{i=1} (-1)^{i-1} \sum_{J \subset [N], |J| = i} |\cap_{j \in J} S_j|$

の右辺は, $\cup_{i=1}^N S_i$ の要素の個数を数えるものになっています.

問題1

いつもの包除原理の例を見ます.

$M$ 以下の正整数 $i$ であって, $i$ が $2, 3, 5$ のいずれかの倍数であるようなものは何個ありますか？
$1 \le M \le 10^{18}$

集合 $S_1$ を, $M$ 以下の正整数で $2$ の倍数全体, $S_2$ , $S_3$ も $M$ 以下の正整数でそれぞれ $3, 5$ の倍数であるもの全体とします. すると, 求めたいものは $|S_1 \cup S_2 \cup S_3|$ です.

包除原理によって,

$\displaystyle |S_1 \cup S_2 \cup S_3|\\ = |S_1| + |S_2| + |S_3|\\ - |S_1 \cap S_2| - |S_2 \cap S_3| - |S_3 \cap S_1| + |S_1 \cap S_2 \cap S_3|$

ですが, $\mathrm{lcm}$ を最小公倍数を表すことにすると, それぞれについて

$\displaystyle |S_1| = \lfloor M/2 \rfloor\\ |S_2| = \lfloor M/3 \rfloor\\ |S_3| = \lfloor M/5 \rfloor\\ |S_1 \cap S_2| = \lfloor M/\textrm{lcm}(2, 3) \rfloor = \lfloor M/6 \rfloor\\ |S_2 \cap S_3| = \lfloor M/\textrm{lcm}(3, 5) \rfloor = \lfloor M/15 \rfloor\\ |S_3 \cap S_1| = \lfloor M/\textrm{lcm}(5, 2) \rfloor = \lfloor M/10 \rfloor\\ |S_1 \cap S_2 \cap S_3| = \lfloor M/\textrm{lcm}(2, 3, 5) \rfloor = \lfloor M/30 \rfloor$

なので, $|S_1 \cup S_2 \cup S_3|$ も計算できます.

問題2

$M$ 以下の正整数 $i$ であって, $i$ が $2, 3, 5$ のうち $2$ つ以上の倍数であるようなものは何個ありますか？
$1 \le M \le 10^{18}$

言い換えると, さきほどの $S_1, S_2, S_3$ において, $M$ 以下の正整数 $i$ であって, $i$ が $S_1, S_2, S_3$ の $2$ つ以上の要素であるようなものを求めればよいです. どうやって求めればよいでしょう？

いつもの包除原理のように,

$\displaystyle |S_1 \cap S_2| + |S_2 \cap S_3| + |S_3 \cap S_1| - |S_1 \cap S_2 \cap S_3|$

を答えにしたくなりますが, これは誤りです. 実際は, $|S_1 \cap S_2 \cap S_3|$ は $1$ 回ではなく $2$ 回超過カウントされるので,

$\displaystyle |S_1 \cap S_2| + |S_2 \cap S_3| + |S_3 \cap S_1| - 2 |S_1 \cap S_2 \cap S_3|$

が求める答えです. このように, $K$ 個以上の集合に属する要素の個数を求めたい, というふうな場合は, ふつうの包除原理は使えないということがあります. そこで包除原理を一般化して同じように解くことができないかを考えました.

一般化包除原理

$b_0 = 0$ を満たす数列 $b=(b_0, b_1, b_2, \cdots)$ があるとします. （ $b_0 \ne 0$ でも全体集合を定めれば OK です）このとき, $a_0 = 0$ を満たす数列 $a = (a_0, a_1, a_2, \cdots)$ であって, 次の条件を満たすようにしたいです.

正整数 $N$ と有限集合 $S_1, \cdots, S_N$ を任意にとる. $\cup_{i=1}^N S_i$ の要素 $x$ であって, $x$ に属する $S_i$ $(i=1,2,\cdots, N)$ の個数がちょうど $k$ 個であるようなものの個数を $C_k$ と書くと,

$\displaystyle \sum_{k=1}^{N} C_kb_k = \sum_{r=1}^N a_r \sum_{J \subset [N], |J|=r} \left|\cap_{j \in J} S_j\right|$

となる.

たとえば, ふつうの包除原理では $b = (0, 1, 1, 1, 1, 1, \cdots)$ , $a = (0, 1, -1, 1, -1, 1, \cdots)$ となります.

$a$ は $N$ によらない数列であることに注意します. そもそもこんなのは存在するのでしょうか？実は数列 $b$ に対して, それに対応する唯一の数列 $a$ が存在します.

存在性と唯一性

$\displaystyle \sum_{k=1}^{N} C_kb_k = \sum_{r=1}^N a_r \sum_{J \subset [N], |J|=r} \left|\cap_{j \in J} S_j\right|$

包除原理の証明を参考にすると, $\cup_{i=1}^N S_i$ の要素 $x$ を任意にとって, $x$ が属する $S_i$ $(i=1,2,\cdots, N)$ の個数をちょうど $k$ 個 $(k \ge 1)$ としたとき, 要素 $x$ は条件の右辺に対して

$\displaystyle \sum^{k}_{i=1} \binom{k}{i} a_i$

だけ寄与します. 条件の式の左辺 $\sum_{k=1}^{N} C_kb_k$ に注目すると, この式は $b_k$ になるべきです. よって

$\displaystyle \sum^{k}_{i=1} \binom{k}{i} a_i = b_k$

となります. これがすべての正整数 $k$ について成り立ってほしいのです. ここで $k=1, 2, \cdots$ と見ていくと,

$b_1 = a_1$
$b_2 = \binom{2}{1} a_1 + a_2$
$b_3 = \binom{3}{1} a_1 + \binom{3}{2} a_2 + a_3$
$b_4 = \binom{4}{1} a_1 + \binom{4}{2} a_2 + \binom{4}{3} a_3 + a_4$

となり, $b_k$ は $a_1, a_2, \cdots, a_k$ の式で書けます. よって $a_1, a_2, a_3, \cdots$ の順に $a$ の値を一意に決定することができます. この操作により $b_n$ まで見ると $a_n$ までが確定するので, $a$ は存在し, かつ一意です.

二項変換と逆変換

実は $a, b$ の関係式は二項変換と呼ばれます.（ $a_0 = 0, b_0 = 0$ を仮定しません）

en.wikipedia.org

science-log.com

二項変換は 2 種類の定義がありますが, 「交代二項変換」ではない方（「単純二項変換」）で,

$\displaystyle \sum^{k}_{i=0} \binom{k}{i} a_i = b_k$

逆変換は,

$\displaystyle \sum^{k}_{i=0} (-1)^{k-i} \binom{k}{i} b_i = a_k$

となります. ただし,「単純二項変換」は『理系のための備忘録』で使用されているだけで, 一般的な単語ではないことに注意してください.

例 : b = (0,0,1,1,1,1,…)

$b=(0,0,1,1,1,1,\cdots)$ として $a$ を求めてみます. この $a$ が求められれば, 問題 2 が一般に解けます.

$a$ の通常型母関数を $f(x) = \sum_{i \ge 0} a_i x^i$ , $b$ の通常型母関数を $g(x) = \sum_{i \ge 0} b_i x^i$ とします.

$g(x) = \frac{x^2}{1-x}$ です. 目標は $f(x)$ を求めることです.

$0 = b_1 = a_1$ より $a_1 = 0$
$1 = b_2 = 2 a_1 + a_2$ より $a_2 = 1$
$1 = b_3 = 3 a_1 + 3 a_2 + a_3$ より $a_3 = 1 - 3 \times 1 = -2$
$1 = b_4 = 4 a_1 + 6 a_2 + 4 a_3 + a_4$ より $a_4 = 1 - 4\times (-2) - 6 \times 1 = 3$
$1 = b_5 = 5 a_1 + 10 a_2 + 10 a_3 + 5 a_4 + a_5$ より $a_5 = 1 - 5\times 3 - 10 \times (-2) - 10 \times 1 = -4$

ここまで来て, $a = (0, 0, 1, -2, 3, -4, \cdots)$ となりました. ここから, $5, -6, 7, -8, 9, \cdots$ が続くと予想します.

さて, 少し脱線しますが $f, g$ の関係式を導いてみます. $a, b$ について,

$\displaystyle \sum^{k}_{i=1} \binom{k}{i} a_i = b_k$

が成り立って欲しいです. 式を変形すると, 畳み込みの式になっているので,

$\displaystyle \sum^{k}_{i=1} \binom{k}{i} a_i = \displaystyle \sum^{k}_{i=1} \binom{k}{k-i} \left([x^i] f(x)\right)\\ \displaystyle = \sum^{k}_{i=1} \left([x^{k-i}] (1+x)^k\right) \left([x^i] f(x)\right)\\ \displaystyle = [x^k] (1+x)^k f(x)$

, すなわち

$\displaystyle [x^k] (1+x)^k f(x) = [x^k] g(x)$

となります. これが $f$ と $g$ の関係を表す式となっています.

いま, $(0, 0, 1, -2, 3, -4, 5, \cdots)$ の母関数は $\frac{x^2}{(1+x)^2}$ ですが,

$k \ge 2$ について

$\displaystyle [x^k] (1+x)^k \frac{x^2}{(1+x)^2}\\ \displaystyle = [x^k] (1+x)^{k-2} x^2 = 1 = b_k$

そして $k \lt 2$ について

$\displaystyle [x^k] (1+x)^k \frac{x^2}{(1+x)^2}\\ = [x^k] \frac{x^2}{(1+x)^{2-k}} = 0 = b_k$

となるので OK です！よって $a = (0, 0, 1, -2, 3, -4, 5, -6, \cdots)$ となり, 包除原理は次の形になります：

正整数 $N$ と有限集合 $S_1, \cdots, S_N$ を任意とする. $\cup_{i=1}^N S_i$ の要素 $x$ であって, $x$ に属する $S_i$ $(i=1,2,\cdots, N)$ の個数が $2$ 個以上であるようなものの個数は,

$\displaystyle \sum_{r=2}^N (r-1)\times(-1)^{r-2} \sum_{J \subset [N], |J|=r} \left|\cap_{j \in J} S_j\right|$

となる.

つまり, ふつうの包除原理のときに「 $k$ 個 ( $k\ge 1$ ) の共通部分には $(-1)^{k-1}$ を掛ける」ところを, 「 $k$ 個 ( $k\ge 2$ ) の共通部分には $(k-1) \times (-1)^{k-1}$ を掛ける」とすればよいです. この意味で, 「ふつうの包除原理と同じノリで解くことができる」と言い表しました.

二項変換の表示

二項変換には, 母関数に関する公式があります. これが便利です.

$a$ の通常型母関数を $f(x) = \sum_{i \ge 0} a_i x^i$ , $b$ の通常型母関数を $g(x) = \sum_{i \ge 0} b_i x^i$ とする. このとき,

$\displaystyle g(x) = \frac{1}{1-x} f\left(\frac{x}{1-x}\right)\\ \displaystyle f(x) = \frac{1}{1+x} g\left(\frac{x}{1+x}\right)$

が成り立つ.

$a$ の指数型母関数を $F(x) = \sum_{i \ge 0} a_i \frac{x^i}{i!}$ , $b$ の指数型母関数を $G(x) = \sum_{i \ge 0} b_i \frac{x^i}{i!}$ とする. このとき,

$\displaystyle G(x) = e^x F(x)\\ \displaystyle F(x) = e^{-x} G(x)$

が成り立つ.

通常型母関数の証明（長い）

上の式を証明します. 上の式の右辺の $x^n$ の係数が $b_n$ の係数になることを示します.

$\displaystyle f(x) = a_0 + a_1 x + a_2 x^2 + \cdots$

に注意すると,

$\displaystyle \frac{1}{1-x} f\left(\frac{x}{1-x}\right) = a_0 \frac{1}{1-x} + a_1 \frac{x}{(1-x)^2} + a_2 \frac{x^2}{(1-x)^3} + \cdots$

です. いま, いわゆる負の二項定理よりすべての $k \ge 0$ に対して

$\displaystyle a_k \frac{x^k}{(1-x)^{k+1}} = a_k x^k + a_k \binom{k+1}{k} x^{k+1} + a_k \binom{k+2}{k} x^{k+2} + \cdots$

が成り立ちます. $n \ge 0$ を任意として, $x^n$ の係数には $a_i \binom{n}{i} x^n$ がすべて足されますから, $b_n$ の定義より

$\displaystyle [x^n] \frac{1}{1-x} f\left(\frac{x}{1-x}\right) = \sum^{n}_{i=0} a_i \binom{n}{i} = b_n$

が成り立ちます. よって

$\displaystyle g(x) = \frac{1}{1-x} f\left(\frac{x}{1-x}\right)$

が示せました. 下の式を示します. 上の式において $x \mapsto \frac{x}{1+x}$ と変換すると,

$\displaystyle g\left(\frac{x}{1+x}\right) = (1+x) f(x)$

すなわち

$\displaystyle f(x) = \frac{1}{1+x} g\left(\frac{x}{1+x}\right)$

となり, 示せました.

指数型母関数の証明（長くない）

$\displaystyle e^x = 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \cdots = \sum_{n \ge 0} \frac{x^n}{n!}$

を思い出します. $e^x F(x)$ の $x^n$ の次数に注目すると, 二項変換の定義によって

$\displaystyle [x^n] (e^x F(x))\\ \displaystyle = \sum_{k = 0}^n \frac{a_k}{k!} \frac{1}{(n-k)!}\\ \displaystyle = \frac{1}{n!} \sum_{k = 0}^n a_k \binom{n}{k}\\ \displaystyle = \frac{b_n}{n!}$

となり, これは $[x^n] G(x)$ に一致します.

a→b, b→a の N 次までの高速計算 (mod 998244353)

mod 998244353 で, $N$ 次までの二項変換を $O(N \log N)$ 時間で求めることができます.

指数型母関数の二項変換が簡単な式で書かれていることに注目します.

$\displaystyle G(x) = e^x F(x)\\ \displaystyle F(x) = e^{-x} G(x)$

二項係数の前計算を行えば, 数列からその指数型母関数の $N$ 次までの係数を $O(N)$ 時間で求められます. さらに指数型母関数の係数から数列の $N$ 項まで求めることも $O(N)$ 時間でできます.

唯一 $e^x F(x)$ , $e^{-x} G(x)$ を求めるのに畳み込みする必要があり, これには $O(N \log N)$ 時間かかります. 以上で二項変換が高速で求められました.

実装例 (c++)

cmb(n, k) は二項係数, fact[i] は階乗 $i!$ , factinv[i] は階乗の逆元 $(i!)^{-1}$ とします.

ftog は $a$ に対する $b$ を, gtof は $b$ に対する $a$ を返します.

vector<mint> ftog(vector<mint> &f){
    int n = f.size();
    vector<mint> F(n);
    for (int i=0; i<n; i++){
        F[i] = f[i] * factinv[i];
    }
    vector<mint> e(n);
    for (int i=0; i<n; i++){
        e[i] = factinv[i];
    }
    vector<mint> G = convolution<mint>(F, e);
    vector<mint> ret(n);
    for (int i=0; i<n; i++){
        ret[i] = G[i] * fact[i];
    }
    return ret;
}

vector<mint> gtof(vector<mint> &g){
    int n = g.size();
    vector<mint> G(n);
    for (int i=0; i<n; i++){
        G[i] = g[i] * factinv[i];
    }
    vector<mint> einv(n);
    mint par = 1;
    for (int i=0; i<n; i++){
        einv[i] = par * factinv[i];
        par *= -1;
    }
    vector<mint> F = convolution<mint>(G, einv);
    vector<mint> ret(n);
    for (int i=0; i<n; i++){
        ret[i] = F[i] * fact[i];
    }
    return ret;
}

x^K / (1-x)^M 型の g について

$b$ の通常型母関数 $g(x)$ が

$\displaystyle g(x) = \frac{x^K}{(1-x)^M}$

（ $K\ge 0, M \ge 0$ ）なら, $a$ の通常型母関数 $f(x)$ は

$\displaystyle f(x) = \frac{x^K}{(1+x)^{K+1-M}}$

となります.

これはおそらく最も使う場面が多いです.

$M=0$ のときは, 「ちょうど $K$ 個の集合に含まれている要素」の個数を表します. $\displaystyle f(x) = \frac{x^K}{(1+x)^{K+1}}$
$M=1, K=1$ のときは, ふつうの包除原理です. $\displaystyle f(x) = \frac{x}{1+x}$
$M=1$ のときは, 「 $K$ 個以上の集合に含まれている要素」の個数を表します. $\displaystyle f(x) = \frac{x^K}{(1+x)^K}$

追記：分母に $(1+x)^n$ が来ていますが, いわゆる負の二項定理というもので,

$\displaystyle \frac{1}{(1+x)^n} = \binom{n-1}{n-1} - \binom{n}{n-1} x + \binom{n+1}{n-1} x^2 - \cdots = \sum_{k \ge 0} \binom{n-1+k}{n-1} (-1)^k x^k\\ \displaystyle \frac{1}{(1-x)^n} = \binom{n-1}{n-1} + \binom{n}{n-1} x + \binom{n+1}{n-1} x^2 + \cdots = \sum_{k \ge 0} \binom{n-1+k}{n-1} x^k$

が成り立ちます.

もう解ける問題たち

問題3

$N$ 個の正整数 $A_1, \cdots, A_N$ が与えられます. $M$ 以下の正整数 $i$ であって, $i$ が $A_1, \cdots, A_N$ のうち $K$ 個以上の倍数であるようなものは何個ありますか？
$1 \le K \le N \le 18$
$1 \le M \le 10^{18}$
$1 \le A_i \le 10^{18}$

bit 全探索ですべてを調べます. lcm のオーバーフローに注意してください.

$g(x) = \frac{x^K}{1-x}$ なので, $f(x) = \frac{x^K}{(1+x)^K}$ とすればよいです.

追記：この場合, $a_n$ は $n \lt K$ については $a_n = 0$ で, $n \ge K$ については $a_n = \binom{K-1+n-K}{K-1} (-1)^{n-K}$ が成り立ちます.

問題4

$N$ 個の正整数 $A_1, \cdots, A_N$ が与えられます. $M$ 以下の正整数 $i$ であって, $i$ が $A_1, \cdots, A_N$ のうち奇数個の倍数であるようなものは何個ありますか？
$1 \le K \le N \le 18$
$1 \le M \le 10^{18}$
$1 \le A_i \le 10^{18}$

$g(x) = \frac{x}{1-x^2}$ なので,

$\displaystyle f(x) = \frac{1}{1+x} g\left(\frac{x}{1+x}\right) = \frac{1}{1+x} \frac{\frac{x}{1+x}}{1-\frac{x^2}{(1+x)^2}} = \frac{x}{1+2x}$

です. よって, $a = (0, 1, -2, 4, -8, 16, -32, 64, \cdots)$ となります. これはすごいです！

問題5

$N$ 個の正整数 $A_1, \cdots, A_N$ が与えられます. $M$ 以下の正整数 $i$ について, $C(i)$ を $1 \le j \le N$ であって $i$ が $A_j$ の倍数であるものの個数とします. このとき, $\sum_{i=1}^{M} C(i)^2$ を $998244353$ で割った余りを求めてください.
$1 \le K \le N \le 18$
$1 \le M \le 10^{18}$
$1 \le A_i \le 10^{18}$

問題6

$(1, 2, \cdots, N)$ の順列 $(p_1, p_2, \cdots, p_N)$ であって, $p_i = i$ となる $1 \le i \le N$ の個数が $K$ 個以下であるものの個数を $998244353$ で割った余りを求めてください. $1 \le K \le N \le 10^7$

これは一般化包除以外でも解けます. ただし, その場合は完全順列の個数を $1, 2, \cdots, N$ について列挙するのが一番簡単です.

練習問題

ABCの黄Diff そのまま使うことができます. 提出
Project Euler

参考文献

Binomial transform - Wikipedia

通常型母関数の二項変換の参考にしました.

４．母関数の応用～二項変換とその逆変換 - 理系のための備忘録

指数型母関数の二項変換がすごく簡潔に表せることが書かれていました.

しょぼんブログ

数学の色々とか様々とか

連載しょぼんコーダー 6 一般化された包除原理と二項変換

普通の包除原理

補題

包除原理の証明

問題1

問題2

一般化包除原理

存在性と唯一性

二項変換と逆変換

例 : b = (0,0,1,1,1,1,…)

二項変換の表示

通常型母関数の証明（長い）

指数型母関数の証明（長くない）

a→b, b→a の N 次までの高速計算 (mod 998244353)

実装例 (c++)

x^K / (1-x)^M 型の g について

もう解ける問題たち

問題3

問題4

問題5

問題6

練習問題

参考文献

普通の包除原理

補題

包除原理の証明

問題1

問題2

一般化包除原理

存在性と唯一性

二項変換と逆変換

例 : b = (0,0,1,1,1,1,…)

二項変換の表示

通常型母関数の証明（長い）

指数型母関数の証明（長くない）

a→b, b→a の N 次までの高速計算 (mod 998244353)

実装例 (c++)

xK / (1-x)M 型の g について

もう解ける問題たち

問題3

問題4

問題5

問題6

練習問題

参考文献

x^K / (1-x)^M 型の g について