A342980 -id:A342980 - cp's OEIS frontend

A342981 Triangle read by rows: T(n,k) is the number of rooted planar maps with n edges, k faces and no isthmuses, n >= 0, k = 1..n+1.

1, 0, 1, 0, 1, 2, 0, 1, 7, 5, 0, 1, 16, 37, 14, 0, 1, 30, 150, 176, 42, 0, 1, 50, 449, 1104, 794, 132, 0, 1, 77, 1113, 4795, 7077, 3473, 429, 0, 1, 112, 2422, 16456, 41850, 41504, 14893, 1430, 0, 1, 156, 4788, 47832, 189183, 319320, 228810, 63004, 4862

Offset: 0

Andrew Howroyd, Apr 02 2021

The number of vertices is n + 2 - k.
For k >= 2, column k is a polynomial of degree 3*(k-2). This is because adding a face can increase the number of vertices whose degree is greater than two by at most two.
By duality, also the number of loopless rooted planar maps with n edges and k vertices.

			Triangle begins:
  1;
  0, 1;
  0, 1,   2;
  0, 1,   7,    5;
  0, 1,  16,   37,    14;
  0, 1,  30,  150,   176,    42;
  0, 1,  50,  449,  1104,   794,   132;
  0, 1,  77, 1113,  4795,  7077,  3473,   429;
  0, 1, 112, 2422, 16456, 41850, 41504, 14893, 1430;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. III: Nonseparable maps, J. Combinatorial Theory Ser. B 18 (1975), 222-259, Table VIb.

Columns k=3..4 are A005581, A006468.
Diagonals are A000108, A006419, A006420, A006421.
Row sums are A000260.
Cf. A002293, A027836, A082680, A269920, A342980, A343092.

