A005470 -id:A005470 - cp's OEIS frontend

A098000 Number of outerplanar graphs on n labeled nodes.

1, 1, 2, 8, 63, 893, 19714, 597510, 22903403, 1056115331, 56744710974, 3475626211316, 238818544070905, 18183183610029003, 1519020289266947462, 138117136134012654182, 13576724206357958780409, 1434561741418662640589225, 162136032834834405685977058, 19516966563322659948894106704

Offset: 0

Steven Finch, Sep 08 2004

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200
M. Bodirsky and M. Kang, The asymptotic number of outerplanar graphs.
S. R. Finch, Planar graph growth constants.
Steven R. Finch, Planar graph growth constants [Cached copy, with permission of the author]

Cf. A097998, A097999, A111564, A005470.

seq(n)={Vec(serlaplace(exp(intformal(serreverse(x/exp((1 + 5*x - sqrt(1 - 6*x + x^2 + O(x^n)))/8))/x))))} \\ Andrew Howroyd, Feb 12 2021

Recurrence known, see Bodirsky and Kang.

Exponential transform of A097998. - Andrew Howroyd, Feb 12 2021

a(0)=1 prepended and terms a(17) and beyond from Andrew Howroyd, Feb 12 2021

A027836 Total number of vertices in all loopless rooted planar maps with n edges.

Original entry on oeis.org

1, 2, 8, 43, 268, 1824, 13156, 98865, 765948, 6075256, 49094708, 402801425, 3346590068, 28099903160, 238079915640, 2032914717645, 17476713955548, 151143219598008, 1314045772469632, 11478299163026540, 100688538612524720, 886622619082002120, 7834289222109530340

Offset: 0

Valery A. Liskovets

nonn

The number of rooted isthmusless n-edge maps in the plane (planar with a distinguished outside face). - Valery A. Liskovets, Mar 17 2005

L. M. Koganov, V. A. Liskovets, T. R. S. Walsh, Total vertex enumeration in rooted planar maps, Ars Combin. 54 (2000), 149-160.
V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

Andrew Howroyd, Table of n, a(n) for n = 0..500
V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., 36, No.4 (2006), 364-387.

Cf. A000260, A005470, A002293, A342981.

12*n*(4*n-1)!*(5*n^2+13*n+2)/(n!*(3*n+3)!);

Join[{1},Table[12n (4n-1)! (5n^2+13n+2)/(n!(3n+3)!),{n,20}]] (* Harvey P. Dale, May 20 2018 *)

a(n) = if(n==0, 1, 12*n*(4*n-1)!*(5*n^2+13*n+2)/(n!*(3*n+3)!)) \\ Andrew Howroyd, Apr 06 2021

a(n) = 12*n*(4*n-1)!*(5*n^2+13*n+2)/(n!*(3*n+3)!) for n > 0.
G.f.: -(1-3*g+g^2)*g where g = 1+x*g^4 is the g.f. of A002293. - Mark van Hoeij, Nov 11 2011
a(n) = Sum_{k=1..n+1} k*A342981(n, k). - Andrew Howroyd, Apr 06 2021

Offset corrected and terms a(21) and beyond from Andrew Howroyd, Apr 06 2021

A039735 Triangle read by rows: T(n,k) = number of nonisomorphic unlabeled planar graphs with n >= 1 nodes and 0 <= k <= 3n-6 edges.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 2, 4, 6, 6, 6, 4, 2, 1, 1, 1, 2, 5, 9, 15, 21, 24, 24, 20, 13, 5, 2, 1, 1, 2, 5, 10, 21, 41, 65, 97, 130, 144, 135, 98, 51, 16, 5, 1, 1, 2, 5, 11, 24, 56, 115, 221, 401, 658, 956, 1217, 1264, 1042, 631, 275, 72, 14, 1, 1, 2, 5

Offset: 1

Brendan McKay

Planar graphs with n >= 3 nodes have at most 3n-6 edges. - Charles R Greathouse IV, Feb 18 2013

			Triangle starts
n\k 0  1  2  3  4  5  6  7  8  9 10 11 12
--:-- -- -- -- -- -- -- -- -- -- -- -- --
1:  1
2:  1  1
3:  1  1  1  1
4:  1  1  2  3  2  1  1
5:  1  1  2  4  6  6  6  4  2  1
6:  1  1  2  5  9 15 21 24 24 20 13  5  2

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. J. Wilson, Introduction to Graph Theory. Academic Press, NY, 1972, p. 162.

F. Harary, The number of linear, directed, rooted, and connected graphs, Trans. Amer. Math. Soc. 78 (1955), 445-463. (MR0068198) See page 457, equation (2.9).

Cf. A005470 (row sums), A008406, A049334.

