|
|
A337518
|
|
Number of non-isomorphic graphs on n unlabeled nodes modulo 3.
|
|
1
|
|
|
1, 1, 2, 1, 2, 1, 0, 0, 1, 0, 2, 2, 0, 0, 1, 2, 0, 1, 0, 2, 1, 2, 0, 0, 2, 0, 0, 1, 1, 1, 0, 0, 2, 0, 1, 0, 2, 1, 0, 0, 2, 2, 0, 2, 0, 0, 2, 1, 2, 1, 0, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 0, 1, 2, 1, 1, 1, 1, 0, 0, 2, 1, 1, 2, 0, 2, 0, 0, 0, 2, 1, 2, 2, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
For the mod-2 case, the sequence is eventually constant, because there are an even number of graphs on n vertices for n>4. (In fact, the number of factors of 2 in A000088(n) is asymptotically n/2; see Cater and Robinson in the Links section.)
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
For n = 4, there are 11 graphs on 4 nodes up to isomorphism, so a(4) = 2 = 11 mod 3.
|
|
PROG
|
(Python)
from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A337518(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r, s) for r, s in combinations(p.keys(), 2))+sum((q>>1)*r+(q*r*(r-1)>>1) for q, r in p.items()), prod(q**r*factorial(r) for q, r in p.items()))%3 for p in partitions(n))) % 3 # Chai Wah Wu, Jul 02 2024
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|