Tài liệu Lý thuyết polya và ứng dụng

  • Số trang: 42 |
  • Loại file: PDF |
  • Lượt xem: 115 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 27125 tài liệu

Mô tả:

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI THỊ HÀ THU LÝ THUYẾT POLYA VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI THỊ HÀ THU LÝ THUYẾT POLYA VÀ ỨNG DỤNG Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: PGS.TS. ĐÀM VĂN NHỈ Thái Nguyên - 2015 i Mục lục Lời cam đoan ii Lời nói đầu 1 1 Lý thuyết Polya 2 1.1 Khái niệm nhóm . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Quan hệ tương đương . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Nhóm con chuẩn tắc và nhóm thương . . . . . . . . . . . 3 1.1.3 Định lý Lagrange và các hệ quả . . . . . . . . . . . . . . 6 Nhóm các phép hoán vị . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.1 Nhóm các phép hoán vị . . . . . . . . . . . . . . . . . . . 7 1.2.2 Chu trình của hoán vị . . . . . . . . . . . . . . . . . . . . 10 Bổ đề Burnside . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3.1 Tác động nhóm lên một tập . . . . . . . . . . . . . . . . . 15 1.3.2 Vận dụng giải bài toán tô màu . . . . . . . . . . . . . . . 19 Đa thức xích các chỉ số . . . . . . . . . . . . . . . . . . . . . . . 22 1.4.1 Khái niệm đa thức xích chỉ số . . . . . . . . . . . . . . . 22 1.4.2 Đa thức xích chỉ số của Cn , Dn , Sn . . . . . . . . . . . . 23 Định lý Polya . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.2 1.3 1.4 1.5 2 Vận dụng Định lý Polya 28 2.1 Vận dụng Định lý Polya trong bài toán tô màu . . . . . . . . . . . 28 2.2 Một vài bài toán tô màu khác . . . . . . . . . . . . . . . . . . . . 36 Kết luận và Đề nghị 37 Tài liệu tham khảo 38 ii Lời cam đoan Tôi xin cam đoan các số liệu và kết quả nghiên cứu trong luận văn này là trung thực và không trùng lặp với các đề tài khác. Tôi cũng xin cam đoan mọi thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. Thái Nguyên, ngày 16 tháng 4 năm 2015 Học viên Bùi Thị Hà Thu 1 Lời nói đầu Luận văn này trình bày lại một số kết quả về lý thuyết Polya và một vài vận dụng. Luận văn được chia ra làm hai chương. Chương 1 gồm năm mục. Mục 1.1 trình bày về khái niệm nhóm. Trong Mục 1.2 tập trung viết về nhóm các phép hoán vị. Mục 1.3 được dành để chứng minh lại Bổ đề Burnside. Mục 1.4 được dành để viết về xích các đa thức chỉ số. Trong Mục 1.5 chúng tôi chứng minh Định lý Polya. Chương 2 gồm hai mục. Mục 2.1 trình bày một vài vận dụng Định lý Polya trong bài toán tô màu. Mục 2.2 trình bày một vài ví dụ về việc vận dụng Định lý Polya trong bài tóan tổ hợp. Trong thời gian sưu tầm tài liệu, làm đề cương và viết luận văn, tôi đã nhận được sử góp ý và chỉ dẫn tận tình của người hướng dẫn. Tôi xin bày tỏ lòng biết ơn chân thành tới thầy của mình, PGS.TS Đàm Văn Nhỉ. Nhân đây, tôi cũng xin chân thành cảm ơn Khoa Toán- Tin, Khoa Sau đại học Trường Đại học Khoa học- Đại học Thái Nguyên đã tạo mọi điều kiện thuận lợi trong quá trình học tập của tôi. Tôi cũng xin được cảm ơn sự nhiệt tình giảng dạy của các giảng viên trong suốt thời gian tôi học tập. Tôi xin cảm ơn Ban giám hiệu Trường THPT Hải An đã luôn tạo điều kiện tốt cho tôi công tác và học tập, để tôi hoàn thành nhiệm vụ học tập của mình. Cuối cùng, tôi xin gửi những lời cảm ơn đặc biệt nhất tới đại gia đình, vì những động viên khích lệ giúp tôi hoàn thành luận văn này. Thái Nguyên ngày 16 tháng 04 năm 2015 Bùi Thị Hà Thu 2 Chương 1 Lý thuyết Polya 1.1 1.1.1 Khái niệm nhóm Quan hệ tương đương Giả thiết tập X 6= ∅. Tích đề các X × X được định nghĩa như sau: X × X = {(x, y)|x, y ∈ X}. Định nghĩa 1.1.1. Tập con S của X × X được gọi là một quan hệ hai ngôi trong X. Nếu (x, y) ∈ S thì ta nói x có quan hệ S với y và viết xSy. Định nghĩa 1.1.2. Giả thiết X 6= ∅ và S 6= ∅ là một quan hệ hai ngôi trong X. Quan hệ S được gọi là một quan hệ tương đương trong X nếu nó thỏa mãn ba điều kiện sau đây: (1) (Phản xạ) Với mọi x ∈ X có xSx. (2) (Đối xứng) Với mọi x, y ∈ X, nếu có xSy thì cũng có ySx. (3) (Bắc cầu) Với mọi x, y, z ∈ X, nếu có xSy và ySz thì cũng có xSz. Khi S là một quan hệ tương đương trong X thì ta thường ký hiệu ∼ thay cho S. Đặt C(x) = {y ∈ X|y ∼ x} và gọi nó là một lớp tương đương với x làm đại diện. Dễ dàng chỉ ra các tính chất sau: Mệnh đề 1.1.3. Với quan hệ tương đương ∼ trong X 6= ∅ ta có 3 (1) Với mọi x ∈ X có x ∈ C(x). (2) Với mọi y, z ∈ C(x) có y ∼ z và y, z ∼ x. (3) Với mọi x, y ∈ X, có hoặc C(x) ∩ C(y) = ∅ hoặc C(x) = C(y). (4) Tập thương X/ ∼ là tập các lớp tương đương không giao nhau. 1.1.2 Nhóm con chuẩn tắc và nhóm thương Trước tiên, ta nhắc lại một số khái niệm và ký hiệu về nhóm. Định nghĩa 1.1.4. Tập G 6= ∅ với phép toán hai ngôi G × G → G, (x, y) 7→ x.y được gọi là một nhóm nếu nó thỏa mãn ba điều kiện (1) (x.y).z = x.(y.z) với mọi x, y, z ∈ G. (2) Có phần tử e ∈ G, được gọi là đơn vị, thỏa mãn e.x = x.e = x với mọi x∈G (3) Với mỗi x ∈ G có phần tử x0 ∈ G để x.x0 = x0 .x = e. Do tính duy nhất của x0 cho mỗi x nên x0 được ký hiệu qua x−1 và được gọi là phần tử nghịch đảo của x. Nhóm G được gọi là một nhóm giao hoán hay nhóm abel nếu x.y = y.x với mọi x, y ∈ G. Để đơn giản, nhiều khi thay cho tích x.y ta viết đơn giản xy và đôi khi để biết phép toán hai ngôi trong nhóm G ta cũng thường viết (G, .). Đôi khi người ta cũng thường ký hiệu phần tử đơn vị của nhóm G bởi 1. Định nghĩa 1.1.5. Cho hai nhóm (G, .) và (G0 , ◦). Ánh xạ φ : G → G0 được gọi là một đồng cấu nếu φ(xy) = φ(x) ◦ φ(y) thỏa mãn cho mọi x, y ∈ G. Đồng cấu φ được gọi là một đẳng cấu nếu nó là một song ánh. Định nghĩa 1.1.6. Cho nhóm G. Lực lượng của G, ký hiệu |G|, được gọi là cấp của G. Nếu |G| < ∞ thì G được gọi là nhóm hữu hạn. 4 Định nghĩa 1.1.7. Tập con H khác rỗng của nhóm G thỏa mãn x.y ∈ H và x−1 ∈ H, khi x, y ∈ H, được gọi là một nhóm con của G. Nhóm con A của nhóm G được gọi là một nhóm con chuẩn tắc của G nếu xax−1 ∈ A với mọi a ∈ A, x ∈ G. Giả thiết A là một nhóm con của nhóm G. Ta ký hiệu hai tập sau: xA = {xa|a ∈ A}, Ax = {ax|x ∈ A}. Tập xA được gọi là lớp ghép trái của A trong X; Tập Ax được gọi là lớp ghép phải của A trong G. Ký hiệu tập thương của G trên A qua G/A = {xA|x ∈ G}. Tiếp tục, định nghĩa quan hệ ∼ trong nhóm G như sau: Với x, y ∈ G, quan hệ x ∼ y nếu x−1 y ∈ A. Bổ đề 1.1.8. Quan hệ ∼ trong G là một quan hệ tương đương. Chứng minh: Vì e ∈ A nên x−1 x = e ∈ G. Vậy x ∼ x với mọi x ∈ G. Giả sử x, y ∈ G thỏa mãn x ∼ y. Khi đó x−1 y ∈ A. Vì A cũng chính là một nhóm nên −1 y −1 x = x−1 y ∈ A. Do vậy y ∼ x. Cuối cùng, giả sử x, y, z ∈ G thỏa mãn x ∼ y và y ∼ z. Khi đó x−1 y, y −1 z ∈ A và ta có x−1 z = x−1 y.y −1 z ∈ A. Từ đây suy ra x ∼ z. Tóm lại, quan hệ ∼ trong G là một quan hệ tương đương. Hệ quả 1.1.9. Với x, y ∈ G, xA = yA khi và chỉ khi x−1 y ∈ A. Chứng minh: Kết quả được suy ra từ Bổ đề 1.1.8. Bổ đề 1.1.10. Với quan hệ tương đương ∼ trong G, mỗi lớp C(x) = xA với x ∈ G. Chứng minh: Thật vậy, vì ∼ là một quan hệ tương đương theo Bổ đề 1.1.8 nên ta có các lớp C(x). Lấy y ∈ C(x). Khi đó x ∼ y và ta có x−1 y ∈ A. Vậy, tồn tại a ∈ A để x−1 y = a. Từ đây suy ra y = xa ∈ xA. Do y được lấy tùy ý nên C(x) ⊂ xA. Lấy y ∈ xA. Khi đó có a ∈ A để y = xa. Vậy x−1 y = a ∈ A hay y ∼ x và suy ra y ∈ C(x). Do y được lấy tùy ý nên C(x) ⊃ xA. Tóm lại C(x) = xA 5 Định lý 1.1.11. Nhóm con A là nhóm con chuẩn tắc của nhóm G khi và chỉ khi xA = Ax với mọi x ∈ G. Chứng minh: Giả thiết A là một nhóm con chuẩn tắc của nhóm G. Lấy y = xa ∈ xA. Vì A là một nhóm con chuẩn tắc nên xax−1 ∈ A. Vậy có b ∈ A để xax−1 = b và suy ra y = xa = bx ∈ Ax. Do y được lấy tùy ý từ xA nên xA ⊂ Ax. Tương tự có xA ⊃ Ax. Tóm lại, xA = Ax với mọi x ∈ G. Ngược lại, Giả thiết xA = Ax với mọi x ∈ G. Với x ∈ G, a ∈ A có xa ∈ xA = Ax và như vậy, tồn tại b ∈ A để xa = bx hay xax−1 = b ∈ A. Điều này chỉ ra A là nhóm con chuẩn tắc của nhóm G Định lý 1.1.12. Với nhóm con chuẩn tắc A của nhóm G, ánh xạ G/A × G/A → G/A, (xA, yA) 7→ xyA là một phép toán hai ngôi và tập thương G/A = {xA|x ∈ G} cùng phép toán hai ngôi trên lập thành một nhóm. Nhóm này được gọi là nhóm thương của G trên A. Chứng minh: Ta có kết quả từ Bổ đề 1.1.10 và Định lý 1.1.11. Có nhiều nhóm con quan trọng được sinh ra bởi một tập con của G. Giả sử A là một tập con khác rỗng của nhóm G. Chuẩn tắc hóa của A trong G là một nhóm con của G được định nghĩa bằng NG (A) = {x ∈ G|xax−1 ∈ A, ∀ a ∈ A}. Tâm hóa của A trong G là một nhóm con của G được định nghĩa bằng CG (A) = {x ∈ G|xa = ax, ∀ a ∈ A}. Tâm của G là một nhóm con của G được định nghĩa bằng Z(G) = {x ∈ G|xa = ax, ∀ a ∈ G}. Chú ý rằng, Z(G) = CG (G) và Z(G) là một nhóm con chuẩn tắc của nhóm G. Cấp của phần tử x ∈ G là số tự nhiên dương nhỏ nhất r để xr = e. Nếu ta ký hiệu nhóm cyclic do x sinh ra qua < x > thì ta có ngay < x >= {e, x, . . . , xr−1 } và r = | < x > |. Chú ý cấp của e bằng 1. 6 1.1.3 Định lý Lagrange và các hệ quả Trong phần này chúng ta chứng minh một vài kết quả quan trọng về lý thuyết nhóm. Giả sử A là một nhóm con của nhóm hữu hạn G. Chỉ số của A trong G, ký hiệu qua |G : A| hoặc ind(A), được định nghĩa bằng |G/A|. Định lý 1.1.13. [Lagrange] Với nhóm con A của nhóm hữu hạn G ta luôn có |G| = |A||G : A|. Chứng minh: Giả thiết G là nhóm hữu hạn cấp n = |G| và A là nhóm con của G với m = |A| và k = |G : A|. Với mỗi x ∈ G ta định nghĩa ánh xạ fx : A → xA, a 7→ xa. Hiển nhiên, ánh xạ fx là một toàn ánh. Từ xa = xb suy ra a = b. Vậy fx còn là một đơn ánh. Do vậy, fx là một song ánh và suy ra m = |A| = |xA|. Vì các xA = C(x) là tách biệt theo Mệnh đề 1.1.3 nên G được phân ra thành k lớp phân biệt và mỗi lớp đều chứa đúng m phần tử. Do vậy |G| = mk = |A||G : A|. Hệ quả 1.1.14. Cấp của mỗi phần tử thuộc nhóm hữu hạn G là một ước số của n = |G|. Chứng minh: Xét nhóm con A sinh ra bởi phần tử a. Cấp của a bằng |A|. Vì |A| là một ước của |G| theo Định lý 1.1.13 nên cấp của phần tử A thuộc nhóm hữu hạn G là một ước số của n = |G|. Hệ quả 1.1.15. [Cauchy] Với nhóm abel hữu hạn G và số nguyên tố p chia hết cấp n = |G| luôn có phần tử của G cấp p. Chứng minh: Quy nạp theo cấp n của nhóm G. Lấy phần tử x ∈ G, x 6= e. Nếu n = p thì G là nhóm cyclic cấp p với phần tử sinh là x theo Định lý 1.1.13. Vậy x có cấp p. Bây giờ giả thiết n > p và tất cả các nhóm con của G đều có cấp nhỏ hơn n và xét những nhóm con với cấp chia hết cho p. Ta chỉ ra những nhóm con như vậy sẽ có phần tử cấp p. Trước tiên, xét trường hợp cấp m của phần tử x chia hết cho p. Khi đó m = | < x > | = kp. Vậy e = xm = (xk )p . Từ đây suy ra | < xk > | = p và xk có cấp p. 7 Tiếp theo, xét trường hợp cấp m của phần tử x không chia hết cho p. Đặt A =< x > và thấy ngay |A| > 1. Vì G là nhóm abel nên A là nhóm con chuẩn tắc của G. Theo Định lý 1.1.13, ta có |G/A| < |G|. Hơn nữa, ta còn có |G/A| chia hết cho p. Vì G/A là một nhóm abel, theo Định lý 1.1.12, với cấp r, r < |G|. Theo giả thiết quy nạp, G/A chứa phần tử cấp p, chẳng hạn yA. Do vậy y p ∈ A. Vì y ∈ / A nên < y p >6=< y > . Theo Định lý 1.1.14, cấp | < y p > | chia hết cấp | < y > |. Từ đây suy ra cấp |y| chia hết cho p. Trở lại trường hợp trên, ta có phần tử của G với cấp p theo giả thiết quy nạp. Ví dụ 1.1.16. Xét tậptất cả các song ánh  f : {1, 2, 3} → {1, 2, 3}. Biểu diễn 1 2 3  hay đơn giản (f (1)f (2)f (3)). Dễ mỗi song ánh f qua  f (1) f (2) f (3) dàng chỉ ra rằng tất cả có 6 song ánh và chúng lập thành  một nhóm không giao  hoán cấp 6 = 2.3. Phần tử đơn vị e =   1 2 3    ,  1 2 3 1 3 2 3 2 1   1 2 3 . và  3 1 2   ,  1 2 3 2 1 3  1 2 3 1 2 3  . Các phần tử cấp 2 là   ; Các phần tử cấp 3 là  1 2 3 2 3 1   k2π + Ví dụ 1.1.17. Xét tập tất cả các căn bậc 10 của đơn vị G = {zk |zk = cos 10 k2π i sin , k = 1, 2, . . . , 10}. Với phép nhân các số phức, G là một nhóm giao hoán 10 cấp 10 = 2.5. Phần tử đơn vị e = z10 = cos 2π + i sin 2π = 1. Một phần tử cấp 2 k2π k2π là z5 = cos π + i sin π = −1. Các phần tử cấp 5 là zk = cos + i sin với 10 10 k2π k2π k = 2, 4, 6, 8. Các phần tử cấp 10 là zk = cos + i sin với k = 1, 3, 7, 9. 10 10 1.2 Nhóm các phép hoán vị 1.2.1 Nhóm các phép hoán vị Ký hiệu T = {1, 2, . . . , n}. Mỗi song ánh từ T lên T được gọi là một hoán vị (permutation). Ký hiệu Fn,n là tập tất cả các song ánh từ T lên T. Khi đó mỗi ánh 8 xạ f ∈ Fn,n có thể biểu diễn được qua dãy (f (1), f (2), . . . , f (n)) hoặc ta cũng có thể biểu diễn thành bảng sau:   1 2 ··· n − 1 n . f = f (1) f (2) · · · f (n − 1) f (n) Với ánh xạ đồng nhất, ánh xạ hợp thành và ánh xạ ngược dưới đây:   1 2 ··· n − 1 n  id =  1 2 ··· n − 1 n   1 2 ··· n−1 n  g◦f =  g(f (1)) g(f (2)) · · · g(f (n − 1)) g(f (n))   1 2 · · · n − 1 n  f −1 =  −1 −1 −1 −1 f (1) f (2) · · · f (n − 1) f (n) chúng ta nhận ngay được kết quả: Bổ đề 1.2.1. Cùng với phép hợp thành các ánh xạ, tập Fn,n lập thành một nhóm không giao hoán cấp n! và nhóm này được ký hiệu qua Sn và được gọi là nhóm các phép hoán vị. Chứng minh: Việc kiểm tra các tiên đề nhóm cho Sn là tầm thường. Vì mỗi phần tử f ∈ Sn được xác định hoàn toàn khi biết dãy f (1), f (2), . . . , f (n). Đây là một hoán vị của 1, 2, . . . , n và có tất cả n! hoán vị. Như vậy, cấp của nhóm Sn bằng n!. Vì hợp thành của hai ánh xạ không thỏa mãn luật giao hoán nên nhóm Sn không là nhóm abel.  Ví dụ 1.2.2. Nhóm S3 gồm 6 phần tử  1 2 3 1 2 3  1 2 3 1 2 3 1 2 3  ,  ,  . 1 3 2 3 2 1 2 1 3      , 1 2 3 2 3 1   , 1 2 3 3 1 2  ,   Về mặt hình học của nhóm S3 . Ký hiệu ba đỉnh của một tam giác đều là 1, 2, 3. Khi đó phép quay δ tâm O, tâm tam giác, góc quay 1200 theo chiều dương và ba phép 9 đối xứng µ1 , µ2 , µ3 qua các đường cao đi qua đỉnh 1, 2, 3, tương ứng. Ta có       1 2 3 1 2 3 1 2 3 ,δ =   , δ2 =   id =  1 2 3 2 3 1 3 1 2       1 2 3 1 2 3 1 2 3  , µ2 =   , µ3 =  . µ1 =  1 3 2 3 2 1 2 1 3   1 2 3 4 , Ví dụ 1.2.3. Nhóm S4 gồm 24 phần tử. Xét một nhóm con gồm 8 phần tử  1 2 3 4           1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4  , ,  và  , , 2 3 4 1 3 4 1 2 4 1 2 3 1 4 3 2 3 2 1 4     1 2 3 4 1 2 3 4 ,  .  2 1 4 3 4 3 2 1 Về mặt hình học của nhóm con này. Ký hiệu bốn đỉnh của một hình vuông là 1, 2, 3, 4. Khi đó phép quay δ tâm O, tâm hình vuông, góc quay 900 theo chiều dương và bốn phép đối xứng µ13 , µ24 , ν3 , ν4 qua hai đường chéo (13), (24) và hai đường trung trực của hai cặp cạnh đối tương ứng. Ta có     1 2 3 4 1 2 3 4  ,δ =  id =  2 3 4 1 1 2 3 4     1 2 3 4 1 2 3 4  , δ3 =   δ2 =  3 4 1 2 4 1 2 3     1 2 3 4 1 2 3 4  , µ24 =   µ13 =  1 4 3 2 3 2 1 4     1 2 3 4 1 2 3 4  , ν4 =  . ν3 =  2 1 4 3 4 3 2 1 Bổ đề 1.2.4. Giả sử p ∈ Sn . Khi đó có số dương k nhỏ nhất để pk = id . Với bất kỳ số nguyên dương m, pm = id khi và chỉ khi m:̇k. Chứng minh: Việc tồn tại số nguyên dương k để pk = id được suy ra từ Hệ quả 1.1.14. 10 Nếu m = sk thì pm = psk = (pk )s = id . Ngược lại, nếu m 6 :̇k thì có biểu diễn m = sk + r với 0 < r < k. Khi đó pm = (pk )s pr = pr 6= id . Ví dụ 1.2.5. Xét p = (123456) ∈ Sn . Khi đó p = p1 = (123456) p2 = (123456)(123456) = (135)(246) p3 = (123456)(135)(246) = (14)(25)(36) p4 = (123456)(14)(25)(36) = (153)(264) p5 = (123456)(153)(264) = (165432) p6 = (123456)(165432) = (1)(2)(3)(4)(5)(6) = id pr+6n = pr với mọi số nguyên không âm n, r. 1.2.2 Chu trình của hoán vị Xét nhóm các phép hoán vị Sn của tập T = {1, 2, . . . , n}. Giả sử t ∈ T và phép hoán vị p ∈ Sn . Bổ đề 1.2.6. Giả sử dãy các phần tử t = t1 , t2 , . . . ∈ T được xác định như sau: t1 = t và ti+1 = p(ti ) với i > 1. Nếu k là số tự nhiên nhỏ nhất để tk+1 ∈ {t1 , t2 , . . . , tk } thì tk+1 = p(tk ) = t1 . Chứng minh: Nếu p(tk ) = xi với k > i > 1 thì p(tk ) = xi = p(ti−1 ). Vì p là đơn ánh nên tk = ti−1 , mâu thuẫn với tính nhỏ nhất của k. Bởi vậy tk+1 = p(tk ) = t1 . Vì tk+2 = p(tk+1 ) = p(t1 ) nên tk+2 = t2 , Tương tự, tk+3 = t3 , v.v.... Từ đây suy ra dãy t1 , t2 , . . . tuần hoàn với chu kỳ k. Các số thuộc dãy chính là t1 , t2 , . . . , tk . Định nghĩa 1.2.7. Giả sử t ∈ T = {1, 2, . . . , n} và phép hoán vị p ∈ Sn . Giả sử dãy các phần tử t = t1 , t2 , . . . ∈ T được xác định như sau: t1 = t và ti+1 = p(ti ) với i > 1. Nếu k là số tự nhiên nhỏ nhất để tk+1 = t1 thì Cp (t) = (t1 t2 . . . tk ) được gọi là một k-chu trình của hoán vị p, (cycle of permutation), chứa t. k được gọi là độ dài của chu trình Cp (t) hoặc ta cũng có thể gọi Cp (t) là k-chu trình của 11 p. Hai chu trình Cp (t) và Cq (t0 ) được gọi là tương đương nếu chúng có cùng độ dài và chứa cùng các phần tử và theo cùng một trật tự, có nghĩa: Nếu p(r) = s thì q(r) = s và ngược lại. Định nghĩa 1.2.8. Hai chu trình được gọi là rời nhau nếu chúng không có phần tử chung. Kết quả dưới đây là hiển nhiên. Bổ đề 1.2.9. Mỗi k-chu trình Cp (t) có cấp k.  1 2 3 Ví dụ 1.2.10. Với phép hoán vị p =  1 5 3    2 4 5 1  và hai 1-chu trình  trình hoán vị  5 2 4 1 (1)(3)(254) hoặc đơn giản p = (254). 4 5   thuộc S5 ta có 3-chu 2 4   ,  3 3   . Ta biểu diễn p = Giả thiết p ∈ Sn và t ∈ T = {1, 2, . . . , n}. Giả sử x ∈ Cp (t) = (t1 t2 . . . tk ). Khi đó tồn tại i 6 k để x = ti . Ta sẽ có Cp (x) = (ti ti+1 . . . tk t1 . . . ti−1 ). Hai chu trình Cp (t) và Cp (x) tương đương. Bổ đề 1.2.11. Giả sử p, q ∈ Sn . Nếu t, t0 ∈ T = {1, . . . , n} thì ta có (1) Hoặc Cp (t) và Cp (t0 ) rời nhau hoặc chúng tương đương. (2) Hoặc Cp (t) và Cq (t) trùng nhau hoặc chúng không tương đương. Chứng minh: (1) Nếu Cp (t) và Cp (t0 ) rời nhau thì ta đã có được điều cần chứng minh. Giả sử hai lớp này không ròi nhau. Khi đó có x ∈ Cp (t) ∩ Cp (t0 ) và suy ra cả hai chu trình Cp (t), Cp (t0 ) cùng tương đương với Cp (x). Do vậy, chúng tương đương với nhau. (2) được chứng minh tương tự trên. Bổ đề 1.2.12. Hai chu trình rời nhau thì giao hoán. 12 Chứng minh: Xét hai chu trình rời nhau Cp (t) = {t1 , t2 , . . . , tk } = U và Cp (x) = {x1 , x2 , . . . , xh } = V. Ký hiệu f = p|U , g = p|V . Ta phải chỉ ra f g = gf hay (f g)(y) = (gf )(y) với mọi y ∈ T. Do tính rời nhau của hai chu trình nên ta có thể viết tập T như sau: T = {t1 , t2 , . . . , tk , x1 , x2 , . . . , xh , y1 , y2 , . . . , yr }. Ta có (f g)(ti ) = f (g(ti )) = f (ti ) = ti+1 = g(ti+1 ) = g(f (ti )) = (gf )(ti ). Ta cũng có (f g)(xi ) = f (g(xi )) = f (xi+1 ) = xi+1 = g(xi ) = g(f (xi )) = (gf )(xi ). Hiển nhiên (f g)(yi ) = f (g(yi )) = f (yi ) = yi = g(yi ) = g(f (yi )) = (gf )(yi ). Tóm lại (f g)(y) = (gf )(y) với mọi y ∈ T. Những k-chu trình tương   đương được coi là một, chẳng hạn: Phép hoán vị p = 1 2 3 4 5 6 7   = (16)(24)(357). Ta coi 3-chu trình (357) và (573) là 6 4 5 2 7 1 3 một. Khi đó ta có kết quả sau. Định lý 1.2.13. Mỗi phép hoán vị p ∈ Sn đều có thể phân tích thành tích các chu trình rời nhau. Sự phân tích ấy là duy nhất sai khác các 1-chu trình. Kiểu chu trình của p là dãy độ dài các chu trình trong biểu diễn tích. Chứng minh: Trước tiên ta chứng minh sự tồn tại của phân tích. Giả sử t1 = 1. Định nghĩa theo kiểu truy hồi ti+1 = p(ti ). Gọi k là số tự nhiên dương nhỏ nhất để p(tk+1 ) = t1 . Số k luôn tồn tại vì tập {1, 2, . . . , n} là hữu hạn. Ký hiệu δ = p|{t1 ,...,tk } và q = pδ −1 . Ánh xạ này cố định các phần tử thuộc tập {t1 , . . . , tk }. Bằng quy nạp, ta có thể giả thiết δ đã biểu diễn thành tích r−1 chu trình q = δ1 δ2 . . . δk−1 . Vậy p = qδ = δ1 δ2 . . . δk−1 δk với δk = δ. Ký hiệu Cp (x) = δ1 , . . . , Cp (z) = δk . Ta có biểu diễn p = Cp (x) Cp (y) . . . Cp (z). Tiếp theo, ta chứng minh tính duy nhất của biểu diễn. Giả sử p có biểu diễn thành tích các chu trình rời nhau thứ hai p = µ1 µ2 . . . µs . Giả sử µ1 (i) = j. Khi đó có l để δl (i) 6= i. Vì tính rời nhau nên δl (i) = j. Ta xét µ1 (j). Vì lý do như trên ta có δl (j) = µ1 (j). Cứ tiếp tục như vậy, ta suy ra µ1 = δl . Do tính giao hoán giữa các 13 chu trình rời nhau theo Bổ đề 1.2.12, ta loại bỏ µ1 = δl ở hai bên ta có −1 −1 µ2 . . . µs = µ−1 1 p = δl p = δl δ1 δ2 . . . δk−1 δk và bằng quy nạp ta suy ra các chu trình tương thích bằng nhau. Ta có điều cần chứng minh. Hệ quả 1.2.14. Cấp của một phép hoán vị với biểu diễn thành tích các chu trình rời nhau bằng bội chung nhỏ nhất của độ dài các chu trình. Đặc biệt, nếu phép hoán vị p có cấp k thì p−1 = pk−1 . Chứng minh: Kết quả suy ra từ Bổ đề 1.2.9 và Định lý 1.2.12. Ví dụ 1.2.15. Xét p = (123)(45). Khi đó p có cấp 6 = 3.2. Kiểm tra lại: p = p1 = (123)(45) p2 = (123)(45)(123)(45) = (132) p3 = (123)(45)(132) = (45) p4 = (123)(45)(45) = (123) p5 = (123)(45)(123) = (132)(45) p6 = (123)(45)(132)(45) = (1)(2)(3)(4)(5) = id . Ví dụ 1.2.16. Với hai phép hoán vị   1 2 3 4 5 6 7  p= 6 4 5 2 7 1 3  và q= 1 2 3 4 5 6 7 2 4 5 1 7 6 1   thuộc S7 ta có biểu diễn p = (16)(24)(357) và q = (124)(357)(6) ∈ S7 . Khi đó Cq (3) = (357) tương đương Cp (5) = (573) và Cp (7) = (735); nhưng nó không tương đương với Cq (4) = (412). Cấp của phép hoán vị p bằng bcnn(2, 2, 3) = 6 và cấp của của phép hoán vị q bằng bcnn(3, 3, 1) = 3. Mệnh đề 1.2.17. Giả sử phép hoán vị p ∈ Sn . Nhóm xiclic sinh ra bởi p là < p >= {pi |1 6 i 6 k}, ở đó k bằng cấp của p. Khi đó < p > là một nhóm con của Sn . 14 Chứng minh: Do < p > chứa p nên < p >6= ∅. Giả sử f, g ∈< p > . Khi đó có hai số nguyên dương i, j ∈ {1, . . . , k} để f = pi , g = pj và ta nhận được f g = pi+j . Với i + j ≡ s(mod k) ta có f g = ps ∈< p >, trong đó s ∈ {1, . . . , k}. Từ kết quả này suy ra < p > là một nhóm con của Sn . Định nghĩa 1.2.18. Giả sử T = {1, . . . , n} và phép hoán vị p ∈ Sn . Nếu Cp (x), Cp (y), . . ., Cp (z) là những chu trình không tương đương của p thì phân tích nhân tử chu trình rời nhau là biểu diễn dạng p = Cp (x)Cp (y) . . . Cp (z). Đặc biệt, trong nhóm Sn ta quan tâm đến hai nhóm con Qn , Dn . Phép hoán vị ν = (123 . . . n) và nhóm con xiclic Qn cấp n do ν sinh ra: Qn = {id, ν, ν 2 , ν 3 , . . . , ν n−1 } id = (1)(2)(3) . . . (n), ν = (123 . . . n) = (234 . . . n1), ν 2 = (345 . . . 12) ν 3 = (45 . . . n123), . . . , ν n−1 = (n123 . . . n − 1). Về mặt hình học, đây là nhóm các phép quay ngược chiều quay kim đồng hồ quanh 3600 của một n-giác đều. tâm một góc n Nhóm con Dn gồm các phép quay như trên và các phép đối xứng trục của một n-giác đều. Nhóm con Dn có cấp 2n. Ví dụ nhóm con D5 : D5 = {id, (12345), (13524), 14253), (15432), ((25)(1)(34)} ∪ {(13)(2)(45), (15)(3)(24), ((12)(4)((35), ((14)(5)(23)}. Định nghĩa 1.2.19. Giả sử G và H là hai nhóm con của nhóm Sn . Nếu H ⊂ G thì H cũng được gọi là một nhóm con của G và tập con pH = {ph|h ∈ H} của G được gọi là một lớp trái của H. Mệnh đề 1.2.20. Giả sử phép hoán vị p ∈ G ⊂ Sn . Nếu p(i) = j với i, j ∈ T = {1, 2, . . . , n} thì nhóm xiclic sinh ra bởi p là < p >= {pi |1 6 i 6 k}, ở đó k bằng cấp của p. Khi đó < p > là một nhóm con của Sn . 15 Chứng minh: Do < p > chứa p nên < p >6= ∅. Giả sử f, g ∈< p > . Khi đó có hai số nguyên dương i, j ∈ {1, . . . , k} để f = pi , g = pj và ta nhận được f g = pi+j . Với i + j ≡ s(mod k) ta có f g = ps ∈< p >, trong đó s ∈ {1, . . . , k}. Từ kết quả này suy ra < p > là một nhóm con của Sn . 1.3 Bổ đề Burnside Trong mục này, chúng ta chứng minh một kết quả quan trọng làm cơ sở để xây dựng Lý thuyết Polya. Kết quả này sẽ cho ta công thức xác định số các quỹ đạo của một nhóm tác động lên một tập. Trước tiên ta định nghĩa nhóm tác động lên một tập. 1.3.1 Tác động nhóm lên một tập Định nghĩa 1.3.1. Cho nhóm G với phần tử đơn vị 1 và tập hữu hạn Ω. Ta nói rằng, nhóm G tác động lên tập Ω nếu với mỗi a ∈ Ω và g ∈ G có phần tử xác định g(a) ∈ Ω thỏa mãn hai điều kiện: (1) (hg)(α) = h(g(α)) với mọi g, h ∈ G và mọi α ∈ Ω. (2) 1.α = α với mọi α ∈ Ω. Với g, h ∈ G và mọi α ∈ Ω, ta nói rằng, phần tử g chuyển phần tử α đến phần tử g(α). Bổ đề 1.3.2. Tương ứng φ : α 7→ g(α) trên tập Ω xác định một phép hoán vị của tập Ω. Chứng minh: Với a, b ∈ Ω, nếu φ(a) = φ(b) thì g(a) = g(b). Vì g −1 ∈ G nên g −1 (g(a)) = g −1 (g(b)) hay (g −1 g)(a) = (g −1 g)(b). Do vậy 1(a) = 1(b) hay a = b theo định nghĩa và suy ra φ là một đơn ánh. Vì Ω là một tập hữu hạn và φ là một đơn ánh từ tập Ω vào tập Ω nên φ là một toàn ánh. Do vậy, φ là một song ánh. Từ đó suy ra rằng, tương ứng φ : α 7→ g(α) trên tập Ω xác định một phép hoán vị của tập Ω. 16 Bây giờ Ký hiệu một Orbit, (quỹ đạo), của phần tử a ∈ Ω dưới tác động của nhóm G qua OrbitG hoặc Orbit là tập OrbitG (a) = {g(a)|g ∈ G}. Bổ đề 1.3.3. Xét hai quỹ đạo Orbit(a) và Orbit(b). Nếu a ∈ Orbit(b) thì b ∈ Orbit(a). Chứng minh: Vì a ∈ Orbit(b) nên tồn tại p ∈ G để p(b) = a. Vậy p−1 ∈ G để p−1 (a) = b. Do vậy b ∈ Orbit(a). Bổ đề 1.3.4. Dưới tác động của mỗi nhóm con G ⊂ Sn , hai quỹ đạo Orbit(a) và Orbit(b) hoặc là rời nhau hoặc là bằng nhau. Chứng minh: Trường hợp Orbit(a) = Orbit(b), ta đã có điều cần chứng minh. Xét trường hợp Orbit(a) 6= Orbit(b). Giả sử có c ∈ Orbit(a) ∩ Orbit(b). Ta thấy ngay sự tồn tại của p, q ∈ G để p(b) = c và q(a) = c. Vậy a = q −1 (c) = q −1 (p(b)). Từ đây dễ dàng suy ra Orbit(a) = Orbit(b), mâu thuẫn. Ký hiệu Stabilizer, (Ổn định hóa), Ga của a ∈ Ω và Cố định hóa FixΩ (g) của g ∈ G là các tập Ga = {g ∈ G|g(a) = a} và FixΩ (g) = {a ∈ Ω|g(a) = a}. Hiển nhiên, Orbit(a) và FixΩ (a) là những tập con của Ω; Còn Ga là một nhóm con của nhóm G qua kết quả sau đây. Bổ đề 1.3.5. Tập Ga là một nhóm con của nhóm G. Chứng minh: Ta thấy ngay 1 ∈ Ga theo định nghĩa tác động nhóm. Với g, h ∈ Ga ta luôn có (gh)(a) = g(h(a)) = g(a) = a nên gh ∈ Ga . Vì g −1 (a) = g −1 (g(a)) = (g −1 g)(a) = a nên g −1 ∈ Ga . Do vậy, Ga là một nhóm con của nhóm G. Tiếp theo, chúng ta sẽ thấy mối liên hệ giữa lực lượng của Orbit(a) và cấp của nhóm con Ga và của nhóm G.
- Xem thêm -