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

%I #30 Mar 12 2024 23:47:15

%S 1,1,4,5,1,13,45,80,101,108,109,1,40,361,1586,4505,9482,15913,22348,

%T 27353,30356,31721,32176,32281,32296,32297,1,121,2681,27671,182777,

%U 894103,3491513,11348063,31483113,75820263,160485753,301604003

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

%C Partial row sums of A055154.

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

%C For k-covers with disjoint subsets cf. A102661.

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

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

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

%e Triangle (with rows n >= 1 and columns k >= 1) begins as follows:

%e 1;

%e 1, 4, 5;

%e 1, 13, 45, 80, 101, 108, 109;

%e 1, 40, 361, 1586, 4505, 9482, 15913, 22348, 27353, 30356, 31721, 32176, 32281, 32296, 32297;

%e ...

%e There are T(3,2) = 13 covers of [3] consisting of up to 2 subsets (brackets and commas omitted):

%e 123

%e 123 1

%e 123 2

%e 123 3

%e 123 12

%e 123 13

%e 123 23

%e 12 13

%e 12 23

%e 13 23

%e 12 3

%e 13 2

%e 23 1

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

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

%K nonn,tabf

%O 1,3

%A _Manfred Boergens_, Feb 12 2024