高校数学では、場合の数を「和の法則」「積の法則」「順列 $_nP_r$」「組合せ $_nC_r$」という道具で数えます。
これらの道具は強力ですが、条件が複雑になると ── たとえば「少なくとも1つの条件を満たす」場合の数や「重複を許して合計がちょうど $n$ になる」場合の数を求めるとき ── 手が届かなくなることがあります。
大学の組合せ論では、包除原理と母関数（生成関数）という2つの道具を導入します。
包除原理は、集合の要素数について「足しすぎた分を引き、引きすぎた分を足す」操作を一般化したものであり、高校の「補集合を使う数え方」を任意の個数の集合に拡張します。
母関数は、数列 $a_0, a_1, a_2, \ldots$ を冪級数 $\sum a_n x^n$ に「変換」し、代数的な計算で数え上げの答えを導く手法です。
この2つの道具を使えば、高校の公式だけでは解きにくかった問題が体系的に解けるようになります。
高校の「場合の数」では、次の基本的な考え方を学びます。
また、「少なくとも1つ」を数えるときには補集合を使います。全体の場合の数を $U$ とすると、条件を「少なくとも1つ満たす」場合の数は、
$$U - (\text{1つも満たさない場合の数})$$
として計算します。さらに、$A \cup B$ の要素数について、集合の公式
$$|A \cup B| = |A| + |B| - |A \cap B|$$
を学びます。これは「$A$ と $B$ をそれぞれ数えると共通部分を二重に数えてしまうので、引いて修正する」という考え方です。
高校の範囲では、この2つの集合の公式で十分な場面がほとんどです。しかし、条件が3つ以上になったとき ── たとえば「$A$ または $B$ または $C$ を満たすもの」の個数を求めるとき ── この公式をどう拡張すればよいでしょうか。 また、$_nC_r$ は「$n$ 個から $r$ 個を（重複なしで）選ぶ」場面で使いますが、「同じものを何個でも選んでよい」場合にはどうすればよいでしょうか。 次のセクションで、これらの問いに答える大学の枠組みを見ていきます。
大学の組合せ論では、高校で学んだ個別の公式を、より一般的な原理で統一します。その中心となるのが包除原理と母関数です。
この記事で得られることは次の通りです。
まず、包除原理から始めます。これは高校の $|A \cup B|$ の公式を一般化したもので、任意個の集合に対して「足しすぎた分を引き、引きすぎた分を足す」操作を体系化します。
まず、高校で学んだ2つの集合の場合を確認します。有限集合 $A$, $B$ に対して、
$$|A \cup B| = |A| + |B| - |A \cap B|$$
が成り立ちます。$|A| + |B|$ と足すと $A \cap B$ に属する要素を2回数えてしまうので、1回分を引いて修正しています。
次に、3つの集合 $A$, $B$, $C$ について $|A \cup B \cup C|$ を求めます。2つの場合の公式を繰り返し使います。
まず $A \cup B \cup C = (A \cup B) \cup C$ と見て、2集合の公式を適用します。
$$|A \cup B \cup C| = |A \cup B| + |C| - |(A \cup B) \cap C|$$
ここで $|A \cup B| = |A| + |B| - |A \cap B|$ であり、また $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$ なので、
$$|(A \cup B) \cap C| = |A \cap C| + |B \cap C| - |A \cap B \cap C|$$
です。これらをまとめると、
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$
となります。パターンが見えてきます。「1つずつの要素数を足す」「2つずつの共通部分を引く」「3つの共通部分を足す」という交互の操作です。 この規則性を一般化したものが包除原理です。
有限集合 $A_1, A_2, \ldots, A_n$ に対して、
$$\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i} |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{i < j < k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1} |A_1 \cap A_2 \cap \cdots \cap A_n|$$
右辺は、$k$ 個の集合の共通部分の要素数を、$k = 1$ から $k = n$ まで、符号を交互に変えながら加えたものです。$k$ 個の集合の選び方は $\binom{n}{k}$ 通りあり、$k$ が奇数のときは $+$、偶数のときは $-$ の符号がつきます。
この公式がなぜ正しいのかを、証明で確認します。
証明の方針：$A_1 \cup A_2 \cup \cdots \cup A_n$ に属する任意の要素 $x$ が、右辺で正確に1回だけ数えられることを示します。
要素 $x$ が $A_1, A_2, \ldots, A_n$ のうちちょうど $m$ 個の集合に属するとします（$m \ge 1$）。$x$ が属する集合の個数が $m$ ですから、
したがって、右辺で $x$ が数えられる回数は、
$$\binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \cdots + (-1)^{m-1}\binom{m}{m}$$
です。ここで、二項定理を用います。$(1 + t)^m = \sum_{k=0}^{m} \binom{m}{k} t^k$ に $t = -1$ を代入すると、
$$0 = (1 + (-1))^m = \sum_{k=0}^{m} \binom{m}{k}(-1)^k = \binom{m}{0} - \binom{m}{1} + \binom{m}{2} - \cdots + (-1)^m \binom{m}{m}$$
$\binom{m}{0} = 1$ なので、移項すると
$$\binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \cdots + (-1)^{m-1}\binom{m}{m} = 1$$
よって、$x$ は右辺でちょうど1回だけ数えられます。$A_1 \cup \cdots \cup A_n$ に属さない要素は右辺のどの項にも寄与しないので、右辺は $|A_1 \cup \cdots \cup A_n|$ に等しくなります。 $\blacksquare$
証明の核心は、二項定理 $(1-1)^m = 0$ という等式にあります。各要素が正確に1回数えられることを、組合せ的に確認するのではなく、代数的に（二項定理を使って）示したのがポイントです。
あるクラスの40人の生徒について、数学クラブ $A$（18人）、物理クラブ $B$（15人）、化学クラブ $C$（12人）への所属を調べたところ、$|A \cap B| = 7$、$|A \cap C| = 5$、$|B \cap C| = 4$、$|A \cap B \cap C| = 2$ でした。少なくとも1つのクラブに所属する生徒は何人でしょうか。
包除原理を適用します。
$$|A \cup B \cup C| = 18 + 15 + 12 - 7 - 5 - 4 + 2 = 31$$
したがって、少なくとも1つのクラブに所属する生徒は31人です。どのクラブにも所属しない生徒は $40 - 31 = 9$ 人です。
ここまでで包除原理の定式化と証明ができました。次に、この原理を使って、高校の知識だけでは導出が難しい「完全順列」の個数を求めます。
$n$ 人がそれぞれ1つずつ帽子を持っています。帽子を全部集めてランダムに配り直したとき、誰も自分の帽子を受け取らない配り方は何通りあるでしょうか。
このような順列を完全順列（攪乱順列、derangement）と呼び、その個数を $D_n$ と書きます。$\{1, 2, \ldots, n\}$ の順列 $\sigma$ で、すべての $i$ に対して $\sigma(i) \ne i$ を満たすものの個数です。
小さい $n$ で確認します。$n = 1$ のとき $D_1 = 0$（1人では自分に渡すしかない）です。$n = 2$ のとき $D_2 = 1$（互いに交換する $(2,1)$ の1通り）です。$n = 3$ のとき $D_3 = 2$（$(2,3,1)$ と $(3,1,2)$ の2通り）です。
この問題を、セクション3で学んだ包除原理を使って一般の $n$ に対して解きます。
集合 $A_i$ を「$i$ 番目の人が自分の帽子を受け取る順列全体」と定義します。すると、$D_n$ は「$A_1, A_2, \ldots, A_n$ のいずれにも属さない順列」の個数ですから、
$$D_n = n! - |A_1 \cup A_2 \cup \cdots \cup A_n|$$
です。ここで $n!$ は全順列の数です。包除原理を適用するために、各項を計算します。
$|A_i|$ は「$i$ 番目が固定される順列」の個数です。$i$ を固定して残り $n-1$ 個を並べるので $|A_i| = (n-1)!$ です。同様に、
$k$ 個の集合の選び方は $\binom{n}{k}$ 通りあるので、包除原理より、
$$|A_1 \cup A_2 \cup \cdots \cup A_n| = \binom{n}{1}(n-1)! - \binom{n}{2}(n-2)! + \binom{n}{3}(n-3)! - \cdots + (-1)^{n-1}\binom{n}{n} \cdot 0!$$
ここで $\binom{n}{k}(n-k)! = \dfrac{n!}{k!(n-k)!} \cdot (n-k)! = \dfrac{n!}{k!}$ と簡約できます。したがって、
$$|A_1 \cup \cdots \cup A_n| = \frac{n!}{1!} - \frac{n!}{2!} + \frac{n!}{3!} - \cdots + (-1)^{n-1}\frac{n!}{n!}$$
$D_n = n! - |A_1 \cup \cdots \cup A_n|$ なので、
$$D_n = n! - \frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + \cdots + (-1)^n \frac{n!}{n!} = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$$
$D_n$ は $n$ 個の要素の順列のうち、どの要素も元の位置にない順列（完全順列）の個数です。$k = 0$ の項は $\frac{(-1)^0}{0!} = 1$ であり、$n! \cdot 1 = n!$ に対応します。
実際に計算してみます。
| $n$ | $D_n$ の計算 | $D_n$ | $D_n / n!$ |
|---|---|---|---|
| $1$ | $1 \cdot (1 - 1) = 0$ | $0$ | $0$ |
| $2$ | $2 \cdot (1 - 1 + \frac{1}{2}) = 1$ | $1$ | $0.500$ |
| $3$ | $6 \cdot (1 - 1 + \frac{1}{2} - \frac{1}{6}) = 2$ | $2$ | $0.333$ |
| $4$ | $24 \cdot (1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}) = 9$ | $9$ | $0.375$ |
| $5$ | $120 \cdot (1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}) = 44$ | $44$ | $0.367$ |
$D_n / n!$ の値に注目してください。$n$ が大きくなるにつれて、この比はある値に近づいています。 実は、$e^x$ のマクローリン展開 $e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}$ に $x = -1$ を代入すると、
$$e^{-1} = \sum_{k=0}^{\infty} \frac{(-1)^k}{k!}$$
となり、$D_n / n! = \sum_{k=0}^{n} \frac{(-1)^k}{k!}$ はこの無限級数の部分和です。したがって、$n$ が大きいとき $D_n \approx \frac{n!}{e}$ という近似が成り立ちます。$e^{-1} \approx 0.3679$ です。
$n$ 人の帽子をランダムに配り直したとき、誰も自分の帽子を受け取らない確率は $D_n/n!$ です。この値は $n$ が大きくなると $1/e \approx 0.368$ に収束します。つまり、人数が10人でも100人でも、約37%の確率で「全員が他人の帽子を受け取る」ことになります。これは包除原理と $e^x$ の展開が結びつく例です。
ここまでで、包除原理という道具が「高校の公式だけでは導出しにくい結果」を体系的に与えることを確認しました。 次に、もう1つの道具である母関数を導入します。母関数は包除原理とは異なるアプローチで数え上げ問題に切り込み、特に「合計がちょうど $n$ になる」タイプの問題で威力を発揮します。
次のような問題を考えます。「りんご、みかん、バナナの3種類の果物から、合計5個を選ぶ方法は何通りか（同じ種類を何個選んでもよい）」。 これは重複組合せと呼ばれる問題で、高校でも $_nH_r = {}_{n+r-1}C_r$ という公式を学ぶことがあります。 しかし、「りんごは最大2個まで」のような制約がつくと、高校の公式では対応しにくくなります。
母関数は、このような制約付きの数え上げ問題を、冪級数の積に変換して解く手法です。
数列 $a_0, a_1, a_2, \ldots$ に対して、これを係数とする冪級数を考えます。
$$f(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$$
数列 $\{a_n\}$ の情報を1つの関数 $f(x)$ に「格納」したものです。$x^n$ の係数 $a_n$ が、「$n$ 個を選ぶ方法の数」などの数え上げの答えに対応します。母関数は英語で generating function と呼ばれ、「生成関数」とも訳されます。ここでは $x$ を「形式的な変数」として扱い、収束性は考えないのが組合せ論の流儀です。
「数列を冪級数に変換する」とは、数列の各項 $a_n$ を冪級数 $\sum a_n x^n$ の係数として配置することです。重要なのは、$x$ に具体的な数値を代入して関数の値を求めるのではなく、$x^n$ の係数を読み取ることが目的だという点です。
母関数が威力を発揮する理由は、冪級数の積が数え上げの「合計」に対応することにあります。2つの冪級数 $f(x) = \sum a_n x^n$ と $g(x) = \sum b_n x^n$ の積を考えます。
$$f(x) \cdot g(x) = \left(\sum_{i=0}^{\infty} a_i x^i\right)\left(\sum_{j=0}^{\infty} b_j x^j\right) = \sum_{n=0}^{\infty} \left(\sum_{k=0}^{n} a_k b_{n-k}\right) x^n$$
積 $f(x) \cdot g(x)$ の $x^n$ の係数は $\sum_{k=0}^{n} a_k b_{n-k}$ です。これは「1つ目から $k$ 個、2つ目から $n-k$ 個を選ぶ方法の数」を、$k = 0$ から $k = n$ まで合計したものに対応します。つまり、冪級数の積をとるという操作が、「2つの選択を合わせて合計 $n$ 個にする」という数え上げに自動的に対応しているのです。
この対応を、具体例で確認します。
1円玉と5円玉を使って、合計 $n$ 円を作る方法の数を考えます。
1円玉を $k$ 枚使うとき（$k = 0, 1, 2, \ldots$）、1円玉の寄与を $x^k$ と表します。1円玉は何枚でも使えるので、1円玉の母関数は
$$1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}$$
です。同様に、5円玉を $j$ 枚使うと $5j$ 円になるので、5円玉の母関数は
$$1 + x^5 + x^{10} + x^{15} + \cdots = \frac{1}{1-x^5}$$
です。2つの母関数の積
$$\frac{1}{1-x} \cdot \frac{1}{1-x^5}$$
の $x^n$ の係数が、「1円玉と5円玉を使って合計 $n$ 円を作る方法の数」に対応します。たとえば $n = 7$ なら、$x^7$ の係数を読み取ればよいのです。
実際に展開してみます。$\frac{1}{1-x} = 1 + x + x^2 + \cdots$ と $\frac{1}{1-x^5} = 1 + x^5 + x^{10} + \cdots$ の積で $x^7$ の項を拾うと、
$x^7$ の係数は2です。これは「7円を作る方法は2通り（1円玉7枚か、5円玉1枚と1円玉2枚）」という答えに一致します。
誤解：母関数 $f(x) = \sum a_n x^n$ に $x = 2$ などの値を代入して答えを得る。
正しい理解：母関数では、$x$ は「位置を示す印」（形式的変数）です。$x^n$ の係数を読み取ることが目的であり、$x$ に具体的な値を代入することは（特殊な場合を除き）しません。冪級数が収束するかどうかも、組合せ論の文脈では問題にしません。
ここまでで母関数の基本的な考え方を理解しました。次のセクションでは、この道具を使って重複組合せや制約付きの分配問題を解きます。
「$r$ 種類のものから、重複を許して合計 $n$ 個を選ぶ方法の数」を求めます。各種類について $0$ 個以上いくらでも選べるので、セクション5で見たように、各種類の母関数は
$$1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}$$
です。$r$ 種類あるので、全体の母関数はこの $r$ 個の積です。
$$\left(\frac{1}{1-x}\right)^r = \frac{1}{(1-x)^r}$$
この $x^n$ の係数が求める答えです。$\frac{1}{(1-x)^r}$ の展開公式を導出します。
示すこと：$\frac{1}{(1-x)^r}$ の $x^n$ の係数が $\binom{n+r-1}{r-1}$ であることを示します。
一般化された二項定理を使います。実数 $\alpha$ に対して、一般化された二項係数を
$$\binom{\alpha}{k} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k!}$$
と定義すると、$(1+t)^\alpha = \sum_{k=0}^{\infty} \binom{\alpha}{k} t^k$ が成り立ちます。これは高校で学ぶ二項定理（$\alpha$ が自然数の場合）を実数に拡張したもので、形式的冪級数として等式が成り立ちます。
$(1-x)^{-r} = (1+(-x))^{-r}$ なので $\alpha = -r$、$t = -x$ として、
$$\binom{-r}{k} = \frac{(-r)(-r-1)\cdots(-r-k+1)}{k!} = (-1)^k \frac{r(r+1)\cdots(r+k-1)}{k!} = (-1)^k \binom{r+k-1}{k}$$
ここで、分子の $(-r)(-r-1)\cdots(-r-k+1)$ から $(-1)$ を $k$ 個くくり出すと $(-1)^k \cdot r(r+1)\cdots(r+k-1)$ となることを使いました。
$t^k = (-x)^k = (-1)^k x^k$ なので、
$$\frac{1}{(1-x)^r} = \sum_{k=0}^{\infty} (-1)^k \binom{r+k-1}{k} \cdot (-1)^k x^k = \sum_{k=0}^{\infty} \binom{r+k-1}{k} x^k$$
$(-1)^k \cdot (-1)^k = (-1)^{2k} = 1$ なので符号は消えます。$x^n$ の係数は $\binom{n+r-1}{n} = \binom{n+r-1}{r-1}$ です。 $\blacksquare$
$r$ 種類のものから重複を許して $n$ 個を選ぶ方法の数は、
$$_rH_n = \binom{n+r-1}{r-1} = \binom{n+r-1}{n}$$
これは $\frac{1}{(1-x)^r}$ の $x^n$ の係数です。高校で学ぶ重複組合せの公式 $_rH_n = {}_{n+r-1}C_n$ が、母関数から自然に導出されました。
3種類の果物（りんご、みかん、バナナ）から重複を許して5個選ぶ方法の数を計算します。$r = 3$、$n = 5$ なので、
$$_3H_5 = \binom{5+3-1}{3-1} = \binom{7}{2} = \frac{7 \cdot 6}{2 \cdot 1} = 21$$
21通りです。
母関数の真価は、選べる個数に制約がある場合に発揮されます。先ほどの果物の問題を、「りんごは最大2個まで、みかんは最大3個まで、バナナは制限なし」に変更します。
セクション5で学んだように、各果物の母関数は制約をそのまま反映して次のようになります。
全体の母関数は、
$$(1 + x + x^2)(1 + x + x^2 + x^3) \cdot \frac{1}{1-x}$$
です。この $x^5$ の係数を求めれば答えが得られます。有限の多項式部分を展開します。
$$(1 + x + x^2)(1 + x + x^2 + x^3) = 1 + 2x + 3x^2 + 3x^3 + 2x^4 + x^5$$
これに $\frac{1}{1-x} = 1 + x + x^2 + \cdots$ をかけて $x^5$ の係数を求めます。$\frac{1}{1-x}$ をかけることは「係数の累積和をとる」操作に対応します。つまり、$x^5$ の係数は上の多項式の $x^0$ から $x^5$ までの係数をすべて足したものです。
$$1 + 2 + 3 + 3 + 2 + 1 = 12$$
したがって、制約付きの場合は12通りです。制約なしの場合の21通りと比べると、制約によって場合の数が減っていることがわかります。
母関数のアプローチでは、各要素の選択の制約を「多項式の形」で表現します。制約なし（$0$ 個以上）なら $\frac{1}{1-x}$、最大 $m$ 個なら $1 + x + \cdots + x^m$、ちょうど偶数個なら $1 + x^2 + x^4 + \cdots$ のように、制約をそのまま多項式に翻訳できます。あとは積をとって $x^n$ の係数を読み取るだけです。問題ごとに場合分けの工夫をする必要がなく、機械的に処理できることが最大の利点です。
母関数は数え上げ問題だけでなく、漸化式を解く道具としても使われます。たとえばフィボナッチ数列 $F_0 = 0$、$F_1 = 1$、$F_{n+2} = F_{n+1} + F_n$ の母関数 $F(x) = \sum F_n x^n$ を考えると、漸化式を $F(x)$ についての方程式に変換でき、
$$F(x) = \frac{x}{1 - x - x^2}$$
と求まります。これを部分分数分解することで $F_n$ の一般項（ビネの公式）を導出できます。母関数は数え上げと数列を結びつける強力な橋渡し役です。 この話題は 📖 M-14-1 漸化式と離散力学系 で詳しく扱います。
最後に、この記事で学んだ2つの道具のつながりを確認します。セクション4で求めた完全順列の問題は、母関数でも扱えます。完全順列の個数 $D_n$ を係数にもつ指数型母関数は、
$$\sum_{n=0}^{\infty} \frac{D_n}{n!} x^n = \frac{e^{-x}}{1-x}$$
となります。この式の右辺で $e^{-x} = \sum_{k=0}^{\infty} \frac{(-1)^k}{k!} x^k$ と $\frac{1}{1-x} = \sum_{m=0}^{\infty} x^m$ の積の $x^n$ の係数を求めると、$\sum_{k=0}^{n} \frac{(-1)^k}{k!}$ が得られ、$D_n / n! = \sum_{k=0}^{n} \frac{(-1)^k}{k!}$ というセクション4の結果が再導出されます。
包除原理は「足して引く」という集合論的アプローチ、母関数は「冪級数の代数」というアプローチです。異なる角度から同じ答えに到達できるのが、数え上げの理論の豊かさです。
Q1. 包除原理の証明で、二項定理はどのように使われますか。
Q2. $n = 4$ のとき、完全順列の個数 $D_4$ を計算してください。
Q3. 母関数 $(1+x+x^2)(1+x)$ の $x^2$ の係数を求め、それがどのような数え上げに対応するか説明してください。
Q4. 2種類のものから重複を許して4個選ぶ方法の数を、重複組合せの公式で求めてください。
100人の生徒について、英語が好きな生徒が55人、数学が好きな生徒が40人、両方好きな生徒が20人です。包除原理を使って、英語か数学の少なくとも一方が好きな生徒の人数を求めてください。また、どちらも好きでない生徒は何人ですか。
英語が好きな生徒の集合を $A$、数学が好きな生徒の集合を $B$ とします。包除原理より、
$$|A \cup B| = |A| + |B| - |A \cap B| = 55 + 40 - 20 = 75$$
少なくとも一方が好きな生徒は75人です。どちらも好きでない生徒は $100 - 75 = 25$ 人です。
数列 $1, 2, 3, 4, \ldots$（$a_n = n+1$、$n = 0, 1, 2, \ldots$）の母関数を求めてください。
ヒント：$\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n$ の両辺を $x$ で微分してみてください。
$\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n$ の両辺を $x$ で微分すると、
$$\frac{1}{(1-x)^2} = \sum_{n=1}^{\infty} n x^{n-1} = \sum_{n=0}^{\infty} (n+1) x^n$$
したがって、数列 $a_n = n+1$ の母関数は $\frac{1}{(1-x)^2}$ です。
これは重複組合せの公式 $\frac{1}{(1-x)^r}$ で $r = 2$ とした場合に対応します。$x^n$ の係数は $\binom{n+1}{1} = n+1$ です。
1から1000までの整数のうち、2でも3でも5でも割り切れないものの個数を、包除原理を使って求めてください。
$A$ を2の倍数、$B$ を3の倍数、$C$ を5の倍数の集合とします。$\lfloor x \rfloor$ を $x$ 以下の最大の整数とすると、
$|A| = \lfloor 1000/2 \rfloor = 500$、$|B| = \lfloor 1000/3 \rfloor = 333$、$|C| = \lfloor 1000/5 \rfloor = 200$
$|A \cap B| = \lfloor 1000/6 \rfloor = 166$、$|A \cap C| = \lfloor 1000/10 \rfloor = 100$、$|B \cap C| = \lfloor 1000/15 \rfloor = 66$
$|A \cap B \cap C| = \lfloor 1000/30 \rfloor = 33$
包除原理より、
$$|A \cup B \cup C| = 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$$
2, 3, 5のいずれでも割り切れない整数の個数は $1000 - 734 = 266$ 個です。
赤玉（0〜3個）、白玉（0〜2個）、青玉（0個以上何個でも）から合計6個を選ぶ方法の数を、母関数を使って求めてください。
各色の母関数は次の通りです。
赤と白の積を計算します。
$$(1+x+x^2+x^3)(1+x+x^2) = 1 + 2x + 3x^2 + 3x^3 + 2x^4 + x^5$$
これに $\frac{1}{1-x}$ をかけると、$x^6$ の係数は上の多項式の $x^0$ から $x^6$ までの係数の和です。$x^6$ の項はないので $0$ を加えます。
$$1 + 2 + 3 + 3 + 2 + 1 + 0 = 12$$
答えは 12 通りです。
$n = 5$ のとき、$\{1, 2, 3, 4, 5\}$ の完全順列（攪乱順列）の個数 $D_5$ を包除原理の公式で計算してください。さらに、完全順列を3つ具体的に書き出してください。
$$D_5 = 5!\left(\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!}\right) = 120\left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}\right)$$
通分すると、$120 \cdot \frac{120 - 120 + 60 - 20 + 5 - 1}{120} = 44$ です。
完全順列の例（$\sigma(i) \ne i$ をすべての $i$ で満たす）：