A052516 Number of pairs of sets of cardinality at least 3.

0, 0, 0, 0, 0, 0, 20, 70, 182, 420, 912, 1914, 3938, 8008, 16172, 32526, 65262, 130764, 261800, 523906, 1048154, 2096688, 4193796, 8388054, 16776614, 33553780, 67108160, 134216970

Offset

0,7

Comments

The number of functions f:[n]->[2] such that f maps at least 3 elements to 1 and at least 3 elements to 2. a(6) = 20 since there are C(6,3) ways to choose the 3 elements of {1,2,3,4,5,6} that f maps to 1. - Dennis P. Walsh, Dec 09 2014

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..2000

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 82

Index entries for linear recurrences with constant coefficients, signature (5,-9,7,-2).

Formula

E.g.f.: (exp(x) -1)^2 -x*(2+x)*exp(x) +2*x +2*x^2 +x^3 +x^4/4.

(n-1)*a(n+2) + (1-3*n)*a(n+1) + 2*(n+1)*a(n) = 0, a(0) = .. a(5) = 0, a(6) = 20.

G.f.: 2*x^6*(10-15*x+6*x^2)/((1-x)^3*(1-2*x)). - Colin Barker, Feb 19 2012

a(n) = max(0,2^n-n^2-n-2). - Dennis P. Walsh, Dec 09 2014

E.g.f.: (exp(x) - 1 - x - x^2/2)^2. - Dennis P. Walsh, Dec 09 2014

Maple

Pairs spec := [S, {S=Prod(B, B), B=Set(Z, 3 <= card)}, labeled]: seq(combstruct[count](spec, size=n), n=0..20);
with (combstruct):ZL:=[S, {S=Sequence(U, card=r), U=Set(Z, card>=3)}, labeled]: seq(count(subs(r=2, ZL), size=m), m=0..20); # Zerinvary Lajos, Mar 09 2007
seq(max(0, 2^n-n^2-n-2), n=0..40); # Dennis P. Walsh, Dec 09 2014

Mathematica

Table[Max[0, 2^n-n^2-n-2], {n, 0, 30}] (* Vladimir Joseph Stephan Orlovsky, Feb 15 2011*)

Prog

(PARI) a(n)=max(0, 2^n-n^2-n-2) \\ Charles R Greathouse IV, Nov 20 2011
(Magma) m:=30; R<x>:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( (Exp(x) -1-x-x^2/2)^2 )); [0, 0, 0, 0, 0] cat [Factorial(n+5)*b[n]: n in [1..m-6]]; // G. C. Greubel, May 13 2019
(Sage) (2*x^6*(10-15*x+6*x^2)/((1-x)^3*(1-2*x))).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, May 13 2019

Crossrefs

Cf. A052515.

Sequence in context: A245856 A053741 A303609 * A083873 A240820 A143854

Adjacent sequences: A052513 A052514 A052515 * A052517 A052518 A052519

Keyword

easy,nonn

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Status

approved