OFFSET
0,4
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
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.)
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
E.g.f.: exp(-x/2)*(Sum_{k>=0} A020556(k)*(log(1 + x)/2)^k/k!). - Andrew Howroyd, Jan 13 2020
EXAMPLE
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 + ...
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 *)
PROG
(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
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Vladeta Jovovic, Feb 15 2001
STATUS
approved