A338760 Subword complexity of the infinite word Product_{i>=1} Product_{j=1..i} a^(i-j+1) b^j.

1, 2, 4, 8, 15, 28, 47, 73, 107, 150, 203, 267, 343, 432, 535, 653, 787, 938, 1107, 1295, 1503, 1732, 1983, 2257, 2555, 2878, 3227, 3603, 4007, 4440, 4903, 5397, 5923, 6482, 7075, 7703, 8367, 9068, 9807, 10585, 11403, 12262, 13163, 14107, 15095, 16128, 17207

Offset

0,2

Comments

The infinite word is (ab)(aab.abb)(aaab.aabb.abbb)(aaaab.aaabb.aabbb.abbbb)... . Subword complexity is the number of distinct length-n blocks appearing in the sequence.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..10000

Luke Schaeffer and Kaiyo Wu, Two Infinite Words with Cubic Subword Complexity, J. Integer Sequences 23 (2020), Article 20.10.8.

Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Formula

Equal to 2^n for n <= 3, and n^3/6+n^2/2-5*n/3+3 = A074742(n-1) for n >= 4.

G.f.: (1 - 2*x + 2*x^2 + 2*x^5 - 3*x^6 + x^7)/(1 - x)^4. - Andrew Howroyd, Nov 05 2025

Example

For n=4 the only word omitted is baba.

Crossrefs

Cf. A074742, A338761.

Sequence in context: A284275 A054159 A222028 * A056181 A101976 A339656

Adjacent sequences: A338757 A338758 A338759 * A338761 A338762 A338763

Keyword

nonn,easy

Author

Jeffrey Shallit, Nov 07 2020

Status

approved