パスカルの三角形と
2項分布
–
確率論
I–参考資料
2009/01/08, 西岡
1 階乗と 2 項係数
まず
0!≡1, 1! = 1, 2! = 1×2 = 2, 3!≡1×2×3 = 6, 4!≡= 1×2×3×4 = 24, · · ·, k!≡1×2× · · ·(k−1)×k と記し,k!をkの階乗という. k!は驚くほど早く大きくなる.
次に,自然数 n, k にたいし,
(1) nCk≡ n!
k! (n−k)! = n(n−1)· · ·(n−k−1)
k(k−1)· · ·1 , k= 0,1,· · ·n とおき, 2項係数と呼ぶ. このnCk はn個のものからk個取り出す方法の数である.
2 パスカルの三角形
問題 1. 次の図形で,S7(0), S7(1),· · ·, S7(7)の各点から出発し, 最短路を通ってX へ到達する. それぞれ の最短路の個数を計算せよ.
X
S7(0) S7(1) S7(2) S7(3) S7(4) S7(5) S7(6) S7(7)
[解答] パスカルの3角形と呼ばれる次の図形から,最短路の個数が計算できる.
Step 1. なぜパスカルの図形から最短路の個数が計算出来るかを説明する.
(i) 下の図形で最短路の個数はそれぞれ1つ.
(ii) もう一段増やす. S2(1) から出発すると, 必ず S1(0) かS1(1)を通るので, それらの最短路の個数の 合計.
(iii) さらにもう一段増やす.
• S3(1)は必ず S2(0)かS2(1)を通る,
• S3(2)は必ず S2(1)かS2(2)を通る,
1
X
S7(0) S7(1) S7(2) S7(3) S7(4) S7(5) S7(6) S7(7) 1
1 1
1 1
1
1 1
1
1 1
1 1 1
2
3 3
4 6 4
5 10 10 5
6 15 20 15 6
7 21 35 35 21 7
X
S1(0) S1(1)
1 1
X
S1(0), 1 S1(1), 1
S2(0) S2(1) S2(2) 1 + 1 =2
1 1
X
S1(0), 1 S1(1), 1
S2(0), 1
S2(1), 2
S2(2), 1
S3(0) S3(1), 1+2 =3
S3(2), 2+1=3
S3(3)
1 1
を考えると,
これを繰り返すと,パスカルの三角形で最短路の個数が計算できる.
Step 2. 一方, 組み合わせの個数 nCk との関係を考える．例えば,S2(1)から出発したときの最短路の個
数は,
「右前に 2歩,左前に1 歩 動く」組み合わせの個数. つまり「3 つから1 つを選ぶ方法の個数」=3C1= 3となる.
7段下から出発する場合も同様で,
S7(k)から出発するときの最短路の個数=7Ck
となる.
(∗) パスカルの3角形の計算方法を思い出すと, 次の補題は自明.
2
補題2. 2項係数は次の性質を持つ.
nC0= 1 =nCn, (2)
nCk =nCn−k, (3)
nCk+nCk+1=n+1Ck+1. ⋄ (4)
練習問題 3. (i) 下図の格子上を通り, AからBに行く最短経路は何通り有るか.
!
"
#
$
(ii) 上図の格子上を通り, AからBに行く最短経路は何通り有るか. ただしCは必ず通るとする.
(iii) 上図の格子上を通り, AからBに行く最短経路は何通り有るか. ただしDは通らないものとする. ⋄
[解答] (i) A→B は,上に5 歩,右に4 歩. この組み合わせだから,9C4= 126.
(ii) A→C は上に1 歩,右に3歩. この組み合わせだから,4C3= 4. さらにC→B は,上に4歩, 右に 1歩. この組み合わせだから,5C1= 5. 両者を掛けて, 4·5 = 20.
(iii) A→D は, 上に3 歩,右に2 歩. この組み合わせだから,5C2= 10. さらにD →B は,上に2 歩, 右に2歩. この組み合わせだから,4C2= 6. つまり,A→D→B は, 10·6 = 60. これを,A→B の経路 数から引けばよいので, 126−60 = 66. 2
3 2項分布
定義4. 確率変数X(w)は
(5) X(w)はx1, x2,· · · , xn の値 をとるとする. (5)のX(w)にたいしxi の値をとる確率
P[X(w) =xi]≡f(xi)
をx=x1, x2,· · ·, xmの関数とみて,確率変数X(w)の確率分布 distribution とよぶ. ⋄ 定義5. 成功と失敗の２つの結果しかない試行をベルヌイ試行Bernoulli trialと呼ぶ.
ベルヌイ試行の代表例は
「コイントス: 表=成功, 裏=失敗」
だが,他の多くの確率現象もベルヌイ試行の組み合わせで表現できる. 問題6. 表がでる確率がpのコイン aがある.
(i) コインaを1回投げ,確率変数Z1 を Z1≡
{ 1 表がでたとき 0 裏が出たとき
3
とする. このときZ1の分布 P[Z1(w) =x] =f1(x)はx= 0,1 だけの関数で f1(0) = 1−p, f1(1) =p.
(ii) コインaを2回投げ,確率変数Z2 を
Z2≡2 回のコイン投げで, 表が出た回数 とする. このときZ2の分布 f2(x)はx= 0,1,2 の関数で
f2(k)≡P[Z2=k] =
(1−p)2 k= 0 2p(1−p) k= 1 p2 k= 2 (iii) コインaをn回投げ, 確率変数Zn を
(6) Zn ≡ |w|=n回コインを投げて表が出た回数 とおく. このときZn の分布fn(x)はx= 0,1,· · · , nの関数で
(7) fn(k)≡P[Zn=k] = nCk pk (1−p)n−k, k= 0,1,· · · , n.
ここで
nCk≡ n!
k! (n−k)!
は2項係数 (1)で, その右辺は2項分布binomial distributionと呼ばれ,応用上,特に重要である. [(7)の証明] Zn=kとなるには,
(8) 表がk 回,裏がn−k 回
出ればよい. (8)が起こる確率はpk (1−p)n−k.
また「一列に並んだn個のものからk個選ぶ方法」は,nCk 通り.
n回のコイントスの中で,k回表がで出ると考えて, (8) はnCk 通りの異なった方法で起こる. 2
注意7. 大きな n, kにたいし, (7)のϕn(k)の値を計算することは,決して易しくない. n!がとてつもなく
大きな数になるからである.
4
