A052515 Number of ordered pairs of complementary subsets of an n-set with both subsets of cardinality at least 2.

0, 0, 0, 0, 6, 20, 50, 112, 238, 492, 1002, 2024, 4070, 8164, 16354, 32736, 65502, 131036, 262106, 524248, 1048534, 2097108, 4194258, 8388560, 16777166, 33554380, 67108810, 134217672, 268435398, 536870852, 1073741762

Offset: 0

Author

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

Keywords

• easy
• nonn

Comments

a(n) is the number of binary sequences of length n having at least two 0's and at least two 1's. a(4)=6 because there are six binary sequences of length four that have two or more 0's and two or more 1's: 0011, 0101, 0110, 1100, 1010, 1001. - Geoffrey Critzer, Feb 11 2009

For n>3, a(n) is also the sum of those terms from the n-th row of Pascal's triangle which also occur in A006987: 6, 10+10, 15+20+15, 21+35+35+21,... - Douglas Latimer, Apr 02 2012

From Dennis P. Walsh, Apr 09 2013: (Start)

Column 2 of triangle A200091.

Number of doubly-surjective functions f:[n]->[2].

Number of ways to distribute n different toys to 2 children so that each child gets at least 2 toys. (End)

a(n) is the number of subsets of an n-set of cardinality k with 2 <= k <= n - 2. - Rick L. Shepherd, Dec 05 2014

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 81
• Dennis Walsh, Notes on doubly-surjective finite functions
• Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Programs

Magma

m:=35; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( (Exp(x)-1-x)^2 )); [0,0,0,0] cat [Factorial(n+3)*b[n]: n in [1..m-5]]; // G. C. Greubel, May 13 2019

Maple

Pairs spec := [S,{S=Prod(B,B),B=Set(Z,2 <= card)},labeled]: seq(combstruct[count](spec,size=n), n=0..20);

Mathematica

Join[{0,0,0}, LinearRecurrence[{4,-5,2}, {0,6,20}, 35]] (* G. C. Greubel, May 13 2019 *)
With[{nn=30},CoefficientList[Series[(Exp[x]-x-1)^2,{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, May 29 2023 *)

PARI

concat([0,0,0,0],Vec((6-4*x)/(1-x)^2/(1-2*x)+O(x^35))) \\ Charles R Greathouse IV, Apr 03 2012

PARI

x='x+O('x^35); concat([0,0,0,0],Vec(serlaplace((exp(x)-x-1)^2))) \\ Joerg Arndt, Apr 10 2013

Sage

(2*x^4*(3-2*x)/((1-x)^2*(1-2*x))).series(x, 35).coefficients(x, sparse=False) # G. C. Greubel, May 13 2019

Formula

E.g.f.: (exp(x) - x - 1)^2. - Joerg Arndt, Apr 10 2013

n*a(n+2) - (1+3*n)*a(n+1) + 2(1+n)*a(n) = 0, with a(0) = .. = a(3) = 0, a(4) = 6.

For n>2, a(n) = 2^n - 2n - 2 = A005803(n) - 2 = A070313(n) - 1 = A071099(n) - A071099(n+1) + 1 = 2*A000247(n-1). - Ralf Stephan, Jan 11 2004

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

Extensions

More terms from Ralf Stephan, Jan 11 2004

Definition corrected by Rainer Rosenthal, Feb 12 2010

Definition further clarified by Rick L. Shepherd, Dec 05 2014