A340023
Number of graphs with n integer labeled vertices covering an initial interval of positive integers.
Original entry on oeis.org
1, 1, 4, 24, 263, 5566, 239428, 21074412, 3779440490, 1372163701412, 1003687569555456, 1474604145003923000, 4343524388729516494384, 25623424478746329214500144, 302549202766446393276528844768, 7147753721248229224770005386691680
Offset: 0
a(2) = 4 because there are 2 graphs on 2 vertices and each of these can either have both vertices labeled 1 or one vertex labeled 1 and the other 2.
-
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]];
G[n_, k_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p]*k^Length[p], {p, IntegerPartitions[n]}]; s/n!];
a[n_] := Module[{p = G[n, x]}, Sum[(p /. x -> k)*Sum[Binomial[r, k]*(-1)^(r - k), {r, k, n}], {k, 0, n}]];
a /@ Range[0, 15] (* Jean-François Alcover, Jan 06 2021, 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) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
G(n,k)={my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)*k^#p); s/n!}
a(n)={my(p=G(n,x)); sum(k=0, n, subst(p,x,k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)))}
A340025
Number of connected graphs with vertices labeled with positive integers summing to n.
Original entry on oeis.org
1, 1, 2, 4, 12, 41, 210, 1478, 17128, 352926, 14181309, 1129005180, 175491164826, 52346463432414, 29666505555854777, 31806668884174645842, 64442744342933382243031, 246898165053174167804654086, 1791518193851453375966274280997, 24668222649527263942329934357240780
Offset: 0
-
\\ See A340022 for permcount, edges.
InvEulerT(v)={my(p=log(1+x*Ser(v))); dirdiv(vector(#v,n,polcoef(p,n)), vector(#v,n,1/n))}
seq(n) = {concat([1], InvEulerT(Vec(sum(k=1, n, my(s=0); forpart(p=k, s+=permcount(p) * 2^edges(p) * x^k/prod(j=1, #p, 1 - x^p[j] + O(x^(n-k+1)))); s/k!))))}
A340027
Number of inequivalent vertex colorings of connected graphs on n unlabeled vertices.
Original entry on oeis.org
1, 1, 2, 7, 50, 520, 10665, 400220, 29204589, 4143245857, 1146827743079, 619412332805088, 653237982066620540, 1346571060160843394520, 5432476352054378478159877, 42947950068987980977264834190, 666212968663987333085874313873428, 20301440661023158546856805172595805762
Offset: 0
a(3) = 7 because there are 2 connected graphs on 3 vertices. The complete graph K_3 can be coloring in 3 ways (111, 112, 123) and the path graph P_3 can be colored in 4 ways (111, 112, 121, 123).
-
\\ See links in A339645 for combinatorial species functions.
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
graphsCycleIndex(n)={my(s=0); forpart(p=n, s+=permcount(p) * 2^edges(p) * sMonomial(p)); s/n!}
graphsSeries(n)={sum(k=0, n, graphsCycleIndex(k)*x^k) + O(x*x^n)}
InequivalentColoringsSeq(1+sLog(graphsSeries(15)))
Showing 1-3 of 3 results.
Comments