A059945 Number of 4-block bicoverings of an n-set.

0, 0, 4, 39, 280, 1815, 11284, 68859, 416560, 2509455, 15086764, 90610179, 543928840, 3264374295, 19588645444, 117539063499, 705255937120, 4231600258335, 25389795391324, 152339353740819, 914037866361400, 5484232429393575, 32905410268988404, 197432508689714139

Offset

1,3

References

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..200

Index entries for linear recurrences with constant coefficients, signature (12,-47,72,-36).

Formula

a(n) = (1/4!)*(6^n - 4*3^n - 3*2^n + 12).

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

a(n) = 12*a(n-1) - 47*a(n-2) + 72*a(n-3) - 36*a(n-4) for n > 4. - Harvey P. Dale, Aug 10 2011

G.f.: -x^3*(9*x-4) / ((x-1)*(2*x-1)*(3*x-1)*(6*x-1)). - Colin Barker, Jan 11 2013

Example

There are 4 4-block bicoverings of a 3-set: {{1},{2},{3},{1,2,3}}, {{2},{3},{1,2},{1,3}}, {{1},{3},{1,2},{2,3}} and {{1},{2},{1,3},{2,3}}.

Mathematica

With[{c=1/4!}, Table[c(6^n-4 3^n-3 2^n+12), {n, 20}]] (* or *) LinearRecurrence[ {12, -47, 72, -36}, {0, 0, 4, 39}, 20] (* Harvey P. Dale, Aug 10 2011 *)

Prog

(PARI) a(n) = {(1/4!)*(6^n - 4*3^n - 3*2^n + 12)} \\ Andrew Howroyd, Jan 29 2020

Crossrefs

Column k=4 of A059443.

Cf. A002718.

Sequence in context: A296594 A290559 A360740 * A198853 A093851 A224755

Adjacent sequences: A059942 A059943 A059944 * A059946 A059947 A059948

Keyword

easy,nonn

Author

Vladeta Jovovic, Feb 14 2001

Extensions

More terms from Colin Barker, Jan 11 2013

Status

approved