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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000260 Number of rooted simplicial 3-polytopes with n+3 nodes; or rooted 3-connected triangulations with 2n+2 faces; or rooted 3-connected trivalent maps with 2n+2 vertices.
(Formerly M2946 N1187)
19
1, 1, 3, 13, 68, 399, 2530, 16965, 118668, 857956, 6369883, 48336171, 373537388, 2931682810, 23317105140, 187606350645, 1524813969276, 12504654858828, 103367824774012, 860593023907540, 7211115497448720, 60776550501588855 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Number of rooted loopless planar maps with n edges. E.g., there are a(2)=3 loopless planar maps with 2 edges: two rooted paths (.-.-.) and one digon (.=.). - Valery A. Liskovets, Sep 25 2003

Number of intervals (i.e., ordered pairs (x,y) such that x<=y) in the Tamari lattice (rotation lattice of binary trees) of size n (see Pallo and Chapoton references). - Ralf Stephan, May 08 2007, Jean Pallo (Jean.Pallo(AT)u-bourgogne.fr), Sep 11 2007

Number of rooted triangulations of type [n, 0] (see Brown paper eq (4.8)). - Michel Marcus, Jun 23 2013

Equivalently, number of rooted bridgeless planar maps with n edges. - Noam Zeilberger, Oct 06 2016

REFERENCES

C. F. Earl and L. J. March, Architectural applications of graph theory, pp. 327-355 of R. J. Wilson and L. W. Beineke, editors, Applications of Graph Theory. Academic Press, NY, 1979.

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 714.

Handbook of Combinatorics, North-Holland '95, p. 891.

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, in A Survey of Combinatorial Theory (J. N. Srivastava et al. eds.), pp. 437-448, North-Holland, Amsterdam, 1973.

LINKS

T. D. Noe, Table of n, a(n) for n=0..200

E. A. Bender and N. C. Wormald, The number of loopless planar maps, Discr. Math. 54:2 (1985), 235-237.

William G. Brown, Enumeration of Triangulations of the Disk, Proc. Lond. Math. Soc. s3-14 (1964) 746-768.

F. Chapoton, Sur le nombre d'intervalles dans les treillis de Tamari, arXiv:math/0602368 [math.CO], 2006.

G. Chatel and V. Pons, Counting smaller elements in the Tamari and m-Tamari lattices, arXiv preprint arXiv:1311.3922 [math.CO], 2013.

F. David, A model of random surfaces with nontrivial critical behavior, Nuclear Physics B, v. 257 (1985), 543-576.

Wenjie Fang, Planar triangulations, bridgeless planar maps and Tamari intervals, arXiv:1611.07922 [math.CO], 2016.

C. Germain and J. Pallo, The number of coverings in four Catalan lattices, Intern. J. Computer Math., Vol. 61 (1996) pp. 19-28. (See p. 27.)

Z. Li and Y. Liu, Chromatic sums of general maps on the sphere and the projective plane, Discr. Math. 307 (2007), 78-87.

W. T. Tutte, A census of Hamiltonian polygons, Canad. J. Math., 14 (1962), 402-417.

William T. Tutte, A census of planar triangulations, Canad. J. Math. 14 (1962), 21-38. See Eq. 5.12.

William T. Tutte, On the enumeration of convex polyhedra, J. Combin. Theory Ser. B 28 (1980), no. 2, 105--126. MR0572468 (81j:05073).

T. R. S. Walsh, A. B. Lehman, Counting rooted maps by genus. III: Nonseparable maps, J. Combinatorial Theory Ser. B 18 (1975), 222-259.

FORMULA

a(n) = 2(4n+1)! / ((n+1)!(3n+2)!) = binomial(4n+1, n+1) - 9*binomial(4n+1, n-1).

G.f.: (2-g)*g^2 where g = 1+x*g^4 is the g.f. of A002293. - Mark van Hoeij, Nov 10 2011

G.f.: hypergeom([1,1/2,3/4,5/4],[2,4/3,5/3],256/27*x )= =1+120*x/(Q(0)-120*x); Q(k)=8*x*(2*k+1)*(4*k+3)*(4*k+5)+3*(k+2)*(3*k+4)*(3*k+5)-24*x*(k+2)*(2*k+3)*(3*k+4)*(3*k+5)*(4*k+7)*(4*k+9)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 25 2011

a(n) = binomial( 4*n + 2, n + 1) / ((2*n + 1) * (3*n + 2)). - Michael Somos, Mar 28 2012

a(n) * (n + 1) = A069271(n). - Michael Somos, Mar 2012

0 = F( a(n), a(n+1), ... , a(n+8) ) for all n in Z where a(-1) = 3/4 and F() is a polynomial of degree 2 with integer coefficients and 29 monomials. - Michael Somos, Dec 23 2014

3*(3*n+2)*(3*n+1)*(n+1)*a(n) -8*(4*n+1)*(2*n-1)*(4*n-1)*a(n-1)=0. - R. J. Mathar, Oct 21 2015

a(n) = Sum_{k=1..A000108(n)} k * A263191(n,k). - Alois P. Heinz, Nov 16 2015

a(n) ~ 2^(8*n+7/2) / (sqrt(Pi) * n^(5/2) * 3^(3*n+5/2)). - Vaclav Kotesovec, Feb 26 2016

E.g.f.: 3F3(1/2,3/4,5/4; 4/3,5/3,2; 256*x/27). - Ilya Gutkovskiy, Feb 01 2017

EXAMPLE

G.f. = 1 + x + 3*x^2 + 13*x^3 + 68*x^4 + 399*x^5 + 2530*x^6 + 16965*x^7 + ...

MAPLE

A000260 := proc(n)

    2*(4*n+1)!/((n+1)!*(3*n+2)!) ;

end proc:

MATHEMATICA

Table[Binomial[4n+1, n+1]-9*Binomial[4n+1, n-1], {n, 0, 25}] (* Harvey P. Dale, Aug 23 2011 *)

a[ n_] := SeriesCoefficient[ HypergeometricPFQ[ {1/2, 3/4, 1, 5/4}, {4/3, 5/3, 2}, 256/27 x], {x, 0, n}]; (* Michael Somos, Dec 23 2014 *)

PROG

(PARI) {a(n) = if( n<0, 0, 2 * (4*n + 1)! / ((n + 1)! * (3*n + 2)!))}; /* Michael Somos, Sep 07 2005 */

(PARI) {a(n) = binomial( 4*n + 2, n + 1) / ((2*n + 1) * (3*n + 2))}; /* Michael Somos, Mar 28 2012 */

(Sage) a = lambda(n): binomial( 4*n + 2, n + 1) / ((2*n + 1) * (3*n + 2))  # F. Chapoton, Aug 06 2015

(MAGMA) [Binomial(4*n+1, n+1)-9*Binomial(4*n+1, n-1): n in [0..25]]; // Vincenzo Librandi, Nov 24 2016

CROSSREFS

Cf. A000256, A027836, A069271, A263191.

Sequence in context: A054132 A047149 A200757 * A192737 A125279 A186371

Adjacent sequences:  A000257 A000258 A000259 * A000261 A000262 A000263

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

Edited by F. Chapoton, Feb 03 2011

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 April 29 21:06 EDT 2017. Contains 285614 sequences.