G[m_, y_] := Sum[x^n*Sum[(n + k - 1)!*(2*n - k)!*y^k/(k!*(n + 1 - k)!*(2*k - 1)!*(2*n - 2*k + 1)!), {k, 1, n}], {n, 1, m}] + O[x]^m;
H[n_] := With[{g = 1 + x*y + x*G[n - 1, y]}, Sqrt[InverseSeries[x/g^2 + O[x]^(n + 1), x]/x]];
CoefficientList[#, y]& /@ CoefficientList[H[10], x] // Flatten (* Jean-François Alcover, Apr 15 2021, after Andrew Howroyd *)

\\ here G(n, y) gives A082680 as g.f.
G(n,y)={sum(n=1, n, x^n*sum(k=1, n, (n+k-1)!*(2*n-k)!*y^k/(k!*(n+1-k)!*(2*k-1)!*(2*n-2*k+1)!))) + O(x*x^n)}
H(n)={my(g=1+x*y+x*G(n-1, y), v=Vec(sqrt(serreverse(x/g^2)/x))); vector(#v, n, Vecrev(v[n], n))}
{ my(T=H(8)); for(n=1, #T, print(T[n])) }

G.f. A(x,y) satisfies A(x) = G(x*A(x,y)^2, y) where G(x,y) = 1 + x*y + x*B(x,y) and B(x,y) is the g.f. of A082680.
A027836(n+1) = Sum_{k=1..n+1} k*T(n,k).
A002293(n) = Sum_{k=1..n+1} k*T(n,n+2-k).

A342985 Triangle read by rows: T(n,k) is the number of tree-rooted loopless planar maps with n edges, k faces and no isthmuses, n >= 0, k = 1..n+1.

Original entry on oeis.org

1, 0, 0, 0, 2, 0, 0, 3, 3, 0, 0, 4, 36, 4, 0, 0, 5, 135, 135, 5, 0, 0, 6, 360, 1368, 360, 6, 0, 0, 7, 798, 7350, 7350, 798, 7, 0, 0, 8, 1568, 28400, 73700, 28400, 1568, 8, 0, 0, 9, 2826, 89073, 474588, 474588, 89073, 2826, 9, 0, 0, 10, 4770, 241220, 2292790, 4818092, 2292790, 241220, 4770, 10, 0

Offset: 0

Andrew Howroyd, Apr 03 2021

The number of vertices is n + 2 - k.

For k >= 2, column k without the initial zero term is a polynomial of degree 4*(k-2)+1.

			Triangle begins:
  1;
  0, 0;
  0, 2,    0;
  0, 3,    3,     0;
  0, 4,   36,     4,     0;
  0, 5,  135,   135,     5,     0;
  0, 6,  360,  1368,   360,     6,    0;
  0, 7,  798,  7350,  7350,   798,    7, 0;
  0, 8, 1568, 28400, 73700, 28400, 1568, 8, 0;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. III: Nonseparable maps, J. Combinatorial Theory Ser. B 18 (1975), 222-259, Table VIIIa.

Columns and diagonals 3..5 are A006428, A006429, A006430.
Row sums are A342986.
Cf. A342980, A342982, A342984, A342987.

\\ here G(n,y) is A342984 as g.f.
F(n,y)={sum(n=0, n, x^n*sum(i=0, n, my(j=n-i); y^i*(2*i+2*j)!/(i!*(i+1)!*j!*(j+1)!))) + O(x*x^n)}
G(n,y)={my(g=F(n,y)); subst(g, x, serreverse(x*g^2))}
H(n)={my(g=G(n, y)-x*(1+y), v=Vec(sqrt(serreverse(x/g^2)/x))); vector(#v, n, Vecrev(v[n], n))}
{ my(T=H(8)); for(n=1, #T, print(T[n])) }

T(n,n+2-k) = T(n,k).

G.f.: A(x,y) satisfies A(x,y) = G(x*A(x,y)^2,y) where G(x,y) + x*(1+y) is the g.f. of A342984.

A343090 Triangle read by rows: T(n,k) is the number of rooted toroidal maps with n edges and k faces and without separating cycles or isthmuses, n >= 2, k = 1..n-1.

Original entry on oeis.org

1, 4, 4, 10, 47, 10, 20, 240, 240, 20, 35, 831, 2246, 831, 35, 56, 2282, 12656, 12656, 2282, 56, 84, 5362, 52164, 109075, 52164, 5362, 84, 120, 11256, 173776, 648792, 648792, 173776, 11256, 120, 165, 21690, 495820, 2978245, 5360286, 2978245, 495820, 21690, 165

Offset: 2

Andrew Howroyd, Apr 04 2021

The number of vertices is n-k.

Column k is a polynomial of degree 3*k. This is because adding a face can increase the number of vertices whose degree is greater than two by at most two.

			Triangle begins:
    1;
    4,     4;
   10,    47,     10;
   20,   240,    240,     20;
   35,   831,   2246,    831,     35;
   56,  2282,  12656,  12656,   2282,     56;
   84,  5362,  52164, 109075,  52164,   5362,    84;
  120, 11256, 173776, 648792, 648792, 173776, 11256, 120;
  ...

Andrew Howroyd, Table of n, a(n) for n = 2..1276
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. III: Nonseparable maps, J. Combinatorial Theory Ser. B 18 (1975), 222-259, Table VIc.

Columns 1..4 are A000292, A006422, A006423, A006424.
Row sums are A343091.
Cf. A269921, A342980, A342989, A343092.

\\ Needs F from A342989.
G(n,m,y,z)={my(p=F(n,m,y,z)); subst(p, x, serreverse(x*p^2))}
H(n, g=1)={my(q=G(n, g, 'y, 'z)-x*(1+'z), v=Vec(polcoef(sqrt(serreverse(x/q^2)/x), g, 'y))); [Vecrev(t) | t<-v]}
{ my(T=H(10)); for(n=1, #T, print(T[n])) }

T(n,n-k) = T(n,k).

A099553 Number of rooted 2-connected loopless 4-regular planar maps with n inner faces.

Original entry on oeis.org

1, 2, 10, 42, 209, 1066, 5726, 31688, 180234, 1047356, 6198500, 37253790, 226891665, 1397880330, 8699804598, 54629525808, 345778883678, 2204263514460, 14142192816908, 91263177339092, 592069697914170, 3859674384409668, 25272938482712044

Offset: 3

N. J. A. Sloane, Nov 18 2004

nonn

a(n) is also the number of rooted loopless planar maps with n-1 edges and no isthmuses. - Andrew Howroyd, Apr 01 2021

a(n) is also the number of rooted 2-connected plane quadrangulations with n+1 vertices (allowing multiple edges). - Brendan McKay, Apr 08 2025

			A(x) = x^3 + 2*x^4 + 10*x^5 + 42*x^6 + 209*x^7 + 1066*x^8 + 5726*x^9 + ...

Gheorghe Coserea, Table of n, a(n) for n = 3..305
Han Ren, Yanpei Liu and Zhaoxiang Li, Enumeration of 2-connected Loopless 4-regular Maps on the Plane, European J. Combin., 23 (2002), 93-111.
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. III: Nonseparable maps, J. Combinatorial Theory Ser. B 18 (1975), 222-259, eq (7).

Row sums of A342980.

Cf. A000139, A058860, A290326.

A099553 := proc(n)
    local e;
    e := n-1 ;
    add(binomial(2*e-r,e-2-2*r)*2^r*binomial(2*e,r),r=0..floor(e/2-1)) ;
    %-3*add(binomial(2*e-r,e-3-2*r)*2^r*binomial(2*e,r),r=0..floor((e-3)/2)) ;
    %*2/e ;
end proc:
seq(A099553(n),n=3..30) ; # R. J. Mathar, Aug 28 2018

a[n_] := Module[{e, s}, e = n-1; s = Sum[Binomial[2e-r, e-2-2r]*2^r*Binomial[2e, r], {r, 0, Floor[e/2-1]}]; s = s-3*Sum[Binomial[2e-r, e-3-2r]*2^r*Binomial[2e, r], {r, 0, Floor[(e-3)/2]}]; s=2s/e];
Table[a[n], {n, 3, 30}] (* Jean-François Alcover, Feb 14 2023, after R. J. Mathar *)

F = (2*z^3*x^2 + (2*z^3 - 2*z)*x + (-z + 1))/(-2*z^3*x + 2*z);
G = x*(4*x + 1)*z^4 + 4*x*z^3 - 5*x*z^2 - 2*z + 2;
Z(N) = {
  my(z0=1+O('x^N), z1=0, n=1);
  while (n++,
    z1 = z0 - subst(G, 'z, z0)/subst(deriv(G,'z), 'z, z0);
    if (z1 == z0, break()); z0 = z1);
  z0;
};
seq(N) = Vec(subst(F, 'z, Z(N+3)));
seq(23)
\\ test: y = Ser(seq(303))*'x^3; 0 == 8*y^4 + (32*x + 12)*y^3 + (48*x^2 + 23*x + 6)*y^2 + (32*x^3 + 10*x^2 - 10*x + 1)*y + x^3*(8*x - 1)
\\ Gheorghe Coserea, Jul 13 2018

seq(n)={my(g=1+x*sum(n=1,n,x^n*binomial(3*n, n)*2/((n+1)*(2*n+1))) + O(x*x^n)); Vec(-1 + sqrt(serreverse(x/g^2)/x))} \\ Andrew Howroyd, Apr 06 2021

From Gheorghe Coserea, Jul 12 2018: (Start)
G.f. A(x) = (2*z^3*x^2 + (2*z^3 - 2*z)*x + (-z + 1))/(-2*z^3*x + 2*z), where z = 1 + 2*x^2 + 6*x^3 + 34*x^4 + 176*x^5 + 1004*x^6 + ... satisfies 0 = x*(4*x + 1)*z^4 + 4*x*z^3 - 5*x*z^2 - 2*z + 2. (See Theorem D in reference.)
G.f. y=A(x) satisfies:
0 = 8*y^4 + (32*x + 12)*y^3 + (48*x^2 + 23*x + 6)*y^2 + (32*x^3 + 10*x^2 - 10*x + 1)*y + x^3*(8*x - 1).
0 = x^3*(2*x + 1)*(49*x - 18)*(196*x - 27)*y'''' + x^2*(96040*x^3 - 27587*x^2 - 9297*x + 972)*y''' + (72030*x^4 - 36309*x^3 + 2010*x^2 - 864*x)*y'' - 6*(8*x + 3)*(49*x + 12)*y' + (2352*x + 576)*y.
(End)
Conjecture: 3*n *(3*n-1) *(5*n-8) *(3*n-2)*a(n) -(n-2) *(2*n-3) *(355*n^2 -703*n +300)*a(n-1) -98*(n-2) *(5*n-3) *(2*n-3) *(2*n-5) *a(n-2)=0. - R. J. Mathar, Aug 28 2018
G.f.: x*(A(x) - 1) where A(x) satisfies A(x) = G(x*A(x)^2) and (G(x) + 2*x - 1)/x is the g.f. of A000139. - Andrew Howroyd, Apr 06 2021

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.

Original entry on oeis.org

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

N. J. A. Sloane

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

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

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

Column k=3 of A342980.

Cf. A049600.

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

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

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

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

Name clarified by Andrew Howroyd, Apr 01 2021

A006417 Number of loopless rooted planar maps with 4 faces and n vertices and no isthmuses.

Original entry on oeis.org

1, 20, 131, 469, 1262, 2862, 5780, 10725, 18647, 30784, 48713, 74405, 110284, 159290, 224946, 311429, 423645, 567308, 749023, 976373, 1258010, 1603750, 2024672, 2533221, 3143315, 3870456, 4731845, 5746501, 6935384, 8321522, 9930142, 11788805, 13927545, 16379012

Offset: 2

N. J. A. Sloane

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

Andrew Howroyd, Table of n, a(n) for n = 2..1000
T. R. S. Walsh and 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 (7,-21,35,-35,21,-7,1).

Column k=4 of A342980.

a(n)={if(n<2, 0, (2*n^6 + 39*n^5 + 125*n^4 - 345*n^3 - 1027*n^2 + 846*n + 2160)/360)} \\ Andrew Howroyd, Apr 01 2021

From Colin Barker, Apr 08 2013: (Start)
a(n) = (2160+846*n-1027*n^2-345*n^3+125*n^4+39*n^5+2*n^6)/360.
G.f.: -x^2*(5*x^6-29*x^5+65*x^4-63*x^3+12*x^2+13*x+1) / (x-1)^7. (End)
E.g.f.: exp(x)*(2160 - 360*x - 540*x^2 + 1560*x^3 + 645*x^4 + 69*x^5 + 2*x^6)/360 - 6 - 5*x. - Stefano Spezia, Jul 18 2024

Title improved by Sean A. Irvine, Apr 03 2017

Terms a(14) and beyond from Andrew Howroyd, Apr 01 2021

A006418 Number of loopless rooted planar maps with 5 faces and n vertices and no isthmuses.

Original entry on oeis.org

1, 38, 469, 3008, 12843, 42602, 119042, 293578, 658021, 1367170, 2670203, 4953136, 8794967, 15040494, 24893192, 40031954, 62755945, 96162286, 144361777, 212738384, 308258755, 439838594, 618773310, 859240970, 1178886221, 1599494506, 2147766583, 2856204064

Offset: 2

N. J. A. Sloane

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 2..1000
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 (10, -45, 120, -210, 252, -210, 120, -45, 10, -1).

Column k=5 of A342980.

a(n)={if(n<2, 0, (2*n^9 + 81*n^8 + 918*n^7 + 2142*n^6 - 11886*n^5 - 42651*n^4 + 65182*n^3 + 282348*n^2 - 114696*n - 604800)/30240)} \\ Andrew Howroyd, Apr 01 2021

G.f.: x^2 * (14*x^9 -120*x^8 +440*x^7 -879*x^6 +980*x^5 -482*x^4 -92*x^3 +134*x^2 +28*x+1) / (x-1)^10. - Colin Barker, Apr 09 2013

Name clarified and terms a(13) and beyond from Andrew Howroyd, Apr 01 2021

cp's OEIS Frontend

A342981 Triangle read by rows: T(n,k) is the number of rooted planar maps with n edges, k faces and no isthmuses, n >= 0, k = 1..n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A342985 Triangle read by rows: T(n,k) is the number of tree-rooted loopless planar maps with n edges, k faces and no isthmuses, n >= 0, k = 1..n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A343090 Triangle read by rows: T(n,k) is the number of rooted toroidal maps with n edges and k faces and without separating cycles or isthmuses, n >= 2, k = 1..n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A099553 Number of rooted 2-connected loopless 4-regular planar maps with n inner faces.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A006417 Number of loopless rooted planar maps with 4 faces and n vertices and no isthmuses.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A006418 Number of loopless rooted planar maps with 5 faces and n vertices and no isthmuses.

Views

Author

Keywords

References

Links