Tài liệu Luận văn sư phạm ứng dụng của lý thuyết pólya trong bài toán đếm

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN ĐẶNG THỊ LOAN ỨNG DỤNG LÝ THUYẾT PÓLYA TRONG BÀI TOÁN ĐẾM KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán ứng dụng Hà Nội – Năm 2019 TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN ĐẶNG THỊ LOAN ỨNG DỤNG LÝ THUYẾT PÓLYA TRONG BÀI TOÁN ĐẾM KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán ứng dụng Người hướng dẫn khoa học TS. TRẦN VĨNH ĐỨC Hà Nội – Năm 2019 LỜI CẢM ƠN Sau thời gian học tập nghiên cứu tại trường Đại Học Sư Phạm Hà Nội 2, em xin bày tỏ lòng biết ơn chân thành tới các thầy cô trong trường và quý thầy cô trong khoa Toán, đã tận tình giúp đỡ chỉ bảo trong suốt thời gian em theo học tại khoa và trong thời gian làm khóa luận. Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới TS. Trần Vĩnh Đức – Giảng viên Trường Đại Học Bách Khoa Hà Nội, người trực tiếp hướng dẫn em, luôn tận tâm chỉ bảo và định hướng cho em trong suốt quá trình làm khóa luận để em có thể hoàn thành khóa luận tốt nghiệp. Mặc dù đã có nhiều cố gắng, nhưng vì thời gian và kinh nghiệm bản thân còn nhiều hạn chế nên khóa luận khó tránh khỏi những thiếu sót, em rất mong nhận được sự đóng góp quý báu từ các thầy cô giáo, các bạn sinh viên và bạn đọc. Cuối cùng, em xin chân thành cảm ơn tất cả mọi người đã giúp đỡ và tạo điều kiện thuận lợi cho em hoàn thành khóa luận tốt nghiệp. Em xin chân thành cảm ơn. Hà Nội, tháng 05 năm 2019 Sinh viên Đặng Thị Loan LỜI CAM ĐOAN Khóa luận này là kết quả nghiên cứu của bản thân em dưới sự hướng dẫn và chỉ bảo của thầy giáo TS. Trần Vĩnh Đức. Trong khi thực hiện đề tài nghiên cứu này em đã tham khảo một số tài liệu được ghi trong phần tài liệu tham khảo. Em xin khẳng định kết quả của đề tài “Ứng dụng của lý thuyết Pólya trong bài toán đếm” là kết quả của việc nghiên cứu, học tập và nỗ lực của bản thân. Nếu sai em xin hoàn toàn chịu trách nhiệm. Hà Nội, tháng 05 năm 2019 Sinh Viên Đặng Thị Loan Mục lục Lời mở đầu 1 1 CÁC BÀI TOÁN TỔ HỢP CƠ BẢN 2 1.1 1.2 1.3 Khái quát về tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Cấu hình tổ hợp và cấu trúc tổ hợp . . . . . . . . . . . . . . . . 2 1.1.2 Các bài toán tổng quát . . . . . . . . . . . . . . . . . . . . . . . 3 Các quy tắc đếm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.1 Quy tắc tương ứng một – một . . . . . . . . . . . . . . . . . . . 4 1.2.2 Nguyên lý cộng . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.3 Nguyên lý nhân . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.4 Nguyên lý bao hàm - loại trừ . . . . . . . . . . . . . . . . . . . 5 1.2.5 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . . 6 Một số bài toán đếm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3.1 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3.2 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.3 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2 BỔ ĐỀ BURNSIDE 12 2.1 Các định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 Bổ đề Burnside . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3 ĐA THỨC CHỈ SỐ CHU TRÌNH 19 3.1 Định nghĩa đa thức chỉ số chu trình . . . . . . . . . . . . . . . . . . . . 19 3.2 Định lý Pólya . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3 Đa thức chỉ số chu trình cho các nhóm Cn , Dn và Sn . . . . . . . . . . 22 Nhóm xyclic Cn . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3.1 i Khóa luận tốt nghiệp Đại học Đặng Thị Loan 3.3.2 Nhóm nhị diện Dn . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3.3 Nhóm đối xứng Sn . . . . . . . . . . . . . . . . . . . . . . . . . 24 4 ĐỊNH LÝ ĐẾM PÓLYA 26 4.1 Bổ đề trọng lượng Burnside . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2 Định lý đếm Pólya . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.3 Các ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 KẾT LUẬN 33 TÀI LIỆU THAM KHẢO 34 ii Khóa luận tốt nghiệp Đại học Đặng Thị Loan LỜI MỞ ĐẦU 1. Lí do chọn đề tài Trong lý thuyết tổ hợp, các phép đếm chiếm một phần vô cùng quan trọng và có ứng dụng rất đa dạng. Phương pháp đếm thường dựa vào một số quy tắc, nguyên lý đếm và một số kết quả đếm cho các cấu hình tổ hợp đơn giản. Tuy nhiên, việc xác định chính xác số các cấu hình tổ hợp trong một số bài toán gặp nhiều khó khăn. Mặt khác, lý thuyết Pólya cung cấp cho ta một công cụ mạnh để đếm các đồ vật mà có sự đối xứng nào đó. Vì lí lẽ đó, em chọn đề tài nghiên cứu: “Ứng dụng lý thuyết Pólya trong bài toán đếm” để trình bày lại một số kết quả về lý thuyết Pólya và ứng dụng của nó. 2. Mục đích nghiên cứu Nghiên cứu về lý thuyết Pólya. 3. Phương pháp nghiên cứu Tham khảo và cập nhật những nghiên cứu của tác giả trong nước cũng như ngoài nước liên quan đến đề tài. 4. Cấu trúc khóa luận Nội dung khóa luận gồm bốn chương: Chương 1 "Các bài toán tổ hợp cơ bản" trình bày khái quát về tổ hợp, các quy tắc đếm và một số bài toán toán đếm cơ bản. Chương 2 "Bổ đề Burnside" trình bày một số định nghĩa và bổ đề Burnside. Chương 3 "Đa thức chỉ số chu trình" trình bày định nghĩa của đa thức chỉ số chu trình, định lý Pólya và áp dụng tìm đa thức chỉ số chu trình của một số nhóm quen thuộc. Chương 4 "Định lý đếm Pólya" trình bày về bổ đề trọng lượng Burnside, định lý đếm Pólya và giới thiệu một số bài toán ứng dụng của định lý đếm Pólya. Khóa luận được trình bày trên cơ sở các tài liệu tham khảo được liệt kê trong phần tài liệu tham khảo. Em rất biết ơn các tác giả của tất cả các tài liệu được trích dẫn. 1 Chương 1 CÁC BÀI TOÁN TỔ HỢP CƠ BẢN Chương này trình bày một số kiến thức cơ bản về tổ hợp, các quy tắc đếm cơ bản và một số bài toán đếm cơ bản . Nội dung của chương này được tham khảo trong các tài liệu [1], [2]. 1.1 Khái quát về tổ hợp 1.1.1 Cấu hình tổ hợp và cấu trúc tổ hợp Tư duy về tổ hợp ra đời từ rất sớm. Ở Trung quốc người ta đã biết đến những hình vuông thần bí. Nhà triết học cổ đại Hy Lạp Kxenokrat sống ở thế kỉ IV trước công nguyên đã tính số các từ khác nhau lập từ một bảng chữ cái cho trước. Nhà toán học Pithagore và các học trò của ông đã phát hiện ra tính chất kì lạ của các số trong đó có định lý Pithagore. Mặc dù lý thuyết tổ hợp được coi là một lĩnh vực của toán học rời rạc vào thế kỉ 17 nhưng tổ hợp vẫn là lĩnh vực mờ nhạt và ít được chú ý trong khoảng hai thế kỉ. Cho đến khi máy tính xuất hiện và phát triển thì tổ hợp mới phát triển mạnh mẽ và trở thành một lĩnh vực của toán ứng dụng. Vì tổ hợp có liên quan đến nhiều vấn đề trong nhiều lĩnh vực của đời sống nên khó có thể định nghĩa nó một cách hình thức chặt chẽ. Nói chung lý thuyết tổ hợp là một lĩnh vực toán học nghiên cứu các cấu hình tổ hợp và các cấu trúc tổ hợp mà ta có thể định nghĩa chúng một cách khái quát như sau: 2 Khóa luận tốt nghiệp Đại học Đặng Thị Loan Định nghĩa 1.1 (Cấu hình tổ hợp). Giả sử X là một tập hữu hạn, S là sơ đồ sắp xếp các điều kiện R1 , R2 , ..., Rk được biểu diễn dưới một dạng nào đấy. Một cách sắp xếp các phần tử của X vào sơ đồ S và thỏa mãn các điều kiện R1 , R2 , ..., Rk được gọi là một cấu hình tổ hợp trên X. Ví dụ 1.1. Cho tập X gồm các chữ số tự nhiên. Sơ đồ sắp xếp S là “một số có ba chữ số”. Các điều kiện R1 = “là số chẵn”, R2 = “lớn hơn 500”. Khi đó mỗi số tự nhiên từ tập X theo sơ đồ S thỏa mãn 2 điều kiện R1 , R2 , tức là một số tự nhiên chẵn có ba chữ số và lớn hơn 500 ( ví dụ như 503) là một cấu hình tổ hợp. Định nghĩa 1.2 (Cấu trúc tổ hợp). Giả sử V là một tập hữu hạn. Ta kí hiệu f (V ) là tập tất cả các cấu hình tổ hợp trên V. Khi đó bộ ba G = (V, E, f ) được gọi là một cấu trúc tổ hợp trên V nếu V và E là các tập rời nhau, f là một hàm đi từ E vào φ(V ) và V, E, f thỏa mãn một tiên đề xác định nào đó. Ví dụ 1.2. Giả sử V = {v1 , v2 , ..., vm }, E = {e1 , e2 , ..., en } với E ∩ V = ∅. Ta cũng giả sử S là sơ đồ sắp xếp "cặp (x1 , x2 )"và f là một hàm từ E vào φ(V ). Khi đó, nếu với mọi e ∈ E, f (e) là một cấu hình tổ hợp theo S trên các bản rời nhau A1 và A2 của V thỏa mãn x1 ∈ A, x2 ∈ A, thì cấu trúc tổ hợp (V, E, f ) được gọi là một đa đồ thị có hướng với tập đỉnh là V , tập cung là E. 1.1.2 Các bài toán tổng quát Bài toán đếm. Là bài toán đặt ra với câu hỏi có bao nhiêu cấu hình tổ hợp thuộc dạng đã cho. Để giải quyết bài toán này chúng ta thường dựa vào một số quy tắc như quy tắc cộng, quy tắc nhân, và một số phương pháp đếm nâng cao,... Bài toán đếm thường có trong các bài toán tính xác suất hay để đánh giá độ phức tạp. Ví dụ 1.3. Có bao nhiêu số tự nhiên chẵn có ba chữ số và lớn hơn 500. Ví dụ 1.4. Rút 13 quân bài từ bộ bài tây 52 quân. Có bao nhiêu cách rút 13 quân bài để trong 13 quân đó có “tứ quý”. Bài toán liệt kê. Đây là bài toán cần chỉ rõ những cấu hình tổ hợp thỏa mãn bài toán là những cấu hình tổ hợp nào và cần đưa ra danh sách tất cả các cấu hình tổ hợp có thể có. Vì thế bài toán liệt kê cần xác định một thuật toán để có thể xây dựng được tất cả các cấu hình tổ hợp thỏa mãn bài toán. Có nhiều cách để liệt kê các cấu hình tổ hợp nhưng phải đảm bảo hai nguyên tắc là không được lặp lại và không được bỏ 3 Khóa luận tốt nghiệp Đại học Đặng Thị Loan sót một cấu hình tổ hợp. Bài toán liệt kê có ý nghĩa trong thực tế, hình thành những định hướng để giải quyết các vấn đề. Ví dụ 1.5. Liệt kê các hoán vị của {1, 2, 3, .., n} theo thứ tự từ điển. Bài toán tồn tại. Là bài toán đặt ra với câu hỏi có hay không các cấu hình tổ hợp thỏa mãn bài toán. Trong nhiều bài toán thì sự tồn tại của các cấu hình tổ hợp là hiển nhiên và ta chỉ cần liệt kê hoặc đếm các cấu hình tổ hợp. Tuy nhiên trong nhiều bài toán tổ hợp thì việc chỉ ra có hay không các cấu hình tổ hợp thỏa mãn bài toán cho trước là hết sức khó khăn bởi vì không chỉ ra được cấu hình tổ hợp nào nhưng cũng không khẳng định được là chúng không tồn tại. Bài toán tồn tại có nhiều ý nghĩa trong thực tế và nó còn định hướng xây dựng lý thuyết mới đối với một số bài toán (ví dụ như bài toán Fermat). Ví dụ 1.6. Các bài toán tổ hợp cổ điển nổi tiếng như bài toán 36 sĩ quan, bài toán 4 màu, hay hình lục giác thần bí, bài toán chọn 2n điểm trên lưới n × n điểm. Bài toán tối ưu tổ hợp. Là bài toán đặt ra với câu hỏi cấu hình tổ hợp nào là tốt nhất. Ngoài ra bài toán tối ưu tổ hợp có thể được viết dưới dạng tổng quát như sau: Tìm cực tiểu (hay cực đại) của phiếm hàm: f (x) → min(max) với điều kiện x ∈ D, với D là tập hữu hạn phần tử, hàm f (x) là hàm mục tiêu của bài toán, mỗi phần tử x ∈ D là một phương án còn tập D là tập các phương án của bài toán. Ví dụ 1.7. Một số bài toán tối ưu tổ hợp truyền thống như bài toán người du lịch, bài toán cái túi, bài toán phân công,.. 1.2 Các quy tắc đếm cơ bản 1.2.1 Quy tắc tương ứng một – một Cho hai tập hợp A, B hữu hạn. Nếu như giữa A và B có một quy tắc tương ứng 1–1 (tức là có thể ghép mỗi phần tử của A với đúng một phần tử của B mà mọi phần tử của A và B đều được ghép cặp) thì |A| = |B|. 1.2.2 Nguyên lý cộng Nếu A, B là các tập hữu hạn thỏa mãn A ∩ B = ∅ thì |A ∪ B| = |A| + |B|. 4 Khóa luận tốt nghiệp Đại học Đặng Thị Loan Nguyên lý cộng mở rộng: Nếu A1 , A2 , . . . , An là các tập hữu hạn thỏa mãn Ai ∩ Aj = ∅, ∀i 6= j thì |A1 ∪ A2 ∪ ... ∪ An | = |A1 | + |A2 | + · · · + |An |. Đặc biệt nếu   A ⊂ X thì |A| = |X| − A. Ví dụ 1.8. Giả sử bạn muốn mua 1 đôi giày cỡ 36 hoặc 37. Cỡ giày 36 có 5 màu khác nhau, cỡ giày 37 có 4 màu khác nhau. Hỏi bạn có bao nhiêu sự lựa chọn? Giải.Theo quy tắc cộng có 9 sự lựa chọn. 1.2.3 Nguyên lý nhân Nếu A1 , A2 , .., An là các tập hữu hạn bất kì và A1 × A2 × ... × An là tích Đề các của tập đó thì |A1 × A2 × · · · × An | = |A1 | × |A2 | × · · · × |An |. Ví dụ 1.9. Có 3 kiểu áo và 4 kiểu quần. Hỏi có bao nhiêu cách kết hợp quần áo. Giải.Theo quy tắc nhân có 3.4 = 12 cách kết hợp quần áo. 1.2.4 Nguyên lý bao hàm - loại trừ Cho A, B là các tập hữu hạn. Khi đó: |A ∪ B| = |A| + |B| − |A ∩ B|. Tổng quát: Cho A1 , A2 , ..., An là các tập hữu hạn. Khi đó n n n P P P S |Ai | − |Ai Aj | + |Ai Aj Ak | − · · · + (−1)n−1 |A1 A2 ...An |. | ni=1 Ai | = i=1 1≤i≤j≤n 1≤i n. n−1 k Số tổ hợp có lặp chập k của n là Cnk = Cn+k−1 = Cn+k−1 . Tổ hợp có lặp lại khi một phần tử có thể xuất hiện nhiều lần và thứ tự của các phần tử không cần để ý. Ví dụ 1.20. Xếp 10 viên bi giống nhau vào 4 chiếc hộp. Hãy tìm số cách xếp. Giải. Mỗi một cách xếp 10 viên bi vào 4 chiếc hộp là một tổ hợp có lặp chập 10 của 10 10 . = C13 4 phần tử. Suy ra có C10+4−1 1.3.3 Hoán vị Hoán vị không lặp Định nghĩa 1.9. Cho tập A hữu hạn với |A| = n. Một chỉnh hợp không lặp chập n của n phần tử của A được gọi là một hoán vị không lặp của n phần tử của A. Hoán vị không lặp thường được gọi đơn giản là hoán vị. Kí hiệu số các hoán vị của n phần tử của A là Pn . Khi đó, Pn = Ann = n! n! = = n!. (n − n)! 0! Ví dụ 1.21. Có bao nhiêu số có 4 chữ số khác nhau được lập từ các chữ số 3,4,6,8. Giải. Mỗi 1 số có 4 chữ số được lập từ các chữ số 3,4,6,8 là một hoán vị của 4 phần tử nên sẽ có 4! = 24 số tự nhiên có 4 chữ số khác nhau được lập từ các chữ số 3,4,6,8. Hoán vị có lặp Định nghĩa 1.10. Cho tập hợp An = {a1 , a2 , ..., an } hữu hạn và n số nguyên dương không âm m1 , m2 , ..., mn sao cho tồn tại ít nhất một số mi 6= 0. Giả sử m1 + m2 + · · · + mn = m, A1 , A2 , ..., An là các bản sao rời nhau của A, S là sơ đồ sắp xếp "bộ thứ tự gồm n thành phần (x1 , x2 , ..., xn )", R1 là điều kiện xi ∈ Ai , i = 1, n, 10 Khóa luận tốt nghiệp Đại học Đặng Thị Loan R2 là điều kiện ai xuất hiện ở đúng mi thành phần với i = 1, n. Khi đó cấu hình tổ hợp trên A1 , A2 , ..., Am theo S thỏa mãn điều kiện R1 , R2 được gọi là một hoán vị có lặp của các phần tử a1 , a2 , ..., an của tập A với tham số lặp là m1 , m2 , ..., mn . Theo định nghĩa của chỉnh hợp có lặp và hoán vị có lặp, ta thấy rằng một hoán vị có lặp của các phần tử a1 , a2 , ..., an của tập A với tham số lặp là m1 , m2 , ..., mn chính là một chỉnh hợp có lặp chập m của n các phần tử của A thỏa mãn điều kiện R2 . Ta cũng thấy rằng một hoán vị có lặp các phần tử a1 , a2 , ..., an của tập A với tham số lặp là m1 = m2 = ... = mn = 1 chính là một hoán vị không lặp của n phần tử của A. Kí hiệu Pnk là số hoán vị có lặp các phần tử a1 , a2 , ..., an của tập A với tham số lặp là m1 , m2 , ..., mn . Khi đó để xác định số hoán vị có lặp ta coi mỗi một hoán vị là một cách thực hiện hành động H bao gồm n giai đoạn kế tiếp nhau H1 , H2 , ..., Hn để sắp xếp các vị trí cho m phần tử a1 , a2 , ..., an như sau: m1 Giai đoạn H1 . Chọn vị trí cho m1 phần tử a1 . Bởi vì tất cả có m vị trí nên có Cm cách chọn vị trí cho m1 phần tử a1 . Giai đoạn H2 . Chọn vị trí cho m2 phần tử a2 . Do đã chọn ra m1 vị trí để xếp các m2 phần tử a1 nên sẽ còn lại m − m1 vị trí. Khi đó có Cm−m cách chọn vị trí cho m2 phần 1 tử a2 . ... Giai đoạn Hk . Chọn vị trí cho mk phần tử ak . Do còn lại m − m1 − m2 − ... − mk−1 mk vị trí sau khi thực hiện các giai đoạn trên nên ta có Cm−m cách chọn vị 1 −m2 −...−mk−1 trí cho mk phần tử ak . ... mn Giai đoạn Hn . Chọn vị trí cho mn phần tử an . Tương tự ta cũng có Cm−m 1 −m2 −...−mn−1 cách chọn vị trí cho mn phần tử an . Khi đó theo quy tắc nhân tất cả số hoán vị có lặp các phần tử a1 , a2 , ..., an của tập A với tham số lặp là m1 , m2 , ..., mn là m! . m1 !m2 !...mn ! Ví dụ 1.22. Có thể nhận được bao nhiêu xâu khác nhau bằng cách sắp xếp lại các m2 mn m1 Cm .Cm−m ...Cm−m = 1 1 −...−mn−1 chữ cái của từ SUCCESS. Giải. Ta thấy trong từ SUCCESS có 1 kí tự S, 1 kí tự U, 2 kí tự C, 1 kí tự E và 2 kí tự S. Vì vậy mỗi một cách sắp xếp lại các kí tự của từ SUCCESS là một hoán vị lặp các phần tử S, U, C, E, S với tham số lặp là 1, 1, 2, 1, 2. Do đó sẽ có C71 C61 C52 C31 C22 . 11 Chương 2 BỔ ĐỀ BURNSIDE 2.1 Các định nghĩa Định nghĩa 2.1. Một nhóm G là một tập hợp cùng với phép toán nhóm G×G→G (a, b) 7→ ab nếu thỏa mãn các điều kiện: (i) ∀a, b, c ∈ G thì (ab) c = a (bc) (tính chất kết hợp), (ii) ∃e ∈ G thỏa mãn ae = ea = a ∀a ∈ G (e là phần tử đơn vị), (iii) ∀a ∈ G, ∃b ∈ G sao cho ab = ba = e (phần tử nghịch đảo). G là một nhóm abel nếu G là một nhóm và ab = ba với mọi a, b ∈ G (tính chất giao hoán). Nếu phép toán nhóm viết theo lối nhân thì phần tử đơn vị kí hiệu là 1, nếu phép toán nhóm viết theo lối cộng thì phần tử đơn vị kí hiệu là 0. Phần tử nghịch đảo của a kí hiệu là a−1 (tương ứng −a là phần tử đối của a). Định nghĩa 2.2. Nhóm con của G là một tập con H thỏa mãn H ⊆ G, e ∈ H và với mỗi a, b ∈ H thì a−1 ∈ H. Như vậy nếu a ∈ H thì an , a−n ∈ H ∀n = 1, 2, .... Nếu H = {an : n ∈ Z} với một phần tử a nào đó thì H được gọi là một nhóm xyclic sinh bởi a. Định nghĩa 2.3. Nếu nhóm G có hữu hạn phần tử thì ta nói G có hữu hạn phần tử. Cấp của G là số phần tử của nhóm đó và kí hiệu là |G|. Với mỗi g ∈ G, có một số 12 Khóa luận tốt nghiệp Đại học Đặng Thị Loan nguyên dương n > 0 sao cho g n = 1 thì số nguyên dương n nhỏ nhất đó được gọi là cấp của g và kí hiệu là ord(g). Ví dụ 2.1. Gọi Sn là tập các hoán vị trên X, nghĩa là, Sn là tập các song ánh σ : X → X với X = {1, 2, ..., n} , n ∈ N . Khi đó nhóm Sn là một nhóm hữu hạn và được gọi là nhóm đối xứng (hay nhóm các phép thế). Sn là một nhóm abel khi và chỉ khi n < 3, |Sn | = n!. Nếu thay tập {1, 2, ..., n} bởi tập X có n phần tử thì ta cũng được nhóm đối xứng trên X, kí hiệu SX . Xét nhóm đối xứng Sn và tập X = {1, 2, ..., n}. Với mỗi σ ∈ Sn , i ∈ X ta được σ(i) ∈ X. Ta thấy (σ1 ◦ σ2 ) (i) = σ1 (σ2 (i)). Khi đó ta nói rằng có một tác động của nhóm Sn lên tập X. Tổng quát hơn ta có định nghĩa: Định nghĩa 2.4 (Tác động nhóm). Cho G là một nhóm hữu hạn và X là một tập hữu hạn. Một tác động của nhóm G lên X là một ánh xạ ϕ:G×X →X (g, a) 7→ g (a) thỏa mãn các điều kiện (i) ∀g, h ∈ G, a ∈ X thì (gh) (a) = g (h (a)), (ii) e (a) = a với e là phần tử đơn vị của nhóm G. Khi đó ta nói G tác động lên X (bằng ϕ) và g ∈ G chuyển a ∈ X thành g(a) ∈ X. Nhận xét 2.1. Nếu G tác động lên X (bằng ϕ) và g ∈ G chuyển a ∈ X thành g(a) ∈ X thì với mỗi g ∈ G ánh xạ φg : a 7→ g (a) là một song ánh. Chứng minh. Thật vậy, do G là một nhóm nên ∃g −1 ∈ G để g.g −1 = e. Khi đó g (a1 ) = g (a2 ) ⇔ g −1 (g (a1 )) = g −1 (g (a2 ))

