Displaying 1-10 of 12 results found.
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.
+0
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
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])) }
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).
+0
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
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.
Number of simple graphs on n unlabeled nodes with minimum degree exactly 1.
+0
4
0, 1, 1, 4, 12, 60, 378, 3843, 64455, 1921532, 104098702, 10348794144, 1893781768084, 639954768875644, 400905675004630820, 467554784370658979194, 1019317687720204607541914, 4170177760438554428852944352, 32130458453030025927403299167172
CROSSREFS
The generalization to set-systems is A327335, with covering case A327230. Unlabeled covering graphs are A002494. Cf. A000088, A004110, A100743, A141580, A245797, A261919, A327105, A327362, A327364, A327366, A327372.
Number of simple graphs on n unlabeled nodes with minimum degree exactly 2.
+0
2
0, 0, 1, 2, 8, 43, 360, 4869, 113622, 4605833, 325817259, 40350371693, 8825083057727, 3447229161054412, 2432897732375453872, 3135299553791882831175, 7445569254636418368355175, 32831169277561326131677454356, 270499962116368309216399255404116
Number of non-isomorphic set-systems with n vertices and at least one endpoint/leaf.
+0
5
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.
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).
Number of non-isomorphic set-systems covering n vertices with at least one endpoint/leaf.
+0
11
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.
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).
Triangle read by rows: T(n,k) is the number of graphs with n vertices and minimum vertex degree k, (0 <= k < n).
+0
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
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
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).
Number of labeled n-vertex graphs without vertices of degree <=1.
+0
14
1, 0, 0, 1, 10, 253, 12068, 1052793, 169505868, 51046350021, 29184353055900, 32122563615242615, 68867440268165982320, 290155715157676330952559, 2417761590648159731258579164, 40013923822242935823157820555477, 1318910080336893719646370269435043184
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.
Number of n-node connected labeled graphs without endpoints.
+0
21
1, 1, 0, 1, 10, 253, 12058, 1052443, 169488200, 51045018089, 29184193354806, 32122530765469967, 68867427921051098084, 290155706369032525823085, 2417761578629525173499004146, 40013923790443379076988789688611, 1318910080173114018084245406769861936
REFERENCES
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 404.
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).
EXTENSIONS
More terms from John Renze (jrenze(AT)yahoo.com), Feb 01 2001
Number of unlabeled simple connected bridgeless graphs with n nodes.
(Formerly M2909)
+0
29
1, 0, 1, 3, 11, 60, 502, 7403, 197442, 9804368, 902818087, 153721215608, 48443044675155, 28363687700395422, 30996524108446916915, 63502033750022111383196, 244852545022627009655180986, 1783161611023802810566806448531, 24603891215865809635944516464394339
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).
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.
EXTENSIONS
Reference gives first 22 terms.
Search completed in 0.010 seconds
| 
