login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Vincenzo Librandi, Table of n, a(n) for n = 0..200

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: A213102 A052604 A038225 * A091527 A201200 A102307

Adjacent sequences:  A086449 A086450 A086451 * A086453 A086454 A086455

KEYWORD

nonn

AUTHOR

Roland Bacher, Sep 09 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 14 07:19 EDT 2019. Contains 327995 sequences. (Running on oeis4.)