cp's OEIS Frontend

A002718 Number of bicoverings of an n-set.

%I A002718 M4559 N1941 #55 Apr 18 2025 05:44:00
%S A002718 1,0,1,8,80,1088,19232,424400,11361786,361058000,13386003873,
%T A002718 570886397340,27681861184474,1511143062540976,92091641176725504,
%U A002718 6219762391554815200,462595509951068027741,37676170944802047077248,3343539821715571537772071,321874499078487207168905840
%N A002718 Number of bicoverings of an n-set.
%C A002718 Another description: number of proper 2-covers of [1,...,n].
%D A002718 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 303, #40.
%D A002718 I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.
%D A002718 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002718 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002718 Alois P. Heinz, <a href="/A002718/b002718.txt">Table of n, a(n) for n = 0..100</a>
%H A002718 Peter Cameron, Thomas Prellberg, Dudley Stark, <a href="http://dx.doi.org/10.1016/j.disc.2008.09.008">Asymptotic enumeration of 2-covers and line graphs</a>, Discrete Math. 310 (2010), no. 2, 230-240 (see t_n).
%H A002718 L. Comtet, <a href="/A002718/a002718.pdf">Birecouvrements et birevêtements d'un ensemble fini</a>, Studia Sci. Math. Hungar 3 (1968): 137-152. [Annotated scanned copy. Warning: the table of v(n,k) has errors.]
%F A002718 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).
%F A002718 Stirling_2 transform of A060053.
%F A002718 The e.g.f.'s of A002718 (T(x)) and A060053 (V(x)) are related by T(x) = V(e^x-1).
%F A002718 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
%e A002718 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:
%e A002718   {1,2,3},{1,2},{3}
%e A002718   {1,2,3},{1,3},{2}
%e A002718   {1,2,3},{2,3},{1}
%e A002718   {1,2,3},{1},{2},{3}
%e A002718   {1,2},{1,3},{2,3}
%e A002718   {1,2},{1,3},{2},{3}
%e A002718   {1,2},{2,3},{1},{3}
%e A002718   {1,3},{2,3},{1},{2}
%e A002718 Therefore a(3) = 8. - _Michael B. Porter_, Jul 16 2016
%t A002718 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 *)
%Y A002718 Cf. A020554, A002719, A003462, A059945-A059951, A060053. Row sums of A059443.
%K A002718 nonn,nice
%O A002718 0,4
%A A002718 _N. J. A. Sloane_
%E A002718 More terms from _Vladeta Jovovic_, Feb 18 2001
%E A002718 a(0), a(1) prepended by _Alois P. Heinz_, Jul 29 2016