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,3

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. (End)

References

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

Links

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

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)

Example

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

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 *)

Crossrefs

Cf. A054780, A055621.

Cf. A369950 (partial row sums).

Columns: A029858, A095152, A095153, A095155.

Sequence in context: A209424 A129619 A094573 * A338875 A015112 A174690

Adjacent sequences: A055151 A055152 A055153 * A055155 A055156 A055157

Keyword

easy,nonn,tabf

Author

Vladeta Jovovic, Jun 14 2000

Status

approved