Once again we have a symmetric group acting on nodes, inducing an action on the set of possible edges and on graphs. It acts on the set of self-complementary graphs, but I don't see how to count how many of these are fixed by a given permutation to apply the lemma that is often named after Burnside. So instead I use the formula in the comment of the OEIS entry that says that the number of self-complementary graphs with n nodes is equal to the difference of the number of graphs with n nodes with an even number of edges and with an odd number of edges. The symmetric group acts on these sets of graphs as well. Instead of computing both numbers independently, we will consider the cases of an even number and an odd number of edges in parallel, which will turn out to be simpler and allow optimizations. We'll see that "evaluate the graph polynomial at -1" will lead to the same result.

As usual, we take the sum over the group elements in Burnside's lemma conjugacy class wise, and represent the conjugacy classes by partitions of n. For each conjugacy class, we want to know the difference between the numbers of graphs with an even and odd number of edges that is fixed by a permutation from that class.

Assume we are given a concrete permutation g. The group generated by g acts on the set of possible edges and partitions them into orbits. A graph is fixed by g if for each orbit, it contains either all or none of its edges. Let's look at the orbits. Each edge in one orbit has its endpoints in the same two (possibly same) cycles of g.

Let's first assume the endpoints are from the same cycle of length k>=2. If k is odd, then there are (k-1)/2 orbits of length k. If k is even, then there are k/2-1 orbits of length k and one of length k/2 (for example, if g contains the cycle (123456), then the there is an edge orbit of size 3 containing {1,4}). Note that we get all orbits of even size exactly when k is a multiple of four.

Next consider the case that the endpoints are from different cycles of lengths k and l. Then the orbit has size lcm(k,l), and there are gcd(k,l) such orbits.

In order to combine all the possibilities, consider the product, for each edge orbit, of 1+x^r, where r is the size of the corresponding orbit. The coefficient of x^s of the product gives the number of graphs that are fixed by g and have s edges. We want the sum of the coefficients at even exponents minus the sum of them at odd coefficients, which we get by evaluating the polynomial at x=-1.

If we kept the polynomials and added them together, we'd get the graph polynomial. Instead, we don't even create these polynomials, but do the substitution immediately. For an edge orbit of even size, we get a factor of 2, for an odd size we get 0. (There is also a direct combinatorial argument that if there is an edge orbit of odd size then there are as many fixed graphs with an even number of edges as there are with an odd number of edges. And the factor 2 corresponds to the choice of including the edges of one orbit to the fixed graph or not).

So, by the considerations about edges with points from only one cycle, we get a difference of 0 whenever g contains a cycle of odd length greater than one, or a cycle of even length not divisible by four. We also get a difference of 0 whenever g contains at least two fixed points (cycles of length one).

This means we only need to sum over conjugacy classes with at most one fixed point and all other cycle lengths multiples of four. sparts computes the corresponding partitions of n. There are none unless n is of the form 4k or 4k+1, so in the other cases there are no self-complementary graphs, which can also easily seen by noting that in these cases the total number of possible edges is odd. But this observations alone doesn't lead to the optimization of only considering special partitions, of which there are only as much as there are partitions of k.

ccSize computes the size of a conjugacy class with given cycle lengths. edgeorbits computes the number of edge orbits of the action of the group generated by a permutation with the given cycle lengths, assuming they are of the special form. In the general case, samecyc, the number of edge orbits with edges that have both nodes from the same cycle, could not be calculated like this. (When I wrote the code, I didn't notice that it only depends on n in the relevant cases.)

a puts everything together, and f fixes the different indexing.

250. Coconut, 711 bytes, A000171

from collections import Counter from math import gcd, factorial def sparts(n, m=4): if n%2==1: return [ [1] + p for p in sparts(n-1) ] elif n==0: return [ [] ] elif n<m: return [] else: return [ [m] + p for p in sparts(n-m,m) ] + sparts(n,m+4) def ccSize(l) = centSize = [ val**mult * factorial(mult) for val, mult in Counter(l).items() ] |> reduce$(*) factorial(sum(l)) // centSize def edgeorbits(l) = samecyc = sum(l) // 2 diffcyc = sum ([ gcd(l[i],l[j]) for i in range(len(l)) for j in range(i) ]) samecyc + diffcyc def a(n) = sum ([ ccSize(l)*2**edgeorbits(l) for l in sparts(n) ]) // factorial(n) def f(n) = a(n+1) 

Try it online!

Next sequence

This can easily compute more values than the 31 that OEIS has.

250. Coconut, 711 bytes, A000171

from collections import Counter from math import gcd, factorial def sparts(n, m=4): if n%2==1: return [ [1] + p for p in sparts(n-1) ] elif n==0: return [ [] ] elif n<m: return [] else: return [ [m] + p for p in sparts(n-m,m) ] + sparts(n,m+4) def ccSize(l) = centSize = [ val**mult * factorial(mult) for val, mult in Counter(l).items() ] |> reduce$(*) factorial(sum(l)) // centSize def edgeorbits(l) = samecyc = sum(l) // 2 diffcyc = sum ([ gcd(l[i],l[j]) for i in range(len(l)) for j in range(i) ]) samecyc + diffcyc def a(n) = sum ([ ccSize(l)*2**edgeorbits(l) for l in sparts(n) ]) // factorial(n) def f(n) = a(n+1) 

Try it online!

Next sequence

This can easily compute more values than the 31 that OEIS has.