|
%I #24 Feb 05 2023 02:00:25
%S 1,1,6,22,99,451,2140,10396,51525,259429,1323362,6824434,35519687,
%T 186346759,984400760,5231789176,27954506505,150079713481,809181079294,
%U 4379654830222,23787413800491,129607968854731,708230837732436,3880366912218772,21312485647242829,117321536967959341
%N Number of dissections of a convex n-gon by nonintersecting diagonals into an odd number of regions.
%H Vincenzo Librandi, <a href="/A100300/b100300.txt">Table of n, a(n) for n = 3..200</a>
%H P. Flajolet and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00372-0">Analytic combinatorics of non-crossing configurations</a>, Discrete Math., 204, 203-229, 1999.
%F a(n) = Sum_{k=1..floor((n-1)/2)} C(n-3, 2*k-2)*C(n+2*k-3, 2*k-2)/(2*k-1).
%F G.f.: (1/8)*( z + z^2 - z*sqrt(1-6*z+z^2) - 4*z^2/(1+z) ).
%F (n-1)*(2*n-7)*a(n) = (2*n-5)*(5*n-19)*a(n-1) + (5*n-11)*(2*n-7)*a(n-2) - (2*n-5)*(n-5)*a(n-3). - _Vladeta Jovovic_, Nov 12 2004
%F From _Vladeta Jovovic_, Nov 15 2004: (Start)
%F a(n) = (A001003(n-2) - (-1)^n)/2.
%F a(n) = A100299(n) - (-1)^n. (End)
%F Asymptotic (same as for A100299): a(n) ~ sqrt(3*sqrt(2)-4)*(3+2*sqrt(2))^(n-1)/(8*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 17 2012
%F From _G. C. Greubel_, Feb 04 2023: (Start)
%F a(n) = ( (10*(n-5)^2 + 37*(n-5) + 30)*a(n-1) + (10*(n-5)^2 + 43*(n-5) + 42)*a(n-2) - (n-5)*(2*n-5)*a(n-3) )/((n-1)*(2*n-7)), with a(3) = a(4) = 1, a(5) = 6.
%F a(n) = Hypergeometric4F3([n/2, (n+1)/2, (3-n)/2, (4-n)/2], [1/2, 1, 3/2], 1). (End)
%e a(5)=6 because for a convex pentagon ABCDE we obtain dissections with an odd number of regions by one of the following sets of diagonals: {},{AC,AD}, {BD,BE}, {CE,CA}, {DA,DB} and {EB,EC}.
%p a:=n-> sum(binomial(n-3,2*k-2)*binomial(n+2*k-3,2*k-2)/(2*k-1), k=1..floor((n-1)/2));
%p seq(a(n), n=3..40);
%t Take[CoefficientList[Series[-1/2*x^2/(1+x)+x/8+x^2/8-x/8*Sqrt[1-6*x+x^2 ], {x,0,40}], x],{4,-1}] (* _Vaclav Kotesovec_, Oct 17 2012 *)
%o (PARI) my(x='x+O('x^66)); Vec(x*((1+x)^2 -(1+x)*sqrt(1-6*x+x^2) -4*x)/(8*(1+x))) \\ _Joerg Arndt_, May 12 2013
%o (Magma) R<x>:=PowerSeriesRing(Rationals(), 40); Coefficients(R!( x*((1+x)^2 -(1+x)*Sqrt(1-6*x+x^2) -4*x)/(8*(1+x)) )); // _G. C. Greubel_, Feb 04 2023
%o (SageMath)
%o def A100300(n): return sum(binomial(n-3,2*k)*binomial(n+2*k-1,2*k)/(2*k+1) for k in range((n-3)//2 +1))
%o [A100300(n) for n in range(3,41)] # _G. C. Greubel_, Feb 04 2023
%Y Cf. A001003, A100299.
%K nonn
%O 3,3
%A _Emeric Deutsch_, Nov 12 2004
|
