login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Table of n, a(n) for n=0..29.

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 A225865(n):

    A027375 = lambda i: sum(moebius(i/d)*2^d for d in divisors(i))

    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

Cf. A001037.

Sequence in context: A270452 A270463 A183898 * A319648 A111715 A024525

Adjacent sequences:  A225862 A225863 A225864 * A225866 A225867 A225868

KEYWORD

nonn

AUTHOR

Jeffrey Shallit, May 18 2013

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 22 11:46 EDT 2019. Contains 322330 sequences. (Running on oeis4.)