2014年06月08日
フィボナッチ数
夕方頃から涼しくなって、今は涼しい風が流れています。昼間の暑さがウソのようです。
6/14 (土) はいよいよ石川智晶さんのライブなんですよね。しかし、チケットは結局入手できず、今回は断念です。来年の一月に渋谷でのライブが決定したそうで、次は名古屋でのライブが再び実現するのを期待したいと思います。ちょうど今週の木曜日から金曜日にかけて出張で東京まで行く予定なんですよね。チケットさえ持っていれば、そのままライブの時間まで東京をぶらつくこともできたんですけど、残念です。
「数学問題 bot」に面白そうな問題があったのでチャレンジしました。今回は非常に長いです。
---
■ { 1, 2, ..., n } の空でない部分集合のうち、隣り合う二つの数を含まないようなものはいくつあるか。(Marbel_NIKO様)
求めたい数を S(n) として、まずは、n = 1 から順に数えてみます。
n = 1 : {1}
n = 2 : {1} {2}
n = 3 : {1} {2} {1,3} {3}
n = 4 : {1} {2} {1,3} {3} {1,4} {2,4} {4}
n = 5 : {1} {2} {1,3} {3} {1,4} {2,4} {4} {1,5} {2,5} {1,3,5} {3,5} {5}
:
よって、n = 5 までは S(1) = 1, S(2) = 2, S(3) = 4, S(4) = 7, S(5) = 12 となります。この結果からパターンを調べていきます。
n - 1 までに見つかった部分集合はそのまま n の部分集合になります。それらは n を要素に持たないので、残りは必ず n を要素に持つ部分集合になり、n - 1 までの部分集合に n を加えたものでなければなりません。なぜなら、それ以外の組み合わせは必ず隣り合う二つの数を含んでいるからです。さらに、部分集合の要素に n - 1 が含まれていると、n - 1 と n どうしが隣り合うのでこれらは除外する必要があります。例えば n = 5 のとき、その条件を満たす n = 4 までの部分集合は {1} {2} {1,3} {3} の 4 つなので、これらに 5 を加えた {1,5} {2,5} {1,3,5} {3,5} が求める部分集合になります。これは n = 3 での部分集合そのものに 5 を加えたものに相当します。最後に、n のみを要素とする部分集合 {n} を加える必要があります。
以上から、S(n) は n - 1 までの部分集合の数 S(n-1) に、その一つ前の n - 2 での部分集合の数 S(n-2) を加え、さらに 1 を加えた式
S(1) = 1
S(2) = 2
S(n) = S(n-1) + S(n-2) + 1 ( n > 2 )
で表されます。この漸化式に対して一般項を解けば、求めたい答えが得られます。
この漸化式は、フィボナッチ数列 F(1) = F(2) = 1, F(n) = F(n-1) + F(n-2) によく似ています。従って、フィボナッチ数列の一般項を求める方法を利用することができます。まず、数列 S(n) を xn の係数とする多項式 (これを母関数といいます) を F(x) とすると、
F(x) = S(1)x + S(2)x2 + S(3)x3 + S(4)x4 + ... + S(n)xn + ...
となります。これに S(n) = S(n-1) + S(n-2) + 1 を代入すると、
F(x)
= S(1)x + S(2)x2 + [ S(2) + S(1) + 1 ]x3 + [ S(3) + S(2) + 1 ]x4 + ... + [ S(n-1) + S(n-2) + 1 ]xn + ...
= S(1)x + S(2)x2
+ [ S(2)x3 + S(3)x4 + ... + S(n-1)xn + ... ]
+ [ S(1)x3 + S(2)x4 + ... + S(n-2)xn + ... ]
+ [ x3 + x4 + ... + xn + ... ]
= S(1)x + S(2)x2
+ x[ S(1)x + S(2)x2 + S(3)x3 + ... + S(n-1)xn-1 + ... ] - S(1)x2
+ x2[ S(1)x + S(2)x2 + ... + S(n-2)xn-2 + ... ]
+ x[ 1 + x + x2 + x3 + ... + xn-1 + ... ] - x - x2
= x + 2x2 + xF(x) - x2 + x2F(x) + xG(x) - x - x2
= xF(x) + x2F(x) + xG(x)
より
F(x) = xG(x) / ( 1 - x - x2 )
となります。但し、G(x) は初項 1、公比 x の等比級数です。G(x) は
G(x) = 1 + x + x2 + ...
xG(x) = x + x2 + x3 + ...
の両式を辺々引いて
( 1 - x )G(x) = 1 より G(x) = 1 / ( 1 - x )
と求めることができるので、これを代入すれば
F(x) = x / ( 1 - x )( 1 - x - x2 )
という結果が得られます。
次に得られた式を部分分数分解します。その前に、1 - x - x2 を因数分解するため
1 - x - x2 = ( 1 - ax )( 1 - bx )
とすると、(右辺) = 1 - ( a + b )x + abx2 より a + b = 1, ab = -1 となります。b = 1 - a を ab = -1 に代入して
a( 1 - a ) = -1 より a2 - a - 1 = 0
の解を求めると、二次方程式の解の公式から
a = ( 1 ± √5 ) / 2
となるので、a = ( 1 + √5 ) / 2, b = ( 1 - √5 ) / 2 とすれば
F(x) = x / ( 1 - x )( 1 - ax )( 1 - bx )
と表すことができます。これを
F(x) = A / ( 1 - ax ) + B / ( 1 - bx ) + C / ( 1 - x )
の形にすればいいので、この式をまた一つの分数に戻すと分子部分は
( 1 - bx )( 1 - x )A + ( 1 - ax )( 1 - x )B + ( 1 - ax )( 1 - bx )C
= [ 1 - ( b + 1 )x + bx2 ]A + [ 1 - ( a + 1 )x + ax2 ]B + [ 1 - ( a + b )x + abx2 ]C
= ( A + B + C ) - [ ( b + 1 )A + ( a + 1 )B + C ]x + ( bA + aB - C )x2
となって、これが x と恒等的に等しいならば
A + B + C = 0 --- (1)
( b + 1 )A + ( a + 1 )B + C = -1 --- (2)
bA + aB - C = 0 --- (3)
が成り立ちます。(1) + (3) より
( b + 1 )A + ( a + 1 )B = 0
なので、これを (2) に代入すれば C = -1 が得られ、これを (1) (3) に代入して
A + B = 1 --- (1')
bA + aB = -1 --- (2')
(1') x a - (2') より
( a - b )A = a + 1
よって A = ( a + 1 ) / ( a - b ) で、同様にして B = ( b + 1 ) / ( b - a ) です。a, b の値を代入して
A = ( 5 + 3√5 ) / 10, B = ( 5 - 3√5 ) / 10
となり、これで F(x) を部分関数分解することができました。個々の分数を見ると、これらは G(ax), G(bx), G(x) と等しく、
1 / ( 1 - ax ) = 1 + (ax) + (ax)2 + ...
1 / ( 1 - bx ) = 1 + (bx) + (bx)2 + ...
1 / ( 1 - x ) = 1 + x + x2 + ...
なので、
F(x)
= A[ 1 + (ax) + (ax)2 + ... ] + B[ 1 + (bx) + (bx)2 + ... ] - [ 1 + x + x2 + ... ]
= ( A + B + C ) + ( Aa + Bb - 1 )x + ( Aa2 + Bb2 - 1 )x2 + ...
と表せて、xn の係数は
Aan + Bbn - 1
となります。ところがこれは S(n) でもあることから
S(n) = Aan + Bbn - 1
= [ ( 5 + 3√5 ) / 10 ][ ( 1 + √5 ) / 2 ]n + [ ( 5 - 3√5 ) / 10 ][ ( 1 - √5 ) / 2 ]n - 1
になります。これで S(n) の一般項が得られました。
ちなみにフィボナッチ数列の一般項は
F(n) = ( 1 / √5 )[ ( 1 + √5 ) / 2 ]n - ( 1 / √5 )[ ( 1 - √5 ) / 2 ]n
でこれは「ビネの公式」と呼ばれています。ビネはこの公式を 1843 年に発表しましたが、それより 100 年以上も前の 1730 年にド・モアブルによってすでに発見されていたそうです。S(n) も F(n) も [ ( 1 ± √5 ) / 2 ]n を項に持っていますが、( 1 + √5 ) / 2 > 1 に対して | 1 - √5 | / 2 < 1 なので [ ( 1 - √5 ) / 2 ]n 項は n が大きくなると無視できるほど小さくなります。よって、n が十分大きければ、S(n) も F(n) も n が 1 増加するたびにほぼ ( 1 + √5 ) / 2 倍ずつ大きくなるようになります。
■ 参考文献
「はじめての数論」 Joseph H. Silverman 著
ISBN 978-4-62106-620-1
6/14 (土) はいよいよ石川智晶さんのライブなんですよね。しかし、チケットは結局入手できず、今回は断念です。来年の一月に渋谷でのライブが決定したそうで、次は名古屋でのライブが再び実現するのを期待したいと思います。ちょうど今週の木曜日から金曜日にかけて出張で東京まで行く予定なんですよね。チケットさえ持っていれば、そのままライブの時間まで東京をぶらつくこともできたんですけど、残念です。
「数学問題 bot」に面白そうな問題があったのでチャレンジしました。今回は非常に長いです。
---
■ { 1, 2, ..., n } の空でない部分集合のうち、隣り合う二つの数を含まないようなものはいくつあるか。(Marbel_NIKO様)
求めたい数を S(n) として、まずは、n = 1 から順に数えてみます。
n = 1 : {1}
n = 2 : {1} {2}
n = 3 : {1} {2} {1,3} {3}
n = 4 : {1} {2} {1,3} {3} {1,4} {2,4} {4}
n = 5 : {1} {2} {1,3} {3} {1,4} {2,4} {4} {1,5} {2,5} {1,3,5} {3,5} {5}
:
よって、n = 5 までは S(1) = 1, S(2) = 2, S(3) = 4, S(4) = 7, S(5) = 12 となります。この結果からパターンを調べていきます。
n - 1 までに見つかった部分集合はそのまま n の部分集合になります。それらは n を要素に持たないので、残りは必ず n を要素に持つ部分集合になり、n - 1 までの部分集合に n を加えたものでなければなりません。なぜなら、それ以外の組み合わせは必ず隣り合う二つの数を含んでいるからです。さらに、部分集合の要素に n - 1 が含まれていると、n - 1 と n どうしが隣り合うのでこれらは除外する必要があります。例えば n = 5 のとき、その条件を満たす n = 4 までの部分集合は {1} {2} {1,3} {3} の 4 つなので、これらに 5 を加えた {1,5} {2,5} {1,3,5} {3,5} が求める部分集合になります。これは n = 3 での部分集合そのものに 5 を加えたものに相当します。最後に、n のみを要素とする部分集合 {n} を加える必要があります。
以上から、S(n) は n - 1 までの部分集合の数 S(n-1) に、その一つ前の n - 2 での部分集合の数 S(n-2) を加え、さらに 1 を加えた式
S(1) = 1
S(2) = 2
S(n) = S(n-1) + S(n-2) + 1 ( n > 2 )
で表されます。この漸化式に対して一般項を解けば、求めたい答えが得られます。
この漸化式は、フィボナッチ数列 F(1) = F(2) = 1, F(n) = F(n-1) + F(n-2) によく似ています。従って、フィボナッチ数列の一般項を求める方法を利用することができます。まず、数列 S(n) を xn の係数とする多項式 (これを母関数といいます) を F(x) とすると、
F(x) = S(1)x + S(2)x2 + S(3)x3 + S(4)x4 + ... + S(n)xn + ...
となります。これに S(n) = S(n-1) + S(n-2) + 1 を代入すると、
F(x)
= S(1)x + S(2)x2 + [ S(2) + S(1) + 1 ]x3 + [ S(3) + S(2) + 1 ]x4 + ... + [ S(n-1) + S(n-2) + 1 ]xn + ...
= S(1)x + S(2)x2
+ [ S(2)x3 + S(3)x4 + ... + S(n-1)xn + ... ]
+ [ S(1)x3 + S(2)x4 + ... + S(n-2)xn + ... ]
+ [ x3 + x4 + ... + xn + ... ]
= S(1)x + S(2)x2
+ x[ S(1)x + S(2)x2 + S(3)x3 + ... + S(n-1)xn-1 + ... ] - S(1)x2
+ x2[ S(1)x + S(2)x2 + ... + S(n-2)xn-2 + ... ]
+ x[ 1 + x + x2 + x3 + ... + xn-1 + ... ] - x - x2
= x + 2x2 + xF(x) - x2 + x2F(x) + xG(x) - x - x2
= xF(x) + x2F(x) + xG(x)
より
F(x) = xG(x) / ( 1 - x - x2 )
となります。但し、G(x) は初項 1、公比 x の等比級数です。G(x) は
G(x) = 1 + x + x2 + ...
xG(x) = x + x2 + x3 + ...
の両式を辺々引いて
( 1 - x )G(x) = 1 より G(x) = 1 / ( 1 - x )
と求めることができるので、これを代入すれば
F(x) = x / ( 1 - x )( 1 - x - x2 )
という結果が得られます。
次に得られた式を部分分数分解します。その前に、1 - x - x2 を因数分解するため
1 - x - x2 = ( 1 - ax )( 1 - bx )
とすると、(右辺) = 1 - ( a + b )x + abx2 より a + b = 1, ab = -1 となります。b = 1 - a を ab = -1 に代入して
a( 1 - a ) = -1 より a2 - a - 1 = 0
の解を求めると、二次方程式の解の公式から
a = ( 1 ± √5 ) / 2
となるので、a = ( 1 + √5 ) / 2, b = ( 1 - √5 ) / 2 とすれば
F(x) = x / ( 1 - x )( 1 - ax )( 1 - bx )
と表すことができます。これを
F(x) = A / ( 1 - ax ) + B / ( 1 - bx ) + C / ( 1 - x )
の形にすればいいので、この式をまた一つの分数に戻すと分子部分は
( 1 - bx )( 1 - x )A + ( 1 - ax )( 1 - x )B + ( 1 - ax )( 1 - bx )C
= [ 1 - ( b + 1 )x + bx2 ]A + [ 1 - ( a + 1 )x + ax2 ]B + [ 1 - ( a + b )x + abx2 ]C
= ( A + B + C ) - [ ( b + 1 )A + ( a + 1 )B + C ]x + ( bA + aB - C )x2
となって、これが x と恒等的に等しいならば
A + B + C = 0 --- (1)
( b + 1 )A + ( a + 1 )B + C = -1 --- (2)
bA + aB - C = 0 --- (3)
が成り立ちます。(1) + (3) より
( b + 1 )A + ( a + 1 )B = 0
なので、これを (2) に代入すれば C = -1 が得られ、これを (1) (3) に代入して
A + B = 1 --- (1')
bA + aB = -1 --- (2')
(1') x a - (2') より
( a - b )A = a + 1
よって A = ( a + 1 ) / ( a - b ) で、同様にして B = ( b + 1 ) / ( b - a ) です。a, b の値を代入して
A = ( 5 + 3√5 ) / 10, B = ( 5 - 3√5 ) / 10
となり、これで F(x) を部分関数分解することができました。個々の分数を見ると、これらは G(ax), G(bx), G(x) と等しく、
1 / ( 1 - ax ) = 1 + (ax) + (ax)2 + ...
1 / ( 1 - bx ) = 1 + (bx) + (bx)2 + ...
1 / ( 1 - x ) = 1 + x + x2 + ...
なので、
F(x)
= A[ 1 + (ax) + (ax)2 + ... ] + B[ 1 + (bx) + (bx)2 + ... ] - [ 1 + x + x2 + ... ]
= ( A + B + C ) + ( Aa + Bb - 1 )x + ( Aa2 + Bb2 - 1 )x2 + ...
と表せて、xn の係数は
Aan + Bbn - 1
となります。ところがこれは S(n) でもあることから
S(n) = Aan + Bbn - 1
= [ ( 5 + 3√5 ) / 10 ][ ( 1 + √5 ) / 2 ]n + [ ( 5 - 3√5 ) / 10 ][ ( 1 - √5 ) / 2 ]n - 1
になります。これで S(n) の一般項が得られました。
ちなみにフィボナッチ数列の一般項は
F(n) = ( 1 / √5 )[ ( 1 + √5 ) / 2 ]n - ( 1 / √5 )[ ( 1 - √5 ) / 2 ]n
でこれは「ビネの公式」と呼ばれています。ビネはこの公式を 1843 年に発表しましたが、それより 100 年以上も前の 1730 年にド・モアブルによってすでに発見されていたそうです。S(n) も F(n) も [ ( 1 ± √5 ) / 2 ]n を項に持っていますが、( 1 + √5 ) / 2 > 1 に対して | 1 - √5 | / 2 < 1 なので [ ( 1 - √5 ) / 2 ]n 項は n が大きくなると無視できるほど小さくなります。よって、n が十分大きければ、S(n) も F(n) も n が 1 増加するたびにほぼ ( 1 + √5 ) / 2 倍ずつ大きくなるようになります。
■ 参考文献
「はじめての数論」 Joseph H. Silverman 著
ISBN 978-4-62106-620-1
