A055154 - OEIS

%I #28 Apr 16 2024 13:48:04

%S 1,1,3,1,1,12,32,35,21,7,1,1,39,321,1225,2919,4977,6431,6435,5005,

%T 3003,1365,455,105,15,1,1,120,2560,24990,155106,711326,2597410,

%U 7856550,20135050,44337150,84665490,141118250,206252550,265182450,300540190

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

%C Row sums give A003465.

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

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

%C For covers which may include one empty set see A163353.

%C For disjoint covers see A008277. (End)

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

%H Alois P. Heinz, <a href="/A055154/b055154.txt">Rows n = 1..10, flattened</a>

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

%F From _Vladeta Jovovic_, May 30 2004: (Start)

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

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

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

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

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

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

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

%e Triangle begins:

%e   [1],

%e   [1,3,1],

%e   [1,12,32,35,21,7,1],

%e   ...

%e There are 35 4-covers of a labeled 3-set.

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

%Y Cf. A054780, A055621.

%Y Cf. A369950 (partial row sums).

%Y Columns: A029858, A095152, A095153, A095155.

%K easy,nonn,tabf

%O 1,3

%A _Vladeta Jovovic_, Jun 14 2000