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

Author

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

Keywords

• easy
• nonn

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

Crossrefs

Cf. A052515.

Programs

Magma

m:=30; R:=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

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

PARI

a(n)=max(0,2^n-n^2-n-2) \\ Charles R Greathouse IV, Nov 20 2011

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

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