cp's OEIS Frontend

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

%I A046736 #66 Aug 05 2025 16:18:31
%S A046736 1,0,1,1,4,8,25,64,191,540,1616,4785,14512,44084,135545,418609,
%T A046736 1302340,4070124,12785859,40325828,127689288,405689020,1293060464,
%U A046736 4133173256,13246527139,42557271268,137032656700,442158893833,1429468244788
%N A046736 Number of ways to place non-intersecting diagonals in convex n-gon so as to create no triangles.
%H A046736 T. D. Noe, <a href="/A046736/b046736.txt">Table of n, a(n) for n=2..200</a>
%H A046736 D. Birmajer, J. B. Gil, and 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 A046736 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=93">Encyclopedia of Combinatorial Structures 93</a>
%H A046736 S. Morrison, E. Peters, and 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 A046736 Len Smiley, <a href="http://www.math.uaa.alaska.edu/~smiley/schroed.html">A Nameless Number</a>
%H A046736 Len Smiley, <a href="http://arXiv.org/abs/math.CO/9907057">Variants of Schroeder Dissections</a>, arXiv:math/9907057 [math.CO], 1999.
%H A046736 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 A046736 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 A046736 a(n) = A052524(n-1)/(n-1)!, for n > 0.
%F A046736 Let g = (1-x)/(1-x-x^2) then a(m) = coeff. of x^(m-2) in g^(m-1)/(m-1).
%F A046736 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
%F A046736 a(n) = A143363(n-3) + Sum_{k=0..n-6} ( A143363(k+1)*a(n-k-2) ). - _Muhammed Sefa Saydam_, Feb 14 2025 and Aug 05 2025
%e A046736 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 A046736 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 A046736 (* Programs from _Jean-François Alcover_, Apr 14 2017: Start *)
%t A046736 (* First program *)
%t A046736 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 A046736 (* 2nd program: *)
%t A046736 x*InverseSeries[Series[(y-y^2-y^3)/(1-y), {y, 0, 29}], x]
%t A046736 (* 3rd program: *)
%t A046736 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}]
%t A046736 (* End *)
%o A046736 (PARI) a(n)=if(n<2,0,polcoeff(serreverse((x-x^2-x^3)/(1-x)+x*O(x^n)),n-1))
%o A046736 (Magma)
%o A046736 A046736:= func< n | n eq 2 select 1 else (&+[Binomial(n+k-2,k)*Binomial(n-k-3, k-1)/(n-1): k in [0..Floor(n/2)-1]]) >;
%o A046736 [A046736(n): n in [2..40]]; // _G. C. Greubel_, Jul 31 2024
%o A046736 (SageMath)
%o A046736 def A046736(n): return 1 if n==2 else sum(binomial(n+k-2,k)*binomial(n-k-3, k-1)//(n-1) for k in range(n//2))
%o A046736 [A046736(n) for n in range(2,41)] # _G. C. Greubel_, Jul 31 2024
%Y A046736 Cf. A001003 (Schroeder), A001006 (Motzkin), A000108 (Catalan), A052524.
%K A046736 nonn,nice,easy
%O A046736 2,5
%A A046736 _Len Smiley_