|
|
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
|
|
|
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!.
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,
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|