A005784 Number of 4-covers of an unlabeled n-set.

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

Author

N. J. A. Sloane

Keywords

• easy
• nonn

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

Crossrefs

Column 4 of A055080.

First differences of A006148.

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

Programs

PARI

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

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

Extensions

More terms from Vladeta Jovovic, Jun 03 2000

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