login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%I #42 Aug 31 2024 19:17:44

%S 1,2,5,16,42,116,310,816,2121,5466,13937,35248,88494,220644,546778,

%T 1347344,3302780,8057344,19568892,47329264,114025786,273709732,

%U 654765342,1561257968,3711373005,8797021714,20794198581,49024480880,115292809910,270495295636

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

%C Analogous to A034899 (which also enumerates multisets of words)

%H Alois P. Heinz, <a href="/A102866/b102866.txt">Table of n, a(n) for n = 0..1000</a>

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 64

%H 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 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 G.f.: exp(Sum((-1)^(j-1)/j*(2*z^j)/(1-2*z^j), j=1..infinity)).

%F 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 Weigh transform of A000079. - _Alois P. Heinz_, Jun 25 2018

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

%e 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 series(exp(add((-1)^(j-1)/j*(2*z^j)/(1-2*z^j),j=1..40)),z,40);

%t 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 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 Cf. A000079, A034899, A256142.

%Y Column k=2 of A292804.

%Y Row sums of A208741 and of A360634.

%K nonn

%O 0,2

%A _Philippe Flajolet_, Mar 01 2005