|
| |
|
|
A054780
|
|
Number of n-covers of a labeled n-set.
|
|
13
|
|
|
|
1, 1, 3, 32, 1225, 155106, 63602770, 85538516963, 386246934638991, 6001601072676524540, 327951891446717800997416, 64149416776011080449232990868, 45546527789182522411309599498741023, 118653450898277491435912500458608964207578
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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.
|
|
|
EXAMPLE
|
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
|
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.
These set-systems have ranks A367917.
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
