A116576 Number of distinct squares D(n) in the n-th iterate of the tribonacci morphism (a -> ab, b -> ac, c -> a) on the letter a.

2, 7, 17, 35, 69, 132, 248, 462, 856, 1581, 2915, 5369, 9883, 18186, 33458, 61548, 113214, 208243, 383029, 704511, 1295809, 2383376, 4383724, 8062938, 14830068, 27276761, 50169799, 92276661, 169723255, 312169750, 574169702, 1056062744

Offset

4,1

Comments

See the cited reference (A. Glen) for similar sequences associated to the k-bonacci morphism and particular episturmian (infinite) words.

References

Amy Glen, On Sturmian and episturmian words and related topics, Ph.D. Thesis, The University of Adelaide (Australia), April 2006.

Links

Table of n, a(n) for n=4..35.

Formula

For n >= 6, D(n) = d(n-5) + d(n-6) + 1 + Sum (d(m) + 1), m = 0 ... (n-3), where d(m) = (T(m+1) + T(m-1) - 1)/2 - 1 and the T(m) are the tribonacci numbers: (T(0), T(1), T(2), ...) = (1, 2, 4, 7, 13, ...).

Empirical G.f.: x^4*(2*x^3-x-2) / ((x-1)^2*(x^3+x^2+x-1)). [Colin Barker, Dec 02 2012]

Example

D(4) = 2 because the 4th iterate of the tribonacci morphism on a is abacabaabacab, which contains the two squares aa and abaaba.
D(5) = 7 because the 5th iterate of the tribonacci morphism on a is abacabaabacababacabaabac, which contains the square of each of the following seven strings: a, ab, ba, aba, abacab, bacaba, abacaba.

Mathematica

a[1] = 1; a[2] = 2; a[3] = 4; a[n_] := a[n] = a[n - 1] + a[n - 2] + a[n - 3]; b[1] = 0; b[n_] := b[n] = (a[n - 1] + a[n + 1] - 1)/2 - 1; c[4] = 2; c[5] = 7; c[n_] := b[n - 4] + b[n - 5] + n - 1 + Sum[b[i], {i, n - 2}]; Array[c, 32, 4] (* Robert G. Wilson v, Nov 07 2010 *)

Prog

(MATLAB) T(1) = 1; T(2) = 2; T(3) = 4; for n = 4 : 100 T(n) = T(n-1) + T(n-2) + T(n-3); end; d(1) = 0; for n = 2 : 50 d(n) = (T(n+1) + T(n-1) - 1)/2 - 1; end; D(4) = 2; D(5) = 7; for n = 6 : 50 D(n) = d(n-4) + d(n-5) + 1 + sum(d(1:(n-2))) + (n - 2); end; disp(num2str(D));

Crossrefs

Cf. A080843. [Robert G. Wilson v, Nov 07 2010]

Sequence in context: A070070 A318054 A033937 * A086717 A023657 A045380

Adjacent sequences: A116573 A116574 A116575 * A116577 A116578 A116579

Keyword

nonn,uned

Author

Amy Glen (amy.glen(AT)gmail.com), Apr 07 2006

Status

approved