OFFSET
0,8
COMMENTS
From Manfred Boergens, Apr 11 2024: (Start)
T(n,k) is the number of k-covers of [n] which may include one empty set; with [0] = {}.
For n > 0: If more than half of the subsets of [n] are drawn their union covers [n] (see Formula). - The proof is based on 2^(n-1) being the number of subsets of [n] with one fixed element of [n] missing.
For covers without an empty set see A055154. (End)
LINKS
G. C. Greubel, Table of n, a(n) for the first 11 rows, flattened
FORMULA
T(n,k) = Sum_{j=0..n} (-1)^(n-j)*C(n,j)*C(2^j,k), k=0..2^n.
Row sums form A000371 (nondegenerate Boolean functions of n variables).
Main diagonal equals A134174 and is defined by the g.f.:
Sum_{n>=0} log(1 + (2^n-1)*x)^n/n!.
From Manfred Boergens, Apr 11 2024: (Start)
T(n,k) = A055154(n,k) + A055154(n,k-1) for n > 0, k > 0; A055154(n,j) are not defined for j = 0 and j = 2^n and are set = 0.
T(n,k) = C(2^n,k) for k > 2^(n-1).
T(n,k) < C(2^n,k) for k <= 2^(n-1), n > 0.
(Note: C(2^n,k) is the number of all k-subsets of P([n]).) (End)
EXAMPLE
Triangle begins:
1,1;
0,1,1;
0,1,4,4,1;
0,1,13,44,67,56,28,8,1;
0,1,40,360,1546,4144,7896,11408,12866,11440,8008,4368,1820,560,120,16,1;
0,1,121,2680,27550,180096,866432,3308736,10453960,27991600,64472200,129002640,225783740,347370800,471435000,565722640,601080385,565722720,471435600,347373600,225792840,129024480,64512240,28048800,10518300,3365856,906192,201376,35960,4960,496,32,1; ...
MATHEMATICA
Table[Sum[(-1)^(n - j)*Binomial[n, j]*Binomial[2^j, k], {j, 0,
n}], {n, 0, 5}, {k, 0, 2^n}]//Flatten (* G. C. Greubel, Dec 19 2016 *)
PROG
(PARI) T(n, k)=sum(j=0, n, (-1)^(n-j)*binomial(n, j)*binomial(2^j, k))
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Paul D. Hanna, Jul 25 2009
STATUS
approved