A008406 -id:A008406 - cp's OEIS frontend

A000014 Number of series-reduced trees with n nodes.

0, 1, 1, 0, 1, 1, 2, 2, 4, 5, 10, 14, 26, 42, 78, 132, 249, 445, 842, 1561, 2988, 5671, 10981, 21209, 41472, 81181, 160176, 316749, 629933, 1256070, 2515169, 5049816, 10172638, 20543579, 41602425, 84440886, 171794492, 350238175, 715497037, 1464407113

Offset: 0

N. J. A. Sloane

Other terms for "series-reduced tree": (i) homeomorphically irreducible tree, (ii) homeomorphically reduced tree, (iii) reduced tree, (iv) topological tree.

In a series-reduced tree, vertices cannot have degree 2; they can be leaves or have >= 2 branches.

			G.f. = x + x^2 + x^4 + x^5 + 2*x^6 + 2*x^7 + 4*x^8 + 5*x^9 + 10*x^10 + ...
The star graph with n nodes (except for n=3) is a series-reduced tree. For n=6 the other series-reduced tree is shaped like the letter H. - _Michael Somos_, Dec 19 2014

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 284.
D. G. Cantor, personal communication.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 232.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62, Fig. 3.3.3.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 526.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Matthew Parker, Table of n, a(n) for n = 0..1000 (first 501 terms from Christian G. Bower)
David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], 30 June 2014.
Ira M. Gessel, Good Will Hunting's Problem: Counting Homeomorphically Irreducible Trees, arXiv:2305.03157 [math.CO], 2023.
James Grime and Brady Haran, The problem in Good Will Hunting, 2013 (Numberphile video).
Frank Harary and Geert Prins, The number of homeomorphically irreducible trees and other species, Acta Math., 101 (1959), 141-162.
F. Harary, R. W. Robinson and A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A, 20 (1975), 483-503.
F. Harary, R. W. Robinson and A. J. Schwenk, Corrigenda: Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A 41 (1986), p. 325.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
B. D. McKay, Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes.
B. D. McKay, Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes. [Cached copy of top page only, pdf file, no active links, with permission]
Matthew Parker, The first 2000 terms (7-Zip compressed file)
A. J. Schwenk, Letter to N. J. A. Sloane, Aug 1972
N. J. A. Sloane, Illustration of initial terms
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Series-Reduced Tree
Index entries for sequences related to trees
Index entries for "core" sequences

Cf. A000055 (trees), A001678 (series-reduced planted trees), A007827 (series-reduced trees by leaves), A271205 (series-reduced trees by leaves and nodes).

with(powseries): with(combstruct): n := 30: Order := n+3: sys := {B = Prod(C,Z), S = Set(B,1 <= card), C = Union(Z,S)}:
G001678 := (convert(gfseries(sys,unlabeled,x) [S(x)], polynom)) * x^2: G0temp := G001678 + x^2:
G059123 := G0temp / x + G0temp - (G0temp^2+eval(G0temp,x=x^2))/(2*x):
G000014 := ((x-1)/x) * G059123 + ((1+x)/x^2) * G0temp - (1/x^2) * G0temp^2:
A000014 := 0,seq(coeff(G000014,x^i),i=1..n); # Ulrich Schimke (ulrschimke(AT)aol.com)

a[n_] := If[n<1, 0, A = x/(1-x^2) + x*O[x]^n; For[k=3, k <= n-1, k++, A = A/(1 - x^k + x*O[x]^n)^SeriesCoefficient[A, k]]; s = ((Normal[A] /. x -> x^2) + O[x]^(2n))*(1-x) + A*(2-A)*(1+x); SeriesCoefficient[s, n]/2]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 02 2016, adapted from PARI *)

{a(n) = my(A); if( n<1, 0, A = x / (1 - x^2) + x * O(x^n); for(k=3, n-1, A /= (1 - x^k + x * O(x^n))^polcoeff(A, k)); polcoeff( (subst(A, x, x^2) * (1 - x) + A * (2 - A) * (1 + x)) / 2, n))}; /* Michael Somos, Dec 19 2014 */

