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

%I #58 May 29 2023 12:04:04

%S 0,0,0,0,6,20,50,112,238,492,1002,2024,4070,8164,16354,32736,65502,

%T 131036,262106,524248,1048534,2097108,4194258,8388560,16777166,

%U 33554380,67108810,134217672,268435398,536870852,1073741762

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

%C 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

%C 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

%C From _Dennis P. Walsh_, Apr 09 2013: (Start)

%C Column 2 of triangle A200091.

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

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

%C 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

%H Vincenzo Librandi, <a href="/A052515/b052515.txt">Table of n, a(n) for n = 0..1000</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=81">Encyclopedia of Combinatorial Structures 81</a>

%H Dennis Walsh, <a href="http://capone.mtsu.edu/dwalsh/DOUBSURJ.pdf">Notes on doubly-surjective finite functions</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-5,2).

%F E.g.f.: (exp(x) - x - 1)^2. - _Joerg Arndt_, Apr 10 2013

%F 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.

%F 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

%F G.f.: 2*x^4*(3-2*x)/((1-x)^2*(1-2*x)). - _Colin Barker_, Feb 19 2012

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

%t Join[{0,0,0}, LinearRecurrence[{4,-5,2}, {0,6,20}, 35]] (* _G. C. Greubel_, May 13 2019 *)

%t With[{nn=30},CoefficientList[Series[(Exp[x]-x-1)^2,{x,0,nn}],x] Range[0,nn]!] (* _Harvey P. Dale_, May 29 2023 *)

%o (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

%o (PARI) x='x+O('x^35); concat([0,0,0,0],Vec(serlaplace((exp(x)-x-1)^2))) \\ _Joerg Arndt_, Apr 10 2013

%o (Magma) m:=35; R<x>:=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

%o (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

%K easy,nonn

%O 0,5

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

%E More terms from _Ralf Stephan_, Jan 11 2004

%E Definition corrected by _Rainer Rosenthal_, Feb 12 2010

%E Definition further clarified by _Rick L. Shepherd_, Dec 05 2014