|
|
A002718
|
|
Number of bicoverings of an n-set.
(Formerly M4559 N1941)
|
|
24
|
|
|
1, 0, 1, 8, 80, 1088, 19232, 424400, 11361786, 361058000, 13386003873, 570886397340, 27681861184474, 1511143062540976, 92091641176725504, 6219762391554815200, 462595509951068027741, 37676170944802047077248, 3343539821715571537772071, 321874499078487207168905840
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
Another description: number of proper 2-covers of [1,...,n].
|
|
REFERENCES
|
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 303, #40.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
E.g.f. for k-block bicoverings of an n-set is exp(-x-1/2*x^2*(exp(y)-1))*Sum_{i=0..inf} x^i/i!*exp(binomial(i, 2)*y).
The e.g.f.'s of A002718 (T(x)) and A060053 (V(x)) are related by T(x) = V(e^x-1).
a(n) = Sum_{m=0..n + floor(n/2); k=0..n; s=0..min(m/2,k); t=0..m-2s} Stirling2(n,k) * k!/m! * binomial(m,2s) * A001147(s) * (-1)^(m+s+t) * binomial(m-2s,t) * binomial(t*(t-1)/2,k-s). Interpret m as the number of blocks in a bicovering, k the number of clumps of points that are always all together in blocks. This formula counts bicoverings by quotienting them to the clumpless case (an operation which preserves degree) and counting incidence matrices of those, and counts those matrices as the transposes of incidence matrices of labeled graphs with no isolated points and no isolated edges. - David Pasino, Jul 09 2016
|
|
EXAMPLE
|
For n=3, there are 8 collections of distinct subsets of {1,2,3} with the property that each of 1, 2, and 3 appears in exactly two subsets:
{1,2,3},{1,2},{3}
{1,2,3},{1,3},{2}
{1,2,3},{2,3},{1}
{1,2,3},{1},{2},{3}
{1,2},{1,3},{2,3}
{1,2},{1,3},{2},{3}
{1,2},{2,3},{1},{3}
{1,3},{2,3},{1},{2}
|
|
MATHEMATICA
|
nmax = 16; imax = 2*(nmax - 2); egf := E^(-x - 1/2*x^2*(E^y - 1))*Sum[(x^i/i!)*E^(Binomial[i, 2]*y), {i, 0, imax}]; fx = CoefficientList[Series[egf, {y, 0, imax}], y]*Range[0, imax]!; a[n_] := Drop[ CoefficientList[ Series[fx[[n + 1]], {x, 0, imax}], x], 3] // Total; Table[ a[n] , {n, 2, nmax}] (* Jean-François Alcover, Apr 04 2013 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|