A337518 Number of non-isomorphic graphs on n unlabeled nodes modulo 3.

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

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

Chai Wah Wu, Table of n, a(n) for n = 0..98

Steven C. Cater and Robert W. Robinson, Exponents of 2 in the numbers of unlabeled graphs and tournaments, Congressus Numerantium, 82 (1991), pp. 139-155.

Formula

a(n) = A000088(n) mod 3.

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

Cf. A000088, A007149.

Sequence in context: A024356 A143947 A226518 * A073781 A048622 A105661

Adjacent sequences: A337515 A337516 A337517 * A337519 A337520 A337521

Keyword

nonn

Author

Drake Thomas, Nov 21 2020

Status

approved