OFFSET
0,3
LINKS
Shuo Tan and Jeffrey Shallit, Sets represented as the length-n factors of a word, preprint, arXiv:1304.3666 [cs.FL], 2013.
FORMULA
a(n) = Sum_{i=1..n+1} (i-1)*L(i), where L(i) is the number of Lyndon words of length i (sequence A001037).
EXAMPLE
a(2) = 5, because (for example) there are 2^5 - 5 = 27 distinct subsets of length 3 words arising as the subwords of a binary word of length 5.
MATHEMATICA
a27375[i_] := Sum[MoebiusMu[i/d]*2^d, {d, Divisors[i]}];
a[n_] := Sum[a27375[i+1] i/(i+1), {i, 1, n}];
Table[a[n], {n, 0, 29}] (* Jean-François Alcover, Jul 14 2018, after Peter Luschny *)
PROG
(Sage)
def A027375(i): return sum(moebius(i//d)*2^d for d in divisors(i))
def A225865(n):
return sum(A027375(i+1)*i/(i+1) for i in (1..n))
[A225865(n) for n in (0..30)] # Peter Luschny, May 18 2013
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, May 18 2013
STATUS
approved