A046736 Number of ways to place non-intersecting diagonals in convex n-gon so as to create no triangles.

1, 0, 1, 1, 4, 8, 25, 64, 191, 540, 1616, 4785, 14512, 44084, 135545, 418609, 1302340, 4070124, 12785859, 40325828, 127689288, 405689020, 1293060464, 4133173256, 13246527139, 42557271268, 137032656700, 442158893833, 1429468244788

Offset

2,5

Links

T. D. Noe, Table of n, a(n) for n=2..200

D. Birmajer, J. B. Gil, M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 93

S. Morrison, E. Peters, N. Snyder, Categories generated by a trivalent vertex, arXiv preprint arXiv:1501.06869 [math.QA], 2015.

L. Smiley, A Nameless Number

L. Smiley, Variants of Schroeder Dissections, arXiv:math/9907057 [math.CO], 1999.

Vasiliki Velona, Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs, arXiv:1802.03719 [math.CO], 2018.

Formula

G.f.: A(x)=sum_{n>0} a(n)x^(n-1) satisfies A(x)-A(x)^2-A(x)^3 = x*(1-A(x)).

Let g=(1-x)/(1-x-x^2); then a(m) = coeff. of x^(m-2) in g^(m-1)/(m-1).

D-finite with recurrence: 5*(n-1)*n*(37*n-95)*a(n) = 4*(n-1)*(74*n^2-301*n+300)*a(n-1) + 8*(2*n-5)*(74*n^2-301*n+297)*a(n-2) - 2*(n-3)*(2*n-7)*(37*n-58)*a(n-3). - Vaclav Kotesovec, Aug 10 2013

Example

a(4)=a(5)=1 because of null placement; a(6)=4 because in addition to not placing any, we might also place one between any of the 3 pairs of opposite vertices.

Maple

a := n->1/(n-1)*sum(binomial(n+k-2, k)*binomial(n-k-3, k-1), k=0..floor(n/2-1)); seq(a(i), i=2..30);

Mathematica

a[2]=1; a[n_] := Sum[Binomial[n+k-2, k]*Binomial[n-k-3, k-1], {k, 0, Floor[n/2]-1}]/(n-1);
(* 2nd program: *)
x*InverseSeries[Series[(y-y^2-y^3)/(1-y), {y, 0, 29}], x]
(* 3rd program: *)
a[2]=1; a[3]=0; a[n_] := HypergeometricPFQ[{2-n/2, 5/2-n/2, n}, {2, 4-n}, -4]; Table[a[n], {n, 2, 30}] (* Jean-François Alcover, Apr 14 2017 *)

Prog

(PARI) a(n)=if(n<2, 0, polcoeff(serreverse((x-x^2-x^3)/(1-x)+x*O(x^n)), n-1))

Crossrefs

Cf. A000108 (Catalan), A001003 (Schroeder), A001006 (Motzkin).

A052524(n)=n!*a(n+1) for n>0.

Sequence in context: A297458 A328038 A107840 * A174171 A262042 A227644

Adjacent sequences: A046733 A046734 A046735 * A046737 A046738 A046739

Keyword

nonn,nice,easy

Author

Len Smiley

Status

approved