Burnside’s lemma


Cho X là một tập hợp và G là một nhóm. Ta nói G tác động trên X, hay X là một G-tập, nếu có hàm G\times X\to X, (g,x)\mapsto gx thoả mãn ex=x\forall x\in X và g_1(g_2x)=(g_1g_2)x\forall x\in X\forall g_1,g_2\in G, ở đây e là phần tử đơn vị của G.

Gìơ ta xét một G-tập X, với mỗi x\in X, ta gọi quỹ đạo của x là tập \{gx|g\in G\}. Các quỹ đạo khác nhau của các phần tử trong X làm thành một phân hoạch của X, thật vậy, quan hệ xRy nếu có g\in G để x=gy là một quan hệ tương đương trên X. Khi X và G là các tập hữu hạn thì ta có thể tính số khối của phân hoạch này theo bổ đề sau đây.

Bổ đề Burnside. Nếu X là một G-tập hữu hạn (nghĩa là X và G là các tập hữu hạn và X là một G-tập) và N là số các quỹ đạo khác nhau của các phần tử trong X thì N=\dfrac{1}{|G|}\sum_{g\in G}F(g), trong đó với mỗi g\in G, F(g) là số phần tử của tập \{x\in X|gx=x\}.

Tôi sẽ không đưa ra chứng minh nào của bổ đề này ở  đây, các bạn có thể tìm một chứng minh  trong sách Tổ hợp của Ngô Đắc Tân hay sách về lý thuyết nhóm của Rotman. Gìơ ta đi xét các áp dụng của bổ đề này vào giải các bài toán đếm, các bài tập này đều có trong sách của Rotman.

Bài 1. Cho n và q là các số nguyên dương. Hỏi có bao nhiêu lá cờ gồm n mảnh sao cho mỗi mảnh mang một trong q màu cho trước?(Ví dụ một lá cờ như vậy là cờ của Pháp gồm 3 mảnh).

Lời giải. Vì khi ta tô màu một mặt của lá cờ thì mặt sau sẽ được xác định hoàn toàn màu. Nên số lá cờ bằng số cách tô bảng 1\times n bởi q màu, hai cách tô là như nhau nếu nó ở dạng như hình dưới đây.

(Trong hình trên các c_i là các màu.)

Gọi X là tập các bộ (c_1,c_2,\cdots,c_n) với c_i là một trong q màu đã cho với mỗi i. Ký hiệu S_n là nhóm các hoán vị trên \{1,2,\cdots,n\}, G là nhóm con cyclic sinh bởi hoán vị f của S_n, ở đây f(i)=n+1-i\forall i. Ta cho G tác động trên X theo luật f(c_1,c_2,\cdots,c_n)=(c_n,c_{n-1},\cdots,c_1). Như trên đã phân tích, ta chỉ cần đếm số N các quỹ đạo của các phần tử của x theo tác động này là xong. Theo bổ đề Burnside, ta chỉ cần tính F(id) và F(f). Dễ thấy F(id)=|X|=q^n theo quy tắc nhân. Để tính F(f), ta chú ý rằng (c_1,c_2,\cdots,c_n)\in X không thay đổi khi tác động f nếu và chỉ nếu c_1=c_n,c_2=c_{n-1},\cdots, vậy cùng theo quy tắc nhân ta có F(f)=q^{[\dfrac{n+1}{2}]}. Như thế đáp số của bài toán là \dfrac{1}{2}(q^n+q^{[\dfrac{n+1}{2}]}).

Bài 2. Cho n và q là các số nguyên dương. Chứng minh rằng có

\dfrac{1}{4}(q^{n^2}+2q^{[\dfrac{n^2+3}{4}]}+q^{[\dfrac{n^2+1}{2}]}) cách tô màu bảng vuông n\times n bởi q màu.

Lời giải sơ lược. Lời giải y hệt như trường hợp trên. Ta đánh số các ô của bảng theo kiểu xoáy ốc, chia hai trường hợp n chẵn, lẻ cho dễ đánh số. Tập X bây giờ là tập tất cả các bộ (c_1,c_2,\cdots,c_{n^2}), nhóm G bây giờ là nhóm con cyclic cấp 4 sinh bởi phép quay +90^0 của S_{n^2}.

Chú ý.  Khi n=3,q=n ta có bài số 5 trong VMO 2010.



3 thoughts on “Burnside’s lemma”

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: