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

0, 2, 6, 24, 72, 220, 652, 1848, 5160, 14130, 38102, 101296, 266328, 692740, 1785524, 4563888, 11577888, 29170128, 73032808, 181793136, 450100760, 1108868820, 2719167020, 6639085968, 16144137800, 39107596850, 94393612782, 227062741160, 544439640328, 1301446217244

Offset: 0

Author

Geoffrey Critzer, Sep 03 2012

Keywords

• nonn

Comments

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

Examples

			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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 64.

Crossrefs

Cf. A102866.

Programs

Maple

h:= proc(n, i) option remember; `if`(n=0, [1, 0], `if`(i<1, 0, add(
      (p-> p+[0, p[1]*j])(binomial(2^i, j)*h(n-i*j, i-1)), j=0..n/i)))
    end:
a:= n-> h(n$2)[2]:
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 24 2017

Mathematica

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

Formula

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