G.f.: A(x) = ((x-1)/x)*f(x) + ((1+x)/x^2)*g(x) - (1/x^2)*g(x)^2 where f(x) is g.f. for A059123 and g(x) is g.f. for A001678. [Harary and E. M. Palmer, p. 62, Eq. (3.3.10) with extra -(1/x^2)*Hbar(x)^2 term which should be there according to eq.(3.3.14), p. 63, with eq.(3.3.9)]. [corrected by Wolfdieter Lang, Jan 09 2001]

a(n) ~ c * d^n / n^(5/2), where d = A246403 = 2.189461985660850..., c = 0.684447272004914061023163279794145361469033868145768075109924585532604582794... - Vaclav Kotesovec, Aug 25 2014

A054923 Triangle read by rows: number of connected graphs with k >= 0 edges and n nodes (1<=n<=k+1).

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 2, 3, 0, 0, 0, 1, 5, 6, 0, 0, 0, 1, 5, 13, 11, 0, 0, 0, 0, 4, 19, 33, 23, 0, 0, 0, 0, 2, 22, 67, 89, 47, 0, 0, 0, 0, 1, 20, 107, 236, 240, 106, 0, 0, 0, 0, 1, 14, 132, 486, 797, 657, 235, 0, 0, 0, 0, 0, 9, 138, 814, 2075, 2678, 1806, 551, 0, 0, 0, 0, 0, 5, 126, 1169, 4495, 8548, 8833, 5026, 1301

Offset: 0

N. J. A. Sloane

The diagonal n = k+1 is A000055(n). - Jonathan Vos Post, Aug 10 2008

			Triangle begins:
  1;
  0, 1;
  0, 0, 1;
  0, 0, 1, 2;
  0, 0, 0, 2, 3;
  0, 0, 0, 1, 5   6;
  0, 0, 0, 1, 5, 13,  11;
  0, 0, 0, 0, 4, 19,  33,  23;
  0, 0, 0, 0, 2, 22,  67,  89,  47;
  0, 0, 0, 0, 1, 20, 107, 236, 240, 106;
  ... (so with 5 edges there's 1 graph with 4 nodes, 5 with 5 nodes and 6 with 6 nodes). [Typo corrected by Anders Haglund, Jul 08 2008]

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 93, Table 4.2.2; p. 241, Table A2.

Andrew Howroyd, Table of n, a(n) for n = 0..1325
G. A. Baker et al., High-temperature expansions for the spin-1/2 Heisenberg model, Phys. Rev., 164 (1967), 800-817.
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO] (2017), Table 57.
Gordon Royle, Small graphs
Gus Wiseman, Non-isomorphic representatives of the 12 connected graphs counted in row 5.

Main diagonal is A000055.
Subsequent diagonals give the number of connected unlabeled graphs with n nodes and n+k edges for k=0..2: A001429, A001435, A001436.
Cf. A002905 (row sums), A001349 (column sums), A008406, A046751 (transpose), A054924 (transpose), A046742 (w/o left column), A343088 (labeled).
Cf. A000664, A007718, A050535, A054923, A191646, A191970, A317672, A322114, A322151.

