cp's OEIS Frontend

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

%I A054780 #35 Jan 20 2024 14:53:14
%S A054780 1,1,3,32,1225,155106,63602770,85538516963,386246934638991,
%T A054780 6001601072676524540,327951891446717800997416,
%U A054780 64149416776011080449232990868,45546527789182522411309599498741023,118653450898277491435912500458608964207578
%N A054780 Number of n-covers of a labeled n-set.
%C A054780 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 A054780 Andrew Howroyd, <a href="/A054780/b054780.txt">Table of n, a(n) for n = 0..50</a>
%F A054780 a(n) = Sum_{k=0..n} (-1)^k*binomial(n, k)*binomial(2^(n-k)-1, n).
%F A054780 a(n) = (1/n!)*Sum_{k=0..n} Stirling1(n+1, k+1)*(2^k-1)^n.
%F A054780 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 A054780 a(n) ~ 2^(n^2) / n!. - _Vaclav Kotesovec_, Jun 04 2022
%F A054780 Inverse binomial transform of A367916. - _Gus Wiseman_, Dec 19 2023
%e A054780 From _Gus Wiseman_, Dec 19 2023: (Start)
%e A054780 Number of ways to choose n nonempty sets with union {1..n}. For example, the a(3) = 32 covers are:
%e A054780   {1}{2}{3}  {1}{2}{13}  {1}{2}{123}  {1}{12}{123}  {12}{13}{123}
%e A054780              {1}{2}{23}  {1}{3}{123}  {1}{13}{123}  {12}{23}{123}
%e A054780              {1}{3}{12}  {1}{12}{13}  {1}{23}{123}  {13}{23}{123}
%e A054780              {1}{3}{23}  {1}{12}{23}  {2}{12}{123}
%e A054780              {2}{3}{12}  {1}{13}{23}  {2}{13}{123}
%e A054780              {2}{3}{13}  {2}{3}{123}  {2}{23}{123}
%e A054780                          {2}{12}{13}  {3}{12}{123}
%e A054780                          {2}{12}{23}  {3}{13}{123}
%e A054780                          {2}{13}{23}  {3}{23}{123}
%e A054780                          {3}{12}{13}  {12}{13}{23}
%e A054780                          {3}{12}{23}
%e A054780                          {3}{13}{23}
%e A054780 (End)
%t A054780 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 A054780 Table[Length[Select[Subsets[Rest[Subsets[Range[n]]],{n}],Union@@#==Range[n]&]],{n,0,4}] (* _Gus Wiseman_, Dec 19 2023 *)
%o A054780 (PARI) a(n) = sum(k=0, n, (-1)^k*binomial(n, k)*binomial(2^(n-k)-1, n)) \\ _Andrew Howroyd_, Jan 20 2024
%Y A054780 Main diagonal of A055154.
%Y A054780 Cf. A048291, A088310, A181230, A259763.
%Y A054780 Covers with any number of edges are counted by A003465, unlabeled A055621.
%Y A054780 Connected graphs of this type are counted by A057500, unlabeled A001429.
%Y A054780 This is the covering case of A136556.
%Y A054780 The case of graphs is A367863, covering case of A116508, unlabeled A006649.
%Y A054780 Binomial transform is A367916.
%Y A054780 These set-systems have ranks A367917.
%Y A054780 The unlabeled version is A368186.
%Y A054780 A006129 counts covering graphs, connected A001187, unlabeled A002494.
%Y A054780 A046165 counts minimal covers, ranks A309326.
%Y A054780 Cf. A006126, A058891, A059201, A133686, A323816, A323817, A323818, A326754, A367862, A367901.
%K A054780 easy,nonn
%O A054780 0,3
%A A054780 _Vladeta Jovovic_, May 21 2000