A288265 -id:A288265 - cp's OEIS frontend

A049334 Triangle read by rows: T(n, k) is the number of unlabeled connected planar simple graphs with n >= 1 nodes and 0<=k<=3*n-6 edges.

1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 2, 1, 1, 0, 0, 0, 0, 3, 5, 5, 4, 2, 1, 0, 0, 0, 0, 0, 6, 13, 19, 22, 19, 13, 5, 2, 0, 0, 0, 0, 0, 0, 11, 33, 67, 107, 130, 130, 96, 51, 16, 5, 0, 0, 0, 0, 0, 0, 0, 23, 89, 236, 486, 804, 1112, 1211, 1026, 626, 275, 72, 14, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Brendan McKay

Planar graphs with n >= 3 nodes have at most 3*n-6 edges.

			n\k 0  1  2  3  4  5  6  7  8  9 10 11 12
--:-- -- -- -- -- -- -- -- -- -- -- -- --
1:  1
2:  0  1
3:  0  0  1  1
4:  0  0  0  2  2  1  1
5:  0  0  0  0  3  5  5  4  2  1
6:  0  0  0  0  0  6 13 19 22 19 13  5  2

Georg Grasegger, Table of n, a(n) for n = 1..235 (rows 1..13) (terms n = 1..147 (rows 1..11) from Andrew Howroyd)
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).

Row sums are A003094.
Column sums are A046091.
Cf. A000055, A039735, A049336, A049337, A054924, A288265, A343873 (transpose).

geng -c $n $k:$k | planarg -q | countg -q # Georg Grasegger, Jul 11 2023

T(n, n-1) = A000055(n) and Sum_{k} T(n, k) = A003094(n) if n>=1. - Michael Somos, Aug 23 2015