⇔ g −1 g (a1 ) = g −1 g (a2 ) ⇔ a1 = a2 Vậy ánh xạ φg : a 7→ g (a) là một đơn ánh. Mà X là tập hợp hữu hạn (theo giả thiết) nên φg : a 7→ g (a) là một toàn ánh. Vậy chứng tỏ ánh xạ φg : a 7→ g (a) là một song ánh. 13 Khóa luận tốt nghiệp Đại học Đặng Thị Loan Ví dụ 2.2. Xét trên hình vuông, ta giả sử có các đỉnh có tên là 1,2,3,4. Ta gán cho mỗi đỉnh này hoặc màu trắng (T) hoặc màu vàng (V). Mỗi cách gán màu T hoặc V cho mỗi đỉnh của hình vuông được gọi là một sơ đồ màu của hình vuông. Kí hiệu tất cả các sơ đồ màu của hình vuông là tập X. Giả sử G là tập tất cả các tự đẳng cấu của hình vuông thì khi đó G là một nhóm đối với phép nhân ánh xạ. Mỗi tự đẳng cấu của hình vuông cũng được gọi là một phép đối xứng của hình vuông đó. Người ta chứng minh được rằng nhóm G tất cả các phép đối xứng của hình vuông là nhóm nhị diện Dn bao gồm các phần tử sau: τ = (1, 2) (3, 4), στ = (1, 3), σ 2 τ = (1, 4) (2, 3), σ 3 τ = (2, 4). Các hoán vị σ và τ là σ = (1, 2, 3, 4), τ = (1, 2) (3, 4). Khi đó mỗi sơ đồ màu của hình vuông chính là một ánh xạ đi từ tập các đỉnh của hình vuông {1, 2, 3, 4} vào tập màu {T, V }. Bây giờ ta định nghĩa ánh xạ ϕ của G × X vào X như sau: ϕ:G×X →X (g, a) 7→ g (a) Với g (a) (i) = a (g −1 (i)) , i = 1, 2, 3, 4. Ta đi chứng minh ϕ là một tác động của G lên X. Thật vậy, với mọi i = 1, 2, 3, 4 thì
e (a) (i) = a e−1 (i) = a (e (i)) Do đó e (a) = a ∀a ∈ X. Tiếp tục, nếu có g, h ∈ G, thì
((gh)(a)) (i) = a (gh)−1 (i)
= a (h−1 g −1 )(i)
= a h−1 (g −1 (i))
= h(a) g −1 (i) = g (h(a)) (i) 14