Fibonacci’s rabbits and domino tilings

Reproduces the rabbit problem from Fibonacci’s 1202 Liber Abaci, checks that the same numbers count domino tilings of a 2-by-n strip, and shows the ratio of successive terms approaching the golden ratio.

import matplotlib.pyplot as plt
import numpy as np

from mathematicskit.combinatorics import domino_tilings, fibonacci

Rabbit pairs month by month

# Liber Abaci starts from one pair and counts the pairs after each month.
print("month:       " + " ".join(f"{m:4d}" for m in range(0, 13)))
print("rabbit pairs:" + " ".join(f"{fibonacci(m + 2):4d}" for m in range(0, 13)))
print(f"after a year: {fibonacci(14)} pairs, Fibonacci's own answer")

month:          0    1    2    3    4    5    6    7    8    9   10   11   12
rabbit pairs:   1    2    3    5    8   13   21   34   55   89  144  233  377
after a year: 377 pairs, Fibonacci's own answer

Tilings of a 2-by-n strip

for n in range(1, 8):
    print(f"2 x {n} strip: {domino_tilings(n)} tilings")

2 x 1 strip: 1 tilings
2 x 2 strip: 2 tilings
2 x 3 strip: 3 tilings
2 x 4 strip: 5 tilings
2 x 5 strip: 8 tilings
2 x 6 strip: 13 tilings
2 x 7 strip: 21 tilings

Ratios converge to the golden ratio

n = np.arange(2, 30)
ratios = [fibonacci(k + 1) / fibonacci(k) for k in n]
phi = (1 + np.sqrt(5)) / 2
fig, ax = plt.subplots()
ax.semilogy(n, [abs(r - phi) for r in ratios], "o-")
ax.set_xlabel("n")
ax.set_ylabel(r"$|F_{n+1}/F_n - \varphi|$")
ax.set_title("Successive ratios approach the golden ratio")

Text(0.5, 1.0, 'Successive ratios approach the golden ratio')