|
|
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).
|
|
3
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,7
|
|
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
|
|
LINKS
|
|
|
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
|
|
EXAMPLE
|
a(7)= 3 because the only dissections with 7 edges are given by a hexagon dissected by any of the three halving diagonals.
|
|
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):
|
|
MATHEMATICA
|
CoefficientList[InverseSeries[(x-x^3)/(1-x^2+x^3) + O[x]^40, x], x] // Rest (* Jean-François Alcover, Sep 16 2022 *)
|
|
PROG
|
(PARI) Vec(serreverse((x-x^3)/(1-x^2+x^3)+O(x^44))) \\ Joerg Arndt, Sep 28 2015
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|