A340027 Number of inequivalent vertex colorings of connected graphs on n unlabeled vertices.

1, 1, 2, 7, 50, 520, 10665, 400220, 29204589, 4143245857, 1146827743079, 619412332805088, 653237982066620540, 1346571060160843394520, 5432476352054378478159877, 42947950068987980977264834190, 666212968663987333085874313873428, 20301440661023158546856805172595805762

Offset

0,3

Comments

Equivalence is up to permutation of the colors. Adjacent vertices may have the same color.

Links

Table of n, a(n) for n=0..17.

Example

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).

Prog

(PARI) \\ 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)))

Crossrefs

Cf. A340024, A340025, A340026.

Sequence in context: A139008 A058721 A363862 * A362340 A324513 A086902

Adjacent sequences: A340024 A340025 A340026 * A340028 A340029 A340030

Keyword

nonn

Author

Andrew Howroyd, Jan 02 2021

Status

approved