log(1 + B(x, y)) = Sum{n>0} A(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 A039735. - Michael Somos, Aug 23 2015

A291842 a(n) is the number of labeled connected planar graphs with n edges.

Original entry on oeis.org

1, 3, 17, 140, 1524, 20673, 336259, 6382302, 138525770, 3384987698, 91976075664, 2751117418712, 89832957177685, 3179833729806525, 121286809954760876, 4959277317653328656, 216402696660205555698, 10037527922988058277877, 493159461152794975438450, 25585023231409205439510792

Offset: 1

Gheorghe Coserea, Sep 10 2017

nonn

Gheorghe Coserea, Table of n, a(n) for n = 1..123
E. A. Bender, Z. Gao and N. C. Wormald, The number of labeled 2-connected planar graphs, Electron. J. Combin., 9 (2002), #R43.
P. S. Kolesnikov and B. K. Sartayev, On the special identities of Gelfand--Dorfman algebras, arXiv:2105.13815 [math.RA], 2021.

Cf. A096332, A290326, A291841.

Column sums of A288265.

Q(n,k) = { \\ c-nets with n-edges, k-vertices
  if (k < 2+(n+2)\3 || k > 2*n\3, return(0));
  sum(i=2, k, sum(j=k, n, (-1)^((i+j+1-k)%2)*binomial(i+j-k,i)*i*(i-1)/2*
  (binomial(2*n-2*k+2,k-i)*binomial(2*k-2, n-j) -
  4*binomial(2*n-2*k+1, k-i-1)*binomial(2*k-3, n-j-1))));
};
seq(N) = {
my(x='x+O('x^(N+3)), t='t,
   q=t*x*Ser(vector(N, n, Polrev(vector(2*n\3, k, Q(n,k)),t))),
   d=serreverse((1+x)/exp(q/(2*t^2*x) + t*x^2/(1+t*x))-1),
   g2=intformal(t^2/2*((1+d)/(1+x)-1)),
   b=t*'x^2/2 + 'x*Ser(vector(N+1, n, subst(polcoeff(g2, n, 't),'x,'t))),
   g1=intformal(serreverse('x/exp(b'))/'x),
   e1='x*Ser(vector(N, n, subst(polcoeff(serlaplace(g1), n, 't), 'x, 't))));
   Vec(subst(e1,'t,1));
};
seq(20)

A288266 Triangle read by rows: T(n,k) is the number of labeled planar graphs on n vertices and k edges.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 3, 1, 1, 6, 15, 20, 15, 6, 1, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 4995, 2937, 1125, 195, 1, 21, 210, 1330, 5985, 20349, 54264, 116280, 203490, 293860, 351225, 342405, 255640, 131985, 40950, 5712, 1, 28, 378, 3276, 20475, 98280, 376740, 1184040, 3108105, 6906620, 13112694, 21322812, 29332947, 32823084, 28286520, 17712016, 7513632, 1922760, 223440

Offset: 0

Gheorghe Coserea, Aug 14 2017

Row n >= 3 contains 3*n-5 terms.

			A(x;t) = 1 + x + (1+t)*x^2/2! + (1+3*t+3*t^2+t^3)*x^3/3! + (1+6*t+15*t^2+20*t^3+15*t^4+6*t^5+t^6)*x^4/4! + ...
Triangle starts:
n\k [0] [1] [2]  [3]  [4]   [5]   [6]   [7]   [8]   [9]   [10]  [11]  [12]
[0] 1;
[1] 1;
[2] 1   1;
[3] 1,  3,  3,   1;
[4] 1,  6,  15,  20,  15,   6,    1;
[5] 1,  10, 45,  120, 210,  252,  210,  120,  45,   10;
[6] 1,  15, 105, 455, 1365, 3003, 5005, 6435, 6435, 4995, 2937, 1125, 195;
[7] ...

Gheorghe Coserea, Rows n = 0..126, flattened
E. A. Bender, Z. Gao and N. C. Wormald, The number of labeled 2-connected planar graphs, Electron. J. Combin., 9 (2002), #R43.
M. Bodirsky, C. Groepl and M. Kang, Generating Labeled Planar Graphs Uniformly At Random, Theoretical Computer Science, Volume 379, Issue 3, 15 June 2007, Pages 377-386.
Omer Gimenez, Marc Noy, Asymptotic enumeration and limit laws of planar graphs, J. Amer. Math. Soc. 22 (2009), 309-329.

Cf. A096332, A100960, A266390, A288265, A290326.

Q(n,k) = { \\ c-nets with n-edges, k-vertices
  if (k < 2+(n+2)\3 || k > 2*n\3, return(0));
  sum(i=2, k, sum(j=k, n, (-1)^((i+j+1-k)%2)*binomial(i+j-k,i)*i*(i-1)/2*
  (binomial(2*n-2*k+2,k-i)*binomial(2*k-2, n-j) -
  4*binomial(2*n-2*k+1, k-i-1)*binomial(2*k-3, n-j-1))));
};
A100960_ser(N) = {
my(x='x+O('x^(3*N+1)), t='t+O('t^(N+4)),
   q=t*x*Ser(vector(3*N+1, n, Polrev(vector(min(N+3, 2*n\3), k, Q(n,k)),'t))),
   d=serreverse((1+x)/exp(q/(2*t^2*x) + t*x^2/(1+t*x))-1),
   g2=intformal(t^2/2*((1+d)/(1+x)-1)));
   serlaplace(Ser(vector(N, n, subst(polcoeff(g2, n,'t),'x,'t)))*'x);
};
A288266_seq(N) = {
  my(x='x+O('x^(N+3)), b=t*x^2/2 + serconvol(A100960_ser(N), exp(x)),
     g1=intformal(serreverse(x/exp(b'))/x));
  apply(p->Vecrev(p), Vec(serlaplace(exp(g1))));
};
concat(A288266_seq(8))

A066537(n) = Sum_{k=0..3*n-6} T(n,k) for n >= 3.

A007816(n-3) = T(n, 3*n-6).

cp's OEIS Frontend

A049334 Triangle read by rows: T(n, k) is the number of unlabeled connected planar simple graphs with n >= 1 nodes and 0<=k<=3*n-6 edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

nauty

Formula

A291842 a(n) is the number of labeled connected planar graphs with n edges.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A288266 Triangle read by rows: T(n,k) is the number of labeled planar graphs on n vertices and k edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula