2013 年度前期 離散数学

草刈圭一朗 hkusakari@is.nagoya-u.ac.jpi

講義資料 (3): 集合の計数

3.1

順列と組合わせ

本節は，教科書では紹介せずに利用している順列と組合わせの概念を紹介する．なお，証明は全て割愛する．
定義 3.1 n 個の異なるものから，重複を許さずに k 個取り出して並べたものを，n 個のものから k 個とった順列 (permutation) と呼び，順列の総数を n Pk で記す．なお， n P0 = 1であるとする．
定理 3.2 n, k を 0 ≤ k ≤ n となる任意の自然数とする．このとき以下の等式が成立する．
n Pk=n!
(n − k)!

NOTE: なお， n Pk = n(n − 1) · · · (n − k + 1) と記すと，k = 0 の場合の右辺の値が分かりにくい．k = 0 の場合は n(n − 1) · · · (n − k + 1) = 1 と無理やり解釈することも可能ではある．
定義 3.3 n 個の異なるものから，重複を許さずに k 個取り出した集合を，n 個のものから
k 個とった組合わせ (combination) と呼び，組合わせの総数を n Ck または nk で記す．なお， n C0 = 1 であるとする．
NOTE: 上述の定義で「組合わせ」なる概念を定義してるが，以下では「組合わせ」という単語に特別な意味を与えず単なる自然言語として取り扱っている．注意されたし．
定理 3.4 n, k を 0 ≤ k ≤ n となる任意の自然数とする．このとき以下の等式が成立する．
n Ck=n Pkk!

=n!
k!(n − k)!

定理 3.5 組合わせ数に関して以下の漸化式が成立する．
if k = 0 ∨ n = k 1if 0 < k < nn Ck =n−1 Ck + n−1 Ck−1
 0otherwise

3.2



基本的な集合の数え方

