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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A087809 Number of triangulations (by Euclidean triangles) having 3+3n vertices of a triangle with each side subdivided by n additional points. 0
1, 4, 29, 229, 1847, 14974, 121430, 983476, 7952111, 64193728, 517447289, 4165721377, 33500374796, 269166095800, 2161064409680, 17339917293304, 139060729285871, 1114752741216196, 8933074352513183, 71564554425680839 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

REFERENCES

Andrei Asinowski, C. Krattenthaler, T. Mansour, Counting triangulations of balanced subdivisions of convex polygons, Preprint 2016; http://discretemath.upc.edu/jmda16/wp-content/uploads/2015/09/JMDA2016_paper_15.pdf

LINKS

Table of n, a(n) for n=0..19.

Andrei Asinowski, Christian Krattenthaler, Toufik Mansour, Counting triangulations of some classes of subdivided convex polygons, European Journal of Combinatorics 62 (2017), 92-114; arXiv:1604.02870 [math.CO], 2016.

R. Bacher, Counting Triangulations of Configurations, arXiv:math/0310206 [math.CO], 2003.

FORMULA

A formula is given in the Bacher reference.

It seems that a(n) = Sum_{i, j, k>=0} C(n, i+j)*C(n, j+k)*C(n, k+i)). - Benoit Cloitre, Oct 25 2004; proved in the article by Asinowski et al.

G.f.: seems to be (10*g^3 - 17*g^2 + 7*g - 1)/((1-3*g)*(2*g-1)*(4*g^2 - 6*g+1)) where g*(1-g)^2 = x. - Mark van Hoeij, Nov 10 2011; proved in the article by Asinowski et al.

Conjecture: 2*n*(2*n-1)*(5*n^2 - 29*n + 30)*a(n) + (-295*n^4 + 1926*n^3 - 3425*n^2 + 2106*n - 360)*a(n-1) + 24*(3*n-4)*(3*n-5)*(5*n^2 - 19*n + 6)*a(n-2) = 0. - R. J. Mathar, Apr 23 2015. Proved by Andrei Asinowski, C. Krattenthaler, T. Mansour, Counting triangulations of balanced subdivisions of convex polygons, 2016.

EXAMPLE

a(0)=1 since there is only one triangulation of a triangle (consisting of the triangle itself).

The a(1)=4 triangulations of a triangle with each side subdivided by one additional point are given by

.

       O             O

      / \           /|\

     O _ O         O   O

    / \ / \       / \|/ \

   O _ O _ O  ,  O _ O _ O

.

and rotations by 120 degrees and 240 degrees of the last triangulation.

MATHEMATICA

max = 19; f[x_] := Sum[ a[n]*x^n, {n, 0, max}]; a[0] = 1; g[x_] := Sum[ b[n]*x^n, {n, 0, max}]; b[0] = 0; coes = CoefficientList[ Series[ g[x]*(1 - g[x])^2 - x, {x, 0, max}], x]; solb = Solve[ Thread[ coes == 0]][[1]]; coes = CoefficientList[ Series[ f[x] - ((10*g[x]^3 - 17*g[x]^2 + 7*g[x] - 1)/((1 - 3*g[x])*(2*g[x] - 1)*(4*g[x]^2 - 6*g[x] + 1))), {x, 0, max}], x] /. solb; sola = Solve[ Thread[ coes == 0]][[1]]; Table[a[n] /. sola, {n, 0, max}] (* Jean-Fran├žois Alcover, Dec 06 2011, after Mark van Hoeij *)

CROSSREFS

Sequence in context: A135429 A079756 A221415 * A140526 A151343 A208812

Adjacent sequences:  A087806 A087807 A087808 * A087810 A087811 A087812

KEYWORD

nonn,nice

AUTHOR

Roland Bacher, Oct 16 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 16 12:40 EST 2018. Contains 317272 sequences. (Running on oeis4.)