|
| |
|
|
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
|
|
|
|
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
|
|
|
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
