A208741 Triangular array read by rows. T(n,k) is the number of sets of exactly k distinct binary words with a total of n letters.

2, 4, 1, 8, 8, 16, 22, 4, 32, 64, 20, 64, 156, 84, 6, 128, 384, 264, 40, 256, 888, 784, 189, 4, 512, 2048, 2152, 704, 50, 1024, 4592, 5664, 2384, 272, 1, 2048, 10240, 14368, 7328, 1232, 32, 4096, 22496, 35568, 21382, 4704, 248

Offset

1,1

Comments

Equivalently, T(n,k) is the number of integer partitions of n into distinct parts with two types of 1's, four types of 2's, ... , 2^i types of i's,...; where k is the number of summands (of any type).

Row sums = A102866.

Row lengths increase by 1 at n=A061168(offset).

Links

Alois P. Heinz, Rows n = 0..300, flattened

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 64

Formula

O.g.f.: Product_{i>=1} (1 + y*x^i)^(2^i).

Example

T(3,2) = 8 because we have: {a,aa}, {a,ab}, {a,ba}, {a,bb}, {b,aa}, {b,ab}, {b,ba}, {b,bb}; 2 word languages with total length 3.
Triangle T(n,k) begins:
   2;
   4,     1;
   8,     8;
  16,    22,    4;
  32,    64,   20;
  64,   156,   84,   6;
  ...

Maple

h:= proc(n, i) option remember; expand(`if`(n=0, 1, `if`(i<1, 0,
      add(h(n-i*j, i-1)*binomial(2^i, j)*x^j, j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(h(n$2)):
seq(T(n), n=1..15);  # Alois P. Heinz, Sep 24 2017

Mathematica

nn=12; p=Product[(1+y x^i)^(2^i), {i, 1, nn}]; f[list_] := Select[list, #>0&]; Map[f, Drop[CoefficientList[Series[p[x, y], {x, 0, nn}], {x, y}], 1]]//Flatten

Crossrefs

Cf. A102866, A209406, A360634.

Sequence in context: A193034 A254179 A328641 * A335957 A057115 A065276

Adjacent sequences: A208738 A208739 A208740 * A208742 A208743 A208744

Keyword

nonn,tabf

Author

Geoffrey Critzer, Mar 08 2012

Status

approved