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

Author

Manfred Boergens, Feb 12 2024

Keywords

• nonn
• tabf

Comments

Partial row sums of A055154.

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

Amendments by Manfred Boergens, Mar 09 2025: (Start)

For covers which may include one empty set see A381683.

For disjoint covers see A102661.

For disjoint covers which may include one empty set see A381682. (End)

Examples

			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
		

Links

• John Tyler Rascoe, Rows n = 1..9, flattened

Crossrefs

Cf. A055154, A003465 (diagonal), A102661, A381682, A381683.

Programs

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}]]

Python

from math import comb
def A369950(n,k): return sum((-1)**j*comb(n, j)*comb(2**(n-j)-1, i) for j in range(n+1) for i in range(1,k+1)) # John Tyler Rascoe, Mar 06 2025

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).