Bổ đề Burnside và áp dụng của nó vào bài toán đếm


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 Xg_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 XG 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à XG 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 nq 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)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 nq 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.



Đề thi chọn học sinh giỏi Quốc gia môn Toán năm học 2009-2010


Câu 1. Giải hệ phương trình

x^4-y^4=240

x^3-2y^3=3(x^2-4y^2)-4(x-8y).
Câu 2. Cho dãy số (a_n) xác định bởi  a_1=5, a_n=(a_{n-1}^{n-1}+2^{n-1}+2.3^{n-1})^{\dfrac{1}{n}}\forall n\geq 2.
a. Tìm công thức số hạng tổng quát của dãy;
b. Chứng minh rằng dãy này là dãy giảm.
Câu 3. Cho đường tròn (O). Hai điểm B,C cố định trên đường tròn, BC không phải đường kính. Lấy A là một điểm trên đường tròn không trùng với B,CAD,AE là các đường phân giác trong và ngoài. I là trung điểm của DE. Qua trực tâm tam giác ABC  kẻ đường thẳng vuông góc với AI  cắt AD,AE tại M,N.
a. Chứng minh rằng MN luôn đi qua một điểm cố định;
b. Tìm A  sao cho S(AMN) lớn nhất.
Câu 4. Chứng minh rằng với mọi số nguyên dương n phương trình x^2+15y^2=4^n có ít nhất n nghiệm tự nhiên.
Câu 5. Cho bảng 3\times 3n là một số nguyên dương cho trước. Tìm số các cách tô màu không như nhau khi tô mỗi ô bởi một trong n  màu. Hai cách tô màu gọi la như nhau nếu một cách nhận được từ cách kia bởi một phép quay quanh tâm.

Nguồn MathScope (đã chỉnh sửa).

1.3. Các véc tơ đẳng hướng


Định nghĩa 3Một phần tử x của một mô đun bậc hai (V,Q) được gọi là đẳng hướng nếu Q(x)=0. Một không gian con U của V được gọi là đẳng hướng nếu tất cả các véc tơ của nó đẳng hướng.

Hiển nhiên ta có U đẳng hướng \Leftrightarrow U\subset U^0\Leftrightarrow Q|U=0.

Định nghĩa 4.-Một mô đun bậc hai có một cơ sở hình thành bởi hai phần tử đẳng hưóng x,y sao cho x.y\not =0 được gọi là một phẳng hyperbolic.

Sau khi nhân y với \dfrac{1}{x.y} ta có thể giả sử là x.y=1. Khi đó ma trận của dạng bậc hai tương ứng với x,y\left(\begin{matrix}0&1\\1&0\end{matrix}\right), định thức của nó bằng -1(nói riêng nó là không suy biến).

Mệnh đề 3.-Cho x là một phần tử đẳng hướng khác 0 của một mô đun bậc hai không suy biến (V,Q). Khi đó tồn tại không gian con U của V chứa x và là một phẳng hyperbolic.

V không suy biến, tồn tại z\in V sao cho x.z=1. Phần tử y=2z-(z.z)x là đẳng hướng và x.y=2. Không gian con U=kx+ky có tính chất như mệnh đề yêu cầu.

Hệ quả.-Nếu (V,Q) không suy biến và chứa một phần tử đẳng hướng khác 0 thì Q(V)=k.

(Nói cách khác, với mỗi a\in k tồn tại v\in V để Q(v)=a.)

Chú ý đến mệnh đề, ta chỉ cần chứng minh hệ quả với V là một phẳng hyperbolic với cơ sở x,y sao cho x,y đẳng hướng và x.y=1. Nếu a\in k thì a=Q(x+\dfrac{a}{2}y), từ đây ta có Q(V)=k.