login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A046736 Number of ways to place non-intersecting diagonals in convex n-gon so as to create no triangles. 9
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 10 14:50 EDT 2020. Contains 336381 sequences. (Running on oeis4.)