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

Author

Jeffrey Shallit, Aug 02 2015

Keywords

• nonn

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.

Examples

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

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.

Programs

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

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.