33 lines
912 B
Python
33 lines
912 B
Python
#!/usr/bin/python3
|
|
|
|
from functools import lru_cache
|
|
|
|
def Z_S(n, f, k):
|
|
"""
|
|
The cycle index of the symmetric group has recurrence
|
|
Z(S_n, f(x)) = 1/n \sum_{i=1}^n f(x^i) Z(S_{n-i}, f(x)).
|
|
This function finds the coefficient of x^k in Z(S_n, f(x))
|
|
"""
|
|
# Special case to avoid division by zero
|
|
if n == 0:
|
|
return 1 if k == 0 else 0
|
|
# Special case as a speed optimisation
|
|
if n == 1:
|
|
return f(k)
|
|
return sum(
|
|
sum(f(ij // i) * Z_S(n-i, f, k - ij) for ij in range(0, k+1, i))
|
|
for i in range(1, n+1)
|
|
) // n
|
|
|
|
@lru_cache(maxsize=None)
|
|
def A000598(k): return 1 if k == 0 else Z_S(3, A000598, k-1)
|
|
|
|
@lru_cache(maxsize=None)
|
|
def A000642(k): return Z_S(2, A000598, k)
|
|
|
|
def A000631(k): return Z_S(2, A000642, k)
|
|
|
|
def A000602(k): return A000642(k) + (A000642((k-1) // 2) if k % 2 == 1 else 0) - A000631(k-1)
|
|
|
|
for k in range(500): print(k, A000602(k))
|