A000256 Number of simple triangulations of the plane with n nodes.

1, 1, 0, 1, 3, 12, 52, 241, 1173, 5929, 30880, 164796, 897380, 4970296, 27930828, 158935761, 914325657, 5310702819, 31110146416, 183634501753, 1091371140915, 6526333259312, 39246152584304, 237214507388796, 1440503185260748

Offset: 3

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

A triangulation is simple if it contains no separating 3-cycle. The triangulations are rooted with three fixed exterior nodes. - Andrew Howroyd, Feb 24 2021

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• W. T. Tutte, The enumerative theory of planar maps, pp. 437-448 of J. N. Srivastava, ed., A Survey of Combinatorial Theory, North-Holland, 1973.

Links

• T. D. Noe, Table of n, a(n) for n=3..200
• Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh, Asymptotic Expansions for Sub-Critical Lagrangean Forms, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, Une méthode pour obtenir la fonction génératrice d'une série. FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics; arXiv:0912.0072 [math.NT], 2009.
• P. N. Rathie, A census of simple planar triangulations, J. Combin. Theory, B 16 (1974), 134-138.
• William T. Tutte, A census of planar triangulations, Canad. J. Math. 14 (1962), 21-38.
• William T. Tutte, A Census of Planar Maps, Canad. J. Math. 15 (1963), 249-271.

Crossrefs

First row of array in A210664.

Programs

Maple

R := RootOf(x-t*(t-1)^2, t); ogf := series( (2*R^3+2*R^2-2*R-1)/((R-1)*(R+1)^2), x=0, 20); # Mark van Hoeij, Nov 08 2011

Mathematica

r = Root[x - t*(t - 1)^2, t, 1] ; CoefficientList[ Series[(2*r^3 + 2*r^2 - 2*r - 1)/((r - 1)*(r + 1)^2), {x, 0, 24}], x] (* Jean-François Alcover, Mar 14 2012, after Maple *)

PARI

A000260_ser(N) = {
  my(v = vector(N, n, binomial(4*n+2, n+1)/((2*n+1)*(3*n+2))));
  Ser(concat(1,v));
};
A000256_seq(N) = {
  my(g = A000260_ser(N)); Vec(subst(2 - 1/g, 'x, serreverse(x*g^2)));
};
A000256_seq(24)
\\ test: y = Ser(A000256_seq(200)); 0 == x*(x+4)^2*y^3 - x*(6*x^2+51*x+76)*y^2 + (12*x^3+108*x^2+115*x-1)*y - (8*x^3+76*x^2+54*x-1)
\\ Gheorghe Coserea, Jul 31 2017

PARI

seq(n)={my(g=1+serreverse(x/(1+x)^4 + O(x*x^n) )); Vec(2 - sqrt(serreverse( x*(2-g)^2*g^4)/x ))} \\ Andrew Howroyd, Feb 23 2021

Formula

a(n) = (1/4)*(7*binomial(3*n-9, n-4)-(8*n^2-43*n+57)*a(n-1)) / (8*n^2-51*n+81), n>4. - Vladeta Jovovic, Aug 19 2004

(1/4 + 7/8*n - 9/8*n^3)*a(n) + (-5/4 + 2/3*n + 59/12*n^2 - 13/3*n^3)*a(n+1) + (-1 - 2/3*n + n^2 + 2/3*n^3)*a(n+2). - Simon Plouffe, Feb 09 2012

a(n) ~ 3^(3*n-6+1/2)/(2^(2*n+3)*sqrt(Pi)*n^(5/2)). - Vaclav Kotesovec, Aug 13 2013

From Gheorghe Coserea, Jul 31 2017: (Start)

G.f. y(x) satisfies (with offset 0):

y(x*g^2) = 2 - 1/g, where g=A000260(x). (eqn 2.6 in Tutte's paper)

0 = x*(x+4)^2*y^3 - x*(6*x^2+51*x+76)*y^2 + (12*x^3+108*x^2+115*x-1)*y - (8*x^3+76*x^2+54*x-1).

0 = x*(27*x-4)*deriv(y,x) + x*(7*x+28)*y^2 - 2*(14*x^2+45*x+1)*y + 2*(14*x^2+34*x+1).

(End)

Extensions

More terms from Vladeta Jovovic, Aug 19 2004