login
Number of n-covers of a labeled n-set.
13

%I #35 Jan 20 2024 14:53:14

%S 1,1,3,32,1225,155106,63602770,85538516963,386246934638991,

%T 6001601072676524540,327951891446717800997416,

%U 64149416776011080449232990868,45546527789182522411309599498741023,118653450898277491435912500458608964207578

%N Number of n-covers of a labeled n-set.

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

%H Andrew Howroyd, <a href="/A054780/b054780.txt">Table of n, a(n) for n = 0..50</a>

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

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

%F 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

%F a(n) ~ 2^(n^2) / n!. - _Vaclav Kotesovec_, Jun 04 2022

%F Inverse binomial transform of A367916. - _Gus Wiseman_, Dec 19 2023

%e From _Gus Wiseman_, Dec 19 2023: (Start)

%e Number of ways to choose n nonempty sets with union {1..n}. For example, the a(3) = 32 covers are:

%e {1}{2}{3} {1}{2}{13} {1}{2}{123} {1}{12}{123} {12}{13}{123}

%e {1}{2}{23} {1}{3}{123} {1}{13}{123} {12}{23}{123}

%e {1}{3}{12} {1}{12}{13} {1}{23}{123} {13}{23}{123}

%e {1}{3}{23} {1}{12}{23} {2}{12}{123}

%e {2}{3}{12} {1}{13}{23} {2}{13}{123}

%e {2}{3}{13} {2}{3}{123} {2}{23}{123}

%e {2}{12}{13} {3}{12}{123}

%e {2}{12}{23} {3}{13}{123}

%e {2}{13}{23} {3}{23}{123}

%e {3}{12}{13} {12}{13}{23}

%e {3}{12}{23}

%e {3}{13}{23}

%e (End)

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

%t Table[Length[Select[Subsets[Rest[Subsets[Range[n]]],{n}],Union@@#==Range[n]&]],{n,0,4}] (* _Gus Wiseman_, Dec 19 2023 *)

%o (PARI) a(n) = sum(k=0, n, (-1)^k*binomial(n, k)*binomial(2^(n-k)-1, n)) \\ _Andrew Howroyd_, Jan 20 2024

%Y Main diagonal of A055154.

%Y Cf. A048291, A088310, A181230, A259763.

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

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

%Y This is the covering case of A136556.

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

%Y Binomial transform is A367916.

%Y These set-systems have ranks A367917.

%Y The unlabeled version is A368186.

%Y A006129 counts covering graphs, connected A001187, unlabeled A002494.

%Y A046165 counts minimal covers, ranks A309326.

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

%K easy,nonn

%O 0,3

%A _Vladeta Jovovic_, May 21 2000