cp's OEIS Frontend

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

%I A102866 #42 Aug 31 2024 19:17:44
%S A102866 1,2,5,16,42,116,310,816,2121,5466,13937,35248,88494,220644,546778,
%T A102866 1347344,3302780,8057344,19568892,47329264,114025786,273709732,
%U A102866 654765342,1561257968,3711373005,8797021714,20794198581,49024480880,115292809910,270495295636
%N A102866 Number of finite languages over a binary alphabet (set of nonempty binary words of total length n).
%C A102866 Analogous to A034899 (which also enumerates multisets of words)
%H A102866 Alois P. Heinz, <a href="/A102866/b102866.txt">Table of n, a(n) for n = 0..1000</a>
%H A102866 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 64
%H A102866 Stefan Gerhold, <a href="http://www.emis.de/journals/INTEGERS/papers/l44/l44.pdf">Counting finite languages by total word length</a>, INTEGERS 11 (2011), #A44.
%H A102866 Vaclav Kotesovec, <a href="http://arxiv.org/abs/1509.08708">A method of finding the asymptotics of q-series based on the convolution of generating functions</a>, arXiv:1509.08708 [math.CO], Sep 30 2015, p. 27.
%F A102866 G.f.: exp(Sum((-1)^(j-1)/j*(2*z^j)/(1-2*z^j), j=1..infinity)).
%F A102866 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
%F A102866 Weigh transform of A000079. - _Alois P. Heinz_, Jun 25 2018
%e A102866 a(2) = 5 because the sets are {a,b}, {aa}, {ab}, {ba}, {bb}.
%e A102866 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}.
%p A102866 series(exp(add((-1)^(j-1)/j*(2*z^j)/(1-2*z^j),j=1..40)),z,40);
%t A102866 nn = 20; p = Product[(1 + x^i)^(2^i), {i, 1, nn}]; CoefficientList[Series[p, {x, 0, nn}], x] (* _Geoffrey Critzer_, Mar 07 2012 *)
%t A102866 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 *)
%Y A102866 Cf. A000079, A034899, A256142.
%Y A102866 Column k=2 of A292804.
%Y A102866 Row sums of A208741 and of A360634.
%K A102866 nonn
%O A102866 0,2
%A A102866 _Philippe Flajolet_, Mar 01 2005