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
Examples
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.
Links
- T. D. Noe, Table of n, a(n) for n=2..200
- D. Birmajer, J. B. Gil, and 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, and N. Snyder, Categories generated by a trivalent vertex, arXiv preprint arXiv:1501.06869 [math.QA], 2015.
- Len Smiley, A Nameless Number
- Len 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.
Programs
-
Magma
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]]) >; [A046736(n): n in [2..40]]; // G. C. Greubel, Jul 31 2024
-
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
(* Programs from Jean-François Alcover, Apr 14 2017: Start *) (* First program *) 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}] (* End *)
-
PARI
a(n)=if(n<2,0,polcoeff(serreverse((x-x^2-x^3)/(1-x)+x*O(x^n)),n-1))
-
SageMath
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)) [A046736(n) for n in range(2,41)] # G. C. Greubel, Jul 31 2024
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)).
a(n) = A052524(n-1)/(n-1)!, for n > 0.
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
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
Comments