順列、組み合わせ

• 順列

6文字A B C D E F Gを並べる。
6個の箱があると考える。
1つ目の箱に入れる事が出来る文字は6個
2つ目の箱に入れる事が出来る文字は1個は使ったので5個
....
6つ目の箱に入れる事が出来る文字は5個は使ったので1個
これを計算すると
6×5×4×3×2×1=720通り
これが階乗
n!

箱が3つの場合
6×5×4=120通り
異なるn個のものからr個のものを取り出して並べる順列の総数を
nPr=n(n-1)(n-2)(n-3).....(n-r+1)
6P3=6(6-1)(6-2)=120
これは
nPr=n!/(n-r)!
6P3=6!/3!
と置き換えれる

• 組み合わせ

6文字A B C D E F Gから3を取り出す
6P3=120
から
ABC,ACB,BAC,BCA,CAB,CBAは同じなので
これを除く
これは3文字の並べ方なので3!
nCr=nPr/r!
6C3=6P3/3!

• 同じものを含む順列

AAABBBBの7文字の順列
7つの箱のまず3つの箱にAを入れる残りにBを入れる。
7つの箱から3つの箱を選ぶ組み合わせになる。
7C3=7P3/3!=7*6*5/3*2*1=35
これを応用した有名な問題が最短距離何通り問題
A
┌┬┬┬┐
├┼┼┼┤
└┴┴┴┘
　　　　　B
AからBへ行く最短距離は何通りか
→→→→↓↓↓の順列を考える
7C3=35通り