Burnside引理探究

一、概述

Burnside引理是群作用（group action）的一种重要有力的工具，它能够通过计算不动点（fixed point）数目，来计算出群作用下的轨道（orbit）数目，从而衡量出对称性。Burnside引理的应用十分广泛，包括组合数学、计算几何、图论等领域。

二、核心思想

Burnside引理的核心思想是通过计算群元素的置换对一组元素（一般为有限集合）的不动点数量来计算置换群的轨道数量。

def burnside(s, a):
    # s: 置换群S
    # a: 元素集合
    ans = 0
    for g in s:
        # 计算不动点数量
        fixed_points = len([i for i in a if g(i) == i])
        ans += fixed_points
    # 根据Burnside引理计算轨道数量
    return ans / len(s) 

三、应用实例

1.计算颜色方案数

假设有一面4×4的拼图，每个位置可以被染成4种颜色之一。如果考虑旋转、翻转的对称性，求总共有多少种不同的染色方案数。

解：将4×4的拼图看成元素集合a = {(x,y)|1≤x≤4, 1≤y≤4 }。我们需要计算置换群S4的轨道数量。

def rotate_90(p):
    # 顺时针旋转90度
    return (p[1], -p[0])

def rotate_180(p):
    # 顺时针旋转180度
    return (-p[0], -p[1])

def rotate_270(p):
    # 顺时针旋转270度
    return (-p[1], p[0])

def flip_v(p):
    # 垂直翻转
    return (-p[0], p[1])

def flip_h(p):
    # 水平翻转
    return (p[0], -p[1])

# 置换群S4
S4 = [lambda p:p, rotate_90, rotate_180, rotate_270, flip_v, flip_h, flip_v, flip_h]

# 给出元素集合a
a = [(x,y) for x in range(1,5) for y in range(1,5)]

# 根据Burnside引理计算轨道数量
print(burnside(S4, a))

这个问题的答案是 2,214,336 种。

2. 计算正方形填法数

有$k$个1 $\times$ 1 的小正方形，要放置在一个$n\times n$的大正方形内，每个小正方形都必须占据一个整数坐标点，且不允许重叠。如果考虑旋转、翻转的对称性，求总共可以填放的方案数。

解：将$n\times n$的正方形看成元素集合a，里面的点坐标用$(x,y)$表示。我们需要计算置换群S4的轨道数量。

def trans_rotate(p, r, k):
    # 针对顺时针旋转90度的仿射变换
    if k == 1:
        return (p[1], n - p[0] - 1)
    # 针对顺时针旋转180度的仿射变换
    elif k == 2:
        return (n - p[0] - 1, n - p[1] - 1)
    # 针对顺时针旋转270度的仿射变换
    elif k == 3:
        return (n - p[1] - 1, p[0])

def trans_flip(p, f, k):
    # 垂直翻转的仿射变换
    if k == 4:
        return (p[0], n - p[1] - 1)
    # 水平翻转的仿射变换
    elif k == 5:
        return (n - p[0] - 1, p[1])
    # 对角线翻转的仿射变换
    elif k == 6:
        return (p[1], p[0])
    else:
        return None

def apply_transform(p, t, k):
    # 执行仿射变换
    q = trans_rotate(p, t, k)
    if q is None:
        q = trans_flip(p, t, k)
    return q

# 置换群S4
S4 = []
for k in range(4):
    for t in range(8):
        S4.append(lambda p, t=t, k=k: apply_transform(p, t, k))

# 给出元素集合a
a = [(x,y) for x in range(n) for y in range(n)]

# 根据Burnside引理计算轨道数量
print(burnside(S4, a))

其中$n=5$的结果是 34,907,200 种。

四、拓展应用

Burnside引理还可以应用于计算多面体、格点等的对称性数量。此外，在模拟退火、遗传算法等的随机化搜索算法中，通过Burnside引理可以快速计算出解的数量，从而衡量算法的效率。