数え上げの基礎 ― 加法原理・乗法原理・順列・組合せ

加法原理・乗法原理から出発し，順列$P(n,r)$，組合せ$C(n,r)$，重複順列，重複組合せ$H(n,r)$を定義・証明する教科書スタイルの記事．全射・単射の数え上げまでを扱う．

2026年2月27日

1 加法原理と乗法原理

定義 1 (加法原理).

有限集合

A_{1}, A_{2}, \dots, A_{k}

が互いに素（

A_{i} \cap A_{j} = \emptyset

，

i \neq = j

）であるとき，

∣ A_{1} ⊔ A_{2} ⊔ \dots ⊔ A_{k} ∣ = ∣ A_{1} ∣ + ∣ A_{2} ∣ + \dots + ∣ A_{k} ∣

が成り立つ．これを加法原理（rule of sum）という．

定義 2 (乗法原理).

有限集合

A_{1}, A_{2}, \dots, A_{k}

に対して，

∣ A_{1} \times A_{2} \times \dots \times A_{k} ∣ = ∣ A_{1} ∣ \cdot ∣ A_{2} ∣ \dots ∣ A_{k} ∣

が成り立つ．これを乗法原理（rule of product）という．

注意 3.

加法原理は直和（disjoint union）の濃度に，乗法原理は直積（Cartesian product）の濃度に関する基本的な等式である．組合せ論における数え上げの大部分は，この2原理の繰り返し適用に帰着される．

2 順列

定義 4 (順列).

n

個の相異なる元から

r

個を選んで一列に並べる方法の数を順列（permutation）の数といい，

P (n, r)

と書く．

定理 5.

P (n, r) = n (n - 1) (n - 2) \dots (n - r + 1) = \frac{n !}{( n - r )!}

証明.

乗法原理による．1番目の位置には

n

通り，2番目には残り

n - 1

通り，…，

r

番目には

n - r + 1

通りの選び方がある．よって

P (n, r) = n (n - 1) \dots (n - r + 1)

． □

定義 6 (重複順列).

n

種類の元から重複を許して

r

個選び一列に並べる方法の数を重複順列の数といい，

n^{r}

で与えられる．

3 組合せ

定義 7 (組合せ).

n

個の相異なる元から

r

個を選ぶ（順序を問わない）方法の数を組合せ（combination）の数といい，

(r n)

または

C (n, r)

と書く．

定理 8.

(r n) = \frac{n !}{r ! ( n - r )!}

証明.

r

個の元を選んで並べる方法は

P (n, r)

通りである．同じ

r

個の元の集合は

r!

通りの並べ方に対応するので，

(r n) = P (n, r) / r! = n! / (r! (n - r)!)

． □

4 重複組合せ

定義 9 (重複組合せ).

n

種類の元から重複を許して

r

個を選ぶ（順序を問わない）方法の数を重複組合せの数といい，

H (n, r)

と書く．

定理 10.

H (n, r) = (r n + r - 1)

証明.

n

種類の元を

x_{1}, x_{2}, \dots, x_{n}

とし，各

x_{i}

を

a_{i}

個選ぶとすると，条件は

a_{1} + a_{2} + \dots + a_{n} = r

（

a_{i} \geq 0

）を満たす非負整数解の個数を求めることに等しい．これは「

r

個の星と

n - 1

個の仕切り」の問題（stars and bars）に帰着され，

r + (n - 1) = n + r - 1

個の位置から仕切りを置く

n - 1

個の位置を選ぶ組合せの数

(n - 1 n + r - 1) = (r n + r - 1)

に等しい． □

5 全射・単射の数え上げ

定理 11 (単射の数).

∣ A ∣ = r

，

∣ B ∣ = n

（

r \leq n

）とする．

A

から

B

への単射の個数は

P (n, r) = n! / (n - r)!

である．

証明.

単射

f : A \to B

は

A

の元に

B

の相異なる元を順に割り当てることに等しく，乗法原理より

P (n, r)

通りである． □

定理 12 (全射の数).

∣ A ∣ = n

，

∣ B ∣ = k

（

n \geq k

）とする．

A

から

B

への全射の個数は

j = 0 \sum k (- 1)^{j} (j k) (k - j)^{n}

である．

証明.

包除原理による．

B = {b_{1}, \dots, b_{k}}

とし，

S_{i} = {f : A \to B ∣ b_{i} \in / Im (f)}

とおく．全射でない写像の集合は

S_{1} \cup \dots \cup S_{k}

であり，

∣ S_{i_{1}} \cap \dots \cap S_{i_{j}} ∣ = (k - j)^{n}

であるから，包除原理より全射の数は

k^{n} - ∣ S_{1} \cup \dots \cup S_{k} ∣ = \sum_{j = 0}^{k} (- 1)^{j} (j k) (k - j)^{n}

となる． □

例 13.

A = {1, 2, 3, 4}

，

B = {a, b}

のとき全射の数は

\sum_{j = 0}^{2} (- 1)^{j} (j 2) (2 - j)^{4} = 2^{4} - 2 \cdot 1^{4} + 0 = 14

である．

数え上げの基礎 ― 加法原理・乗法原理・順列・組合せ

1 加法原理と乗法原理

2 順列

3 組合せ

4 重複組合せ

5 全射・単射の数え上げ

関連する「教科書の行間」記事

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