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



(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


%S 1,0,1,1,4,8,25,64,191,540,1616,4785,14512,44084,135545,418609,

%T 1302340,4070124,12785859,40325828,127689288,405689020,1293060464,

%U 4133173256,13246527139,42557271268,137032656700,442158893833,1429468244788

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

%H T. D. Noe, <a href="/A046736/b046736.txt">Table of n, a(n) for n=2..200</a>

%H D. Birmajer, J. B. Gil, M. D. Weiner, <a href="http://arxiv.org/abs/1503.05242">Colored partitions of a convex polygon by noncrossing diagonals</a>, arXiv preprint arXiv:1503.05242 [math.CO], 2015.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=93">Encyclopedia of Combinatorial Structures 93</a>

%H S. Morrison, E. Peters, N. Snyder, <a href="http://arxiv.org/abs/1501.06869">Categories generated by a trivalent vertex</a>, arXiv preprint arXiv:1501.06869 [math.QA], 2015.

%H L. Smiley, <a href="http://www.math.uaa.alaska.edu/~smiley/schroed.html">A Nameless Number</a>

%H L. Smiley, <a href="http://arXiv.org/abs/math.CO/9907057">Variants of Schroeder Dissections</a>, arXiv:math/9907057 [math.CO], 1999.

%H Vasiliki Velona, <a href="https://arxiv.org/abs/1802.03719">Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs</a>, arXiv:1802.03719 [math.CO], 2018.

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

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

%F 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

%e 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.

%p 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);

%t 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);

%t (* 2nd program: *)

%t x*InverseSeries[Series[(y-y^2-y^3)/(1-y), {y, 0, 29}], x]

%t (* 3rd program: *)

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

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

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

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

%K nonn,nice,easy

%O 2,5

%A _Len Smiley_

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 June 22 20:16 EDT 2021. Contains 345388 sequences. (Running on oeis4.)