|
|
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).
|
|
80
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,10
|
|
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]
|
|
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
|
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Overview of the 12 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
|
|
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
|
|
EXAMPLE
|
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,
...
|
|
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]&;
|
|
PROG
|
(Sage)
def T(n, k):
return len(list(graphs(n, size=k)))
(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
|
|
CROSSREFS
|
Row lengths: A000124; number of connected graphs for given number of vertices: A001349; number of graphs for given number of edges: A000664.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
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
|
|
STATUS
|
approved
|
|
|
|