cp's OEIS Frontend

A260881 Number of trapezoidal words of length n.

%I A260881 #20 Sep 17 2018 09:23:05
%S A260881 1,2,4,8,16,28,46,70,102,140,190,250,318,398,496,602,724,862,1018,
%T A260881 1192,1382,1584,1816,2070,2340,2630,2956,3300,3668,4064,4484,4934,
%U A260881 5416,5918,6468,7042,7640,8274,8962,9674,10418,11202,12022,12884,13786,14712,15704,16742,17812,18924,20096
%N A260881 Number of trapezoidal words of length n.
%C A260881 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.
%C A260881 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.
%H A260881 Robert Israel, <a href="/A260881/b260881.txt">Table of n, a(n) for n = 0..10000</a>
%H A260881 M. Bucci, A. De Luca, and G. Fici, <a href="https://arxiv.org/abs/1203.1203">Enumeration and structure of trapezoidal words</a>, arXiv:1203.1203 [cs.FL], 2012.
%H A260881 M. Bucci, A. De Luca, and G. Fici, <a href="https://doi.org/10.1016/j.tcs.2012.11.007">Enumeration and structure of trapezoidal words</a>, Theoretical Computer Science  468 (2013) 12-22.
%F A260881 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.
%e A260881 For n = 5 we have a(5) = 28, since all binary strings of length 5 are trapezoidal except 00110, 01100, 10011, 11001.
%p A260881 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)):
%p A260881 map(f, [$1..100]); # _Robert Israel_, Aug 02 2015
%t A260881 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}];
%t A260881 Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Sep 17 2018 *)
%K A260881 nonn
%O A260881 0,2
%A A260881 _Jeffrey Shallit_, Aug 02 2015