From Michael Somos, Aug 23 2015: (Start)
Sum_{k} T(n, k) = A005470(n) if n >= 1.
log(1 + A(x, y)) = Sum_{n>0} B(x^n, y^n) / n where A(x, y) = Sum_{n>0, k>=0} T(n,k) * x^n * y^k and similarly B(x, y) with A049334. (End)

A046646 a(n) = 2binomial(3n-3, n-1)/(2*n-1) for n >= 2, and a(1) = 1.

Original entry on oeis.org

1, 2, 6, 24, 110, 546, 2856, 15504, 86526, 493350, 2861430, 16829280, 100134216, 601661144, 3645533040, 22249511328, 136657509918, 844061090670, 5239262085330, 32665844580600, 204480219795390, 1284624902435490

Offset: 1

N. J. A. Sloane

Number of certain rooted planar maps.

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Daniel Birmajer, Juan B. Gil, Michael D. Weiner, Bounce statistics for rational lattice paths, arXiv:1707.09918 [math.CO], 2017, p. 10.
W. G. Brown, Enumeration of non-separable planar maps, Canad. J. Math., 15 (1963), 526-545.
W. G. Brown, Enumeration of non-separable planar maps [Annotated scanned copy]

A diagonal of A046651.

Cf. A046647, A005470, A000139, A001764.

[1] cat [2*Binomial(3*n-3,n-1)/(2*n-1): n in [2..30]]; // Vincenzo Librandi, Oct 13 2013

alias(PS=ListTools:-PartialSums): A046646List := proc(m) local A, P, n;
A := [1,2]; P := [2]; for n from 1 to m - 2 do P := PS(PS([op(P), P[-1]]));
A := [op(A), P[-1]] od; A end: A046646List(22); # Peter Luschny, Mar 26 2022

Join[{1},Table[(2*Binomial[3n-3,n-1])/(2n-1),{n,2,30}]] (* Harvey P. Dale, Oct 12 2013 *)

From Emeric Deutsch, Mar 03 2004: (Start)
a(n) = 2*binomial(3*n-3, n-1)/(2*n-1) for n >= 2, and a(1) = 1.
a(n) = 2*A001764(n-1) for n >= 2. (End)
a(n) = (n+1) * A000139(n). - F. Chapoton, Feb 23 2024
G.f.: (1+g)/(1-g) where g*(1-g)^2 = x. - Mark van Hoeij, Nov 10 2011

More terms from Emeric Deutsch, Mar 03 2004

New name using a formula of Emeric Deutsch by Peter Luschny, Feb 23 2024

A069729 Number of rooted non-separable bi-Eulerian planar maps with 2n edges. Bi-Eulerian means all its vertices and faces are of even valency.

Original entry on oeis.org

1, 1, 2, 8, 54, 442, 4032, 39706, 413358, 4487693, 50348500, 579994802, 6827955072, 81854670861, 996529292432, 12293898494952, 153421680489694, 1934041122204318, 24599034335501730, 315369011873625930, 4072021557616191708, 52915860528084306704, 691646518495876375968

Offset: 0

Valery A. Liskovets, Apr 07 2002

nonn

The formula from the article by Liskovets and Walsh, p. 218, B'ns(n), gives incorrect data {1, 4, 25, 204, 1964, 21070, 243681, ...}. Here is the incorrect formula rewritten into Mathematica: Table[(Sum[(-1)^j*3^(n - j - 1)*Binomial[2*n + j - 1, j] * Sum[(-1)^k*Binomial[j, k]*Binomial[3*n, n - j - k - 1], {k, 0, Min[j, n - j - 1]}], {j, 0, n - 1}] - 2*Sum[(-1)^j*3^(n - j - 1)*Binomial[2*n + j - 1, j] * Sum[(-1)^k*Binomial[j, k]*Binomial[3*n, n - j - k - 2], {k, 0, Min[j, n - j - 2]}], {j, 0, n - 2}])/n, {n, 1, 20}]. - Vaclav Kotesovec, Apr 13 2018

			A(x) = 1 + x + 2*x^2 + 8*x^3 + 54*x^4 + 442*x^5 + 4032*x^6 + ...

Gheorghe Coserea, Table of n, a(n) for n = 0..500
V. A. Liskovets and T. R. S. Walsh, Enumeration of Eulerian and unicursal planar maps, Discr. Math., 282 (2004), 209-221.

Cf. A069726, A005470.

CoefficientList[1 + InverseSeries[Series[-(1+x)^4*(18*x^2-30*x-1 + (1-12*x)^(3/2))/(6*(3*x+2)^3), {x, 0, 25}], x], x] (* Vaclav Kotesovec, Apr 14 2018, after Gheorghe Coserea *)

