|
%I #37 Feb 24 2020 14:39:46
%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_
|
