A102866 Number of finite languages over a binary alphabet (set of binary words of total length n).

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

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.

Row sums of A208741 and of A360634.

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