A054780 Number of n-covers of a labeled n-set.

1, 1, 3, 32, 1225, 155106, 63602770, 85538516963, 386246934638991, 6001601072676524540, 327951891446717800997416, 64149416776011080449232990868, 45546527789182522411309599498741023, 118653450898277491435912500458608964207578

Offset: 0

Author

Vladeta Jovovic, May 21 2000

Keywords

• easy
• nonn

Comments

Also, number of n X n rational {0,1}-matrices with no zero rows or columns and with all rows distinct, up to permutation of rows.

Examples

			From _Gus Wiseman_, Dec 19 2023: (Start)
Number of ways to choose n nonempty sets with union {1..n}. For example, the a(3) = 32 covers are:
  {1}{2}{3}  {1}{2}{13}  {1}{2}{123}  {1}{12}{123}  {12}{13}{123}
             {1}{2}{23}  {1}{3}{123}  {1}{13}{123}  {12}{23}{123}
             {1}{3}{12}  {1}{12}{13}  {1}{23}{123}  {13}{23}{123}
             {1}{3}{23}  {1}{12}{23}  {2}{12}{123}
             {2}{3}{12}  {1}{13}{23}  {2}{13}{123}
             {2}{3}{13}  {2}{3}{123}  {2}{23}{123}
                         {2}{12}{13}  {3}{12}{123}
                         {2}{12}{23}  {3}{13}{123}
                         {2}{13}{23}  {3}{23}{123}
                         {3}{12}{13}  {12}{13}{23}
                         {3}{12}{23}
                         {3}{13}{23}
(End)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..50

Crossrefs

Main diagonal of A055154.

Cf. A048291, A088310, A181230, A259763.

Covers with any number of edges are counted by A003465, unlabeled A055621.

Connected graphs of this type are counted by A057500, unlabeled A001429.

This is the covering case of A136556.

The case of graphs is A367863, covering case of A116508, unlabeled A006649.

Binomial transform is A367916.

These set-systems have ranks A367917.

The unlabeled version is A368186.

A006129 counts covering graphs, connected A001187, unlabeled A002494.

A046165 counts minimal covers, ranks A309326.

Cf. A006126, A058891, A059201, A133686, A323816, A323817, A323818, A326754, A367862, A367901.

Programs

Mathematica

Join[{1}, Table[Sum[StirlingS1[n+1, k+1]*(2^k - 1)^n, {k, 0, n}]/n!, {n, 1, 15}]] (* Vaclav Kotesovec, Jun 04 2022 *)
Table[Length[Select[Subsets[Rest[Subsets[Range[n]]],{n}],Union@@#==Range[n]&]],{n,0,4}] (* Gus Wiseman, Dec 19 2023 *)

PARI

a(n) = sum(k=0, n, (-1)^k*binomial(n, k)*binomial(2^(n-k)-1, n)) \\ Andrew Howroyd, Jan 20 2024

Formula

a(n) = Sum_{k=0..n} (-1)^k*binomial(n, k)*binomial(2^(n-k)-1, n).

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

G.f.: Sum_{n>=0} log(1+(2^n-1)*x)^n/((1+(2^n-1)*x)*n!). - Paul D. Hanna and Vladeta Jovovic, Jan 16 2008

a(n) ~ 2^(n^2) / n!. - Vaclav Kotesovec, Jun 04 2022

Inverse binomial transform of A367916. - Gus Wiseman, Dec 19 2023