counting_chap3_1

３．Properties of Binomial
Coefficients(前半)
笹沼亮介
Ex3.1
互いに異なる40個の実数の列がある。
この列に”bubble pass”を１回適用した時に
もとの20番目の数字が30番目に来ている確率を求めよ。
, r2 , r3 , r4 , , rn
列： r1　“babble pass”:
問題では n = 40
riと ri 1を比較して、 ri  ri 1ならば交換する
これを i  1から i  n  1まで行う
１
９
８
７


・”babble pass”１回の適用で(部分)列の
最大の数が(部分)列の右端に移動する。
・ r20が r30に移動するには、元の列の部分列
{r1 , r2 , r30}の中で r20が最大、かつ r20  r31
・ r20より大きい数字が少なくとも１個
・ r20より小さい数字が少な
・もとの列を降順に並
くとも２９個
び換えた列を
a1 , a2 ,, a40 とする
９
８
７
１
ak  r20とおくと　2  k  11
また、 a1  r31  ak 1
・ r31の候補は (k  1)個　
(
k 1
通り
1
)
・ r31の候補の残りは r31以降に並べる


9 ( k 2)
通り
・ a1から ak 以外の(40  k )個をランダムに
 (40  k！通り
)

あるｋについて
(

k 1
1
)
 9 ( k  2 )  (40  k！
) 通り
全てのｋについて足す
( )
11
k 1
1

 9 ( k  2 )  (40  k！
) 通り
k 2
 →条件を満たす全ての場合の数


列の全ての場合の数は→ ４０！通り
求める確率は
11
1

40! k  2
(
k 1

)
9 ( k  2 )  (40  k！
1
)

もっと簡単な方法は？

・最初の３１個の数字のみを考える。
・全ての並び方は３１！通り
・ r31を最大に、 r20を二番目に固定すると

→２９！通り


29!
31!

・求める確率は

・ r31以降は考えなくてよい
11
1

40! k  2
(
k 1
1
)  9 (k 2)

29!
 (40  k！
) 
31!
二項係数（binomial coefficient）
( x  y ) を展開
n
( x  y ) n  a0 x n  a1 x n 1 y    an 1 xyn 1  an y n
ak
(0  k  n) を二項係数という
Ex3.2
１秒に１回駒を右か上に動かす。
５秒後に駒はどこにあるか？その確率は？
最初の位置は（０，０）とする。

到達点は(5,0),(4,1),(3,2),(2,3),(1,4),(0,5)
・ ( m,n ) : (m  n)秒後に
(m, n)に到達する場合の数
( m , n )  ( m 1, n )  ( m , n 1)

それぞれの場合の数を
求める。
１
１
５
１
４
10
１
３
６
10
( 2,3)  10
１
２
３
４
５
(1, 4 )  5
１
１
１
１
１
( 5, 0 )  1
( 4,1)  5
(3, 2 )  10
( 0,5)  1 合計は32通り
１

確率は
1
(5,0) 
32
10
5
( 2,3) 

32 16
5
( 4,1) 
32
5
(1,4) 
32
10
5
(3,2) 

32 16
1
(0,5) 
32
パスカルの三角形
１
１
１
１
１

N行目が、
２
３
４
１
５
(r  u )
N
１
１
６
10
１
３
４
10
１
５
を展開した時の係数
１
(r  u )5  (r  u )( r  u )( r  u )( r  u )( r  u )
rかuのどちらかを選ぶ、を５回繰り返す→ 2 通り
r 3u 2 の係数は、５回のうち３回r、２回uを選ぶ
5
→
通り
5
(2 )
このようにして次の定理３．１が求められる。
定理３．１
( x  y) 
n
n
0
()
n
n n1
n
x 
y
x y 
n
1
n
()
( )
（nは正の整数）
係数はパスカルの三角形の行と対応
Ex3.3
格子点上で駒を上下左右に動かす。開始時は(0,0)
６ステップ以下で(2,2)に到達する確率は？
上下左右への移動をそれぞれ
U,D,L,Rとする。
（１ステップでは距離１の移動）
(2,2)に到達するには、最低で
４ステップ必要。
2
0
0
2

