A260881 Number of trapezoidal words of length n.

1, 2, 4, 8, 16, 28, 46, 70, 102, 140, 190, 250, 318, 398, 496, 602, 724, 862, 1018, 1192, 1382, 1584, 1816, 2070, 2340, 2630, 2956, 3300, 3668, 4064, 4484, 4934, 5416, 5918, 6468, 7042, 7640, 8274, 8962, 9674, 10418, 11202, 12022, 12884, 13786, 14712, 15704, 16742, 17812, 18924, 20096

Offset

0,2

Comments

A word w is trapezoidal if it is defined over the alphabet {0,1} and if it contains, as a factor, at most one special factor of length k for each k. A factor (block) x is called "special" if both x0 and x1 appear in w.

There are many other characterizations. For example, a word is trapezoidal if there are at most k+1 distinct factors of length k for each n.

Links

Robert Israel, Table of n, a(n) for n = 0..10000

M. Bucci, A. De Luca, and G. Fici, Enumeration and structure of trapezoidal words, arXiv:1203.1203 [cs.FL], 2012.

M. Bucci, A. De Luca, and G. Fici, Enumeration and structure of trapezoidal words, Theoretical Computer Science 468 (2013) 12-22.

Formula

a(n) = 1 + Sum_{i=1..n}(n-i+1)*phi(i) + Sum_{i=0..floor((n-4)/2)}2*(n-2*i-3)*phi(i+2), where phi is the Euler phi function.

Example

For n = 5 we have a(5) = 28, since all binary strings of length 5 are trapezoidal except 00110, 01100, 10011, 11001.

Maple

f:= n -> 1 + add((n-i+1)*numtheory:-phi(i), i=1..n) + add(2*(n-2*i-3)*numtheory:-phi(i+2), i=0..floor((n-4)/2)):
map(f, [$1..100]); # Robert Israel, Aug 02 2015

Mathematica

a[n_] := 1+Sum[(n-i+1)EulerPhi[i], {i, 1, n}] + Sum[2(n-2i-3)EulerPhi[i+2], {i, 0, (n-4)/2}];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Sep 17 2018 *)

Crossrefs

Sequence in context: A280783 A104899 A057975 * A089055 A305122 A276677

Adjacent sequences: A260878 A260879 A260880 * A260882 A260883 A260884

Keyword

nonn

Author

Jeffrey Shallit, Aug 02 2015

Status

approved