A369950 Triangle read by rows: T(n,k) = number of j-covers of [n] with j<=k, k=1..2^n-1.

1, 1, 4, 5, 1, 13, 45, 80, 101, 108, 109, 1, 40, 361, 1586, 4505, 9482, 15913, 22348, 27353, 30356, 31721, 32176, 32281, 32296, 32297, 1, 121, 2681, 27671, 182777, 894103, 3491513, 11348063, 31483113, 75820263, 160485753, 301604003

Offset

1,3

Comments

Partial row sums of A055154.

Also, number of k-covers of [n] allowing for empty subsets.

For k-covers with disjoint subsets cf. A102661.

Links

Table of n, a(n) for n=1..38.

Formula

T(n,k) = Sum_{i=1..k} (1/i!)*Sum_{j=0..i} Stirling1(i+1, j+1)*(2^j-1)^n.

T(n,k) = Sum_{i=1..k} Sum_{j=0..n} (-1)^j*C(n, j)*C(2^(n-j)-1, i).

T(n,2^n-1) = A003465(n).

Example

Triangle (with rows n >= 1 and columns k >= 1) begins as follows:
 1;
 1, 4, 5;
 1, 13, 45, 80, 101, 108, 109;
 1, 40, 361, 1586, 4505, 9482, 15913, 22348, 27353, 30356, 31721, 32176, 32281, 32296, 32297;
 ...
There are T(3,2) = 13 covers of [3] consisting of up to 2 subsets (brackets and commas omitted):
 123
 123 1
 123 2
 123 3
 123 12
 123 13
 123 23
 12 13
 12 23
 13 23
 12 3
 13 2
 23 1

Mathematica

Flatten[Table[Sum[Sum[StirlingS1[i+1, j+1] (2^j-1)^n, {j, 0, i}]/i!, {i, k}], {n, 6}, {k, 2^n-1}]]

Crossrefs

Cf. A055154, A003465 (diagonal), A102661 (disjoint subsets).

Sequence in context: A206282 A082051 A196848 * A266699 A234937 A210590

Adjacent sequences: A369947 A369948 A369949 * A369951 A369952 A369953

Keyword

nonn,tabf

Author

Manfred Boergens, Feb 12 2024

Status

approved