・４ステップで(2,2)へ到達する場合

4
R,R,U,Uを並べる→
2, 2


 
4
4!

6
2! 2!
通り
4
４つの全ての並べ方は、
通り
よって、４ステップの場合の確率は
6
4
4






・５（奇数）ステップで(2,2)に到達することはない。
奇数ステップでは、(偶数,奇数)または(奇数,偶数)にしか
行けない
(2,2)が(偶数,偶数)の点のため、５ステップでは到達しな
い。
・６ステップで到達する場合を考える。
R,R,U,U,D,UかR,R,U,U,L,Rを並べる。
→
2
   120通り
6
3, 2,1







・Rが２個とUが２個が最初に現れたら
４ステップの場合になる。
そのため、６つをランダムに並べた場合から、４ステップ
で到達する場合を引く必要がある。
４ステップで到達した後、UD・DU・LR・RLのどれかが入
る
よって、 120  6  4  96通り
６つの全ての並べ方は、 4 6 通り
６ステップで(2,2)に到達する確率は→
96
6
4

６ステップ以下で(2,2)に到達する確率は
6
96
3
 6 
4
4
4
64
Ex3.4
0から9までの数字を８つ使うプレートを作る。
（重複を許す。）
0が偶数個含まれるプレートはいくつあるか？



0の個数をkとすると、 k  0, 2,4,6,8
0以外の数字の数は(8-k)個
0の位置を決める
→ 8
通り

k

0以外の数字を選ぶ

よって、あるkに対して →
３
７
→
０
9
8  k 通り
 9
8
k
３
8  k 通り
０
２
４
９

それぞれのｋに関して足すと
 9
8
0


8
 9
8
2
6

 9
8
4
4
 9

8
6
2

 9
8
8
0
定理３．１を利用して計算する。
      
 9   9   9   9   9   9   9   9  1
(9  1)  9  9  9  9  9  9  9  9  1
8
(9  1)


8
8
8
1
7
8
2
6
8
3
5
8
4
4
8
5
3
8
6
2
8
7
8
8
1
7
8
2
6
8
3
5
8
4
4
8
5
3
8
6
2
8
7
この２つを足して２で割ればよい
よって
(9  1)8  (9  1)8
108  88

2
2
定理３．２



n,k : n≧k を満たす正の整数
n
(a) n
k
nk
   
n個からk個選ぶこと＝
n個から選ばないものをn-k個選ぶこと
      

(b)

・パスカルの三角形から明らか
別の考え方
n個のうち、1つだけ特別なもの(FAT)を作る
k+1個の選び方を、二つのグループに分ける
(A)FATを含むもの (B)FATを含まないもの





(A)→
n
k 1
 
n 1
k
n 1
k 1
(B)→
n 1
k
 
n 1
k 1
この二つを足す

(c)
        (
n
0
n
1
n
2

 n  1 n
nが偶数の時、 


 2  2

nが奇数の時、 n  1   n  1


 2 
n
 n 1 
 2 


n
)  ( n  )
2
 
2
 n  1
0k 
から k  1  n  k  1

 2 
   (k  1)!(n  k  1)!  k  1  1
 
k!( n  k )!
nk
n
k
n
k 1
k    n
n
k
n 1
k 1

(d)

(e)

式変形だけなので省略・・・
k

   (n  k  1) 
n
k
n
k 1
          
n 1
1
n 2
2

(f)

(b)を何度も適用する。

(g)

(f)に(a)を適用する。
n
0

n
k 1
n k
k
 
n 1
k
 
        
n
n
n 1
n
nk
n
n  k 1
k

n 1
k 1
n  k 1
n 1



(h)
         2
n
0
(1  1)
n
1
n
n
n
n
を展開

または集合S={1,2,・・・,n}の部分集合(要素数k)の数

(i)

        (1)    0
n
0
n
1
(1  1)
n
n
2
を展開
n n
n
   2   3     n   n2
n
1
n
2
n
3

(j)

(d)と(h)を適用する。
k
   n
