counting_chap5_1

5
Recursions
朴大地
5. Recursions
• Recursion
– 訳：再帰、帰納
– 意味：あるものを記述する際に、それ自体が記
述中にあらわれること
• テクニック
– Fn という数を数えよう
Fn = ( Fn¡ 1; Fn¡ 2; ¢¢¢ の表式 )
–
Example 5.1. 球と大円
• 大円(great circle)とは
– その面が球の中心を通るような円
– （e.g. 経線、赤道）
• 球の表面に大円を描いていく
– 重ねてはいけない
– それで分断される領域の数
– いくつか？
EX5.1 球に大円を5つ描く。できる領域の数の
最大値 M 5 , 最小値 m5 はいくつか?
• 今, k ¡ 1 個の円があるとして
k 個目の円 Ck を描くと?
– 1. 領域の数の増加
= ( Ck の交点の数 )
c.f. 平面グラフのオイラーの公式
– 2. 交点の数は?
– 2つの大円は必ず2つの点で交わっているはず
2 ～ 2(k ¡ 1) 個
EX5.1 球に大円を5つ描く。できる領域の数の
最大値 M 5 , 最小値 m5 はいくつか?
• 最小の場合
– 交点が一致するように描く
– mk = mk¡ 1 + 2
= mk¡ 2 + 2 + 2
..
.
= m1 + 2(k ¡ 1)
– また m1 = 2 より、 m5 = 10
EX5.1 球に大円を5つ描く。できる領域の数の
最大値 M 5 , 最小値 m5 はいくつか?
• 最大の場合
– 交点をずらすように描く
– M k = M k¡ 1 + 2(k ¡ 1)
..
.
= M 1 + k(k ¡ 1)
– また M 1 = 2 より、 M 5 = 22
Example 5.2. fat集合
[ MOSP 1999, by Cecil Rousseau]
• fat集合とは以下の条件を満たす整数集合
– 「集合内のどの要素も集合のサイズ以上」
• 例
–○
f 7; 10; 13g f 2; 3g
f 1g
; = fg
– × f 1; 2; 3g f 3; 5; 7; 10g
EX5.2 整数集合 f 1; 2; ¢¢¢; ng の部分集合で
どの数字も2以上離れているfat集合の数 an 、
どの数字も3以上離れている集合の数 bn とする
このとき、 an = bn を証明せよ
• 例 a7 = b7 = 19
; ; f 1g; f 2g; f 3g;
; ; f 1g; f 2g; f 3g;
f 4g; f 5g; f 6g; f 7g
f 4g; f 5g; f 6g; f 7g
f 2; 4g; f 2; 5g; f 2; 6g;
f 1; 4g; f 1; 5g; f 1; 6g;
f 2; 7g; f 3; 5g; f 3; 6g;
f 1; 7g; f 2; 5g; f 2; 6g;
f 3; 7g; f 4; 6g; f 4; 7g;
f 2; 7g; f 3; 6g; f 3; 7g;
f 5; 7g; f 3; 5; 7g
f 4; 7g; f 1; 4; 7g
EX5.2 整数集合 f 1; 2; ¢¢¢; ng の部分集合で
どの数字も2以上離れているfat集合の数 an 、
どの数字も3以上離れている集合の数 bn とする
このとき、 an = bn を証明せよ
• 例
;
f 1g
f 2g
f 3g
f 4g; f 4; 1g
b6
f 5g; f 5; 2g; f 5; 1g
f 6g; f 6; 3g; f 6; 2g; f 6; 1g
b7
f 7g; f 7; 4g; f 7; 3g; f 7; 2g; f 7; 1g; f 7; 4; 1g
EX5.2 整数集合 f 1; 2; ¢¢¢; ng の部分集合で
どの数字も2以上離れているfat集合の数 an 、
どの数字も3以上離れている集合の数 bn とする
このとき、 an = bn を証明せよ
• 例 b7
b4
;
f 7g
f 1g
f 7; 1g
f 2g
f 7; 2g
f 3g
f 7; 3g
f 4g; f 4; 1g
f 7; 4g; f 7; 4; 1g
f 5g; f 5; 2g; f 5; 1g
b6
f 6g; f 6; 3g; f 6; 2g; f 6; 1g
WHY?
b7 = b6 + b4
EX5.2 整数集合 f 1; 2; ¢¢¢; ng の部分集合で
どの数字も2以上離れているfat集合の数 an 、
どの数字も3以上離れている集合の数 bn とする
このとき、 an = bn を証明せよ
• 一般に ;
f 1g
bn
bn¡
bn¡
3
1
f ng
f n; 1g
f 2g
..
.
f n; 2g
..
.
f n ¡ 3g; f n ¡ 3; 1g; ¢¢¢
..
.
f n; n ¡ 3g; ¢¢¢
f n ¡ 1g; f n ¡ 1; 1g; ¢¢¢
1対1対応
bn = bn¡ 1 + bn¡
3
EX5.2 整数集合 f 1; 2; ¢¢¢; ng の部分集合で
どの数字も2以上離れているfat集合の数 an 、
どの数字も3以上離れている集合の数 bn とする
このとき、 an = bn を証明せよ
• 例
;
f 1g
f 2g
f 3g
a6
f 4g; f 4; 2g
f 5g; f 5; 3g; f 5; 2g
f 6g; f 6; 4g; f 6; 3g; f 6; 2g
a7
f 7g; f 7; 5g; f 7; 4g; f 7; 3g; f 7; 2g; f 7; 5; 3g
EX5.2 整数集合 f 1; 2; ¢¢¢; ng の部分集合で
どの数字も2以上離れているfat集合の数 an 、
どの数字も3以上離れている集合の数 bn とする
このとき、 an = bn を証明せよ
• 例 a7
a4
;
f 7g
f 1g
f 7; 2g-1
f 2g
f 7; 3g-1
f 3g
f 7; 4g-1
f 4g; f 4; 2g
f 7; 5g; f 7; 5; 3g
f 5g; f 5; 3g; f 5; 2g
a6
f 6g; f 6; 4g; f 6; 3g; f 6; 2g
-1
-1 -1
7を除去して
他を1づつひく
a7 = a6 + a4
EX5.2 整数集合 f 1; 2; ¢¢¢; ng の部分集合で
どの数字も2以上離れているfat集合の数 an 、
どの数字も3以上離れている集合の数 bn とする
このとき、 an = bn を証明せよ
• 一般に ;
f 1g
an
an¡
an¡
3
1
f ng
f n; 2g
f 2g
..
.
f n; 3g
..
.
f n ¡ 3g; f n ¡ 3; 2g; ¢¢¢
..
.
f n; n ¡ 2g; ¢¢¢
f n ¡ 1g; f n ¡ 1; 2g; ¢¢¢
1対1対応
an = an¡ 1 + an¡
3
EX5.2 整数集合 f 1; 2; ¢¢¢; ng の部分集合で
どの数字も2以上離れているfat集合の数 an 、
どの数字も3以上離れている集合の数 bn とする
このとき、 an = bn を証明せよ
• 結局
an = an¡ 1 + an¡
3
a0 = 1; a1 = 1; a2 = 1; a3 = 1
bn = bn¡ 1 + bn¡ 3
b0 = 1; b1 = 1; b2 = 1; b3 = 1
より an = bn である。証明終
Example 5.3. 0～4
• 0, 1, 2, 3, 4 を使って n 文字の数字列をつくる
• 但し、隣り合う数字の差は 1
• 例
– 32321012343
– 0121210101023434
• 何通りの数字列が作れるか?
EX5.3 0,1,2,3,4で、隣り合う数字の差が1であるような
10 字の数字列をつくる。何通りつくれるか?
• Sketch of Solution1
bi :奇数 ci :偶数
– 偶奇を考える
– b1c1b2c2b3c3b4c4b5
b1 の決め方 2通り
ci
bi + 1
bi
bi を決めた時の
1
2
3
1
2
1
1
0
1
3
2
3
3
2
1
3
4
3
bi + 1の決め方 3 通り
左に b1 § 1
右に b5 § 1 で 4 通り
2 ¢34 ¢4 = 648
通り
EX5.3 0,1,2,3,4で、隣り合う数字の差が1であるような
10 字の数字列をつくる。何通りつくれるか?
• Solution2
– A n : 0, 4で終わる列の数
– B n : 1, 3で終わる列の数
– Cn : 2で終わる列の数
•
n n+ 1
1
An
Bn
¢¢¢¢¢¢4
¢¢¢¢¢¢3 4
Cn ¢¢¢¢¢¢2
¢¢¢¢¢¢1 0
¢¢¢¢¢¢0
A n+ 1
A n+ 1
A n+ 1 = B n
EX5.3 0,1,2,3,4で、隣り合う数字の差が1であるような
10 字の数字列をつくる。何通りつくれるか?
• Solution2
– A n : 0, 4で終わる列の数
– B n : 1, 3で終わる列の数
– Cn : 2で終わる列の数
•
n n+ 1
1
An
Bn
¢¢¢¢¢¢4
¢¢¢¢¢¢3
Cn ¢¢¢¢¢¢2
¢¢¢¢¢¢1
¢¢¢¢¢¢0
3
3
1
1
B n+ 1
B n+ 1
A n+ 1 = B n
B n+ 1 = A n + 2Cn
EX5.3 0,1,2,3,4で、隣り合う数字の差が1であるような
10 字の数字列をつくる。何通りつくれるか?
• Solution2
– A n : 0, 4で終わる列の数
– B n : 1, 3で終わる列の数
– Cn : 2で終わる列の数
•
n n+ 1
1
An
Bn
¢¢¢¢¢¢4
¢¢¢¢¢¢3 2
Cn ¢¢¢¢¢¢2
¢¢¢¢¢¢1 2
¢¢¢¢¢¢0
Cn+ 1
A n+ 1 = B n
B n+ 1 = A n + 2Cn
Cn+ 1 = B n
EX5.3 0,1,2,3,4で、隣り合う数字の差が1であるような
10 字の数字列をつくる。何通りつくれるか?
• Solution2
– A n : 0, 4で終わる列の数
– B n : 1, 3で終わる列の数
– Cn : 2で終わる列の数
• Answer
B n+ 1 = 3B n¡
1
A 10 + B 10 + C10
A n+ 1 = B n
B n+ 1 = A n + 2Cn
Cn+ 1 = B n
= B 10 + 2B 9 = 3B 8 + 2 ¢3B 7
= ¢¢¢= 34B 2 + 2 ¢34B 1 = 648
(B 1 = 2; B 2 = 4)
Example 5.4. a, b, c
[ Romania 1998]
• a, b, c を使って記号列をつくる
• A n : a, b 同じものが連続して現れない
–○: abccabcccabca
–×: acbcaacbcacca
• B n : 3種類異なるものが連続して現れない
–○: cbccaccaccbba
–×: ccbccbcacccbb
• jB n+ 1j = 3jA n j を証明しよう
EX5.4 a, b, c で記号列 Sn をつくる、そのうち
a, b 同じものが連続して現れない集合 A n 、
異なる3つが連続して現れない集合 B n とする
このとき、 jB n+ 1j = 3jA n j を証明せよ
• Solution1
– ‘a’ → 1, ‘b’ → 2, ‘c’ → 0 でそれぞれ置き換える
– 写像 ¢ : Sn+ 1 !7 Sn
– ¢ (x 1; x 2; x 3; ¢¢¢; x n + 1)
= (x 2 ¡ x 1; x 3 ¡ x 2; ¢¢¢; x n + 1 ¡ x n )
mod 3
sn+ 1 : 0 1 0 1 2 2 1 2 1 1 1 0 2 0 2
¢ (sn+ 1) : 1 2 1 1 0 2 1 2 0 0 2 2 1 2
sn+ 1 2= B n , ¢ (sn+ 1) 2= A n WHY?
EX5.4 a, b, c で記号列 Sn をつくる、そのうち
a, b 同じものが連続して現れない集合 A n 、
異なる3つが連続して現れない集合 B n とする
このとき、 jB n+ 1j = 3jA n j を証明せよ
• Solution1
– 写像 ¢ (x 1; x 2; x 3; ¢¢¢; x n + 1)
= (x 2 ¡ x 1; x 3 ¡ x 2; ¢¢¢; x n + 1 ¡ x n )
– この写像は1対3対応
sn
: 1 2 1 1 0 2
¢
¡ 1
・ 0 1 0 1 2 2 1
(sn )
・ 1 2 1 2 0 0 2
・ 2 0 2 0 1 1 0
jB n+ 1j = 3jA n j
mod 3
EX5.4 a, b, c で記号列 Sn をつくる、そのうち
a, b 同じものが連続して現れない集合 A n 、
異なる3つが連続して現れない集合 B n とする
このとき、 jB n+ 1j = 3jA n j を証明せよ
• Solution2
– A n の中で
• X n : aで終わる記号列
• Yn : bで終わる記号列
• Z n : cで終わる記号列
1
Xn
Yn
Zn
n n+ 1
¢¢¢¢¢¢a
¢¢¢¢¢¢b
¢¢¢¢¢¢c
X n+ 1
a
a
jX n+ 1j = jYn j + jZ n j
EX5.4 a, b, c で記号列 Sn をつくる、そのうち
a, b 同じものが連続して現れない集合 A n 、
異なる3つが連続して現れない集合 B n とする
このとき、 jB n+ 1j = 3jA n j を証明せよ
• Solution2
– A n の中で
• X n : aで終わる記号列
• Yn : bで終わる記号列
• Z n : cで終わる記号列
1
Xn
Yn
Zn
n n+ 1
¢¢¢¢¢¢a
¢¢¢¢¢¢b
¢¢¢¢¢¢c
b
Yn+ 1
b
jX n+ 1j = jYn j + jZ n j
jYn+ 1j = jX n j + jZ n j
EX5.4 a, b, c で記号列 Sn をつくる、そのうち
a, b 同じものが連続して現れない集合 A n 、
異なる3つが連続して現れない集合 B n とする
このとき、 jB n+ 1j = 3jA n j を証明せよ
• Solution2
– A n の中で
• X n : aで終わる記号列
• Yn : bで終わる記号列
• Z n : cで終わる記号列
1
Xn
Yn
Zn
n n+ 1
¢¢¢¢¢¢a
¢¢¢¢¢¢b
¢¢¢¢¢¢c
c
c
c
jX n+ 1j = jYn j + jZ n j
jYn+ 1j = jX n j + jZ n j
jZ n+ 1j = jX n j + jYn j + jZ n j
Z n+ 1
EX5.4 a, b, c で記号列 Sn をつくる、そのうち
a, b 同じものが連続して現れない集合 A n 、
異なる3つが連続して現れない集合 B n とする
このとき、 jB n+ 1j = 3jA n j を証明せよ
• Solution2
– A n の中で
• X n : aで終わる記号列
• Yn : bで終わる記号列
• Z n : cで終わる記号列
• 結局
jA n+ 2j = jX n+ 2j + jYn+ 2j + jZ n+ 2j
jX n+ 1j = jYn j + jZ n j
jYn+ 1j = jX n j + jZ n j
jZ n+ 1j = jX n j + jYn j + jZ n j
= 2jX n+ 1j + 2jYn+ 1j + 3jZ n+ 1j = 2jA n+ 1j + jA n j
EX5.4 a, b, c で記号列 Sn をつくる、そのうち
a, b 同じものが連続して現れない集合 A n 、
異なる3つが連続して現れない集合 B n とする
このとき、 jB n+ 1j = 3jA n j を証明せよ
• Solution2
– B n の中で
• Tn : 同じ記号で終わる列 (…aa, …bb, …cc)
• Un : それ以外の記号列 (…ab, ba, ca, ac, bc, cb)
n n+ 1
Tn
¢¢¢¢¢¢aa
Un
¢¢¢¢¢¢ba
a
b
c
a
b
jB n+ 1j = 3jTn j + 2jUn j
B n+ 1
EX5.4 a, b, c で記号列 Sn をつくる、そのうち
a, b 同じものが連続して現れない集合 A n 、
異なる3つが連続して現れない集合 B n とする
このとき、 jB n+ 1j = 3jA n j を証明せよ
• Solution2
– B n の中で
• Tn : 同じ記号で終わる列 (…aa, …bb, …cc)
• Un : それ以外の記号列 (…ab, ba, ca, ac, bc, cb)
n n+ 1
Tn
¢¢¢¢¢¢aa
jB n+ 1j = 3jTn j + 2jUn j
a
Tn+ 1
Un
¢¢¢¢¢¢ba
a
jTn+ 1j = jB n j
EX5.4 a, b, c で記号列 Sn をつくる、そのうち
a, b 同じものが連続して現れない集合 A n 、
異なる3つが連続して現れない集合 B n とする
このとき、 jB n+ 1j = 3jA n j を証明せよ
• Solution2
– B n の中で
• Tn : 同じ記号で終わる列 (…aa, …bb, …cc)
• Un : それ以外の記号列 (…ab, ba, ca, ac, bc, cb)
•
jB n j ¡ jB n¡ 1j = jB n j ¡ jTn j = jUn j
= 3(jTn j + jUn j) ¡ (3jTn j + 2jUn j) = 3jB n j ¡ jB n+ 1j
jB n+ 1j = 2jB n j + jB n¡ 1j
jB n+ 1j = 3jTn j + 2jUn j
jTn+ 1j = jB n j
EX5.4 a, b, c で記号列 Sn をつくる、そのうち
a, b 同じものが連続して現れない集合 A n 、
異なる3つが連続して現れない集合 B n とする
このとき、 jB n+ 1j = 3jA n j を証明せよ
• Solution2 A n B n
– 2つのRecursion
jA n+ 1j = 2jA n j + jA n¡ 1j
jB n+ 1j = 2jB n j + jB n¡ 1j
– スタート
jB 2j = 3jA 1j = 9
jB 3j = 3jA 2j = 21
jB n+ 1j = 3jA n j
Example 5.5. コイン
[ AIME 1995]
• コイン投げを何回か繰り返す。
– 5回連続で表(H)が出たら成功 : Success
– それまでに、2回連続で裏(T)が出たら失敗
• Success
– THHHHTHTHHHHH
• Failure
– HTHHHTT
EX5.5 コインを繰り返し投げる。2回連続で裏(T)が
出る前に、5回連続で表(H)が出る確率は?
• Successとなる T, H 列を分類
– T H - - - - - - (success)
– H T H - - - - - - (success)
– H H T H - - - - - - (success)
– H H H T H - - - - - - (success)
– H H H H T H - - - - - - (success)
– H H H H H (success)
1
pt = ph
2
³1 1 1
1´
1
ph =
+ + +
pt +
2 4 8 16
32
pt
T から始まって
サクセスする確率
ph
H から始まって
サクセスする確率
1
1
ph =
; pt =
17
34
3
ph + pt =
34
Example 5.6. 正四面体
[ AIME 1985]
• 正四面体（ABCD）で虫(A Bug)が乱歩
– 頂点 A からスタート
1
– 次の頂点をランダムに選んで進む（確率 3 ）
A
D
B
C
正四面体を
真上から見た図
EX5.6 正四面体 ABCD 上で乱歩。
ちょうど 7歩目に頂点 A にいる確率は?
•
an : n 歩目に頂点 A にいる確率
– 1 ¡ an : n 歩目に頂点 B, C, D にいる確率
1
an+ 1 = (1 ¡ an )
3
• Answer
A
1
2
7
a1 = 0; a2 = ; a3 = ; a4 =
3
9
27
20
61
182
a5 =
; a6 =
; a7 =
81
243
729
D
B
C
5. Recursions
1
• さっきの an+ 1 = 3(1 ¡ an ) を解こう
1
– 公比 ¡ の等比級数
3
1
– an+ 1 ¡ x = ¡ (an ¡ x) とおくと
3
1
1
– x = (1 ¡ x) より x =
4
3
1
an+ 1 ¡
= ¡
4
1 ³
an = + ¡
4
1
1
(an ¡ )
3
4
1´ n ³ 3´
3
4
5. Recursions
• 写像 f : N0 !7 R a1; a2; ¢¢¢; ak 2 R
• f (n) ¡ a1f (n ¡ 1) ¡ a2f (n ¡ 2) ¡ ¢¢¢¡ ak f (n ¡ k) = 0
– constant homogeneous recursion of degree k
• f (n) ¡ a1f (n ¡ 1) ¡ a2f (n ¡ 2) ¡ ¢¢¢¡ ak f (n ¡ k) = g(n)
– constant inhomogeneous recursion of degree k
• x k ¡ aa x k¡ 1 ¡ a2x k¡ 2 ¡ ¢¢¢¡ ak = 0
– characteristic equation(特性方程式)
f (n) = c1z1n + c2z2n + ¢¢¢+ ck zkn
= 0 に対して f (n) = zn が(¤)を
Theorem 5.1. 複素数 z 6
満たすとき、またその時に限り z は (¤¤) を満たす
(¤) f (n) ¡ a1f (n ¡ 1) ¡ a2f (n ¡ 2) ¡ ¢¢¢¡ ak f (n ¡ k) = 0
(¤¤) x k ¡ aa x k¡ 1 ¡ a2x k¡ 2 ¡ ¢¢¢¡ ak = 0
• Proof
– f (n) = zn が (¤) を満たす
zn¡ k (zk ¡ aa zk¡ 1 ¡ a2zk¡ 2 ¡ ¢¢¢¡ ak ) = 0
– これは
z が (¤¤) を満たすことと同値 (z 6= 0)
Theorem 5.2. 2つの写像 f 1(n); f 2(n) が (¤) を満たす
とき、その線形結合 c1f 1(n) + c2f 2(n) は (¤) を満たす
(¤) f (n) ¡ a1f (n ¡ 1) ¡ a2f (n ¡ 2) ¡ ¢¢¢¡ ak f (n ¡ k) = 0
• Proof
¡
¢
– c1f 1(n) + c2f 2(n) ¡ a1 c1f (n ¡ 1) + c2f (n ¡ 1) ¡ ¢¢¢
= c1(f 1(n) ¡ a1f 1(n ¡ 1) ¡ ¢¢¢¡ ak f 1(n ¡ k))
+ c2(f 2(n) ¡ a1f 2(n ¡ 1) ¡ ¢¢¢¡ ak f 2(n ¡ k)) = 0
Theorem 5.3. もし (¤) が異なる特性根 z1; z2; ¢¢¢; zk を
持つならば、 (¤) を満たす全ての f (n) は
f (n) = c1z1n + c2z2n + ¢¢¢+ ck zkn
の形で書ける
(¤) f (n) ¡ a1f (n ¡ 1) ¡ a2f (n ¡ 2) ¡ ¢¢¢¡ ak f (n ¡ k) = 0
• Proof
n
n
n
f
(n)
=
c
z
+
c
z
+
¢¢¢+
c
z
1 1
2 2
k k が (¤) を満たすこ
–
とはTheorem5.1. , Theorem5.2. より言える
– 逆に f (n) が (¤) を満たすとき
• f (0); f (1); ¢¢¢; f (k ¡ 1) が上の形で書ける
• （どんな初期値に対しても c1; c2; ¢¢¢; ck が存在する）
f (n) が上の形で書ける
Theorem 5.3. もし (¤) が異なる特性根 z1; z2; ¢¢¢; zk を
持つならば、 (¤) を満たす全ての f (n) は
f (n) = c1z1n + c2z2n + ¢¢¢+ ck zkn
の形で書ける
(¤) f (n) ¡ a1f (n ¡ 1) ¡ a2f (n ¡ 2) ¡ ¢¢¢¡ ak f (n ¡ k) = 0
• Proof
– ファンデルモンドの行列式
Y
c1; c2; ¢¢¢; ck
(zj ¡ zi ) 6
= 0
1· i · j · k
2
6
6
6
6
6
6
4
1
z1
z12
..
.
z1k¡
32
1
z2
z22
1
z2k¡
1
¢¢¢
¢¢¢
1
1
zk
zk2
..
.
¢¢¢ zkk¡
76
76
76
76
76
76
54
1
3
c1
c2
c3
..
.
ck
2
7 6
7 6
7 6
7 = 6
7 6
7 6
5 4
一意に定まる
3
f (0)
7
f (1) 7
7
f (2) 7
7
..
7
.
5
f (k ¡ 1)
Theorem 5.4. もし (¤) が異なる特性根 z1; z2; ¢¢¢; zm を
持ち、それらの重複度が e1; e2; ¢¢¢; em ならば、
(¤) を満たす全ての f (n) は次の線形結合の形で
書ける
z1n ; nz1n ; ¢¢¢ne1 ¡ 1z1n
z2n ; nz2n ; ¢¢¢ne2 ¡ 1z2n
..
.
zmn ; nzmn ; ¢¢¢nem ¡ 1zmn
(¤) f (n) ¡ a1f (n ¡ 1) ¡ a2f (n ¡ 2) ¡ ¢¢¢¡ ak f (n ¡ k) = 0
Theorem 5.5. 写像 f (n) が (¤0) を満たすならば、
(¤) を満たす f 1(n) 、 (¤0) を満たす f 2(n) を用い
f (n) = f 1(n) + f 2(n)
と書ける
(¤) f (n) ¡ a1f (n ¡ 1) ¡ a2f (n ¡ 2) ¡ ¢¢¢¡ ak f (n ¡ k) = 0
(¤0) f (n) ¡ a1f (n ¡ 1) ¡ a2f (n ¡ 2) ¡ ¢¢¢¡ ak f (n ¡ k) = g(n)
Example 5.7. 正八角形
[ IMO 1979]
• 正八角形 (ABCDEFGH) 頂点をカエル（A Frog）
が歩く
• 頂点 E に来ると歩くのをやめる
• un : ちょうど n 歩目で頂点 E に到達する
歩道 (walk) の数
A
H
u1 = u2 = u3 = 0; u4 = 2
B
G
C
F
D
E
EX5.7 正八角形上で、頂点A から始まり n 歩目で
頂点E にはじめて到達する歩道の数 un は?
• Solution Outline
– n 歩目にちょうど A ～ H にいる歩道の数
– an ～ hn とする ( 対称性よりH = B, G = C, F = D )
en = dn¡ 1 + f n¡ 1 = 2dn¡
dn = cn¡
1
A
H
1
an = 2bn¡
B
G
C
F
1
cn = bn¡ 1 + dn¡
1
bn = an¡ 1 + cn¡
1
en+ 3 ¡ 4en+ 1 + 2en¡ 1 = 0
D
E
EX5.7 正八角形上で、頂点A から始まり n 歩目で
頂点E にはじめて到達する歩道の数 un は?
• Solution Outline
– en+ 3 ¡ 4en+ 1 + 2en¡ 1 = 0
q
p
x = § 2§ 2
– x 4 ¡ 4x 2 + 2 = 0
特性方程式
特性根
– Theorem 5.3 より
un = en = asn + b(¡ s) n + ct n + d(¡ t) n
と書ける
¡
q
s=
2+
p
q
2; t =
p ¢
2¡
2
EX5.7 正八角形上で、頂点A から始まり n 歩目で
頂点E にはじめて到達する歩道の数 un は?
• Solution Outline
n
n
n
n
u
=
e
=
as
+
b(¡
s)
+
ct
+
d(¡
t)
– n
n
– e1 = e2 = e3 = 0; e4 = 2 より
(a ¡ b)s + (c ¡ d)t = 0
(a + b)s2 + (c + d)t 2 = 0
A
H
B
G
C
F
(a ¡ b)s3 + (c ¡ d)t 3 = 0
(a + b)s4 + (c + d)t 4 = 2
t2
s2
a = b= p ;c = d = ¡ p
4 2
4 2
D
E
EX5.7 正八角形上で、頂点A から始まり n 歩目で
頂点E にはじめて到達する歩道の数 un は?
• Solution Outline
n
n
n
n
u
=
e
=
as
+
b(¡
s)
+
ct
+
d(¡
t)
– n
n
t2
s2
– a = b= p ;c = d = ¡ p
4 2
4 2
–
¡
q
s=
u2n¡
u2n
2+
p
q
2; t =
p ¢
2¡
2
A
B
G
C
F
D
= 0
p n¡ 1
p n¡ 1¢
1 ¡
= p (2 + 2)
¡ (2 ¡ 2)
2
1
H
E

Download Report