cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-5 of 5 results.

A008406 Triangle T(n,k) read by rows, giving number of graphs with n nodes (n >= 1) and k edges (0 <= k <= n(n-1)/2).

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, 1, 2, 5, 9, 15, 21, 24, 24, 21, 15, 9, 5, 2, 1, 1, 1, 1, 2, 5, 10, 21, 41, 65, 97, 131, 148, 148, 131, 97, 65, 41, 21, 10, 5, 2, 1, 1, 1, 1, 2, 5, 11, 24, 56, 115, 221, 402, 663, 980, 1312, 1557, 1646, 1557
Offset: 1

Views

Author

N. J. A. Sloane, Mar 15 1996

Keywords

Comments

T(n,k)=1 for n>=2 with k=0, k=1, k=n*(n-1)/2-1 and k=n*(n-1)/2 (therefore the quadruple {1,1,1,1} marks the transition to the next sublist for a given number of vertices (n>2)). [Edited by Peter Munn, Mar 20 2021]

Examples

			Triangle begins:
1,
1,1,
1,1,1,1,
1,1,2,3,2,1,1, [graphs with 4 nodes and from 0 to 6 edges]
1,1,2,4,6,6,6,4,2,1,1,
1,1,2,5,9,15,21,24,24,21,15,9,5,2,1,1,
1,1,2,5,10,21,41,65,97,131,148,148,131,97,65,41,21,10,5,2,1,1,
...

References

  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 264.
  • J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
  • F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
  • F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
  • R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

Links

Crossrefs

Row sums give A000088.
Cf. A046742, A046751, A000717, A001432, A001431, A001430, A001433, A001434, A048179, A048180 etc.
Cf. also A039735, A002905, A054924 (connected), A084546 (labeled graphs).
Row lengths: A000124; number of connected graphs for given number of vertices: A001349; number of graphs for given number of edges: A000664.
Cf. also A000055.

Programs

  • Maple
    seq(seq(GraphTheory:-NonIsomorphicGraphs(v,e),e=0..v*(v-1)/2),v=1..9); # Robert Israel, Dec 22 2015
  • Mathematica
    << Combinatorica`; Table[CoefficientList[GraphPolynomial[n, x], x], {n, 8}] // Flatten (* Eric W. Weisstein, Mar 20 2013 *)
<< Combinatorica`; Table[NumberOfGraphs[v, e], {v, 8}, {e, 0, Binomial[v, 2]}] // Flatten (* Eric W. Weisstein, May 17 2017 *)
permcount[v_] := Module[{m=1, s=0, k=0, t}, For[i=1, i <= Length[v], i++, t = v[[i]]; k = If[i>1 && t == v[[i-1]], k+1, 1]; m *= t*k; s += t]; s!/m];
edges[v_, t_] := Product[Product[g = GCD[v[[i]], v[[j]]]; t[v[[i]]*v[[j]]/ g]^g,{j, 1, i-1}], {i, 2, Length[v]}]*Product[c = v[[i]]; t[c]^Quotient[ c-1, 2]*If[OddQ[c], 1, t[c/2]], {i, 1, Length[v]}];
row[n_] := Module[{s = 0}, Do[s += permcount[p]*edges[p, 1 + x^#&], {p, IntegerPartitions[n]}]; s/n!] // Expand // CoefficientList[#, x]&;
Array[row, 8] // Flatten (* Jean-François Alcover, Jan 07 2021, after Andrew Howroyd *)
  • PARI
    permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v,t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i],v[j])); t(v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(c)^((c-1)\2)*if(c%2, 1, t(c/2)))}
G(n, A=0) = {my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i+A)); s/n!}
{ for(n=1, 7, print(Vecrev(G(n)))) } \\ Andrew Howroyd, Oct 22 2019, updated  Jan 09 2024
  • Sage
    def T(n,k):
    return len(list(graphs(n, size=k)))
# Ralf Stephan, May 30 2014

Formula

O.g.f. for n-th row: 1/n! Sum_g det(1-g z^2)/det(1-g z) where g runs through the natural matrix representation of the pair group A^2_n (for A^2_n see F. Harary and E. M. Palmer, Graphical Enumeration, page 83). - Leonid Bedratyuk, Sep 23 2014

Extensions

Additional comments from Arne Ring (arne.ring(AT)epost.de), Oct 03 2002
Text belonging in a different sequence deleted by Peter Munn, Mar 20 2021

A005470 Number of unlabeled planar simple graphs with n nodes.

Original entry on oeis.org

1, 1, 2, 4, 11, 33, 142, 822, 6966, 79853, 1140916, 18681008, 333312451
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Euler transform of A003094. - Christian G. Bower

Examples

			a(2) = 2 since o o and o-o are the two planar simple graphs on two nodes.

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • W. T. Trotter, ed., Planar Graphs, Vol. 9, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Amer. Math. Soc., 1993.
  • Turner, James; Kautz, William H. A survey of progress in graph theory in the Soviet Union. SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 19. - N. J. A. Sloane, Apr 08 2014
  • Vetukhnovskii, F. Ya. "Estimate of the Number of Planar Graphs." In Soviet Physics Doklady, vol. 7, pp. 7-9. 1962. - From N. J. A. Sloane, Apr 08 2014
  • R. J. Wilson, Introduction to Graph Theory. Academic Press, NY, 1972, p. 162.

Links

Crossrefs

Cf. A003094 (connected planar graphs), A034889, A039735 (planar graphs by nodes and edges).
Cf. A126201.

Programs

  • Mathematica
    A003094 = Cases[Import["https://oeis.org/A003094/b003094.txt", "Table"], {, }][[All, 2]];
(* EulerTransform is defined in A005195 *)
EulerTransform[Rest @ A003094] (* Jean-François Alcover, Apr 25 2013, updated Mar 17 2020 *)

Extensions

n=8 term corrected and n=9..11 terms calculated by Brendan McKay
Terms a(0) - a(10) confirmed by David Applegate and N. J. A. Sloane, Mar 09 2007
a(12) added by Vaclav Kotesovec after A003094 (computed by Brendan McKay), Dec 06 2014

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.

Original entry on oeis.org

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

Views

Author

Brendan McKay

Keywords

Comments

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

Examples

			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

Links

Crossrefs

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

Programs

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

Formula

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

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

Views

Author

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

Keywords

Comments

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.

Crossrefs

Cf. A005470, A039735, A126100.

Extensions

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

A343872 Number of planar graphs with n edges and no isolated nodes.

Original entry on oeis.org

1, 1, 2, 5, 11, 26, 68, 177, 497, 1475, 4608, 15188, 52778, 192339, 733676, 2917722, 12052138, 51517308, 227068741, 1028492568
Offset: 0

Views

Author

Andrew Howroyd, May 05 2021

Keywords

Comments

The first difference between this sequence and A000664 is for n=9 edges where we see K_{3,3}, the "utility graph".

Crossrefs

Cf. A000664, A005470, A039735, A046091.

Programs

  • Mathematica
    A046091 = Cases[Import["https://oeis.org/A046091/b046091.txt", "Table"], {, }][[All, 2]];
etr[f_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d f[d], {d, Divisors[j]}] b[n - j], {j, 1, n}]/n]; b];
a = etr[A046091[[# + 1]]&];
a /@ Range[0, Length[A046091]-1] (* Jean-François Alcover, Jan 01 2022 *)

Formula

Euler transform of A046091.
Showing 1-5 of 5 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.