InvEulerMT(u)={my(n=#u, p=log(1+x*Ser(u)), vars=variables(p)); Vec(serchop( sum(i=1, n, moebius(i)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i), 1))}
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, x)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p,i->1+x^i)); s/n!}
T(n)={Mat([Col(p+O(y^n), -n) | p<-InvEulerMT(vector(n, k, G(k, y + O(y^n))))])}
{my(A=T(10)); for(n=1, #A, print(A[n,1..n]))} \\ Andrew Howroyd, Oct 23 2019

a(83)-a(89) corrected by Andrew Howroyd, Oct 24 2019

A084546 Triangle read by rows: T(n,k) = C( C(n,2), k) for n >= 0, 0 <= k <= C(n,2).

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, 1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1, 1, 21, 210, 1330, 5985, 20349, 54264, 116280, 203490, 293930, 352716, 352716, 293930, 203490, 116280, 54264, 20349, 5985, 1330, 210, 21, 1

Offset: 0

N. J. A. Sloane, Jul 13 2003

T(n,k) gives number of labeled simple graphs with n nodes and k edges.

			Triangle begins:
  1;
  1;
  1, 1;
  1, 3,  3,  1;
  1, 6, 15, 20, 15, 6, 1;
  ...

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 517.

Alois P. Heinz, Rows n = 0..42, flattened
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 (2017) table 66.

Cf. A083029. A subset of the rows of Pascal's triangle A007318.
Cf. A006125 (row sums), A008406 (unlabeled graphs).
Main diagonal gives A116508.

C:= binomial:
T:= (n, k)-> C( C(n, 2), k):
seq(seq(T(n, k), k=0..C(n, 2)), n=0..10);  # Alois P. Heinz, Feb 17 2023

Table[Table[Binomial[Binomial[n,2],k],{k,0,Binomial[n,2]}],{n,1,7}]//Grid (* Geoffrey Critzer, Apr 28 2011 *)

T(0,0)=1 prepended by Alois P. Heinz, Feb 17 2023

A054924 Triangle read by rows: T(n,k) = number of nonisomorphic unlabeled connected graphs with n nodes and k edges (n >= 1, 0 <= k <= n(n-1)/2).

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, 1, 0, 0, 0, 0, 0, 6, 13, 19, 22, 20, 14, 9, 5, 2, 1, 1, 0, 0, 0, 0, 0, 0, 11, 33, 67, 107, 132, 138, 126, 95, 64, 40, 21, 10, 5, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 23, 89, 236, 486, 814, 1169, 1454, 1579, 1515, 1290, 970, 658, 400, 220, 114

Offset: 1

N. J. A. Sloane

			Triangle begins:
1;
0,1;
0,0,1,1;
0,0,0,2,2,1,1;
0,0,0,0,3,5,5,4,2,1,1;
0,0,0,0,0,6,13,19,22,20,14,9,5,2,1,1;
the last batch giving the numbers of connected graphs with 6 nodes and from 0 to 15 edges.

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

R. W. Robinson, Rows 1 to 20 of triangle, flattened (corrected by Sean A. Irvine, Apr 29 2022)
G. A. Baker et al., High-temperature expansions for the spin-1/2 Heisenberg model, Phys. Rev., 164 (1967), 800-817.
Sean A. Irvine, Java code (github)
Gordon Royle, Small graphs
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967

Cf. A008406, A054925.
Other versions of this triangle: A046751, A076263, A054923, A046742.
Row sums give A001349, column sums give A002905. A046751 is essentially the same triangle. A054923 and A046742 give same triangle but read by columns.
Main diagonal is A000055. Next diagonal is A001429. Largest entry in each row gives A001437.

A076263 gives a Mathematica program which produces the nonzero entries in each row.
Needs["Combinatorica`"]; Table[Print[row = Join[Array[0&, n-1], Table[ Count[ Combinatorica`ListGraphs[n, k], g_ /; Combinatorica`ConnectedQ[g]], {k, n-1, n*(n-1)/2}]]]; row, {n, 1, 8}] // Flatten (* Jean-François Alcover, Jan 15 2015 *)

A003049 Number of connected Eulerian graphs with n unlabeled nodes.

Original entry on oeis.org

1, 0, 1, 1, 4, 8, 37, 184, 1782, 31026, 1148626, 86539128, 12798435868, 3620169692289, 1940367005824561, 1965937435288738165, 3766548132138130650270, 13666503289976224080346733

Offset: 1

N. J. A. Sloane

These are connected graphs with every node of even degree (cf. A002854).

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 117.
Valery A. Liskovets, Enumeration of Euler graphs. (Russian), Vesci Akad. Navuk BSSR, Ser. Fiz.-Mat. Navuk 1970, No.6, 38-46 (1970). Math. Rev., Vol. 44, 1972, p. 1195, #6557.
R. W. Robinson, Enumeration of Euler graphs, pp. 147-153 of F. Harary, editor, Proof Techniques in Graph Theory. Academic Press, NY, 1969.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1979.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Chai Wah Wu, Table of n, a(n) for n = 1..88 (terms 1..60 from Max Alekseyev)
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Erich Friedman, Illustration of initial terms
V. A. Liskovec, Enumeration of Euler Graphs, (in Russian), Akademiia Navuk BSSR, Minsk., 6 (1970), 38-46. (annotated scanned copy)
C. L. Mallows and N. J. A. Sloane, Two-graphs, switching classes and Euler graphs are equal in number, SIAM J. Appl. Math., 28 (1975), 876-880.
C. L. Mallows and N. J. A. Sloane, Two-graphs, switching classes and Euler graphs are equal in number, SIAM J. Appl. Math., 28 (1975), 876-880. [Copy on N. J. A. Sloane's Home Page]
Brendan McKay, Combinatorial Data (Eulerian graphs).
R. W. Robinson, Enumeration of Euler graphs, pp. 147-153 of F. Harary, editor, Proof Techniques in Graph Theory. Academic Press, NY, 1969. (Annotated scanned copy)
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Eulerian Graph.

Cf. A002854, A008683.

A002854 = Import["https://oeis.org/A002854/b002854.txt", "Table"][[All, 2]];
(* EulerInvTransform is defined in A022562 *)
EulerInvTransform[A002854] (* Jean-François Alcover, Aug 27 2019, updated Mar 17 2020 *)

from functools import lru_cache
from itertools import combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A003049(n):
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<>1)-1)*r+(q*r*(r-1)>>1) for q, r in p.items())+any(q&1 for q in p),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n)))
    @lru_cache(maxsize=None)
    def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
    return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n # Chai Wah Wu, Jul 03 2024

