A116576 - OEIS

%I #14 Dec 17 2017 07:35:01

%S 2,7,17,35,69,132,248,462,856,1581,2915,5369,9883,18186,33458,61548,

%T 113214,208243,383029,704511,1295809,2383376,4383724,8062938,14830068,

%U 27276761,50169799,92276661,169723255,312169750,574169702,1056062744

%N 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.

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

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

%F 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, ...).

%F Empirical G.f.: x^4*(2*x^3-x-2) / ((x-1)^2*(x^3+x^2+x-1)). [_Colin Barker_, Dec 02 2012]

%e D(4) = 2 because the 4th iterate of the tribonacci morphism on a is abacabaabacab, which contains the two squares aa and abaaba.

%e 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.

%t 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 *)

%o (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));

%Y Cf. A080843. [_Robert G. Wilson v_, Nov 07 2010]

%K nonn,uned

%O 4,1

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