|
|
A225865
|
|
a(n) = 2^m minus (the total number of distinct subsets of length-(m-n) binary words that can appear as the factor of a word of length m, for 0 <= n < m/2).
|
|
1
|
|
|
0, 1, 5, 14, 38, 83, 191, 401, 849, 1740, 3600, 7285, 14845, 29938, 60486, 121686, 245046, 492090, 988782, 1983945, 3981105, 7982802, 16006686, 32080696, 64292920, 128812795, 258059003, 516891668, 1035249788, 2073167531
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
|
|
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}];
|
|
PROG
|
(Sage)
def A027375(i): return sum(moebius(i//d)*2^d for d in divisors(i))
return sum(A027375(i+1)*i/(i+1) for i in (1..n))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|