トリボナッチ数

Tribonacci numbers answer an obvious follow-up question: what if each term sums the three before it rather than the two? The underlying mathematics is old. Linear recurrences with constant coefficients were well understood by the eighteenth century, when Abraham de Moivre developed generating-function techniques for them and Daniel Bernoulli showed that the ratio of consecutive terms of such a sequence converges to the largest root of its characteristic equation — the general fact that makes every sequence of this shape grow geometrically.

The name, though, is recent, and its author is unexpected. "Tribonacci" was coined in 1963 by Mark Feinberg, then a fourteen-year-old high-school student in Philadelphia, in a short article for the first volume of The Fibonacci Quarterly. The journal had only just been founded, by Verner E. Hoggatt Jr. of San Jose State College and Brother Alfred Brousseau of St Mary's College, who also set up the Fibonacci Association that year and were glad to print work by schoolchildren. Feinberg tabulated the sequence and computed the limiting ratio of successive terms, 1.839…, now called the tribonacci constant.

That constant is where the real interest lies. It is the unique real root of x³ = x² + x + 1, an algebraic number of degree three. Its two complex conjugates have modulus roughly 0.737 — comfortably less than one, which makes it a Pisot number and explains why the terms lock into near-perfect geometric growth after only a handful of steps. Unlike the golden ratio it has no expression in square roots alone, but it does have a closed form in cube roots. It also shows up in solid geometry, in the coordinates of the snub cube, and at the centre of a self-similar tiling: Gérard Rauzy's 1982 study of the substitution a→ab, b→ac, c→a produced the figure now known as the Rauzy fractal.

主な性質

• T(0) = 0, T(1) = T(2) = 1, and T(n) = T(n−1) + T(n−2) + T(n−3) for n ≥ 3.
• The ratio of consecutive terms converges to the tribonacci constant ≈ 1.8392867552141612, the real root of x³ = x² + x + 1.
• That constant has the closed form (1 + ∛(19 + 3√33) + ∛(19 − 3√33)) / 3, and satisfies the tidy identity t + t⁻³ = 2 exactly.
• Its two other (complex) roots have modulus 1/√t ≈ 0.7374, below 1, so the constant is a Pisot number.
• T(n) is even exactly when n ≡ 0 or 3 (mod 4): the parity pattern repeats with period four.
• T(0) + T(1) + … + T(n) = (T(n+2) + T(n) − 1) / 2, so any partial sum is available in one step.
• T(n+1) counts the ordered ways to write n as a sum of 1s, 2s and 3s: n = 4 has T(5) = 7 such sums.
• T(63) = 15,832,480,722,303,616 is the first term above 2⁵³ − 1, so this page computes with arbitrary-precision integers.

登場する場面

• The staircase problem — how many ways to climb n steps taking 1, 2 or 3 at a time — is exactly this sequence, which is why it is a fixture of dynamic-programming courses and coding interviews.
• The number of binary strings of length n containing no run of three consecutive 1s is T(n+2), a constraint that shows up in run-length-limited channel coding.
• The tribonacci constant governs the geometry of the snub cube, one of the thirteen Archimedean solids: its vertex coordinates are built from that root.
• The tribonacci substitution a→ab, b→ac, c→a generates the tribonacci word and the Rauzy fractal, objects used in symbolic dynamics and in the study of aperiodic order and quasicrystals.
• Tribonacci is the k = 3 case of the k-step Fibonacci family; as k grows the limiting ratio climbs from φ ≈ 1.618 towards 2, which is why doubling sequences are the limit of this construction.