login
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)
4

%I M4490 #69 Apr 13 2022 13:25:18

%S 1,8,20,38,63,96,138,190,253,328,416,518,635,768,918,1086,1273,1480,

%T 1708,1958,2231,2528,2850,3198,3573,3976,4408,4870,5363,5888,6446,

%U 7038,7665,8328,9028,9766,10543,11360,12218,13118,14061,15048

%N 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.

%C 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

%C 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

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

%H T. D. Noe, <a href="/A006416/b006416.txt">Table of n, a(n) for n=2..1000</a>

%H Milan Janjic, <a href="http://www.pmfbl.org/janjic/">Two Enumerative Functions</a>

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H T. R. S. Walsh, A. B. Lehman, <a href="https://dx.doi.org/10.1016/0095-8956(75)90050-7">Counting rooted maps by genus. III: Nonseparable maps</a>, J. Combinatorial Theory Ser. B 18 (1975), 222-259.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4, -6, 4, -1).

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

%F a(n-3) = (1/6)*n^3-(1/2)*n^2-(8/3)*n+6, n=6,7,... - _Milan Janjic_, Nov 09 2007

%F 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

%F a(n+2) = Hyper2F1([-3, n], [1], -1). - _Peter Luschny_, Aug 02 2014

%F a(n) = binomial(n+3, 3) - 3*(n+1). - _Robert H Cowen_, Jun 23 2018

%p A006416:=(1+4*z-6*z**2+2*z**3)/(z-1)**4; # Conjectured by _Simon Plouffe_ in his 1992 dissertation.

%p a := n -> hypergeom([-3, n-2], [1], -1);

%p seq(round(evalf(a(n),32)), n=2..41); # _Peter Luschny_, Aug 02 2014

%t f[n_]:=Sum[i+i^2-6,{i,1,n}]/2;Table[f[n],{n,3,5!}] (* _Vladimir Joseph Stephan Orlovsky_, Mar 08 2010 *)

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

%t f[n_]:= Binomial[n,3] - 3(n-2); Table[{n,f[n]},{n,5,100}]//TableForm (* _Robert H Cowen_, Jun 23 2018 *)

%o (PARI) Vec((1+4*x-6*x^2+2*x^3)/(1-x)^4 + O(x^40)) \\ _Andrew Howroyd_, Jul 15 2018

%Y Column k=3 of A342980.

%Y Cf. A049600.

%K nonn,easy,nice

%O 2,2

%A _N. J. A. Sloane_

%E Name clarified by _Andrew Howroyd_, Apr 01 2021