| Displaying 1-8 of 8 results found.
page
1
Triangle read by rows where T(n,k) is the number of unlabeled simple graphs with n vertices and exactly k endpoints (vertices of degree 1).
+10
9
1, 1, 0, 1, 0, 1, 2, 0, 2, 0, 5, 1, 3, 1, 1, 16, 6, 7, 2, 3, 0, 78, 35, 25, 8, 7, 2, 1, 588, 260, 126, 40, 20, 6, 4, 0, 8047, 2934, 968, 263, 92, 25, 13, 3, 1, 205914, 53768, 11752, 2434, 596, 140, 47, 12, 5, 0, 10014882, 1707627, 240615, 34756, 5864, 1084, 256, 58, 21, 4, 1
FORMULA
Column-wise partial sums of A327372.
EXAMPLE
Triangle begins:
1;
1, 0;
1, 0, 1;
2, 0, 2, 0;
5, 1, 3, 1, 1;
16, 6, 7, 2, 3, 0;
78, 35, 25, 8, 7, 2, 1;
588, 260, 126, 40, 20, 6, 4, 0;
8047, 2934, 968, 263, 92, 25, 13, 3, 1;
...
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) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
G(n)={sum(k=0, n, my(s=0); forpart(p=k, s+=permcount(p) * 2^edges(p) * prod(i=1, #p, (1 - x^p[i])/(1 - (x*y)^p[i]) + O(x*x^(n-k)))); x^k*s/k!)*(1-x^2*y)/(1-x^2*y^2)}
T(n)={my(v=Vec(G(n))); vector(#v, n, Vecrev(v[n], n))}
CROSSREFS
Row sums without the first column are A141580.
Triangle read by rows: T(n,k) is the number of graphs with n vertices and maximum vertex degree k, (0 <= k < n).
+10
8
1, 1, 1, 1, 1, 2, 1, 2, 4, 4, 1, 2, 8, 12, 11, 1, 3, 15, 43, 60, 34, 1, 3, 25, 121, 360, 378, 156, 1, 4, 41, 378, 2166, 4869, 3843, 1044, 1, 4, 65, 1095, 14306, 68774, 113622, 64455, 12346, 1, 5, 100, 3441, 104829, 1141597, 3953162, 4605833, 1921532, 274668
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
FORMULA
G.f. for column k=0: A(x)=1/(1-x).
G.f. for column k=1: B(x)=x^2/((1-x^2)(1-x)).
G.f. for column k=2: 1/((1-x)(1-x^2))*Product_{i>=3} 1/(1-x^i)^2 - B(x) - A(x).
(End)
T(n, 0) = 1.
EXAMPLE
Triangle begins:
1,
1, 1,
1, 1, 2,
1, 2, 4, 4,
1, 2, 8, 12, 11,
1, 3, 15, 43, 60, 34,
1, 3, 25, 121, 360, 378, 156,
1, 4, 41, 378, 2166, 4869, 3843, 1044,
...
CROSSREFS
Row sums are A000088 (simple graphs on n nodes). Cf. A294217 (triangle of n-node minimum vertex degree counts).
Number of labeled simple graphs with n vertices and exactly n - 1 endpoints (vertices of degree 1).
+10
7
0, 1, 0, 6, 4, 50, 66, 532, 1016, 6876, 16750, 104456, 303612, 1821976, 6067166, 35857200, 133160176, 785514512, 3192117966, 18948962656, 83099447300, 498931946016, 2336474411062, 14234346694976, 70598633745576, 437304764440000, 2282139344678726, 14390600621415552
COMMENTS
Graphs consist of zero or more paths on two nodes each and either a single isolated node or a star with two or more peripheral nodes. - Andrew Howroyd, Sep 05 2019
FORMULA
(n-1)*(n-2)*a(n) - n*(n-3)*(n-2)*a(n-1) - n*(n-1)^2*a(n-2) + (2*n-7)*n*(n-1)*(n-2)*a(n-3) - n*(n-1)*(n-2)*(n-3)*(n-4)*a(n-5) = 0. - Robert Israel, Sep 06 2019
EXAMPLE
The a(4) = 4 edge-sets:
{12,13,14}
{12,23,24}
{13,23,34}
{14,24,34}
MAPLE
f:= gfun:-rectoproc({(n-1)*(n-2)*a(n)-n*(n-3)*(n-2)*a(n-1)-n*(n-1)^2*a(n-2)+(2*n-7)*n*(n-1)*(n-2)*a(n-3)-n*(n-1)*(n-2)*(n-3)*(n-4)*a(n-5)=0, a(0)=0, a(1)=1, a(2)=0, a(3)=6, a(4)=4}, a(n), remember):
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Count[Length/@Split[Sort[Join@@#]], 1]==n-1&]], {n, 0, 5}]
With[{nn=30}, CoefficientList[Series[x Exp[x^2/2](Exp[x]-x), {x, 0, nn}], x] Range[ 0, nn]!] (* Harvey P. Dale, Apr 28 2022 *)
PROG
(PARI) seq(n)={Vec(serlaplace(x*exp(x^2/2 + O(x^n))*(exp(x + O(x^n))-x)), -(n+1))} \\ Andrew Howroyd, Sep 05 2019
Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and minimum vertex-degree k.
+10
6
1, 1, 0, 1, 1, 0, 4, 3, 1, 0, 23, 31, 9, 1, 0, 256, 515, 227, 25, 1, 0, 5319, 15381, 10210, 1782, 75, 1, 0, 209868, 834491, 815867, 221130, 15564, 231, 1, 0, 15912975, 83016613, 116035801, 47818683, 5499165, 151455, 763, 1, 0, 2343052576, 15330074139, 29550173053, 18044889597, 3291232419, 158416629, 1635703, 2619, 1, 0
COMMENTS
The minimum vertex-degree of the empty graph is infinity. It has been included here under k = 0. - Andrew Howroyd, Mar 09 2020
EXAMPLE
Triangle begins:
1
1 0
1 1 0
4 3 1 0
23 31 9 1 0
256 515 227 25 1 0
5319 15381 10210 1782 75 1 0
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], k==If[#=={}||Union@@#!=Range[n], 0, Min@@Length/@Split[Sort[Join@@#]]]&]], {n, 0, 5}, {k, 0, n}]
PROG
(PARI)
GraphsByMaxDegree(n)={
local(M=Map(Mat([x^0, 1])));
my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
my(merge(r, p, v)=acc(p + sum(i=1, poldegree(p)-r-1, polcoef(p, i)*(1-x^i)), v));
my(recurse(r, p, i, q, v, e)=if(i<0, merge(r, x^e+q, v), my(t=polcoef(p, i)); for(k=0, t, self()(r, p, i-1, (t-k+x*k)*x^i+q, binomial(t, k)*v, e+k))));
for(k=2, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], my(p=src[i, 1]); recurse(n-k, p, poldegree(p), 0, src[i, 2], 0)));
Mat(M);
}
Row(n)={if(n==0, [1], my(M=GraphsByMaxDegree(n), u=vector(n+1)); for(i=1, matsize(M)[1], u[n-poldegree(M[i, 1])]+=M[i, 2]); u)}
CROSSREFS
Row sums without the first column are A006129. Row sums without the first two columns are A100743.
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
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.
+10
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.
+10
2
0, 0, 1, 2, 8, 43, 360, 4869, 113622, 4605833, 325817259, 40350371693, 8825083057727, 3447229161054412, 2432897732375453872, 3135299553791882831175, 7445569254636418368355175, 32831169277561326131677454356, 270499962116368309216399255404116
Number of simple graphs on n unlabeled nodes with maximum degree exactly 2.
+10
2
0, 0, 2, 4, 8, 15, 25, 41, 65, 100, 150, 225, 327, 474, 678, 962, 1348, 1884, 2602, 3581, 4889, 6644, 8968, 12064, 16124, 21476, 28462, 37585, 49407, 64747, 84495, 109936, 142522, 184226, 237350, 304977, 390669, 499169, 636039, 808468, 1024996, 1296573, 1636151
PROG
(PARI) seq(n) = Vec( (1-x)*(1-x^2)/prod(k=1, n, 1 - x^k + O(x*x^n))^2 - 1/((1-x)*(1-x^2)), -n) \\ Andrew Howroyd, Sep 03 2019
Search completed in 0.008 seconds
| 
