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

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

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

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

Sequence in context: A350037 A070430 A336302 * A164612 A309748 A180401

Adjacent sequences: A163350 A163351 A163352 * A163354 A163355 A163356

Keyword

nonn,tabf,changed

Author

Paul D. Hanna, Jul 25 2009

Status

approved