login
A086452
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
1, 4, 30, 250, 2236, 20979, 203748, 2031054, 20662980, 213679114, 2239507936, 23735786529, 253964904550, 2739547645735, 29761236016632, 325318710375558, 3575517449089572, 39489206184518220, 438032736572732520
OFFSET
0,2
COMMENTS
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.
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).
LINKS
Andrei Asinowski, Christian Krattenthaler, Toufik Mansour, Counting triangulations of some classes of subdivided convex polygons, arXiv:1604.02870 [math.CO], 2016.
FORMULA
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)
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
a(n) ~ 3^(3+1/2)*12^n/(7*sqrt(7*Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 14 2012
EXAMPLE
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).
MATHEMATICA
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 *)
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 *)
PROG
(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
CROSSREFS
Cf. A000108.
Sequence in context: A052604 A357204 A038225 * A334719 A091527 A201200
KEYWORD
nonn
AUTHOR
Roland Bacher, Sep 09 2003
STATUS
approved