場合の数
数え上げの基本
ものの数を正しく数えるには「数えもらしをしない」「同じものを繰り返して数えない」ことが大切である。数える個数が少ないときには、適当に数えても間違いは出にくいが、数える個数が多いときには、何らかの方針をもって数え上げないとミスを犯しやすくなる。ここでは、数を数え上げるときに、私達が普段何気なく使っている基本的な方法について確認していこう。
整理して考えるということ
表でまとめる
樹形図でまとめる
積の法則・和の法則
物を数えるときに使う考え方
積の法則
和の法則
集合の要素の個数と場合の数
“場合”を集合の要素に対応させる
積の法則・和の法則（集合版）
補集合での考え方
ド・モルガンの法則
包含と排除の原理
順列
この『順列』から『資源配分(配分先に区分がない)』までの8つのセクションでは、数え上げに関する応用的な手法をみていく。各セクションは、「ボールと箱のモデル」で体系的にまとめることができる。縦の欄にはボールと箱の区別の有無を、横の欄にはボールを箱にしまう際に、それが『写像』でいうところの何と対応するのかを示している。
| ボール・箱 | 単射 | 写像全て | 全射 | |
| あり・あり | 順列 | 重複順列 | 部屋割り | |
| なし・あり | 組合せ | 重複組合せ | 資源配分 | |
| あり・なし | （右枠の和） | 部屋割り（区別なし） | ||
| なし・なし | （右枠の和） | 資源配分（区別なし） |
順列について
順列$_{n}\text{P}_{r}$の定義
順列$_{n}\text{P}_{r}$の計算
ボールと箱のモデル1
円順列
円順列$cir(n)$の定義
円順列$cir(n)$の計算
ネックレス順列$neck(n)$の定義・計算
重複順列
カード引きでは、1回目に引く場合と2回目に引く場合では状況が異なるが、さいころ投げでは1回目に出る目と2回目に出る目に全体として変化が無い。さいころ投げで順序を考慮する場合には、下でみるように重複順列を考えることになる。
| ボール・箱 | 単射 | 写像全て | 全射 | |
| あり・あり | 順列 | 重複順列 | 部屋割り | |
| なし・あり | 組合せ | 重複組合せ | 資源配分 | |
| あり・なし | （右枠の和） | 部屋割り（区別なし） | ||
| なし・なし | （右枠の和） | 資源配分（区別なし） |
重複順列について
重複順列$_{n}\Pi_{r}$の定義
重複順列$_{n}\Pi_{r}$の計算
ボールと箱のモデル2
部屋割り
例えば，5人の人が鶴の間，亀の間，松の間の3つの部屋に泊まる場合， 部屋を割り当てる方法（空部屋はでないようにする）には何通りの方法があるだろうか． このような問題は，人を「区別するボール」，部屋を「区別する箱」として，ボールと箱のモデルで考えることができる．
| ボール・箱 | 単射 | 写像全て | 全射 | |
| あり・あり | 順列 | 重複順列 | 部屋割り | |
| なし・あり | 組合せ | 重複組合せ | 資源配分 | |
| あり・なし | （右枠の和） | 部屋割り（区別なし） | ||
| なし・なし | （右枠の和） | 資源配分（区別なし） |
部屋割りの数
ボールと箱のモデル3
★包含と排除の原理の一般形
包含と排除の原理（一般の場合）
部屋割りの数$room(m,r)$の計算
撹乱順列
組合せ
順列では、ものを取り出したときの順番の違いを考えに入れていたが、順番は区別せず取り出したものの区別だけを考えたいことがあり、これを組合せという。順列と同じように、組合せも数が多くなると樹形図を書くのが大変になる。ここでは、組合せの数を計算で求める方法について考えよう。
| ボール・箱 | 単射 | 写像全て | 全射 | |
| あり・あり | 順列 | 重複順列 | 部屋割り | |
| なし・あり | 組合せ | 重複組合せ | 資源配分 | |
| あり・なし | （右枠の和） | 部屋割り（区別なし） | ||
| なし・なし | （右枠の和） | 資源配分（区別なし） |
組合せについて
組合せ$_{n}\text{C}_{r}$の定義
組合せ$_{n}\text{C}_{r}$の計算
ボールと箱のモデル4
同じものを含む順列
同じものを含む順列$\text{C}(n_1,n_2,\cdots,n_m)$の定義
同じものを含む順列$\text{C}(n_1,n_2,\cdots,n_m)$の計算
$_{n}\text{C}_{r}$の性質
$_{n}\text{C}_{r}$の性質
2項定理
$(a+b)^n$を展開するということ
$a^4b$の係数はいくつになるのか
$a^3b^2$の係数はいくつになるのか
$(a+b)^5$の展開式
$(a+b)^n$の展開式(2項定理)
パスカルの三角形
重複組合せ
順列で順序を考慮しなければ組合せなるように、重複順列で順序を考慮しなければ重複組合せになる。ここでは、この重複組合せの計算についてみていこう。
| ボール・箱 | 単射 | 写像全て | 全射 | |
| あり・あり | 順列 | 重複順列 | 部屋割り | |
| なし・あり | 組合せ | 重複組合せ | 資源配分 | |
| あり・なし | （右枠の和） | 部屋割り（区別なし） | ||
| なし・なし | （右枠の和） | 資源配分（区別なし） |
重複組合せについて
重複組合せ$_nH_r$の定義
重複組合せ$_nH_r$の計算
ボールと箱のモデル5
資源配分
5本の鉛筆(区別しない)を3人の人に配る場合(鉛筆をもらわない人はいないとする)、配り方には何通りの方法があるだろうか。このような問題は、鉛筆を区別しないボール、人を区別する箱として、ボールと箱のモデルで考えることができる。
| ボール・箱 | 単射 | 写像全て | 全射 | |
| あり・あり | 順列 | 重複順列 | 部屋割り | |
| なし・あり | 組合せ | 重複組合せ | 資源配分 | |
| あり・なし | （右枠の和） | 部屋割り（区別なし） | ||
| なし・なし | （右枠の和） | 資源配分（区別なし） |
資源配分の数
ボールと箱のモデル6
資源配分の数$resource(n,r)$の計算
部屋割り（部屋に区別が無い場合）
部屋割りでは、ボールと箱のモデルで「区別するn個のボールを、区別するr個の箱に最低1個は配る場合の数」を扱った。『部屋割り』の問題において、部屋の作りが同じなどという理由で、部屋を区別する必要がない場合も考えられる。ここでは、部屋を区別しない場合の部屋割り、すなわち箱を区別しない場合のボールの配分について考えてみよう。
| ボール・箱 | 単射 | 写像全て | 全射 | |
| あり・あり | 順列 | 重複順列 | 部屋割り | |
| なし・あり | 組合せ | 重複組合せ | 資源配分 | |
| あり・なし | （右枠の和） | 部屋割り（区別なし） | ||
| なし・なし | （右枠の和） | 資源配分（区別なし） |
部屋割り（部屋に区別が無い場合）の数
ボールと箱のモデル7
★$_nS_r$の計算
第2種スターリング数の性質
部屋割り(部屋に区別が無い場合)の和
資源配分（配分先に区別が無い場合）
資源配分では、ボールと箱のモデルで「区別しないn個のボールを、区別するr個の箱に最低1個は配る場合の数」を扱った。『資源配分』の問題において、同じ種類の袋に配分するなどの理由で、配分先を区別する必要がない場合も考えられる。ここでは、配分先を区別しない場合の資源配分、すなわち箱を区別しない場合のボールの配分について考えてみよう。
| ボール・箱 | 単射 | 写像全て | 全射 | |
| あり・あり | 順列 | 重複順列 | 部屋割り | |
| なし・あり | 組合せ | 重複組合せ | 資源配分 | |
| あり・なし | （右枠の和） | 部屋割り（区別なし） | ||
| なし・なし | （右枠の和） | 資源配分（区別なし） |