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. (Formerly M4490)

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

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

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

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

Prog

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

Crossrefs

Column k=3 of A342980.

Cf. A049600.

Sequence in context: A073607 A351967 A086062 * A273069 A273144 A272842

Adjacent sequences: A006413 A006414 A006415 * A006417 A006418 A006419

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

Name clarified by Andrew Howroyd, Apr 01 2021

Status

approved