組み合わせの数
順列
例題
A,B,C,D,E の 5 つの文字から 3 文字取って並べる並べ方は何通りあるか?
解法
- 1文字目は A,B,C,D,E のうちの1文字を選ぶので、 5 通り
- 2文字目は残りの 4 文字のうちから 1 文字を選ぶので 4 通り
- 3文字目は残りの 3 文字のうちから 1 文字を選ぶので 3 通り
従って、求める並べ方は全部で 5 × 4 × 3 = 60 通りある。
一般化
n 個のものから m 個を取り出して並べる時、並べ方の数
を nPm で表すとすると、これは次の式で得られる。
階乗
n の階乗を次で定義する。
すると、順列は次の様に階乗で定義できる。
なお、 0!=1 とする。
組み合わせの数
n 個のものから m 個のものを取る組み合わせを考える。
これは、順列から派生できる。
例題
A,B,C,D,E の 5 つの文字から 3 文字取る組み合わせの数は何通りあるか?
解法
- 1文字目は A,B,C,D,E のうちの1文字を選ぶので、 5 通り
- 2文字目は残りの 4 文字のうちから 1 文字を選ぶので 4 通り
- 3文字目は残りの 3 文字のうちから 1 文字を選ぶので 3 通り
従って、求める並べ方は全部で 5 × 4 × 3 = 60 通りある。
一方、並べたもののうち、同じ組み合わせがいくつあるか考える。
つまり、 A,B,C と A,C,B と B,A,C と B,C,A と C,A,B と C,B,A は同じ組み
合わせだと考える。
これは、取り出した 3 文字を並べる並べ方だけ同じ組み合わせがあると言う
ことである。
つまり、各組み合わせに対して 3! = 6 通りの重複があることになる。
したがって、求める組み合わせの数は 60 / 6 = 10 通りである。
一般化
n 個のものから m 個を取り出す組み合わせを
nCm で表すとすると、これは次の式で得られる。
公式
基本公式
漸化式
二項定理
特に、 a=1, b=1 と置くと、
Stirlingの公式