A163353 - OEIS

%I #14 Apr 14 2024 03:45:47

%S 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,

%T 11408,12866,11440,8008,4368,1820,560,120,16,1,0,1,121,2680,27550,

%U 180096,866432,3308736,10453960,27991600,64472200,129002640,225783740,347370800,471435000,565722640,601080385,565722720,471435600,347373600

%N G.f.: A(x,y) = Sum_{n>=0,m>=0} (2^m-1)^n*x^n * log(1+y)^m/m!.

%C From _Manfred Boergens_, Apr 11 2024: (Start)

%C T(n,k) is the number of k-covers of [n] which may include one empty set; with [0] = {}.

%C 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.

%C For covers without an empty set see A055154. (End)

%H G. C. Greubel, <a href="/A163353/b163353.txt">Table of n, a(n) for the first 11 rows, flattened</a>

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

%F Row sums form A000371 (nondegenerate Boolean functions of n variables).

%F Main diagonal equals A134174 and is defined by the g.f.:

%F Sum_{n>=0} log(1 + (2^n-1)*x)^n/n!.

%F From _Manfred Boergens_, Apr 11 2024: (Start)

%F 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.

%F T(n,k) = C(2^n,k) for k > 2^(n-1).

%F T(n,k) < C(2^n,k) for k <= 2^(n-1), n > 0.

%F (Note: C(2^n,k) is the number of all k-subsets of P([n]).) (End)

%e Triangle begins:

%e 1,1;

%e 0,1,1;

%e 0,1,4,4,1;

%e 0,1,13,44,67,56,28,8,1;

%e 0,1,40,360,1546,4144,7896,11408,12866,11440,8008,4368,1820,560,120,16,1;

%e 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; ...

%t Table[Sum[(-1)^(n - j)*Binomial[n, j]*Binomial[2^j, k], {j, 0,

%t    n}], {n, 0, 5}, {k, 0, 2^n}]//Flatten (* _G. C. Greubel_, Dec 19 2016 *)

%o (PARI) T(n,k)=sum(j=0,n,(-1)^(n-j)*binomial(n,j)*binomial(2^j,k))

%Y Cf. A000371 (row sums), A134174 (main diagonal).

%K nonn,tabf

%O 0,8

%A _Paul D. Hanna_, Jul 25 2009