MSE #4333643

memory.py

#!/usr/bin/env python3
from math import prod, comb
from fractions import Fraction as F
N = 12
denom = prod(range(1, 2*N, 2))
print(f"denom = {denom}")

states = {(0, N, 0): 1}
def dp(k, v):
	states[k] = states.get(k, 0) + v

for n in range(N, -1, -1):
	for k in range(n//2+1):
		for d in range(2*N+1):
			p = states.get((k, n, d), 0)
			if p == 0:
				continue
			del states[(k, n, d)]
			if k == n == 0:
				print(f"{d} -> {p*denom}")
				continue
			dp((k, n-1, d+1), p*F(n-2*k, comb(2*(n-k), 2)))
			dp((k+1, n, d+1), p*F(comb(2*n-4*k, 2)-n+2*k, comb(2*(n-k), 2)))
			dp((k, n-1, d+2), p*F(4*k*(n-2*k), comb(2*(n-k), 2)))
			dp((k-1, n-2, d+3), p*F(comb(2*k, 2), comb(2*(n-k), 2)))