A006416 Number of loopless rooted planar maps with 3 faces and n vertices and no isthmuses. Also a(n)=T(4,n-3), array T as in A049600.

1, 8, 20, 38, 63, 96, 138, 190, 253, 328, 416, 518, 635, 768, 918, 1086, 1273, 1480, 1708, 1958, 2231, 2528, 2850, 3198, 3573, 3976, 4408, 4870, 5363, 5888, 6446, 7038, 7665, 8328, 9028, 9766, 10543, 11360, 12218, 13118, 14061, 15048

Offset: 2

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

If Y_i (i=1,2,3) are 2-blocks of an n-set X then, for n>=6, a(n-3) is the number of (n-3)-subsets of X intersecting each Y_i (i=1,2,3). - Milan Janjic, Nov 09 2007

a(n) is also the number of triangle subgraphs in a complete graph on n+3 vertices, minus 3 non-incident edges, for n > 2. - Robert H Cowen, Jun 23 2018

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n=2..1000
• Milan Janjic, Two Enumerative Functions
• 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, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• T. R. S. Walsh, A. B. Lehman, Counting rooted maps by genus. III: Nonseparable maps, J. Combinatorial Theory Ser. B 18 (1975), 222-259.
• Index entries for linear recurrences with constant coefficients, signature (4, -6, 4, -1).

Crossrefs

Column k=3 of A342980.

Cf. A049600.

Programs

Maple

A006416:=(1+4*z-6*z**2+2*z**3)/(z-1)**4; # Conjectured by Simon Plouffe in his 1992 dissertation.
a := n -> hypergeom([-3, n-2], [1], -1);
seq(round(evalf(a(n),32)), n=2..41); # Peter Luschny, Aug 02 2014

Mathematica

f[n_]:=Sum[i+i^2-6,{i,1,n}]/2;Table[f[n],{n,3,5!}] (* Vladimir Joseph Stephan Orlovsky, Mar 08 2010 *)
CoefficientList[Series[(1+4x-6x^2+2x^3)/(1-x)^4,{x,0,50}],x] (* or *) LinearRecurrence[{4,-6,4,-1},{1,8,20,38},50] (* Harvey P. Dale, Aug 25 2013 *)
f[n_]:= Binomial[n,3] - 3(n-2); Table[{n,f[n]},{n,5,100}]//TableForm (* Robert H Cowen, Jun 23 2018 *)

PARI

Vec((1+4*x-6*x^2+2*x^3)/(1-x)^4 + O(x^40)) \\ Andrew Howroyd, Jul 15 2018

Formula

G.f.: x^2*(1+4*x-6*x^2+2*x^3)/(1-x)^4.

a(n-3) = (1/6)*n^3-(1/2)*n^2-(8/3)*n+6, n=6,7,... - Milan Janjic, Nov 09 2007

a(2)=1, a(3)=8, a(4)=20, a(5)=38, a(n)=4*a(n-1)-6*a(n-2)+4*a(n-3)-a(n-4). - Harvey P. Dale, Aug 25 2013

a(n+2) = Hyper2F1([-3, n], [1], -1). - Peter Luschny, Aug 02 2014

a(n) = binomial(n+3, 3) - 3*(n+1). - Robert H Cowen, Jun 23 2018

Extensions

Name clarified by Andrew Howroyd, Apr 01 2021