RECURSIONS （後半）
M1 鈴木洋介
Ex ５．８
n進数の正の整数があり、以下の条件を満たす。
・各桁の数は全て異なる。
・どの桁の数もその数より左にあるいずれかの数+1または-1となってい
る。（いちばん左の数字は除く）
このような数の個数anを求めよ。
例：n=4
123
1232
2310
2301
解法１
(n+1)進数の条件を満たす数の集合を２つのグループに分ける。
（カッコ内はn=3の例）
(1)どの桁にも数nが使われていないグループ。
⇒(1,2,10,12,21,102,120,210)・・・8個
⇒an 個
(2)いずれかの桁に数nが使われているグループ。
⇒(3,23,32,123,213,231,321,1023,1203, 2103, 1230,2130,2310,3210)・・・14個
⇒そのようなk桁の数はn,n-1,…,n-k+1の並べ替えでなければならない。
⇒そのような数は2n+1-2個。（計算は省略）
an+1=an+2n+1-2
a1=0
これを解いて
an+1=a0+(2n+1+2n+…+22)-2n
=2n+2-4-2n
an=2n+1-2n-2
解法２
F(n)を、０で始まるものも許した条件を満たすn進数の個数とする。
F(1)=1 (0)
F(2)=4 (0,1,01,10)
F(3)=11 (0,1,2,01,10,12,21,012,102,120,210)
・・・
(n+1)進数の題意を満たす数の集合を３グループに分ける。
（カッコ内はn=2の例）
(a)１桁の数0,1,2,…,n・・・n+1個
(0,1,2)
(b)題意を満たすn進数の最後尾に、
各桁の最大値+1の桁を追加したもの・・・F(n)個
(0,1,01,10)→(01,12,012,102)
(c)題意を満たすn進数の各桁の数を1増やしたものの最後尾に、
各桁の最小値-1の桁を追加したもの・・・F(n)個
(0,1,01,10) →(1,2,12,21)→(10,21,120,210)
以上よりF(n+1)=n+1+2F(n)。
F(n+1)=n+1+2F(n)
F(n+1)+a(n+1)+b=2(F(n)+an+b)とおくとa=1,b=2となる。
F(1)+1・1+2=1+1+2=4より、
F(n)+n+2=2n+1 ,F(n)= 2n+1 -n-2。
最後に、0で始まる不適切なn進数は
0,01,012,…,0123・・・(n-1)とn個存在するので差し引いて
an= F(n)= 2n+1 -2n-2。
Ex ５．９
長さが24の円周を、点P1～P24によって24等分する。
これらの点のうち相異なる8個を選んだとき、どの2点で表される孤の長さ
も3か8でないような選び方はいくつあるか。
P1
P2
P3
P4
P5
P6
P9
P8
P7
Ex ５．９
長さが24の円周を、点P1～P24によって24等分する。
これらの点のうち相異なる8個を選んだとき、どの2点で表される孤の長さ
も3か8でないような選び方はいくつあるか。
P1 P4 P7 P10 P13 P16 P19 P22
P9 P12 P15 P18 P21 P24 P3 P6
P17 P20 P23 P2 P5 P8 P11 P14
上のように頂点を並べて考える
・各列からは１つしか頂点を選べない
・i行目と(i+1)行目の頂点は違う色でなければならない
Ex ５．９‘
n本の半径でn分割された円盤をk色で彩色する場合の数pn,kを求めよ。
p8,3は？(n,k≧3)
k-1
順番に彩色するならば
最初の面をk色、
その隣をk-1色、
そのまた隣をk-1色・・・
と塗ればよい
k
k-1
最後と最初の色が
一致する場合がある！
k-1
・・・
最初の面と最後の面を
ひとまとめにすると、
一致する場合の数は
pn-1,kとなることがわかる。
Ex ５．９‘
n本の半径でn分割された円盤をk色で彩色する場合の数pn,kを求めよ。
p8,3は？ (n,k≧3)
k-1
pn,k=k(k-1)n-1-pn-1,k
p3,k=k(k-1)(k-2)
k
k-1
k-1
これを計算して
pn,k=k(k-1)n-1-k(k-1)n-2+k(k-1)n-3-・・・
+(-1)n-4k(k-1)3+(-1)n-3k(k-1)(k-2)
・・・
(k-1)n+(-1)n-4(k-1)3
=k
1+(k-1)
+(-1)n-3k(k-1)(k-2)
=(k-1)n+(-1)n(k-1)
p8,3=28+2=258
Ex ５．１０
n桁の自然数がある。このうち任意の長さの同じ数字の並びが連続して
現れないような自然数の数f(n)は8nより多いことを証明せよ。
例
１２３４２３４５
１２３３４５
１２３４５２３４
方針：
f(n)≧8f(n-1)を帰納法で証明する。
f(1)=9>8より、 f(n)≧8n-1f(1) >8nが言える。
f(1)=9,f(2)=81。
f(n)≧8f(n-1) (n=2,3,…,k-1)を仮定する。
k-1桁の条件を満たす数の末尾にもう１桁追加したとき、
その数の末尾にr桁の繰り返しが２回出現する場合は
b1 b2 … bk-2r a1 a2 … ar a1 a2 … ar -1 ar
•
•
•
(k-r)桁の条件を満たす数と上記のような数は一対一
対応する。
よって上記のような自然数の数はf(k-r)。
rのとりうる値は1,2,…, k/2 。
f(k)=10f(k-1) – {f(k-1)+f(k-2)+f(k-3)+ ・・・ + f(k- k/2 )}
f(n)≧8f(n-1)をn=2,3,…k-1で仮定したのを利用して、
f(k)= 10f(k-1) – {
≧ 10f(k-1) – {
= 10f(k-1) – {
≧ 10f(k-1) – {
≧ 10f(k-1) – {
＞ 10f(k-1) –
= 8f(k-1)
f(k-1) + f(k-2) + f(k-3)
+ ・・・ + f(k- k/2 ) }
f(k-1) + f(k-2) + f(k-3)
+ ・・・ + f(k-(k-1)) }
f(k-1) + f(k-2) + f(k-3)
+ ・・・ + f(1)
}
f(k-1) + f(k-1)/8 + f(k- 1)/82 + ・・・
}
f(k-1) + f(k-1)/2 + f(k- 1)/22 + ・・・
}
2f(k-1)
Ex ５．１１
自然数の数列{a1,…an}があり、a1=1、すべてのi=1,…n-1において、
ai+1≦ai+1となる。このような全ての数列のパターンに対して、その積の和
∑(a1,…an)はいくらになるか。
１
１
１
１
２
２
１ ２ ３
２
１
１
２
３
２ １ ２ ３ １ ２ ３
a1=mとした場合の∑(a1,…an)をf(m,n)とする。
f(1,1)=1
f(1,2)=1・1+1・2=3
f(1,3)=1・1・1+1・1・2+1・2・1+1・2・2+1・2・3=15
f(1,4)=1・1・1・1+1・1・1・2+1・1・2・1+・・・
４
m
1
2
m+1
・・・
n-1
f(m,n)=m( f(1,n-1) + f(2,n-1) + ・・・ + f(m+1,n-1) )
また、f(m,1)=m
と表すことにする。( 5!!=5・3・1=15 )
であることを示す。
上式がn=1,2,…,kで成立すると仮定すると
・・・
Ex ５．１２
n×nマスの盤面に、互いにとりあわないようにルーク（飛車）をn個配置す
る。さらに、盤面の左上と右下を通り、盤のマス目に沿った長さ2nのパス
を描く。このとき、ルークが二分された盤面の片方のみに配置される。
このような条件を満たすルークの配置とパスの描き方は何通りか。
対称性より、ルークは全て
左下の側の面に配置されるとする。
この場合のルークとパスの組み合わせの
集合をSnとすると、
求める場合の数は2|Sn|。
各盤面の状態は2×nの行列で表すことができる。
一対一対応
[
[
１行目：各列における赤い横線の高さ
２行目：各列におけるルークの位置
（上から５，４，３，２，１で表す）
この行列の性質：
(1)n=a1≧a2≧a3 ≧ … ≧ an ≧1
(2)任意のi=1,2,..,nに対してai ≧ bi
(3) b1 b2 b3…bn は1からnまでの数の並べ替え
]
a1 a2 a3…an
b1 b2 b3…bn
55444
25413
]
次のような盤面のサイズをnからn-1にするような変換を考える。
[
55444
25413
]
全要素-1
[
4433
1423
これが(2n-1)対1の変換であることを示す。
]
逆写像を考える。
1
0
[
2
n-2 n-1
] [
c1 c2 c3…cn-1
d1 d2 d3…dn-1
]
c1+1 c2+1 …ck+1 c ck+1+1…cn-1+1
d1+1 d2+1 …dk+1 1 dk+1+1…dn-1+1
kの選び方：0,1,2,…,n-1のn通り
kに対して、cのとりうる値：
k=0のとき、n
k=1,2,…n-2のとき、 ck+1+1 , ck+1,…,ck+1
k=n-1のとき、1,2,…,cn-1
これらをまとめると、kに対してcの値は(ck-ck+1+1)通り
（c0=c1=n,cn=1とする）
|Sn|=(2n-1)|Sn-1|
|S1|=1
|Sn|=(2n-1)!!
よって答えは2(2n-1)!!
Ex ５．１３
u=[1,1]、v=[1,-1]とする。
u,vそれぞれn個ずつを組み合わせて(0,0)から(2n,0)までのパスを作りた
い。ただし、パスはx軸を横切ってはならない。
このようなパスAnは何通りできるか。（Cataran Path）
0
2r
1
2r-1
(2r,0)は(0,0)以外でx軸と接する
最も左の点。
2n
0
2r
|Ar-1|
1
2n
|An-r|
2r-1
図より、あるrに対して
パスの本数は|Ar-1|・|An-r|
よってr=1,2,…nについての和をとると
|An|=|A0||An-1|+|A1||An-2|+・・・+|An-1|・|A0|
また、|A0|=1
これを解いて
（この証明はのちの輪講で）
Ex ５．１４
u=[1,1]、v=[1,-1]とする。
u,vそれぞれ2n個ずつを組み合わせて(0,0)から(4n,0)までのパスを作り
たい。ただし、パスは(2,0),(6,0)・・・(4n-2,0)を通ってはならない。
このようなパスは何通りできるか。
解法１：Ex ５．１３を利用して再帰
0
4n
4r
1
4r-1
(4r,0)は(0,0)以外でx軸と接する
最も左の点。
|Ar-1|
0
4n
4r
1
|Ar-1|
4r-1
(4r,0)は(0,0)以外でx軸と接する
最も左の点。
|Z2n-2r|
Z2nを条件を満たすパスの集合と
する。
図より、あるrに対して
パスの本数は2|A2r-1|・|Z2n-2r|
よって
r=1,2,…nに対して和をとると
|Z2n|=2|A1|・|Z2n-2|+
2|A3|・|Z2n-4|+
・・・
2|A2n-1|・|Z0|
|Z2n|=|A2n|を帰納法によって示す。
|Z2n|=2|A1|・|Z2n-2|+2|A3|・|Z2n-4|+・・・2|A2n-1|・|Z0|
|A0|=|Z0|=1とする。
|A2|=|Z2|=2。
|Z2n|=|A2n|がn=0,1,2,…k-1で成立すると仮定すると
|Z2k|=2|A1|・|Z2k-2|+2|A3|・|Z2k-4|+・・・+2|A2k-1|・|Z0|
=2|A1|・|A2k-2|+2|A3|・|A2k-4|+・・・+2|A2k-1|・|A0|
=|A0|・|A2k-1|+|A1|・|A2k-2|+・・・+|A2k-2|・|A1|+|A2k-1|・|A0|
|Z2n|=|A2n|を帰納法によって示す。
|Z2n|=2|A1|・|Z2n-2|+2|A3|・|Z2n-4|+・・・2|A2n-1|・|Z0|
|A0|=|Z0|=1とする。
|A2|=|Z2|=2。
|Z2n|=|A2n|がn=0,1,2,…k-1で成立すると仮定すると
|Z2k|=2|A1|・|Z2k-2|+2|A3|・|Z2k-4|+・・・+2|A2k-1|・|Z0|
=2|A1|・|A2k-2|+2|A3|・|A2k-4|+・・・+2|A2k-1|・|A0|
=|A0|・|A2k-1|+|A1|・|A2k-2|+・・・+|A2k-2|・|A1|+|A2k-1|・|A0|
|An|=|A1|・|An-1|+|A2|・|An-2|+・・・|An-1|・|A0|
を利用して
|Z2k|=|A2k|。
以上より|Z2n|=|A2n|。
解法２：Z2n、A2n間の一対一対応する変換を示す
１．x軸を横切る点でパスを分割する。
各パスはx軸上での距離が4の倍数となる。
２．x軸より正の部分は、そのまま。
３．x軸より負の部分をx軸について対称移動させた後、
(4k-2,0)のいずれかの点を通るようなパスへ変換を行う。
０．両端のu,vを切り取る。
１．最も右側にある4の倍数の交点を4rとする。
２．4rより右のパス、u、4rより左のパス、vの順番でパスをつなげる。
0
0
18
8
x軸と(4k-2,0)のみで接する 10
x軸との交点はない
逆写像が定義できることから、これは全単射である
20
© Copyright 2024 ExpyDoc
