A000256 Number of simple triangulations of the plane with n nodes. (Formerly M2923 N1173)

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,5

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.

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)

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 *)

Prog

(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

Crossrefs

First row of array in A210664.

Sequence in context: A151197 A007198 A348479 * A274396 A299113 A124202

Adjacent sequences: A000253 A000254 A000255 * A000257 A000258 A000259

Keyword

nonn,nice

Author

N. J. A. Sloane

Extensions

More terms from Vladeta Jovovic, Aug 19 2004

Status

approved