フィボナッチ数列
$F_1=F_2=1,\ F_{n}=F_{n-2}+F_{n-1}$ で定義される数列を フィボナッチ数列 とよびます。規則にしたがって最初の $10$ 項を書き並べると以下のようになります。
\[1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55\tag{1}\]
フィボナッチ数列の一般項は
\[F_n=\frac{\phi^n-(1-\phi)^n}{\sqrt{5}}\tag{2}\]
によって与えられます (ビネの公式)。ここで $\phi$ は黄金比とよばれる定数で、
\[\phi=\frac{1+\sqrt{5}}{2}=1.6180339887...\tag{3}\]
によって定義されています。フィボナッチ数列の隣り合う項は、この黄金比に収束することが知られています:
\[\lim_{n\rightarrow\infty}\frac{F_n}{F_{n-1}}=\phi\tag{4}\]
漸化式 $F_{n}=F_{n-2}+F_{n-1}$ を満たすように、$n$ を負番号まで拡張することもできます。後述する SymPy の fibonacci() 関数は、負番号のフィボナッチ数も生成できます。
それでは、Python でフィボナッチ数列を実装してみましょう。正の整数 n を与えて、第 n 項までのフィボナッチ数列をリストで返す fibonacci_list() 関数です。
# PYTHON_FIBONACCI_01
# In[1]
# フィボナッチ数列生成関数
def fibonacci_list(n):
fib = [1, 1]
if n == 1:
fib = [1]
else:
for k in range(2, n):
fib.append(fib[k-1]+fib[k-2])
return fib
上のコードは少しだけ工夫して条件分枝の記述を減らしています。最初に変数 fib に [1, 1] を格納し、引数 n に 1 が渡されたときだけ [1] に置き換えます。n に 2 が渡されたかどうかのチェックはしません。n == 2 のときは range(2, 2) が空リストであるために、for 以下の処理は実行されないからです。
$F_1$ から $F_{10}$ のリストを作ってみます。
# In[2]
# フィボナッチ数列を第10項まで求める
fib = fibonacci_list(10)
print(fib)
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
特定のフィボナッチ数だけ欲しいときは、インデックスで参照します。
# In[3]
# 7番目のフィボナッチ数を取得
print(fib[8])
# 34
十分大きな番号の隣り合う 2 項の比が黄金比 $1.6180339887...$ に近い値となることを確認しておきましょう。収束が速いので、それほど多くの項数は必要ありません。
# In[4]
# フィボナッチ数列を第100項まで求める
fib = fibonacci_list(100)
# F(50)/F(49)
phi_1 = fib[49] / fib[48]
# F(100)/F(99)
phi_2 = fib[99] / fib[98]
print(phi_1)
print(phi_2)
# 1.618033988749895
# 1.618033988749895
計算機代数システム SymPy にはフィボナッチ数あるいはフィボナッチ多項式を生成する sympy.fibonacci() が用意されています。sympy.fibonacci(n) は n 番目のフィボナッチ数を返します。
# SYMPY_FIBONACCI
# In[1]
import sympy
# 10番目のフィボナッチ数を生成
fib = sympy.fibonacci(10)
print(fib)
# 55
数列を生成するときはループで処理します。
# In[2]
fib = [sympy.fibonacci(x) for x in range(-5, 5)]
print(fib)
# [5, -3, 2, -1, 1, 0, 1, 1, 2, 3]
この実行結果を見るとわかるように、sympy.fibonacci(n) は「前の 2 項を足して新しい項を作る」という規則にしたがって負番号に対応するフィボナッチ数も返します。
sympy.fibonacci(n, sym) はフィボナッチ多項式オブジェクトを返します。フィボナッチ多項式 とは、以下の漸化式で定義される多項式列です。
\[\begin{align*}&F_1(x)=0,\ F_2(x)=1\\[6pt]
&F_n(x)=xF_{n-1}(x)+F_{n-2}(x)\quad (n\geq 2)\end{align*}\tag{5}\]
$x=1$ とした場合は、フィボナッチ数列となります。
引数 n, x にシンボルを与えて、n 番目のフィボナッチ多項式を生成してみます。
# PYTHON_FIBONACCI_03
# In[1]
import sympy
x = sympy.Symbol("x")
n = sympy.Symbol("n")
# n番目のフィボナッチ多項式
fib_pol = sympy.fibonacci(n,x)
print(fib_pol)
# fibonacci(n, x)
n に適当な値を代入することで、任意番号のフィボナッチ多項式が得られます。$F_7(x)$ を取得してみましょう。
# In[2]
fib = fib_pol.subs(n, 7)
print(fib)
# x**6 + 5*x**4 + 6*x**2 + 1
トリボナッチ数列
トリボナッチ数列 は直前 3 項の和で生成される数列です。
\[T_{n+3}=T_n+T_{n+1}+T_{n+2}\tag{6}\]
最初の 3 項の選び方は色々あります。たとえば、
\[T_1=T_2=1,\ T_3=2\tag{7}\]
とすると、
\[1,\ 1,\ 2,\ 4,\ 7,\ 13,\ 24,\ 44,\ 81,\ ...\tag{8}\]
のように並びます。ちなみに、フィボナッチはイタリアの数学者レオナルド・フィボナッチの名前に由来しますが、トリボナッチという人は存在しません。Python でトリボナッチ数列を実装してみましょう。
# PYTHON_TRIBONACCI
# In[1]
# トリボナッチ数列生成関数
def tribonacci_list(n, t0, t1, t2):
tri = [t0, t1, t2]
if n == 1:
tri = [t0]
elif n == 2:
tri = [t0, t1]
else:
for k in range(3, n):
tri.append(tri[k-1]+tri[k-2]+tri[k-3])
return tri
n には生成する数列の項数を指定します。
t0, t1, t2 には最初の 3 項を渡します。
$1,\ 1,\ 2$ から始まる $10$ 項のトリボナッチ数列を表示してみます。
# In[2]
# 1,1,2から始まる10項のトリボナッチ数列を生成
tri = tribonacci_list(10, 1, 1, 2)
print(tri)
# [1, 1, 2, 4, 7, 13, 24, 44, 81, 149]
【ChatGPT講義】トリボナッチ数列
講師: 皆さん、こんにちは。今日は数列の中でも興味深い「トリボナッチ数列」についてお話しします。
生徒A: トリボナッチ数列って、聞いたことがありませんが、一体どんな数列なんですか?
講師: いい質問ですね、生徒Aさん。トリボナッチ数列は、フィボナッチ数列に似た性質を持つ数列です。フィボナッチ数列と同様に、前の数値に基づいて次の数値を求める規則に従います。
生徒B: フィボナッチ数列は、前の2つの数値を足して次の数値を得るっていうことでしたよね?
講師: その通りです、生徒Bさん。フィボナッチ数列では、最初の2つの数値が1と1(または0と1)で、その後の数値は前の2つの数値を足して求めます。しかし、トリボナッチ数列では、前の3つの数値を足して次の数値を得るのです。
生徒C: つまり、最初の3つの数値が与えられれば、それ以降の数値を求めることができるんですね。
講師: 正解です、生徒Cさん。例えば、最初の3つの数値を1, 2, 3とすると、4番目の数値は1 + 2 + 3 = 6となります。そして、5番目の数値は2 + 3 + 6 = 11となります。このように、前の3つの数値を足して次の数値を求めるのがトリボナッチ数列の特徴です。
生徒A: なるほど、トリボナッチ数列は前の3つの数値に依存して次の数値を決めるんですね。でも、この数列にはどんな応用があるんですか?
講師: 素晴らしい質問です、生徒Aさん。トリボナッチ数列は実際にもさまざまな応用があります。例えば、自然界の一部の植物の成長パターンや、音楽のリズムパターン、さらには金融市場の動向など、様々な現象においてトリボナッチ数列の性質が見られることがあります。
生徒B: なるほど、トリボナッチ数列は私たちの周りで実際に活用されているんですね。興味深いです!
講師: そうですね、生徒Bさん。数学の中には私たちの身の回りに潜んでいる不思議な法則がたくさんあります。トリボナッチ数列もその一つです。
生徒C: トリボナッチ数列について学ぶことで、自然や社会の中で起こるパターンや規則性についても理解が深まりそうですね。
講師: その通りです、生徒Cさん。数学は単なる計算だけでなく、私たちの世界を深く理解するためのツールでもあります。トリボナッチ数列を通じて、数学の面白さや応用の広がりを感じていただければと思います。