A290222 Multiset transform of A011782, powers of 2: 1, 2, 4, 8, 16, ...

1, 0, 1, 0, 2, 1, 0, 4, 2, 1, 0, 8, 7, 2, 1, 0, 16, 16, 7, 2, 1, 0, 32, 42, 20, 7, 2, 1, 0, 64, 96, 54, 20, 7, 2, 1, 0, 128, 228, 140, 59, 20, 7, 2, 1, 0, 256, 512, 360, 156, 59, 20, 7, 2, 1, 0, 512, 1160, 888, 422, 162, 59, 20, 7, 2, 1, 0, 1024, 2560, 2168, 1088, 442, 162, 59, 20, 7, 2, 1

Offset: 0

Author

M. F. Hasler, Jul 24 2017

Keywords

• nonn
• tabl

Comments

T(n,k) is the number of multisets of exactly k binary words with a total of n letters and each word beginning with 1. T(4,2) = 7: {1,100}, {1,101}, {1,110}, {1,111}, {10,10}, {10,11}, {11,11}. - Alois P. Heinz, Sep 18 2017

Examples

			The triangle starts:
1;
0    1;
0    2    1;
0    4    2    1;
0    8    7    2    1;
0   16   16    7    2   1;
0   32   42   20    7   2   1;
0   64   96   54   20   7   2  1;
0  128  228  140   59  20   7  2  1;
0  256  512  360  156  59  20  7  2  1;
0  512 1160  888  422 162  59 20  7  2  1;
0 1024 2560 2168 1088 442 162 59 20  7  2  1;
(...)
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened
• Index entries for triangles generated by the Multiset Transformation

Crossrefs

Cf. A034691 (row sums), A000007 (column k=0), A011782 (column k=1), A178945(n-1) (column k=2).

The reverse of the n-th row converges to A034899.

Cf. A000079, A209406, A292506.

Programs

Maple

b:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
      `if`(min(i, p)<1, 0, add(binomial(2^(i-1)+j-1, j)*
         b(n-i*j, i-1, p-j), j=0..min(n/i, p)))))
    end:
T:= (n, k)-> b(n$2, k):
seq(seq(T(n, k), k=0..n), n=0..14);  # Alois P. Heinz, Sep 12 2017

Mathematica

b[n_, i_, p_] := b[n, i, p] = If[p > n, 0, If[n == 0, 1, If[Min[i, p] < 1, 0, Sum[Binomial[2^(i - 1) + j - 1, j] b[n - i j, i - 1, p - j], {j, 0, Min[n/i, p]}]]]];
T[n_, k_] := b[n, n, k];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 14}] // Flatten (* Jean-François Alcover, Dec 07 2019, after Alois P. Heinz *)

Formula

G.f.: 1 / Product_{j>=1} (1-y*x^j)^(2^(j-1)). - Alois P. Heinz, Sep 18 2017