A100300 Number of dissections of a convex n-gon by nonintersecting diagonals into an odd number of regions.

1, 1, 6, 22, 99, 451, 2140, 10396, 51525, 259429, 1323362, 6824434, 35519687, 186346759, 984400760, 5231789176, 27954506505, 150079713481, 809181079294, 4379654830222, 23787413800491, 129607968854731, 708230837732436, 3880366912218772, 21312485647242829, 117321536967959341

Offset

3,3

Links

Vincenzo Librandi, Table of n, a(n) for n = 3..200

P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.

Formula

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

G.f.: (1/8)*( z + z^2 - z*sqrt(1-6*z+z^2) - 4*z^2/(1+z) ).

(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

From Vladeta Jovovic, Nov 15 2004: (Start)

a(n) = (A001003(n-2) - (-1)^n)/2.

a(n) = A100299(n) - (-1)^n. (End)

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

From G. C. Greubel, Feb 04 2023: (Start)

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.

a(n) = Hypergeometric4F3([n/2, (n+1)/2, (3-n)/2, (4-n)/2], [1/2, 1, 3/2], 1). (End)

Example

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

Maple

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));
seq(a(n), n=3..40);

Mathematica

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

Prog

(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
(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
(SageMath)
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))
[A100300(n) for n in range(3, 41)] # G. C. Greubel, Feb 04 2023

Crossrefs

Cf. A001003, A100299.

Sequence in context: A349834 A240049 A078418 * A027296 A179601 A151495

Adjacent sequences: A100297 A100298 A100299 * A100301 A100302 A100303

Keyword

nonn

Author

Emeric Deutsch, Nov 12 2004

Status

approved