Let B(x) = g.f. for A002854. Then g.f. A(x) for A003049 satisfies 1 + B(x) = exp(Sum_{n>=1} A(x^n)/n). - Robinson (1969).
Inverse Euler transform of A002854. (This is equivalent to the Robinson formula.) - Franklin T. Adams-Watters, Jul 24 2006
Let B(x) = g.f. for A002854. Then A(x) = Sum_{m >= 1} (mu(m)/m) * log(1 + B(x^m)), where mu(m) = A008683(m). (This is essentially a re-statement of the equation on p. 151 in Robinson (1969).) - Petros Hadjicostas, Feb 24 2021

a(1)-a(26) were computed by R. W. Robinson

More terms from Vladeta Jovovic, Apr 18 2000

A033301 Number of 4-valent (or quartic) graphs with n nodes.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 1, 2, 6, 16, 60, 266, 1547, 10786, 88193, 805579, 8037796, 86223660, 985883873, 11946592242, 152808993767, 2056701139136, 29051369533596, 429669276147047, 6640178380127244, 107026751932268789, 1796103830404560857, 31334029441145918974, 567437704731717802783

Offset: 0

Ronald C. Read

Because the triangle A051031 is symmetric, a(n) is also the number of (n-5)-regular graphs on n vertices. - Jason Kimberley, Sep 22 2009

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.

M. Meringer, Tables of Regular Graphs
M. Meringer, Erzeugung Regulärer Graphen, Diploma thesis, University of Bayreuth, January 1996. [From Herman Jamke (hermanjamke(AT)fastmail.fm), Sep 25 2010]
N. J. A. Sloane, Transforms
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Quartic Graph

4-regular simple graphs: A006820 (connected), A033483 (disconnected), this sequence (not necessarily connected).

