самый простой способ (по крайней мере, для лишенного геометрического воображения компьютера) — посчитать Эйлерову характеристику: с одной стороны, она равна 2-2g, а с другой стороны, из 2n-угольника получается карта с 1 гранью, n ребрами и… надо только как-то посчитать количество вершин
если считать, что i-е ребро соединяет вершины i и i+1, то при его склейке с j-м ребром i-я вершина склеевается с (j+1)-й… то есть если думать про склейку как про перестановку (инволюцию на множестве сторон), то количество вершин — это количество циклов в композиции этой перестановки с циклическим сдвигом на 1
вообще книжка Звонкина и Ландо учит, что про ленточный (вложенный в поверхность) граф бывает удобно думать как про тройку перестановок… но я отвлекся, а пора переходить к реализации
перебор инволюций реализовал в том же духе, как перебирал в https://t.me/compmathweekly/9 разбиения на доминошки:
def involutions(n,state=[]):
if state == []:
state = [-1]*(2*n)
for i in range(2*n):
if state[i] == -1:
for j in range(i+1,2*n):
if state[j] == -1:
newst = state.copy()
newst[i], newst[j] = j, i
yield from involutions(n,newst)
return
yield state
осталось добавить вычисление рода через подсчет количества циклов:
def genus(perm):
N = len(perm)
state = [(perm[i]+1) % N for i in range(N)]
v = 0
for i in range(N):
j = state[i]
if j != -1:
v += 1
while j != i:
state[j], j = -1, state[j]
return (N//2-v+1)//2
# v-n+1 = 2-2g => g = (n-v+1)/2
for n in range(1,6+1):
counts = [0]*(n//2+1)
for perm in involutions(n):
counts[genus(perm)] += 1
print(f"n={n}:",*counts)
n=1: 1
n=2: 2 1
n=3: 5 10
n=4: 14 70 21
n=5: 42 420 483
n=6: 132 2310 6468 1485
в следующий раз попробую мб написать, что можно увидеть в таблице возникающих чисел