A334335 Inverse Euler transform of A000568.

1, 0, 1, 2, 8, 43, 398, 6413, 184596, 9540998, 894012628, 153204356304, 48387996396590, 28352880689501075, 30992600581556641380, 63499394791445838416399, 244849247994227524521679624, 1783153933475289754036309451798, 24603857772350530383609071261316942

Offset: 1

Author

Pontus von Brömssen, Apr 23 2020

Keywords

• nonn

Comments

It appears that a(n) is the number of connected even graphs with n vertices, as defined in the Andersson paper (verified for n <= 10): a graph G is even if, for a given orientation of its edges, all automorphisms of G reverse the orientation of an even number of edges. If this is true, it means that A000568(n) is the number of even graphs (not necessarily connected) with n vertices. [This has been proved by Royle et al. 2023. - Pontus von Brömssen, Apr 06 2022]

Links

• Pontus von Brömssen, Table of n, a(n) for n = 1..76
• Pontus Andersson (von Brömssen), On the asymptotic distributions of subgraph counts in a random tournament, Random Structures & Algorithms 13 (1998), 249-260.
• Gordon F. Royle, Cheryl E. Praeger, S. P. Glasby, Saul D. Freedman, and Alice Devillers, Tournaments and even graphs are equinumerous, Journal of Algebraic Combinatorics 57 (2023), 515-524; arXiv version, arXiv:2204.01947 [math.CO], 2022.

Crossrefs

Cf. A000568.

Programs

Python

from functools import lru_cache
from itertools import product
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A334335(n):
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<<(sum(p[r]*p[s]*gcd(r,s) for r,s in product(p.keys(),repeat=2))-sum(p.values())>>1),prod(q**p[q]*factorial(p[q]) for q in p)) for p in partitions(n) if all(q&1 for q in p)))
    @lru_cache(maxsize=None)
    def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
    return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n # Chai Wah Wu, Jul 03 2024