A102866 Number of finite languages over a binary alphabet (set of nonempty 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
Keywords
Examples
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}.
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.
Programs
-
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 *)
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
Comments