login
Number of maximal triangulations (using all 2(n+2) points) of a convex polygon having (n+2) sides and an interior point in the middle of each side.
1

%I #22 Nov 07 2016 08:51:34

%S 1,4,30,250,2236,20979,203748,2031054,20662980,213679114,2239507936,

%T 23735786529,253964904550,2739547645735,29761236016632,

%U 325318710375558,3575517449089572,39489206184518220,438032736572732520

%N Number of maximal triangulations (using all 2(n+2) points) of a convex polygon having (n+2) sides and an interior point in the middle of each side.

%C One might also bend slightly inwards each side around its midpoint, getting a kind of a star-shaped polygon having (n+2) "rays" and count the triangulations of this non-convex polygon.

%C Related to the Catalan sequence 1,1,2,5,14,42,.. (A000108) counting the triangulations of a convex polygon having (n+2) sides (which are not subdivided).

%H Vincenzo Librandi, <a href="/A086452/b086452.txt">Table of n, a(n) for n = 0..200</a>

%H Andrei Asinowski, Christian Krattenthaler, Toufik Mansour, <a href="http://arxiv.org/abs/1604.02870">Counting triangulations of some classes of subdivided convex polygons</a>, arXiv:1604.02870 [math.CO], 2016.

%F a(n) = sum(k=0..n+2, binomial(n+2, k)*(-1)^k*binomial(2*(2*n+2-k), 2*n+2-k)/(2*n+3-k) ); (by inclusion-exclusion)

%F Recurrence: 2*(n+1)*(2*n+3)*a(n) = (67*n^2+36*n+4)*a(n-1) - (223*n^2-481*n+276)*a(n-2) - 30*n*(2*n-5)*a(n-3). - _Vaclav Kotesovec_, Oct 14 2012

%F a(n) ~ 3^(3+1/2)*12^n/(7*sqrt(7*Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 14 2012

%e a(1)=4=14-3*5+3*2-1 (a triangle with each side subdivided by its midpoint can be triangulated in exactly 4 ways using all 6 vertices).

%t Table[Sum[Binomial[n+2,k]*(-1)^k*Binomial[2*(2*n+2-k),2*n+2-k]/(2*n+3-k),{k,0,n+2}],{n,0,20}] (* _Vaclav Kotesovec_, Oct 14 2012 *)

%t Table[Binomial[4n+4, 2n+2]*Hypergeometric2F1[-2n-3, -n - 2, -2n-3/2, 1/4]/(2n+3), {n, 0, 20}] (* _Jean-François Alcover_, Nov 07 2016 *)

%o (PARI) a(n) = sum(k=0, n+2, binomial(n+2,k)*(-1)^k*binomial(2*(2*n+2-k), 2*n+2-k)/(2*n+3-k) ); \\ _Joerg Arndt_, May 10 2013

%Y Cf. A000108.

%K nonn

%O 0,2

%A _Roland Bacher_, Sep 09 2003