login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A060053 Number of r-bicoverings (or restricted proper 2-covers) of an n-set. 16
1, 0, 1, 5, 43, 518, 8186, 163356, 3988342, 116396952, 3985947805, 157783127673, 7131072006829, 364166073164914, 20827961078794845, 1323968417981743817, 92917890994442697487, 7157607311779373890120, 602043767970637640566684 (list; graph; refs; listen; history; text; internal format)
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, Dudley Stark, Asymptotic enumeration of 2-covers and line graphs, arXiv:0707.0664 [math.CO], 2007.

Peter Cameron, Thomas Prellberg, 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

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

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

Row 2 of A331039.

Row sums of A060052.

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

Sequence in context: A188365 A107720 A299425 * A227176 A132691 A256033

Adjacent sequences:  A060050 A060051 A060052 * A060054 A060055 A060056

KEYWORD

easy,nonn

AUTHOR

Vladeta Jovovic, Feb 15 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 6 17:32 EDT 2020. Contains 335479 sequences. (Running on oeis4.)