本節は，教科書 1.3.1 節の後半 (pp.25–26) に対応する．
定義 3.6 有限集合 A の要素数を |A| で記す (#A で記すこともある)．

19



定理 3.7 任意の有限集合 A, B に対して以下の等式が成立する．

(1) |A × B| = |A| × |B|(2) |2A | = 2|A|

(3) |B A | = |B||A|

なお，(3) において，00 = 1 と考えるとする．

NOTE: 00 = 1 と考えるのは実は当たり前の話ではない．実は xy の定義は複素数上にまで自然に拡張できるのだが，この拡張した関数が (x, y) = (0, 0) において連続 (そのうち習う概念?) ではないのである．実際，00 = 0 と考えても 00 = 1 と考えても，さらに言うと 00 = e と考えても，それなりに妥当な議論が可能になってしまう．
NOTE: 本講義中では 00 = 1 と仮定しておく．なお，教科書でもこの仮定を導入しているはずなのだが，教科書では x0 の形の計算処理に甘いところがあり若干のバグがある．本
資料ではバグは修正されてるのでご心配なく．

3.3

ふるいわけ公式 (包除原理)

本節は，教科書 1.3.1 節の前半 (pp.24–25) と 1.3.3 節 (pp.32–38) に対応する．
定理 3.8 任意の有限集合 A, B に対して |A ∪ B| = |A| + |B| − |A ∩ B| が成立．
証明 左辺は A ∪ B に属する要素数を表している．そこで，右辺でこれらの要素がどのように数えられているかを考えてみる．

• A にのみ属する要素: |A| の中で 1 回だけ数えられている．
• B にのみ属する要素: |B| の中で 1 回だけ数えられている．
• A と B の両方に属する要素: |A|，|B|，|A ∩ B| のそれぞれで 1 回ずつ数えられてるので全体として 1 + 1 − 1，すなわち 1 回だけ数えられている．
以上より A ∪ B の要素がどれも 1 回ずつ数えられているので，右辺は |A ∪ B| に一致．
定理 3.8 は任意個の集合を取り扱えるように拡張することができる．
定理 3.9 任意の有限集合 A1 , A2 , . . . , An に対して以下の関係が成立する．

|A1 ∪ · · · ∪ An | =nX
k=1(−1)k+1[X|Ai1 ∩ · · · ∩ Aik |]1≤i1 <···<ik ≤n

証明 n に関する帰納法で示す．n = 1 の場合は明らか．n > 1 とする．以下では証明の可読性を高めるために制約条件「1 ≤ i1 < · · · < ik ≤ n」を「ik E n」で略記する．

|A1 ∪ · · · ∪ An | = |A1 ∪ · · · ∪ An−1 | + |An | − |(A1 ∪ · · · ∪ An−1 ) ∩ An |(∵ 定理 3.8 より)= |A1 ∪ · · · ∪ An−1 | + |An | − |(A1 ∩ An ) ∪ · · · ∪ (An−1 ∩ An )|PPn−1k+1[ ik En−1 |Ai1 ∩ · · · ∩ Aik |]=k=1 (−1)+|An | − |(A1 ∩ An ) ∪ · · · ∪ (An−1 ∩ An )|(∵ 帰納法の仮定より)
20====
==

Pn−1

k+1
[|Ai1 ∩ · · · ∩ Aik |]
k=1 (−1)
Pn−1 ik En−1Pk+1+|An | − k=1 (−1) [ ik En−1 |(Ai1 ∩ An ) ∩ · · · ∩ (Aik ∩ An )|]P(∵ 帰納法の仮定より)
Pn−1
Pk+1
[ ik En−1 |Ai1 ∩ · · · ∩ Aik |]
k=1 (−1)
Pn−1
P+|An | − k=1(−1)k+1 [ ik En−1 |Ai1 ∩ · · · ∩ Aik ∩ An |]PnPk+1[ ik En∧ik 6=n |Ai1 ∩ · · · ∩ Aik |]
k=1 (−1)
PP+|An | − nk=2(−1)k+2 [ ik En∧ik =n |Ai1 ∩ · · · ∩ Aik |]PnPk+1[ ik En∧ik 6=n |Ai1 ∩ · · · ∩ Aik |]
k=1 (−1)
PP+|An | + nk=2 (−1)k+1 [ ik En∧ik =n |Ai1 ∩ · · · ∩ Aik |]PnPk+1[ ik En∧ik 6=n |Ai1 ∩ · · · ∩ Aik |]
k=1 (−1)
PP+ nk=1 (−1)k+1 [ ik En∧ik =n |Ai1 ∩ · · · ∩ Aik |]PPnk+1[ ik En |Ai1 ∩ · · · ∩ Aik |]
k=1 (−1)

NOTE: この定理で示した等式は，ふるいわけ公式 (sieve formula) や包除原理 (inclusionexclusion principle) と呼ばれる有名でかつ重要な公式である．
例 3.10 出席者 n 人のパーティで出席者全員がプレゼントを持ち寄りプレゼント交換を行うという．このとき，誰も自分のプレゼントには当たらないような交換のしかたの数は何通りあるだろうか？
出席者 n 人に 1 から n までの通し番号を付け，また番号 j の出席者が持ってきたプレゼントも同じ番号 j で表すとする．そして，1, 2, . . . , n 番の出席者が受け取ったプレゼントの番号が j1 , j2 , . . . , jn であるということを順序対 (j1 , j2 , . . . , jn ) で表現し，これらの順序対全体を X で表現する．また，番号 i の出席者が自分で持ってきたプレゼントを受け取ってしまう交換方法に対応する順序対全体を Ai で表す．明らかに Ai は以下のように表現できる．
Ai = {(j1 , . . . , jn ) ∈ X | ji = i}
このとき求める交換の仕方の数は |(A1 ∪ · · · ∪ An )c | 通りとなり，補集合の定義より以下のように展開できる．

|(A1 ∪ · · · ∪ An )c | = |X| − |A1 ∪ · · · ∪ An | = n! − |A1 ∪ · · · ∪ An |定理 3.9 より，|A1 ∪ · · · ∪ An | =nX
k=1(−1)k+1[X|Ai1 ∩ · · · ∩ Aik |]1≤i1 <···<ik ≤n以上より求める交換の仕方の数は次のように求められる．ただし，可読性を高めるために制約条件「1 ≤ i1 < · · · < ik ≤ n」を「P 」で略記している．

|(Ai ∪ · · · ∪ An )c | =======

n! − |A1 ∪ · · · ∪ An |PP
n! − nk=1(−1)k+1 [ P |Ai1 ∩ · · · ∩ Aik |]PPn! − nk=1(−1)k+1 [ P |{(j1 , . . . , jn ) ∈ X | ji1 = i1 , . . . , jik = ik }|]PPn! − nk=1(−1)k+1 [ P (n − k)!]P
n! − nk=1(−1)k+1 n Ck (n − k)!
Pn! − nk=1(−1)k+1 n!
k!
n!(1 − 1!1 + 2!1 − · · · + (−1)n n!1 )21上記の結果を用いると，|X| = n! であるので，でたらめにプレゼントを交換しても誰も自分のプレゼントに当たってしまわない確率 pn は111
pn = 1 − + − · · · + (−1)n1! 2!
n!
−1で与えられる．limn→∞ pn = e ≈ 0.367879 · · · であるので，出席者の数が十分多い場合，でたらめにプレゼントを交換しても，誰も自分のプレゼントに当たってしまわない確率は約 37% となる (実は n ≥ 4 ならばいつでも約 37%)．結構高い確率で上手くいくようである．低いと感じる人もいるかも知れないが…．
3.4関数の数え上げ

本節は，教科書 1 節の練習問題 10 番 (p.39) に対応する．
定理 3.11 A, B を |A| = n，|B| = k であるような任意の有限集合とする．このとき，Aから B への単射の個数は以下のようになる．

|{f ∈ B A | f は単射 }| = n! k Cn
証明 n > k のときは両辺共に 0 となり成立．n ≤ k の場合を考えると，単射の個数は，A の各要素に B の異る要素を次々と割り当てる仕方の数と一致するので k(k−1) · · · (k−n+1) =k!
= n! k Cn となる．
(k−n)!
定理 3.12 A, B を |A| = n，|B| = k であるような任意の有限集合とする．このとき，Aから B への全射の個数は以下のようになる．

|{f ∈ B A | f は全射 }| =kX(−1)i k Ci (k − i)ni=0A

証明 S = {f ∈ B | f は全射 }，B = {b1 , b2 , . . . , bk } とし，各 j に対し Fj = {f ∈ B A |bj 6∈ f (A)} とする．このとき，定理 3.7(3) を考えて各 j1 , . . . , ji (1 ≤ j1 < · · · < ji ≤ k) に対し以下を得る．

|Fj1 ∩ · · · ∩ Fji | = |(B \ {bj1 , . . . , bji })A | = (k − i)n定理 3.7(3) と定理 3.9 を考えて，求める個数 |S| は以下のように得られる．

|S| =======|B A \ (F1 ∪ · · · ∪ Fk )|k n − |(F1 ∪ · · · ∪ Fk )|PP
k n − ki=1 (−1)i+1 [ 1≤j1 <···<ji ≤k |Fj1 ∩ · · · ∩ Fji |]PP
k n − ki=1 (−1)i+1 [ 1≤j1 <···<ji ≤k (k − i)n ]Pk n − ki=1 (−1)i+1 k Ci (k − i)nP
k n + ki=1 (−1)i k Ci (k − i)nPkni
i=0 (−1) k Ci (k − i)NOTE: |A| = n < k = |B| のときは明らかに |{f ∈ B A | f は全射 }| = 0．すなわち，Pn < k のときは， ki=0 (−1)i k Ci (k − i)n = 0 の関係が成立する．
nNOTE: 全射の個数は後述するスターリング数 (Sm) と密接な関係がある (定理 3.21 参照)．

223.5カタラン数

本節は，教科書 1.3.2 節の後半 (pp.29–32) に対応する．
定義 3.13 右図のような n×n の格子の右下半分のみからなる道路網を考える．このような道路網で格子点 O(0, 0) から P (n, n)まで行く最短経路の個数をカタラン数 (Catalan number) と呼び，Cn で記す．ただし，便宜上 C0 = 1 とする．
P

O定理 3.14 カタラン数に関して以下の漸化式が成立する．
(1if n = 0
Cn =C0 Cn−1 + C1 Cn−2 + · · · + Cn−1 C0 if n > 0
証明 n = 0 のときは明らか．n > 0 とする．k を 0 < k ≤ n となる任意の自然数とする．
このとき以下の関係が成立する．

• 格子点 (0, 0) から格子点 (k, k) に行く経路のうち，任意の i < k に対して格子点 (i, i)を通らない経路の個数は，格子点 (1, 0) と格子点 (k, k − 1) を対角とする正方形上のカタラン数に対応する．すなわち Ck−1 と一致する．
• 格子点 (k, k) から格子点 (n, n) に行く経路は Cn−k 通り存在する．
Pn
これらの事実より Cn = k=1 Ck−1Cn−k = C0 Cn−1 + C1 Cn−2 + · · · + Cn−1 C0 が得られる．
定理 3.15 (オイラーの公式)

Cn =2n Cnn+1

証明 (概略のみ示す) 格子点 O(0, 0) から P (n, n) までの最短経路の個数は 2n Cn 個．これらのうち不適な経路，すなわち線分 OP の上側にはみ出す経路の個数は，格子点 (0, 1) と(n, n+1) を結ぶ線分に関する対称性に着目することにより，格子点 (0, 0) から (n−1, n+1)への最短経路の個数と一致することが分かる (詳細は本文 pp.30–32 を参照)．よって，不Cn を得る．
適な経路の個数は 2n Cn−1 ．よって，Cn = 2n Cn − 2n Cn−1 = 2nn+1


NOTE: 定理 3.14 の漸化式を解いてオイラーの公式を導くことは結構大変．母関数の概念を用いると，それなりの手間で証明できるのだが，本講義の枠組みを越えるので割愛．
NOTE: レオンハルト・オイラー（Leonhard Euler) はスイスの誇る 18 世紀に活躍した数学者．歴史上最も多産な数学者とも呼ばれる程に膨大な業績を残した (晩年は全盲になるも研究を続行し続けた)．それゆえに，数学のあらゆる分野に「オイラーの公式」なるものが存在する．例えば，ejθ = cos θ + j sin θ もオイラーの公式と呼ばれる．

23

3.6n 個の玉を k 個の箱に空箱が無いように入れる組合わせ

本節は，教科書 1.3.2 節の前半 (pp.26–29) に対応する．
n 個の玉を k 個の箱に空箱ができないように入れる組合わせは何通り有るだろうか？この組合わせは玉を区別するかどうか，箱を区別するかどうかによって解が変わってくる．本節ではそれぞれの場合について議論する．

3.6.1

玉も箱も区別しない場合

定義 3.16 区別のない n 個の玉を区別のない k 個の箱に空箱が無いように入れる組合わせの数を n の k 部分への分割数 (partition number) と呼び，Pnk で記す．
NOTE: n の分割数 Pn は Pn0 + Pn1 + · · · + Pnn で与えられる．上で与えた “k 部分への分割数” と微妙に異なる概念である事に注意されたし．というわけで求める答は Pnk 通りであるのだが，これだけでは嬉しくない．では，Pnk とは具体的にどのような数なのだろうか？Pnk を直接表す式は知られていないが (少なくとも私は知らない)，以下の漸化式により Pnk を与えることができる．
定理 3.17 n の k 部分への分割数に関して以下の漸化式が成立する．
if (n > 0 ∧ k = 1) ∨ n = k 1k12k
Pn =Pn−k + Pn−k + · · · + Pn−k if 1 < k < n
 0otherwise

証明 1 < k < n の場合のみ考える．k 個の箱に玉を 1 個ずつ入れ，それから残り n − k 個の玉を k 個の箱のうちのいくつか (1 個から k 個まで) の箱に空箱がないように入れる組合
12k
わせの数が Pnk に一致する．すなわち，Pnk = Pn−k+ Pn−k+ · · · + Pn−k．
3.6.2玉を区別せず箱を区別する場合

定理 3.18 区別のない n 個の玉を区別のある k 個の箱に空箱が無いように入れる組合わせの個数は，0 < k ≤ n の場合 n−1 Ck−1 個となり，k = n = 0 の場合は 1 個になり，それ以外の場合は 0 個になる．
証明 0 < k ≤ n の場合のみ示す．n 個の玉を一列に並べ，玉と玉の間 n − 1 個所に k − 1個所の仕切りを作る方法の個数と一致する．すなわち， n−1 Ck−1 個となる．
3.6.3玉を区別し箱を区別しない場合

定義 3.19 区別のある n 個の玉を区別のない k 個の箱に空箱が無いように入れる組合わ
せの数を (第 2 種) スターリング数 (Stirling number) と呼び，Snk で記す．
24

というわけで求める答は Snk 通りであるのだが，これだけでは嬉しくない．では，スターリング数とは具体的にどのような数なのだろうか？
定理 3.20 スターリング数 Snk に対して以下の漸化式が成立する．
if (n > 0 ∧ k = 1) ∨ n = k 1kk−1kSn =Sn−1 + kSn−1 if 1 < k < n
 0otherwise

証明 1 < k < n の場合のみ示す．区別のある n 個の玉を区別のない k 個の箱にわける方法は，以下の 2 つの作業の個数の和と一致する．

(i) 最初の n − 1 個を k − 1 個の箱に入れ，最後の 1 個を残りの箱に入れる．
(ii) 最初の n − 1 個を k 個の箱に入れ，最後の 1 個をどれかの箱に付け加える．
k−1k−1kk(i) の個数は Sn−1個であり，(ii) の個数は kSn−1個である．よって，Snk = Sn−1+ kSn−1を得る．
定理 3.21k

Snk =1 X(−1)i k Ci (k − i)nk! i=0

証明 箱を区別すると考えた場合，求める個数は，玉全体からなる集合から箱全体からなるPk集合への全射の個数と一致する．よって，この場合は定理 3.12 より i=0 (−1)i k Ci (k − i)nPkとなる．実際には箱を区別しないので，これを k! で割った値 k!1 i=0 (−1)i k Ci (k − i)n がSnk と一致する．
3.6.4

玉も箱も区別する場合

定理 3.22 区別のある n 個の玉を区別のある k 個の箱に空箱が無いように入れる組合わせの個数は k!Snk 個となる．
証明 定理 3.21 の証明ですでに言及しているが，求める個数は，玉全体からなる集合から箱全体からなる集合への全射の個数と一致する．よって，定理 3.12 と定理 3.21 より k!Snkが導かれる．
演習課題
問 3.1 n, k を 0 < k ≤ n となる整数とする．このとき以下の等式が成立することを数学的帰納法を用いて証明せよ．
n Ck= k−1 Ck−1 + k Ck−1 + · · · + n−1 Ck−1

25

問 3.2 x, y を実数とし，n を自然数とする．このとき以下の等式が成立することを数学的帰納法を用いて証明せよ．
nXn−i i(x + y)n =yn Ci xi=0NOTE: この等式は非常に有名な二項定理 (binomial theorem) と呼ばれる定理．パスカルが 1653 年に発表した確率論の文献に表れる．この文献は確率とか期待値とかの概念を導入した，ようは，確率論の分野を創始したとも言える重要な文献．なお，パスカルはこの研究を賭博師からの賭博に関する質問を受けて開始したそうな．
NOTE: 二項定理自体はもっと古くから知られていた．有名なところでは 10 世紀のアル=カラジ (ペルシア) とハラユーダ (インド) の成果が知られてるそうです．最も古い発見はさらに遡って紀元前 3 世紀のピンガラ（インド）によるものだそうです．なお，アル=カラジは二項定理 (他にも色々な定理) の証明も与えており，これらの証明は数学的帰納法を用いた最初の証明だそうな．
問 3.3 赤，青，黄，緑の 4 色で正四面体の 4 つの面を塗り分ける．回転して同じになる塗り方を同一と見做すと何通りの塗り方があるか．理由を含めて答えよ．

NOTE: パスツールによる『光学異性体』の大発見に繋がる問題．光学異性体と言えば，我らが名大の野依教授の (2001 年度) ノーベル化学賞受賞も記憶に新しい．
問 3.4 カタラン数の最初の 5 項 C0 , C1 , C2 , C3 , C4 を求めよ．
問 3.5 出場者数 4 人のトーナメント戦の構造は以下の 5 通りが考えられる．

ただし，いずれの場合も出場者は登録順に左から並んでいると考える．出場者数が n 人である場合のトーナメント戦の構造が Tn 通りであるとする．このとき以下の問いに答えよ．

(i) 総試合数は何試合になるか？
(ii) Tn の漸化式を与えよ．
(iii) n = 1, 2, 3, 4, 5 の場合の Tn を求め，一般項を予測せよ．
ヒント: Tn は今回の講義で与えたある数列と密接な関係にある．
(iv) (iii) で予測した Tn の一般項が，(ii) で与えた漸化式が与える Tn と一致することを数学的帰納法を用いて証明せよ．
問 3.6 2n 人から 1 人あたり 500 円ずつ集める事を考える．ここで，n 人は 500 円硬貨を1 つ，残り n 人は 1000 円札を 1 枚持ってるだけであるとする．集金の途中でお釣りが足りなくならないような集金の順番は何通りあるか理由を含めて答えよ．ただし，金額のみを考え，誰から集めたかは区別しないものとする．

26

問 3.7 スターリング数 S51 , S52 , S53 , S54 , S55 を求めよ．
問 3.8 『源氏香』とは江戸時代に成立した香道の優雅な遊び．源氏香では 5 種類の香木を 5 包ずつ合計 25 包を混ぜ合わせ，そこから無作為に抽出した 5 包を順に焚き，香席に5 回香炉が回される．その後，香席の客は下図のように，同じ香りと思うものの上の部分を横線で繋いで答える (正確には，図に対応する源氏物語の帖名で答える)．

例えば，一番左の図は，2 番目と 3 番目，4 番目と 5 番目がそれぞれ同じ香りである事を，真ん中の図は，2,4,5 番目が同じ香りである事を，一番右の図は，1,3,5 番目，2,4 番目がそれぞれ同じ香りである事を表している．さて，答のパターンが何通りあるか答えよ．

NOTE: なお，上問の解答を k 通りとおくと，源氏物語の帖数は k + 2 帖となる．よって，最初の帖の『桐壺』と最後の帖の『夢の浮橋』には図が与えられていない．ちなみに，上図は左から順に『若紫 (わかむらさき)』『澪標 (みおつくし)』『蜻蛉 (かげろう)』という名前が与えられている．関係ない話ではあるが，これらの３つの帖はかなりやばい話，特に『若紫』は何故発禁処分をくらわないかが不思議なくらいである…．

27