n
k
n 1
k 1
n
n

         2
n
0
n 1
n
1
n
n
n
 k    n    n    n 2
n
k 1
n
n
k
k 1
n 1
k 1
n 1
k 0
n 1
k
n 1

(k)
1  k  n  1かつnが素数 
 はnで割り切れる
n
k
n( n  1)!
＝整数
( n  k )! k!

nが素数ならば、
( n  1)!
＝整数
( n  k )! k!
(a )  nk    nn k 
(c )
        (
n
0
(d ) k
(f)
(b)
n
1
n
2
   n
n
k
n 1
k 1
    
n 1
1
n
0

      
n
 n 1 
 2 


n 2
2
2
 
  
(h)
         2
n
0
n
(e ) k  nk   ( n  k  1) k n1 
  
n 1
n
n 1
k
)  ( n  )
(g )
n
n
n 1
k 1
n
k 1
  
n
1
nk
n
n
n
n k
k
 
 
n  k 1
k
n  k 1
n 1

n
(i )
           (1)    0
( j)
   2   3     n   n 2
(k)
n
0
n
1

n
k
n
1
n
2
n
2

n n
n
n
3
n
n
はnで割り切れる（ただし、nは素数かつ1≦k≦n-1）
n 1
 
n
k
の拡張
n, k : 0  k  nを満たす整数
n, k : 整数（ n  0)
→
  0
0
0
に拡張
，kが負、またはk>nの時
  0
n
k
この拡張後も、定理3.1,定理3.2は成り立つ。
Ex3.5
円周上に並んだ10個の点を結んで、いくつの凸多角
形が作れるか？
異なる点を用いた場合、形が同じでも区別する。


点をk個選ぶとする。
多角形を作るには
3  k  10


k角形は 10 通り
k
  通り
10

全部で
k 3
10
k
      
10
3

10
4
10
10
            
10
0
10
1
10
10
10
0
10
1
(hを適用)
2
10
 (1  10  45)  968
10
2
Ex3.6
以下の式(A)を計算せよ。
          
11
0
11
1
11
2
11
11
1
2
3
12
(d)を変形すると
1
k 1
   
11
k
12
k 1
k 1
12
 
n 1
k
1

n
 ( A)
 
n
k 1
(0  k  11)
11
1

12 k 0
 
12
k 1
1  12
 
12  k 0




   
12
k
12
0

1 12

2 1
12
(h)を適用
Ex3.7
以下の式(B)を証明せよ。nは正の整数とする。
(1)

k
k 1
n
k 1

n
k
(1)
Sn  
k
k 1
n
1
1
 1 
2
n
k 1

n
k
とする
 ( B)
(1) k 1

k
k 1
n
Sn
 
n
k
k 1
(1)

k
k 1
k 1
n 1
(1)

k
k 1
n 1
S n 1

(b)
(d)
    
n
k
k 1
(1)
 Sn  
n 1
k 1
n 1

 
n 1
k
n
k 1
 
n 1
k
(1) k 1

k
k 1
n
Sn
S n 1

 
n
k
1 n 1
k
 Sn 
( 1)

n  1 k 1

n 1
k

mを１以上の整数とすると
S m 1  S m
1 m 1
k m 1

( 1)  k 

m  1 k 1
1
1
k m 1


(1)  k 

m  1 m  1 k 0
m 1
(1) k 1

k
k 1
n
Sn
 
n
k
 (1)    0
m 1

(i)から
k
k 0

よって
m 1
k
1
S m 1  S m 
m 1

m=1からm=n-1までについて足す
S 2  S1
S3  S 2
1

11
1

2 1

S n  S n 1
1

n
(1) k 1

k
k 1
n
Sn
S n  S1
 
n
k
1
1
1
1




2
3
4
n
S1  1なので式 ( B)は成り立つ。
ところで、Ex3.1の式は
11
1

40! k  2

(
k 1
1
)  9 (k 2)

29!
 (40  k！
) 
31!
定理３．２を駆使することで（左辺）＝（右辺）が確かめら
れます。

Download Report