A384631 Number of self-inverse double cosets in D_n\S_n/D_n.

1, 2, 4, 8, 17, 52, 153, 482, 1623, 5879, 21926, 85436, 344998, 1444437, 6230232, 27704051, 126571091, 593974930, 2856031804, 14065575098, 70822693101, 364420818168, 1913609207886, 10249715874962, 55938458263035, 310915671908063, 1758452185453926, 10115287840489764

Offset: 3

Author

Ludovic Schwob, Jun 05 2025

Keywords

• nonn

Comments

D_n is the dihedral group of order 2*n, seen as a subgroup of the symmetric group S_n.

Cosets in S_n/D_n are in bijection with polygons obtained by connecting cyclically n equally spaced points on a circle. Double cosets in D_n\S_n/D_n are in bijection with polygons up to rotation and reflection.

Links

• Ludovic Schwob, On the enumeration of double cosets and self-inverse double cosets, arXiv:2506.04007 [math.CO], 2025. See Proposition 4.2 p.9.

Crossrefs

Cf. A001710 (polygons), A000940 (polygons up to rotation and reflection), A384630 (self-inverse cycles).

Programs

Python

# From Proposition 4.2 in the reference:
from sympy import divisors, factorial, totient
def A384631(n):
    s = 0
    if n%2==0:
        for d in divisors(n//2):
            if d%2==0:
                s += totient(d)*factorial(n//d)*(d//2)**(n//2//d)//factorial(n//2//d)
            else:
                s += totient(d)*sum(factorial(n//d)*d**i//2**i//factorial(i)//factorial(n//d-2*i) for i in range(n//2//d+1))
        s += n//2*((n%4)//2+1)*factorial(2*(n//4))//factorial(n//4)
    else:
        for d in divisors(n):
            s += totient(d)*sum(factorial(n//d)*d**i//2**i//factorial(i)//factorial(n//d-2*i) for i in range(n//d//2+1))
        if n%4==1:
            s += n*factorial(n//2)//factorial(n//4)
    return s//n//2