Regular graphs A005176 (any degree), A051031 (triangular array), chosen degrees: A000012 (k=0), A059841 (k=1), A008483 (k=2), A005638 (k=3), A033301 (k=4), A165626 (k=5), A165627 (k=6), A165628 (k=7).

A006820 = Cases[Import["https://oeis.org/A006820/b006820.txt", "Table"], {, }][[All, 2]];
(* EulerTransform is defined in A005195 *)
EulerTransform[Rest @ A006820] (* Jean-François Alcover, Nov 26 2019, updated Mar 17 2020 *)

Euler transform of A006820. - Martin Fuller, Dec 04 2006

a(16) from Axel Kohnert (kohnert(AT)uni-bayreuth.de), Jul 24 2003
a(17)-a(19) from Jason Kimberley, Sep 12 2009
a(20)-a(21) from Herman Jamke (hermanjamke(AT)fastmail.fm), Sep 25 2010
a(22) from Jason Kimberley, Oct 15 2011
a(22) corrected and a(23)-a(28) from Andrew Howroyd, Mar 08 2020

A000171 Number of self-complementary graphs with n nodes.

Original entry on oeis.org

1, 0, 0, 1, 2, 0, 0, 10, 36, 0, 0, 720, 5600, 0, 0, 703760, 11220000, 0, 0, 9168331776, 293293716992, 0, 0, 1601371799340544, 102484848265030656, 0, 0, 3837878966366932639744, 491247277315343649710080, 0, 0

Offset: 1

N. J. A. Sloane

