# 250. [Coconut](http://coconut-lang.org), 711 bytes, [A000171](https://oeis.org/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!](https://tio.run/##dZHLboMwEEX3fMUsUskG2jyUVVWy6Sd0iVi4xk4d@YGMqdSq/07HQICkKguE587MPVxzx53tQt9L7wxwp7XgQTnbgjKN8wFeXWeD8MmgGxY@rsKZ1zlIxoPziukkqYWEtmE@tMTmYIojfU4AlAT7cCiKfTwAeBE6b6GEcl9BBg1I5/Gt7Dz6uKdQYa/QcbQodveD1Up@MbfqqLTifsb8Z2Zyg3YozuQmO9LxZzh/U9@CaAoFruPChniGAhd@Mp2mptMB0iUCEgt0cF490RPbMZHYjt5ToLj3SQVhWhIBfk5IW3dcbEgaVyxL285gK4XtdkYY8UR9Fs6/K6SeEFtmBP/iSDgOxZkD1msl5VwHUsarI7pUVa7LS/WH@EqtIq1n9owZCDtAxPJlKStEpyvj7Go1EjJiJ7DRdg40PaTpDX5yY6zXV0RnqRp@aEnGTvckB5volu1pP5IddzRmalizIRI/0xM0XtnQ/wI "Coconut – Try It Online")

[Next sequence](https://oeis.org/A000711)

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

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.