login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A260881 Number of trapezoidal words of length n. 4
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 (list; graph; refs; listen; history; text; internal format)
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
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
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Aug 02 2015
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 09:28 EDT 2024. Contains 371268 sequences. (Running on oeis4.)