A005784 Number of 4-covers of an unlabeled n-set. (Formerly M3535)

1, 4, 17, 65, 230, 736, 2197, 6093, 15864, 38960, 90837, 202005, 430577, 883057, 1748909, 3355213, 6252575, 11345602, 20089514, 34778306, 58964020, 98053576, 160151566, 257229974, 406739271, 633795181, 974126408, 1477999320, 2215409037, 3282874359, 4812278064

Offset

0,2

Comments

Number of 4 X n binary matrices with at least one 1 in every column up to row and column permutations. - Andrew Howroyd, Feb 28 2023

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Stefano Spezia, Table of n, a(n) for n = 0..10000

R. J. Clarke, Covering a set by subsets, Discrete Math., 81 (1990), 147-152.

Vladeta Jovovic, Binary matrices up to row and column permutations

Index entries for linear recurrences with constant coefficients, signature (5, -7, -1, 5, -1, 21, -33, 0, -4, 8, 68, -57, -3, -57, 13, 100, -32, 32, -100, -13, 57, 3, 57, -68, -8, 4, 0, 33, -21, 1, -5, 1, 7, -5, 1).

Formula

G.f.: (x^20 - x^19 + 4*x^18 + 9*x^17 + 23*x^16 + 39*x^15 + 90*x^14 + 131*x^13 + 204*x^12 + 238*x^11 + 252*x^10 + 238*x^9 + 204*x^8 + 131*x^7 + 90*x^6 + 39*x^5 + 23*x^4 + 9*x^3 + 4*x^2 - x + 1)/((1 - x^4)^3*(1 - x^3)^4*(1 - x^2)^3*(1 - x)^5).

a(n) ~ n^14/2092278988800. - Stefano Spezia, Aug 08 2022

a(n) = n^14/2092278988800 + n^13/19926466560 + n^12/418037760 + n^11/14598144 + 689*n^10/522547200 + 253*n^9/13934592 + 2184839*n^8/11705057280 + 10313*n^7/6967296 + 2319707*n^6/250822656 + 1817221*n^5/39813120 + 2405336243*n^4/13795246080 + 151784975*n^3/306561024 + 93746545019*n^2/95103590400 + 924100468541*n/717352796160 + 1 + (n^2/486 + 5*n/162 + 233/2187)*floor(n/3) + (n^2/256 + 15*n/256 + 101/512)*floor(n/4) - (n^3/1458 + 7*n^2/486 + 22*n/243 + 356/2187)*floor((n+1)/3) + (n^5/122880 + 5*n^4/16384 + 125*n^3/24576 + 359*n^2/8192 + 10967*n/61440 + 8461/32768)*floor(n/2) + (n/256 + 15/512)*floor((n+1)/4). - Vaclav Kotesovec, Aug 09 2022

Prog

(PARI) Vec(G(4, x)*(1 - x) + O(x^40)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

Crossrefs

Column 4 of A055080.

First differences of A006148.

Cf. A002620, A005783, A005785, A005786, A055066.

Sequence in context: A122231 A119916 A209375 * A095252 A181410 A102207

Adjacent sequences: A005781 A005782 A005783 * A005785 A005786 A005787

Keyword

easy,nonn

Author

N. J. A. Sloane

Extensions

More terms from Vladeta Jovovic, Jun 03 2000

a(0)=1 prepended by Alois P. Heinz, Aug 08 2022

Status

approved