A055154 Triangle read by rows: T(n,k) = number of k-covers of a labeled n-set, k=1..2^n-1.

1, 1, 3, 1, 1, 12, 32, 35, 21, 7, 1, 1, 39, 321, 1225, 2919, 4977, 6431, 6435, 5005, 3003, 1365, 455, 105, 15, 1, 1, 120, 2560, 24990, 155106, 711326, 2597410, 7856550, 20135050, 44337150, 84665490, 141118250, 206252550, 265182450, 300540190

Offset: 1

Author

Vladeta Jovovic, Jun 14 2000

Keywords

• easy
• nonn
• tabf

Comments

Row sums give A003465.

From Manfred Boergens, Apr 11 2024: (Start)

If more than half of the nonempty subsets of [n] are drawn their union covers [n] (see Formula). - The proof is based on 2^(n-1)-1 being the number of nonempty subsets of [n] with one fixed element of [n] missing.

For covers which may include one empty set see A163353.

For disjoint covers see A008277.

For disjoint covers which may include one empty set see A256894 (amendment by Manfred Boergens, Mar 09 2025). (End)

Examples

			Triangle begins:
  [1],
  [1,3,1],
  [1,12,32,35,21,7,1],
  ...
There are 35 4-covers of a labeled 3-set.
		

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 165.

Links

• Alois P. Heinz, Rows n = 1..10, flattened

Crossrefs

Cf. A054780, A055621.

Cf. A369950 (partial row sums).

Cf. 256894.

Columns: A029858, A095152, A095153, A095155.

Programs

Mathematica

nn=5;Map[Select[#,#>0&]&,Transpose[Table[Table[Sum[(-1)^j Binomial[n,j] Binomial[2^(n-j)-1,m],{j,0,n}],{n,1,nn}],{m,1,2^nn-1}]]]//Grid (* Geoffrey Critzer, Jun 27 2013 *)

Formula

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

From Vladeta Jovovic, May 30 2004: (Start)

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

E.g.f.: Sum(exp(y*(2^n-1))*log(1+x)^n/n!, n=0..infinity)/(1+x). (End)

Also exp(-y)*Sum((1+x)^(2^n-1)*y^n/n!, n=0..infinity).

From Manfred Boergens, Apr 11 2024: (Start)

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

T(n,k) < C(2^n-1,k) for k<2^(n-1).

(Note: C(2^n-1,k) is the number of all k-subsets of P([n])\{{}}.) (End)