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

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.

Links

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

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

Example

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)

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

Prog

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

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.

Sequence in context: A355084 A202806 A368601 * A203323 A367565 A222683

Adjacent sequences: A054777 A054778 A054779 * A054781 A054782 A054783

Keyword

easy,nonn

Author

Vladeta Jovovic, May 21 2000

Status

approved