login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A102866 Number of finite languages over a binary alphabet (set of binary words of total length n). 17
1, 2, 5, 16, 42, 116, 310, 816, 2121, 5466, 13937, 35248, 88494, 220644, 546778, 1347344, 3302780, 8057344, 19568892, 47329264, 114025786, 273709732, 654765342, 1561257968, 3711373005, 8797021714, 20794198581, 49024480880, 115292809910, 270495295636 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Analogous to A034899 (which also enumerates multisets of words)

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 64

Stefan Gerhold, Counting finite languages by total word length, INTEGERS 11 (2011), #A44.

Vaclav Kotesovec, A method of finding the asymptotics of q-series based on the convolution of generating functions, arXiv:1509.08708 [math.CO], Sep 30 2015, p. 27.

FORMULA

G.f.: exp(Sum((-1)^(j-1)/j*(2*z^j)/(1-2*z^j), j=1..infinity)).

Asymptotics (Gerhold, 2011): a(n) ~ c * 2^(n-1)*exp(2*sqrt(n)-1/2) / (sqrt(Pi) * n^(3/4)), where c = exp( Sum_{k>=2} (-1)^(k-1)/(k*(2^(k-1)-1) ) = 0.6602994483152065685... . - Vaclav Kotesovec, Sep 13 2014

Weigh transform of A000079. - Alois P. Heinz, Jun 25 2018

EXAMPLE

a(2) = 5 because the sets are {a,b}, {aa}, {ab}, {ba}, {bb}.

a(3) = 16 because the sets are {a,aa}, {a,ab}, {a,ba}, {a,bb}, {b,aa}, {b,ab}, {b,ba}, {b,bb}, {aaa}, {aab}, {aba}, {abb}, {baa}, {bab}, {bba}, {bbb}.

MAPLE

series(exp(add((-1)^(j-1)/j*(2*z^j)/(1-2*z^j), j=1..40)), z, 40);

MATHEMATICA

nn = 20; p = Product[(1 + x^i)^(2^i), {i, 1, nn}]; CoefficientList[Series[p, {x, 0, nn}], x] (* Geoffrey Critzer, Mar 07 2012 *)

CoefficientList[Series[E^Sum[(-1)^(k-1)/k*(2*x^k)/(1-2*x^k), {k, 1, 30}], {x, 0, 30}], x] (* Vaclav Kotesovec, Sep 13 2014 *)

CROSSREFS

Cf. A000079, A034899, A256142.

Column k=2 of A292804.

Sequence in context: A188947 A076958 A163825 * A148368 A148369 A148370

Adjacent sequences:  A102863 A102864 A102865 * A102867 A102868 A102869

KEYWORD

nonn

AUTHOR

Philippe Flajolet, Mar 01 2005

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 May 17 21:11 EDT 2021. Contains 343990 sequences. (Running on oeis4.)