A060053 Number of r-bicoverings (or restricted proper 2-covers) of an n-set.

1, 0, 1, 5, 43, 518, 8186, 163356, 3988342, 116396952, 3985947805, 157783127673, 7131072006829, 364166073164914, 20827961078794845, 1323968417981743817, 92917890994442697487, 7157607311779373890120, 602043767970637640566684

Offset: 0

Author

Vladeta Jovovic, Feb 15 2001

Keywords

• easy
• nonn

Comments

A bicovering is called an r-bicovering if the intersection of every two blocks contains at most one element.

Another name for this sequence is the number of restricted proper 2-covers of [1,...,n].

Number of T_0 2-regular set-systems on an n-set. - Andrew Howroyd, Jan 08 2020

Examples

			There are 5 r-bicoverings of a 3-set: 1 3-block bicovering {{1, 2}, {1, 3}, {2, 3}} and 4 4-block bicoverings {{1}, {2}, {3}, {1, 2, 3}}, {{2}, {3}, {1, 2}, {1, 3}}, {{1}, {3}, {1, 2}, {2, 3}}, {{1}, {2}, {1, 3}, {2, 3}}.
G.f. = 1 + x^2 + 5*x^3 + 43*x^4 + 518*x^5 + 8186*x^6 + 163356*x^7 + ...
		

References

• I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983. (See p. 203.)

Links

• Robert Gerbicz, Table of n, a(n) for n = 0..100
• Peter Cameron, Thomas Prellberg, and Dudley Stark, Asymptotic enumeration of 2-covers and line graphs, arXiv:0707.0664 [math.CO], 2007.
• Peter Cameron, Thomas Prellberg, and Dudley Stark, Asymptotic enumeration of 2-covers and line graphs, Discrete Math. 310 (2010), no. 2, 230-240. (See v_n.)

Crossrefs

Row 2 of A331039.

Row sums of A060052.

Cf. A060051, A002718, A059443, A003462, A059945-A059951.

Programs

Maple

A060053 := proc(n) local h, m; h := (m,n) -> add((-1/2)^k*binomial(m*(m-1)/2,n-k)/k!, k=0..n); n!*add(h(m,n)/m!, m=0..3*n); ceil(evalf(%/exp(1),99)) end: seq(A060053(i), i=0..18);
# Caveat computator! Limited accuracy. Do not use it for n > 50. - Peter Luschny, Jul 06 2011

Mathematica

f[n_] := FullSimplify[(n!/E)*Sum[(1/m!)*Sum[(-1/2)^k*Binomial[m*(m - 1)/2,
n - k]/k!, {k, 0, n}], {m, 0, Infinity}]] (* Robert G. Wilson v, Jul 03 2011 *)

PARI

a(n)=round(n!/exp(1)*sum(m=0,3*n+1,1/m!*sum(k=0,n,(-1/2)^k*binomial(m*(m-1)/2,n-k)/k!)))

PARI

\\ here egf1 is A020556 as e.g.f.
egf1(n)={my(bell=serlaplace(exp(exp(x + O(x^(2*n+1)))-1))); sum(i=0, n, sum(k=0, i, (-1)^k*binomial(i,k)*polcoef(bell, 2*i-k))*x^i/i!) + O(x*x^n)}
seq(n)={my(A=egf1(n), B=log(1+x + O(x*x^n))/2); Vec(serlaplace(exp(-x/2 + O(x*x^n))*sum(k=0, n, polcoef(A,k)*B^k)))} \\ Andrew Howroyd, Jan 13 2020

Formula

E.g.f. for number of k-block r-bicoverings of an n-set is exp(-x-x^2*y/2)*Sum_{i=0..inf} (1+y)^binomial(i, 2)*x^i/i!.

a(n) = row sums of A060052.

Inverse binomial transform of A014500. - Vladeta Jovovic, Aug 22 2006

The e.g.f.'s of A002718 (T(x)) and A060053 (V(x)) are related by T(x) = V(e^x-1).

The e.g.f.'s of A014500 (U(x)) and A060053 (V(x)) are related by U(x) = e^x*V(x).

E.g.f.: exp(-x/2)*(Sum_{k>=0} A020556(k)*(log(1 + x)/2)^k/k!). - Andrew Howroyd, Jan 13 2020