|
|
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
|
|
|
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)):
|
|
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}];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|