seq(N) = {
  my(x='x+O('x^(2*N-1)), y=1+serreverse(x/(3*(1+x)^3)), f=(1+3*y-y^2)/3,
     g=subst(f, 'x, 'x^2), v=Vec(subst(g, 'x, serreverse(x*g^2))));
  vector((#v+1)\2, n, v[2*n-1]);
};
seq(23) \\ Gheorghe Coserea, Apr 13 2018

G.f. y=A(x) satisfies 0 = y^9 - y^8 + 18*x*y^6 - 66*x*y^5 + 47*x*y^4 + 81*x^2*y^3 - 81*x^2*y^2 + 27*x^2*y - 3*x^2. - Gheorghe Coserea, Apr 13 2018
a(n) ~ 2^(6*n - 1) * 3^(8*n - 1/2) / (3125 * sqrt(Pi) * 13^(4*n - 5/2) * n^(5/2)). - Vaclav Kotesovec, Apr 13 2018
A(x) = 1 + serreverse(-(1+x)^4*(18*x^2-30*x-1 + (1-12*x)^(3/2))/(6*(3*x+2)^3)); equivalently, it can be rewritten as A(x) = 1 + serreverse((y - 1)*(3*y^2 + y - 1)^4 / (243 * y^6 * (2*y-1)^3)), where y = A000108(3*x). - Gheorghe Coserea, Apr 14 2018

More terms from Gheorghe Coserea, Apr 13 2018

A112944 Number of unrooted regular odd-valent planar maps with 2 vertices; maps are considered up to orientation-preserving homeomorphisms and the vertices are of valency 2n+1.

Original entry on oeis.org

1, 2, 7, 39, 308, 3013, 33300, 394340, 4878109, 62232321, 812825244, 10818489817, 146250545528, 2003199281223, 27747288947266, 388087900316025, 5474206895126243, 77795972452841542, 1112947041203866164, 16016508647052018408, 231727628211887783830, 3368855109532696440867

Offset: 0

Valery A. Liskovets, Oct 10 2005

nonn

			There exist 2 planar maps with two 3-valent vertices: a map with three parallel edges and a map with one loop in each vertex and a link. Therefore a(1)=2.

M. Bousquet, G. Labelle and P. Leroux, Enumeration of planar two-face maps, Discrete Math., vol. 222 (2000), 1-25.
Z. C. Gao, V. A. Liskovets and N. C. Wormald, Enumeration of unrooted odd-valent regular planar maps, Preprint, 2005.

Cf. A005470, A112945, A113181, A113182.

a[n_] := (1/2) Binomial[2n, n] + (1/(4n+2)) Sum[EulerPhi[k] Binomial[2 Floor[n/k], Floor[n/k]]^2, {k, Divisors[2n+1]}];
Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Jul 24 2018 *)

a(n) = binomial(2*n, n)/2 + sumdiv(2*n+1, k, eulerphi(k)* binomial(2*(n\k), (n\k))^2)/(4*n+2); \\ Michel Marcus, Oct 14 2015

a(n) = (1/2)binomial(2n, n) + (1/(4n+2))sum_{k|(2n+1)}phi(k)* binomial(2*floor(n/k), floor(n/k))^2, where phi(k) is the Euler function A000010.

More terms from Michel Marcus, Oct 14 2015

A126201 Number of rooted connected unlabeled planar graphs on n nodes.

Original entry on oeis.org

1, 1, 3, 11, 57, 375, 3398, 40043, 585440, 9895493

Offset: 1

David Applegate and N. J. A. Sloane, Mar 09 2007

Number of "pointed" connected planar graphs on n nodes: number of pairs (G,P) where G is a connected unlabeled planar graph with n nodes and P runs through the orbit representatives of nodes in G under the action of Aut(G).

For n <= 4 this agrees with A126100; a(5) = A126100(5) - 1 = 57, since K_5 is the only excluded graph on 5 nodes.

Cf. A005470, A039735, A126100.

a(6)-a(10) from Brendan McKay, Mar 10 2007

A103941 Number of unrooted loopless n-edge maps in the plane (planar with a distinguished outside face).

Original entry on oeis.org

1, 1, 2, 6, 22, 103, 614, 3872, 26414, 186988, 1367976, 10254326, 78461338, 610598818, 4821248244, 38546510368, 311560875422, 2542507084588, 20925300483992, 173530381632724, 1448900079476152, 12172334379246523, 102833593763830038, 873187910184763024, 7449120536014301138

Offset: 0

Valery A. Liskovets, Mar 17 2005

V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

Andrew Howroyd, Table of n, a(n) for n = 0..500
V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., 36, No.4 (2006), 364-387.

Cf. A002293, A006390, A103942, A000260, A005470.

a[n_] := (1/(2n)) (Binomial[4n, n]/(3n+1) + Sum[Boole[0 < k < n] EulerPhi[ n/k] Binomial[4k, k], {k, Divisors[n]}] + q[n]);
q[n_] := If[EvenQ[n], 0, Binomial[2n, (n-1)/2]];
Array[a, 20] (* Jean-François Alcover, Sep 01 2019 *)

a(n) = {if(n==0, 1, (sumdiv(n, d, if(dAndrew Howroyd, Mar 28 2021

For n > 0, a(n) = (1/(2n))*[binomial(4n, n)/(3n+1) + Sum_{0A000010, q(n)=0 if n is even and q(n)=binomial(2n, (n-1)/2) if n is odd.

a(0)=1 prepended and terms a(21) and beyond from Andrew Howroyd, Mar 28 2021

A361366 Number of unlabeled simple planar digraphs with n nodes.

Original entry on oeis.org

1, 3, 16, 218, 9026, 907123

Offset: 1

Manfred Scheucher, Mar 09 2023

M. Kirchweger, M. Scheucher, and S. Szeider, SAT-Based Generation of Planar Graphs, in preparation.

Directed variant of A005470.

Cf. A000273

A006849 Number of strongly self-dual planar maps with 2n edges.

Original entry on oeis.org

2, 9, 69, 567, 5112, 48114, 469179, 4691115, 47849940, 495893502, 5206886874, 55273052646, 592211326464, 6395881806180, 69555215111319, 761015877850035, 8371174661041500, 92523509359662150, 1027010953940099238

Offset: 1

N. J. A. Sloane

A planar map is called strongly self-dual if it is self-dual with respect to an orientation-preserving duality. - Valery A. Liskovets, May 27 2006

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

Gheorghe Coserea, Table of n, a(n) for n = 1..200
V. A. Liskovets, Enumeration of nonisomorphic planar maps, Selecta Math. Sovietica, 4 (No. 4, 1985), 303-323.

Cf. A005159, A000108, A005470.

With[{nn = 21}, CoefficientList[InverseSeries[Series[2*x/(12*x^2 + 12*x + 3), {x, 0, nn}]] + InverseSeries[Series[2*x/(12*x^2 + 1), {x, 0, nn}]], x]] (* Gheorghe Coserea, Aug 15 2015 *)
a[n_] := 3^n*CatalanNumber[n]/2 + If[OddQ[n], 3^((n-1)/2)*CatalanNumber[(n-1)/2]/2, 0]; Array[a, 20] (* Jean-François Alcover, Jan 17 2018 *)

C = n -> binomial(2*n, n) / (n + 1);
a(n) = if (n%2, ( 3^n*C(n) + 3^((n-1)/2)*C((n-1)/2) )/2, 3^n*C(n)/2);
apply(n -> a(n), vector(30, i, i)) \\ Gheorghe Coserea, Aug 04 2015

x='x + O('x^33); Vec(-1/2 + 1/(1 + (1 - 12*x)^(1/2)) + x/(1 + (1 - 12*x^2)^(1/2))) \\ Gheorghe Coserea, Aug 15 2015

a(2k) = 3^(2k)C(2k)/2=A005159(2k)/2 (4k edges, k>0) and a(2k-1) = (3^(2k-1)C(2k-1)+3^(k-1)C(k-1))/2 =(A005159(2k-1)+A005159(k-1))/2 (4k-2 edges, k>0) where C(n) = A000108(n) (Catalan numbers). - Valery A. Liskovets, May 27 2006

G.f.: -1/2 + 1/(1 + (1 - 12*x)^(1/2)) + x/(1 + (1 - 12*x^2)^(1/2)). - Gheorghe Coserea, Aug 15 2015

More terms from Valery A. Liskovets, May 27 2006

cp's OEIS Frontend

A098000 Number of outerplanar graphs on n labeled nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A027836 Total number of vertices in all loopless rooted planar maps with n edges.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A039735 Triangle read by rows: T(n,k) = number of nonisomorphic unlabeled planar graphs with n >= 1 nodes and 0 <= k <= 3n-6 edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A046646 a(n) = 2*binomial(3*n-3, n-1)/(2*n-1) for n >= 2, and a(1) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions

A069729 Number of rooted non-separable bi-Eulerian planar maps with 2n edges. Bi-Eulerian means all its vertices and faces are of even valency.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A112944 Number of unrooted regular odd-valent planar maps with 2 vertices; maps are considered up to orientation-preserving homeomorphisms and the vertices are of valency 2n+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A126201 Number of rooted connected unlabeled planar graphs on n nodes.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A046646 a(n) = 2binomial(3n-3, n-1)/(2*n-1) for n >= 2, and a(1) = 1.