a(n) = A007869(n)-A054960(n), where A007869(n) is number of unlabeled graphs with n nodes and an even number of edges and A054960(n) is number of unlabeled graphs with n nodes and an odd number of edges.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 139, Table 6.1.1.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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 = 1..100
H. Fripertinger, Self-complementary graphs
Victoria Gatt, Mikhail Klin, Josef Lauri, Valery Liskovets, From Schur Rings to Constructive and Analytical Enumeration of Circulant Graphs with Prime-Cubed Number of Vertices, in Isomorphisms, Symmetry and Computations in Algebraic Graph Theory, (Pilsen, Czechia, WAGT 2016) Vol. 305, Springer, Cham, 37-65.
Richard A. Gibbs, Self-complementary graphs J. Combinatorial Theory Ser. B 16 (1974), 106--123. MR0347686 (50 #188). - _N. J. A. Sloane_, Mar 27 2012
Sebastian Jeon, Tanya Khovanova, 3-Symmetric Graphs, arXiv:2003.03870 [math.CO], 2020.
B. D. McKay, Self-complementary graphs
R. C. Read, On the number of self-complementary graphs and digraphs, J. London Math. Soc., 38 (1963), 99-104.
Eric Weisstein's World of Mathematics, Self-Complementary Graph
D. Wille, Enumeration of self-complementary structures, J. Comb. Theory B 25 (1978) 143-150

Cf. A047660, A051251, A047832.

Cf. A008406 (triangle of coefficients of the "graph polynomial").

< -1, {n, 1, 20}]  (* Geoffrey Critzer, Oct 21 2012 *)
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_] := 4 Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i - 1}], {i, 2, Length[v]}] + 2 Total[v];
a[n_] := Module[{s = 0}, Switch[Mod[n, 4], 2|3, 0, _, Do[s += permcount[4 p]*2^edges[p]*If[OddQ[n], n*2^Length[p], 1], {p, IntegerPartitions[ Quotient[n, 4]]}]; s/n!]];
Array[a, 40] (* Jean-François Alcover, Aug 26 2019, after Andrew Howroyd *)

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) = {4*sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + 2*sum(i=1, #v, v[i])}
a(n) = {my(s=0); if(n%4<2, forpart(p=n\4, s+=permcount(4*Vec(p)) * 2^edges(p) * if(n%2, n*2^#p, 1))); s/n!} \\ Andrew Howroyd, Sep 16 2018

a(4n) = A003086(2n).

a(4*n+1) = A047832(n), a(4*n+2) = a(4*n+3) = 0. - Andrew Howroyd, Sep 16 2018

More terms from Ronald C. Read and Vladeta Jovovic

A001434 Number of graphs with n nodes and n edges.

Original entry on oeis.org

1, 0, 0, 1, 2, 6, 21, 65, 221, 771, 2769, 10250, 39243, 154658, 628635, 2632420, 11353457, 50411413, 230341716, 1082481189, 5228952960, 25945377057, 132140242356, 690238318754, 3694876952577, 20252697246580, 113578669178222, 651178533855913, 3813856010041981

Offset: 0

N. J. A. Sloane

The labeled version is A116508. - Gus Wiseman, Feb 22 2024

			From _Gus Wiseman_, Feb 22 2024: (Start)
Representatives of the a(0) = 1 through a(5) = 6 graphs:
  {}  .  .  {12,13,23}  {12,13,14,23}  {12,13,14,15,23}
                        {12,13,24,34}  {12,13,14,23,24}
                                       {12,13,14,23,25}
                                       {12,13,14,23,45}
                                       {12,13,14,25,35}
                                       {12,13,24,35,45}
(End)

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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 = 0..50 (terms 1..40 from Sean A. Irvine)
CombOS - Combinatorial Object Server, Generate graphs
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967.

The connected case is A001429, labeled A057500.
The covering case is A006649, labeled A367863.
Diagonal n = k of A008406.
The labeled version is A116508.
The version with loops is A368598, connected A368983.
Allowing up to n edges gives A370315, labeled A369192.
A000088 counts unlabeled graphs, labeled A006125.
A001349 counts unlabeled connected graphs, labeled A001187.
A002494 counts unlabeled covering graphs, labeled A006129.
Cf. A000055, A005703, A014068, A054924, A137916, A137917, A236570, A369201.

(* first do *) Needs["Combinatorica`"] (* then *) Table[ NumberOfGraphs[n, n], {n, 24}] (* Robert G. Wilson v, Mar 22 2011 *)
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Subsets[Subsets[Range[n],{2}],{n}]]],{n,0,5}] (* Gus Wiseman, Feb 22 2024 *)

a(n) = polcoef(G(n, O(x*x^n)), n) \\ G defined in A008406. - Andrew Howroyd, Feb 02 2024

More terms from Vladeta Jovovic, Jan 07 2000

a(0)=1 prepended by Andrew Howroyd, Feb 02 2024

A263340 Triangle read by rows: T(n,k) is the number of graphs with n vertices containing k triangles.

Original entry on oeis.org

1, 1, 2, 3, 1, 7, 2, 1, 0, 1, 14, 7, 5, 2, 3, 1, 0, 1, 0, 0, 1, 38, 23, 28, 14, 18, 9, 7, 5, 4, 1, 4, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 107, 102, 141, 117, 123, 92, 80, 63, 49, 35, 35, 23, 15, 17, 10, 4, 9, 5, 2, 3, 3, 2, 2, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1

Offset: 0

Christian Stump, Oct 15 2015

Row sums give A000088.
First column is A006785.
Row lengths are 1 + binomial(n,3). - Geoffrey Critzer, Apr 13 2017

			Triangle begins:
  1;
  1;
  2;
  3,1;
  7,2,1,0,1;
  14,7,5,2,3,1,0,1,0,0,1;
  38,23,28,14,18,9,7,5,4,1,4,1,1,1,0,0,1,0,0,0,1;
  ...

Pontus von Brömssen, Rows n = 0..10, flattened
FindStat - Combinatorial Statistic Finder, The number of triangles of a graph.
Gus Wiseman, The graphs counted under row n = 5.

Row sums are A000088, labeled A006125.
Column k = 0 is A006785 (lab A213434), covering A372169 (lab A372168).
Counting edges gives A008406 (lab A084546), covering A370167 (lab A054548).
Row lengths are A050407.
The labeled version is A372170, covering A372167.
The covering case is A372173, sums A002494, labeled A006129.
Column k = 1 is A372194 (lab A372172), covering A372174 (lab A372171).
A001858 counts acyclic graphs, unlabeled A005195.
A372176 counts labeled graphs by directed cycles, covering A372175.
Cf. A000055, A053530, A137917, A137918, A140637, A144958, A322700, A370169.

Table[Table[Count[Table[Tr[MatrixPower[AdjacencyMatrix[GraphData[{n, i}]], 3]]/6, {i, 1, NumberOfGraphs[n]}], k], {k, 0, Binomial[n, 3]}], {n, 1, 7}] (* Geoffrey Critzer, Apr 13 2017 *)

Row 7 from Geoffrey Critzer, Apr 13 2017

T(0,0)=1 prepended by Alois P. Heinz, Apr 13 2017

A372176 Irregular triangle read by rows where T(n,k) is the number of labeled simple graphs on n vertices with exactly 2k directed cycles of length > 2.

Original entry on oeis.org

1, 1, 2, 7, 1, 38, 19, 0, 6, 0, 0, 0, 1, 291, 317, 15, 220, 0, 0, 70, 55, 0, 0, 0, 0, 30, 15, 0, 0, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Gus Wiseman, Apr 25 2024

A directed cycle in a simple (undirected) graph is a sequence of distinct vertices, up to rotation, such that there are edges between all consecutive elements, including the last and the first.

			Triangle begins (zeros shown as dots):
   1
   1
   2
   7 1
   38 19 . 6 ... 1
   291 317 15 220 .. 70 55 .... 30 15 ........ 10 ............... 1
The T(4,3) = 6 graphs:
  12,13,14,23,24
  12,13,14,23,34
  12,13,14,24,34
  12,13,23,24,34
  12,14,23,24,34
  13,14,23,24,34

Column k = 0 is A001858 (unlabeled A005195), covering A105784.
Row lengths are A002807 + 1.
Row sums are A006125, unlabeled A000088.
Counting edges instead of cycles gives A084546 (covering A054548), unlabeled A008406 (covering A370167).
Counting triangles instead of cycles gives A372170 (covering A372167), unlabeled A263340 (covering A372173).
The covering case is A372175.
Column k = 1 is A372193 (covering A372195), unlabeled A236570.
A006129 counts graphs, unlabeled A002494.
A322661 counts covering loop-graphs, unlabeled A322700.
Cf. A000272, A053530, A137916, A144958, A213434, A367863, A372168, A372169, A372171, A372172, A372191.

cyc[y_]:=Select[Join@@Table[Select[Join@@Permutations/@Subsets[Union@@y,{k}], And@@Table[MemberQ[Sort/@y,Sort[{#[[i]],#[[If[i==k,1,i+1]]]}]],{i,k}]&], {k,3,Length[y]}],Min@@#==First[#]&];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Length[cyc[#]]==2k&]], {n,0,4}, {k,0,Length[cyc[Subsets[Range[n],{2}]]]/2}]

cp's OEIS Frontend

A000014 Number of series-reduced trees with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A054923 Triangle read by rows: number of connected graphs with k >= 0 edges and n nodes (1<=n<=k+1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A084546 Triangle read by rows: T(n,k) = C( C(n,2), k) for n >= 0, 0 <= k <= C(n,2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A054924 Triangle read by rows: T(n,k) = number of nonisomorphic unlabeled connected graphs with n nodes and k edges (n >= 1, 0 <= k <= n(n-1)/2).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

A003049 Number of connected Eulerian graphs with n unlabeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A033301 Number of 4-valent (or quartic) graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A000171 Number of self-complementary graphs with n nodes.

Views

Author

Keywords

Comments