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,2

Comments

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

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.

Formula

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

Example

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.

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]

Crossrefs

Cf. A102866.

Sequence in context: A338614 A087645 A174700 * A178847 A173844 A107761

Adjacent sequences: A216155 A216156 A216157 * A216159 A216160 A216161

Keyword

nonn

Author

Geoffrey Critzer, Sep 03 2012

Status

approved