A089382 Total number of triangles in all the dissections of a convex (n+3)-gon by nonintersecting diagonals.

1, 4, 20, 104, 553, 2984, 16272, 89440, 494681, 2749772, 15348372, 85967112, 482927985, 2719787856, 15351385152, 86816721792, 491819758417, 2790451952660, 15854070902964, 90187514559208, 513619224125657, 2928073006131704, 16708228671139600, 95423104768226144, 545408567460801513

Offset

0,2

Links

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

Formula

G.f.: (3-z+q)*(1+z-q)^2/(64*q*z^2), where q = sqrt(1-6*z+z^2).

Recurrence: n*(n+2)*a(n) = (8*n^2 + 7*n - 3)*a(n-1) - (13*n^2 - 17*n - 6)*a(n-2) + 2*(n-3)*(n+1)*a(n-3). - Vaclav Kotesovec, Oct 14 2012

a(n) ~ (1 + sqrt(2))^(2*n+3) / (2^(11/4) * sqrt(Pi*n)). - Vaclav Kotesovec, Oct 14 2012, simplified Dec 24 2017

a(n) = Sum_{j=0..n}((-1)^j*2^(n-j)*binomial(n+3,j)*binomial(2*n-j+2,n+2)). - Vladimir Kruchinin, Apr 08 2016

Example

a(1)=4 because in the three dissections of a square we have altogether four triangles: no triangle in the "no-diagonals" dissection and two triangles in each of the dissections by one of the two diagonals of the square.

Mathematica

Table[SeriesCoefficient[(3-x+Sqrt[1-6*x+x^2])*(1+x-Sqrt[1-6*x+x^2])^2/(64*Sqrt[1-6*x+x^2]*x^2), {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Oct 14 2012 *)

Prog

(PARI)  x='x+O('x^66); q = sqrt(1-6*x+x^2); Vec((3-x+q)*(1+x-q)^2/(64*q*x^2)) \\ Joerg Arndt, May 10 2013
(Maxima)
a(n):=sum((-1)^j*2^(n-j)*binomial(n+3, j)*binomial(2*n-j+2, n+2), j, 0, n); /* Vladimir Kruchinin, Apr 08 2016 */

Crossrefs

Cf. A001003.

Sequence in context: A120978 A035028 A104550 * A291089 A192619 A026305

Adjacent sequences: A089379 A089380 A089381 * A089383 A089384 A089385

Keyword

nonn

Author

Emeric Deutsch, Dec 28 2003

Status

approved