A216158 - OEIS

%I #36 Nov 22 2023 10:34:01

%S 0,2,6,24,72,220,652,1848,5160,14130,38102,101296,266328,692740,

%T 1785524,4563888,11577888,29170128,73032808,181793136,450100760,

%U 1108868820,2719167020,6639085968,16144137800,39107596850,94393612782,227062741160,544439640328,1301446217244

%N The total number of nonempty words in all length n finite languages on an alphabet of two letters.

%C A finite language is a set of distinct words with size being the total number of letters in all words.

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

%H Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, Cambridge Univ. Press, 2009, page 64.

%F a(n) = Sum_{k>0} k * A208741(n,k).

%e a(3) = 24 because the sets (languages) 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} where the distinct words are separated by commas.

%p h:= proc(n, i) option remember; `if`(n=0, [1, 0], `if`(i<1, 0, add(

%p       (p-> p+[0, p[1]*j])(binomial(2^i, j)*h(n-i*j, i-1)), j=0..n/i)))

%p     end:

%p a:= n-> h(n$2)[2]:

%p seq(a(n), n=0..30);  # _Alois P. Heinz_, Sep 24 2017

%t nn=30;p=Product[(1+y x^i)^(2^i),{i,1,nn}];CoefficientList[Series[D[p,y]/.y->1,{x,0,nn}],x]

%Y Cf. A102866.

%K nonn

%O 0,2

%A _Geoffrey Critzer_, Sep 03 2012