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引理可以快速計算出解的數量，從而衡量演算法的效率。