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