A067955 Number of dissections of a convex polygon by nonintersecting diagonals into polygons with even number of sides and having a total number of n edges (sides and diagonals).

1, 0, 0, 1, 0, 1, 3, 1, 8, 13, 15, 56, 79, 157, 399, 624, 1448, 3061, 5571, 12826, 25559, 51608, 113828, 227954, 482591, 1031681, 2117323, 4542331, 9591243, 20119244, 43164172, 91165297, 193826856, 415024053, 881294603, 1886458874, 4038398755

Offset: 1

Author

Emeric Deutsch, Mar 06 2002

Keywords

• nonn

Comments

Number of ordered trees with n-1 edges, all of whose nodes have odd outdegree greater than two.

Conjecture: Number of lattice paths that do not cross below the x-axis from (1,0) to (n,0) using up-step (1,1) and down-steps {(1,-z): z is a positive even integer}. For example, a(8) = 1: [(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,-6)]. - Nicholas Ham, Aug 24 2015

Examples

			a(7)= 3 because the only dissections with 7 edges are given by a hexagon dissected by any of the three halving diagonals.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..2604

Programs

Maple

Order := 40: solve(series((G-G^3)/(1-G^2+G^3),G)=z,G);
# Alternative:
f:= gfun:-rectoproc({115*n*(n+1)*a(n)+(617*n+1236)*(n+1)*a(n+1)+(2*(569*n^2+2657*n+3006))*a(n+2)+(2*(436*n^2+2737*n+4254))*a(n+3)+(6*(32*n^2+267*n+554))*a(n+4)-(4*(29*n^2+260*n+570))*a(n+5)-(8*(n+6))*(11*n+53)*a(n+6)-(16*(n+7))*(n+6)*a(n+7) = 0,a(0)=0,a(1)=1,a(2)=0,a(3)=0,a(4)=1,a(5)=0,a(6)=1},a(n),remember):
map(f, [$1..100]); # Robert Israel, Sep 01 2015

Mathematica

CoefficientList[InverseSeries[(x-x^3)/(1-x^2+x^3) + O[x]^40, x], x] // Rest (* Jean-François Alcover, Sep 16 2022 *)

PARI

Vec(serreverse((x-x^3)/(1-x^2+x^3)+O(x^44))) \\ Joerg Arndt, Sep 28 2015

Formula

a(n) = (1/n)Sum_{j=1..floor((n-1)/3)} binomial(n, j)binomial((n-3-j)/2, j-1). [formula seems wrong]

G.f. G(z) satisfies (1+z)*G^3 - z*G^2 - G + z = 0.

115*n*(n+1)*a(n)+(617*n+1236)*(n+1)*a(n+1)+(2*(569*n^2+2657*n+3006))*a(n+2)+(2*(436*n^2+2737*n+4254))*a(n+3)+(6*(32*n^2+267*n+554))*a(n+4)-(4*(29*n^2+260*n+570))*a(n+5)-(8*(n+6))*(11*n+53)*a(n+6)-(16*(n+7))*(n+6)*a(n+7) = 0. - Robert Israel, Sep 01 2015

G.f. is the series reversion of (x-x^3)/(1-x^2+x^3). - Joerg Arndt, Sep 28 2015