login
This site is supported by donations to The OEIS 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. 25
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].

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).

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!)))

CROSSREFS

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

Sequence in context: A231277 A188365 A107720 * 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 28 16:56 EDT 2017. Contains 288839 sequences.