Search: a261919 -id:a261919
|
| |
|
|
A004110
|
|
Number of n-node unlabeled graphs without endpoints (i.e., no nodes of degree 1).
(Formerly M1504)
|
|
+10
33
|
|
|
|
1, 1, 1, 2, 5, 16, 78, 588, 8047, 205914, 10014882, 912908876, 154636289460, 48597794716736, 28412296651708628, 31024938435794151088, 63533059372622888758054, 244916078509480823407040988, 1783406527599529094009748567708
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
a(n) is also the number of unlabeled mating graphs with n nodes. A mating graph has no two vertices with identical sets of neighbors. - Tanya Khovanova, Oct 23 2008
|
|
|
REFERENCES
|
F. Harary, Graph Theory, Wiley, 1969. See illustrations in Appendix 1.
F. Harary and E. Palmer, Graphical Enumeration, (1973), compare formula (8.7.11).
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
|
|
|
MATHEMATICA
|
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_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
a[n_] := Sum[permcount[p] * 2^edges[p] * Coefficient[Product[1 - x^p[[i]], {i, 1, Length[p]}], x, n - k]/k!, {k, 1, n}, {p, IntegerPartitions[k]}]; a[0] = 1;
|
|
|
PROG
|
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) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
a(n) = {my(s=0); sum(k=1, n, forpart(p=k, s+=permcount(p) * 2^edges(p) * polcoef(prod(i=1, #p, 1-x^p[i]), n-k)/k!)); s} \\ Andrew Howroyd, Sep 09 2018
|
|
|
CROSSREFS
|
Cf. A059166 (n-node connected labeled graphs without endpoints), A059167 (n-node labeled graphs without endpoints), A004108 (n-node connected unlabeled graphs without endpoints), A006024 (number of labeled mating graphs with n nodes), A129584 (bi-point-determining graphs).
If isolated nodes are forbidden, see A261919.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A007146
|
|
Number of unlabeled simple connected bridgeless graphs with n nodes.
(Formerly M2909)
|
|
+10
29
|
|
|
|
1, 0, 1, 3, 11, 60, 502, 7403, 197442, 9804368, 902818087, 153721215608, 48443044675155, 28363687700395422, 30996524108446916915, 63502033750022111383196, 244852545022627009655180986, 1783161611023802810566806448531, 24603891215865809635944516464394339
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
Also unlabeled simple graphs with spanning edge-connectivity >= 2. The spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (without removing incident vertices) to obtain a set-system that is disconnected or covers fewer vertices. - Gus Wiseman, Sep 02 2019
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
PROG
|
(PARI) \\ Translation of theorem 3.2 in Hanlon and Robinson reference. See A004115 for graphsSeries and A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(gc=sLog(graphsSeries(n)), gcr=sPoint(gc)); sSolve( gc + gcr^2/2 - sRaise(gcr, 2)/2, x*sv(1)*sExp(gcr) )}
NumUnlabeledObjsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 31 2020
|
|
|
CROSSREFS
|
Cf. A005470 (number of simple graphs).
Cf. A007145 (number of simple connected rooted bridgeless graphs).
Cf. A052446 (number of simple connected bridged graphs).
Cf. A263914 (number of simple bridgeless graphs).
Cf. A263915 (number of simple bridged graphs).
Row sums of A263296 if the first two columns are removed.
BII-numbers of set-systems with spanning edge-connectivity >= 2 are A327109.
Graphs with non-spanning edge-connectivity >= 2 are A327200.
2-vertex-connected graphs are A013922.
Cf. A000719, A001349, A002494, A261919, A327069, A327071, A327074, A327075, A327077, A327109, A327144, A327146.
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Reference gives first 22 terms.
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A004108
|
|
Number of n-node unlabeled connected graphs without endpoints.
(Formerly M2910)
|
|
+10
24
|
|
|
|
1, 1, 0, 1, 3, 11, 61, 507, 7442, 197772, 9808209, 902884343, 153723152913, 48443147912137, 28363697921914475, 30996525982586676021, 63502034385272108655525, 244852545421597419740767106, 1783161611489937453151313949442, 24603891216883233547700609793901996
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
Also number of n-node unlabeled connected mating graphs, cf. A006024 and A092430 (conjectured by Vladeta Jovovic, proved by G. Kilibarda). - Vladeta Jovovic, Oct 07 2004
|
|
|
REFERENCES
|
F. Harary and E. Palmer, Graphical Enumeration, (1973), formula (8.7.11).
Goran Kilibarda, "Enumeration of unlabeled mating graphs", Belgrade, 2004, to be published.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
MATHEMATICA
|
terms = 19;
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
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_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
b[n_] := Sum[permcount[p]*2^edges[p]*Coefficient[Product[1 - x^p[[i]], {i, 1, Length[p]}], x, n - k]/k!, {k, 1, n}, {p, IntegerPartitions[k]}];
A004110 = Table[b[n], {n, 1, terms-1}];
|
|
|
CROSSREFS
|
Cf. A059166 (n-node connected labeled graphs without endpoints), A059167 (n-node labeled graphs without endpoints), A004110 (Euler Transform, n-node unlabeled graphs without endpoints).
Cf. A092430 (n-node labeled connected mating graphs).
Counts include those for distance-critical graphs, A349402.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A059166
|
|
Number of n-node connected labeled graphs without endpoints.
|
|
+10
21
|
|
|
|
1, 1, 0, 1, 10, 253, 12058, 1052443, 169488200, 51045018089, 29184193354806, 32122530765469967, 68867427921051098084, 290155706369032525823085, 2417761578629525173499004146, 40013923790443379076988789688611, 1318910080173114018084245406769861936
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
REFERENCES
|
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 404.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = Sum_{i=0..n} (-1)^i*binomial(n, i)*c(n-i)*(n-i)^i, for n>2, a(0)=1, a(1)=1, a(2)=0, where c(n) is number of n-node connected labeled graphs (cf. A001187).
E.g.f.: 1 + x^2/2 + log(Sum_{n >= 0} 2^binomial(n, 2)*(x*exp(-x))^n/n!).
|
|
|
MAPLE
|
c:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
add(k*binomial(n, k)*2^((n-k)*(n-k-1)/2)*c(k), k=1..n-1)/n)
end:
a:= n-> max(0, add((-1)^i*binomial(n, i)*c(n-i)*(n-i)^i, i=0..n)):
|
|
|
MATHEMATICA
|
Flatten[{1, 1, 0, Table[n!*Sum[(-1)^(n-j)*SeriesCoefficient[1+Log[Sum[2^(k*(k-1)/2)*x^k/k!, {k, 0, j}]], {x, 0, j}]*j^(n-j)/(n-j)!, {j, 0, n}], {n, 3, 15}]}] (* Vaclav Kotesovec, May 14 2015 *)
c[0] = 1; c[n_] := c[n] = 2^(n*(n-1)/2) - Sum[k*Binomial[n, k]*2^((n-k)*(n - k - 1)/2)*c[k], {k, 1, n-1}]/n; a[0] = a[1] = 1; a[2] = 0; a[n_] := Sum[(-1)^i*Binomial[n, i]*c[n-i]*(n-i)^i, {i, 0, n}]; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Oct 27 2017, using Alois P. Heinz's code for c(n) *)
|
|
|
PROG
|
(PARI) seq(n)={Vec(serlaplace(1 + x^2/2 + log(sum(k=0, n, 2^binomial(k, 2)*(x*exp(-x + O(x^n)))^k/k!))))} \\ Andrew Howroyd, Sep 09 2018
|
|
|
CROSSREFS
|
Cf. A059167 (n-node labeled graphs without endpoints), A004108 (n-node connected unlabeled graphs without endpoints), A004110 (n-node unlabeled graphs without endpoints).
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
More terms from John Renze (jrenze(AT)yahoo.com), Feb 01 2001
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A100743
|
|
Number of labeled n-vertex graphs without vertices of degree <=1.
|
|
+10
14
|
|
|
|
1, 0, 0, 1, 10, 253, 12068, 1052793, 169505868, 51046350021, 29184353055900, 32122563615242615, 68867440268165982320, 290155715157676330952559, 2417761590648159731258579164, 40013923822242935823157820555477, 1318910080336893719646370269435043184
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
LINKS
|
|
|
|
FORMULA
|
E.g.f.: exp(-x+x^2/2)*(Sum_{n>=0} 2^(n*(n-1)/2)*(x/exp(x))^n/n!). - Vladeta Jovovic, Jan 26 2006
|
|
|
EXAMPLE
|
The a(4) = 10 edge-sets:
{12,13,24,34}
{12,14,23,34}
{13,14,23,24}
{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}
{12,13,14,23,24,34}
(End)
|
|
|
MATHEMATICA
|
m = 13;
egf = Exp[-x + x^2/2]*Sum[2^(n (n-1)/2)*(x/Exp[x])^n/n!, {n, 0, m+1}];
s = egf + O[x]^(m+1);
a[n_] := n!*SeriesCoefficient[s, n];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Min@@Length/@Split[Sort[Join@@#]]>1&]], {n, 0, 4}] (* Gus Wiseman, Aug 18 2019 *)
|
|
|
PROG
|
(PARI) seq(n)={Vec(serlaplace(exp(-x + x^2/2 + O(x*x^n))*sum(k=0, n, 2^(k*(k-1)/2)*(x/exp(x + O(x^n)))^k/k!)))} \\ Andrew Howroyd, Sep 04 2019
|
|
|
CROSSREFS
|
Graphs without isolated nodes are A006129.
Graphs without endpoints are A059167.
Labeled graphs with endpoints are A245797.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A327230
|
|
Number of non-isomorphic set-systems covering n vertices with at least one endpoint/leaf.
|
|
+10
11
|
| |
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. A leaf is an edge containing a vertex that does not belong to any other edge, while an endpoint is a vertex belonging to only one edge.
Also covering set-systems with minimum vertex-degree 1.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
Non-isomorphic representatives of the a(1) = 1 through a(3) = 14 set-systems:
{{1}} {{1,2}} {{1,2,3}}
{{1},{2}} {{1},{2,3}}
{{2},{1,2}} {{1},{2},{3}}
{{1,3},{2,3}}
{{3},{1,2,3}}
{{1},{3},{2,3}}
{{2,3},{1,2,3}}
{{2},{1,3},{2,3}}
{{2},{3},{1,2,3}}
{{3},{1,3},{2,3}}
{{1},{2},{3},{2,3}}
{{3},{2,3},{1,2,3}}
{{2},{3},{1,3},{2,3}}
{{2},{3},{2,3},{1,2,3}}
|
|
|
CROSSREFS
|
Unlabeled covering set-systems are A055621.
The non-covering version is A327335 (partial sums).
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A294217
|
|
Triangle read by rows: T(n,k) is the number of graphs with n vertices and minimum vertex degree k, (0 <= k < n).
|
|
+10
9
|
|
|
|
1, 1, 1, 2, 1, 1, 4, 4, 2, 1, 11, 12, 8, 2, 1, 34, 60, 43, 15, 3, 1, 156, 378, 360, 121, 25, 3, 1, 1044, 3843, 4869, 2166, 378, 41, 4, 1, 12346, 64455, 113622, 68774, 14306, 1095, 65, 4, 1, 274668, 1921532, 4605833, 3953162, 1141597, 104829, 3441, 100, 5, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
Terms may be computed without generating each graph by enumerating the number of graphs by degree sequence. A PARI program showing this technique for graphs with labeled vertices is given in A327366. Burnside's lemma can be used to extend this method to the unlabeled case. - Andrew Howroyd, Mar 10 2020
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n, n-1) = 1.
|
|
|
EXAMPLE
|
Triangle begins:
1;
1, 1;
2, 1, 1;
4, 4, 2, 1;
11, 12, 8, 2, 1;
34, 60, 43, 15, 3, 1;
156, 378, 360, 121, 25, 3, 1;
...
|
|
|
CROSSREFS
|
Row sums are A000088 (simple graphs on n nodes).
Cf. A263293 (triangle of n-node maximum vertex degree counts).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A327335
|
|
Number of non-isomorphic set-systems with n vertices and at least one endpoint/leaf.
|
|
+10
5
|
| |
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. A leaf is an edge containing a vertex that does not belong to any other edge, while an endpoint is a vertex belonging to only one edge.
Also covering set-systems with minimum covered vertex-degree 1.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
Non-isomorphic representatives of the a(1) = 1 through a(3) = 18 set-systems:
{{1}} {{1}} {{1}}
{{1,2}} {{1,2}}
{{1},{2}} {{1},{2}}
{{1},{1,2}} {{1,2,3}}
{{1},{1,2}}
{{1},{2,3}}
{{1},{1,2,3}}
{{1,2},{1,3}}
{{1},{2},{3}}
{{1,2},{1,2,3}}
{{1},{2},{1,3}}
{{1},{1,2},{1,3}}
{{1},{1,2},{2,3}}
{{1},{2},{1,2,3}}
{{1},{1,2},{1,2,3}}
{{1},{2},{3},{1,2}}
{{1},{2},{1,2},{1,3}}
{{1},{2},{1,2},{1,2,3}}
|
|
|
CROSSREFS
|
The covering version is A327230 (first differences).
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A327372
|
|
Triangle read by rows where T(n,k) is the number of unlabeled simple graphs covering n vertices with exactly k endpoints (vertices of degree 1).
|
|
+10
5
|
|
|
|
1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 3, 1, 1, 1, 1, 11, 5, 4, 1, 2, 0, 62, 29, 18, 6, 4, 2, 1, 510, 225, 101, 32, 13, 4, 3, 0, 7459, 2674, 842, 223, 72, 19, 9, 3, 1, 197867, 50834, 10784, 2171, 504, 115, 34, 9, 4, 0, 9808968, 1653859, 228863, 32322, 5268, 944, 209, 46, 16, 4, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,11
|
|
|
LINKS
|
|
|
|
FORMULA
|
Column-wise first differences of A327371.
|
|
|
EXAMPLE
|
Triangle begins:
1
0 0
0 0 1
1 0 1 0
3 1 1 1 1
11 5 4 1 2 0
|
|
|
PROG
|
(PARI) \\ Needs G(n) defined in A327371.
T(n)={my(v=Vec(G(n)*(1 - x))); vector(#v, n, Vecrev(v[n], n))}
|
|
|
CROSSREFS
|
The non-covering version is A327371.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A369932
|
|
Triangle read by rows: T(n,k) is the number of unlabeled simple graphs with n edges and k vertices and without endpoints or isolated vertices.
|
|
+10
5
|
|
|
|
0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 3, 2, 0, 0, 0, 0, 3, 5, 2, 0, 0, 0, 0, 2, 11, 9, 3, 0, 0, 0, 0, 1, 15, 32, 16, 4, 0, 0, 0, 0, 1, 12, 63, 76, 25, 5, 0, 0, 0, 0, 0, 8, 89, 234, 162, 39, 6, 0, 0, 0, 0, 0, 5, 97, 515, 730, 332, 60, 9
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,20
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
Triangle begins:
0;
0, 0;
0, 0, 1;
0, 0, 0, 1;
0, 0, 0, 1, 1;
0, 0, 0, 1, 3, 2;
0, 0, 0, 0, 3, 5, 2;
0, 0, 0, 0, 2, 11, 9, 3;
0, 0, 0, 0, 1, 15, 32, 16, 4;
0, 0, 0, 0, 1, 12, 63, 76, 25, 5;
...
|
|
|
PROG
|
(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) = {my(s=O(x*x^n)); sum(k=0, n, forpart(p=k, s+=permcount(p) * edges(p, w->1+y^w+O(y*y^n)) * x^k * prod(i=1, #p, 1-(y*x)^p[i], 1+O(x^(n-k+1))) / k!)); s*(1-x)}
T(n)={my(r=Vec(substvec(G(n), [x, y], [y, x]))); vector(#r-1, i, Vecrev(Pol(r[i+1]/y), i)) }
{ my(A=T(12)); for(i=1, #A, print(A[i])) }
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.012 seconds
|
