Luận văn Thạc sĩ Toán học: Định lý đếm polya

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:49

Thêm vào BST

Báo xấu

37
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trên những cơ sở đó luận văn được chia thành ba chương với nội dung chính như sau: Chương 1 - Trình bày một số khái niệm cơ bản về nhóm, định lý Lagrange, tác động nhóm và công thức lớp. Chương 2 - Trình bày bổ đề Burnside, định lý Polya con và các ví dụ. Chương 3 - Là nội dung chính của luận văn, chương này trình bày định lý đếm Polya và các ví dụ. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Định lý đếm polya

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN NGỌC CHI ĐỊNH LÝ ĐẾM POLYA 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 NGUYỄN NGỌC CHI ĐỊNH LÝ ĐẾM POLYA 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 TS. ĐOÀN TRUNG CƯỜNG Thái Nguyên - 2015
i Mục lục Lời cam đoan iii Lời cảm ơn iv Mở đầu 1 1 Kiến thức chuẩn bị 3 1.1 Khái niệm và ví dụ về nhóm . . . . . . . . . . . . . . . . . 3 1.2 Định lý Lagrange . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Tác động nhóm và công thức lớp . . . . . . . . . . . . . . . 10 2 Bổ đề Burnside 13 2.1 Bổ đề Burnside . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Định lý Polya con (Polya’s Baby Theorem) . . . . . . . . . . 15 2.3 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Bài tập đề nghị . . . . . . . . . . . . . . . . . . . . . . . . 21 3 Định lý đếm Polya 23 3.1 Bổ đề Burnside với trọng . . . . . . . . . . . . . . . . . . . 23 3.2 Định lý đếm Polya (Polya’s Enumeration Theorem) . . . . . 25 3.3 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.4 Bài tập đề nghị . . . . . . . . . . . . . . . . . . . . . . . . 39
ii Kết luận 41 Tài liệu tham khảo 43
iii 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 20 tháng 11 năm 2015 Họ và tên Nguyễn Ngọc Chi
iv Lời cảm ơn Sau một năm nghiên cứu miệt mài luận văn thạc sỹ của tôi với chủ đề "Định lý đếm Polya" đã được hoàn thành tại trường Đại học Khoa học - Đại học Thái Nguyên. Những kết quả ban đầu mà luận văn thu được là nhờ sự hướng dẫn tận tình và nghiêm khắc của thầy TS. Đoàn Trung Cường. Tôi xin gửi lời cảm ơn sâu sắc đến thầy. Tôi xin chân thành cảm ơn tới các thầy, cô giáo trong khoa Toán - Tin, Phòng Đào tạo Khoa học và Quan hệ quốc tế, các bạn học viên lớp Cao học Toán K7D và các bạn đồng nghiệp đã tạo điều kiện thuận lợi, động viên tác giả trong quá trình học tập và nghiên cứu . Tác giả cũng xin bày tỏ lòng biết ơn sâu sắc tới gia đình và người thân luôn khuyến khích, động viên tác giả trong suốt quá trình học tập và làm luận văn. Mặc dù có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu sót và hạn chế. Tác giả mong nhận được những ý kiến đóng góp quý báu của các thầy cô và bạn đọc để luận văn được hoàn thiện hơn. Thái Nguyên, 2015 Nguyễn Ngọc Chi Học viên Cao học Toán K7D, Trường ĐH Khoa học - ĐH Thái Nguyên
1 Mở đầu Cấu trúc nhóm xuất hiện một cách tự nhiên trong Toán học và Toán học phổ thông như Giải tích, Đại số, Số học, Tổ hợp. Một ví dụ tiêu biểu trong Tổ hợp là ứng dụng lý thuyết nhóm vào bài toán tô mầu thông qua bổ đề Burnside. Mục đích chính của luận văn này là trình bày bài toán tô mầu, bổ đề Burnside, các định lý Polya và ứng dụng vào các bài tập cho học sinh phổ thông. Bổ đề Burnside là một kết quả cơ bản của lý thuyết nhóm khi vận dụng vào bài toán tô mầu với hệ quả là định lý Polya. Bài toán đặt ra là tô mầu r mảnh vải khác nhau bởi bộ n mầu. Nếu ta gọi G là một nhóm con của nhóm Sr là nhóm các phép hoán vị r mảnh vải thì hai cách tô mầu là như nhau nếu cách tô mầu này nhận được từ cách tô mầu kia bằng một phép hoán vị các mảnh vải trong G. Hỏi có bao nhiêu cách tô mầu khác nhau? Nội dung của luận văn chỉ ra được số cách tô mầu khác nhau chính là số quỹ đạo của tác động nhóm G vào tập các mảnh vải và để đếm số quỹ đạo này ta sử dụng bổ đề Burnside với hệ quả là định lý Polya. Trong thực tế với các bài toán tô mầu ta thường gặp những yêu cầu kỹ hơn, cụ thể hơn trong cách thức tô mầu. Cụ thể với bộ mầu M = {M1 , M2 , . . . , Mm } và bộ số nguyên t1 , t2 , . . . , tn ≥ 0 khi tô r mảnh vải bởi bộ m mầu ở bài toán trên kèm theo điều kiện mầu Mi xuất hiện đúng ti lần. Hỏi có bao nhiêu cách tô mầu khác nhau? Để giải bài toán này ta cần sử dụng đến khái niệm hàm sinh và đa thức chỉ số xích để đi đến một công cụ mạnh hơn bổ đề Burnside
2 đó chính là định lý đếm Polya. Trong luận văn này bài toán tô mầu sẽ xuất hiện ở việc tô các đỉnh của một đa giác đều, tô mầu vòng cổ, tô mầu các ô vuông của lưới vuông, hay tô mầu các hình đa diện đều như tứ diện đều, khối lập phương, bát diện đều. Đồng thời luận văn cũng đề cập đến việc ứng dụng của bài toán tô mầu vào đếm số đồng phân của các phân tử hợp chất hóa học. Đây là bài toán khó nhưng có nhiều ứng dụng trong việc tìm và đặt tên các hợp chất hóa học hữa cơ. Trên những cơ sở đó luận văn được chia thành ba chương với nội dung chính như sau: Chương 1: Trình bày một số khái niệm cơ bản về nhóm, định lý Lagrange, tác động nhóm và công thức lớp. Chương 2: Trình bày bổ đề Burnside, định lý Polya con và các ví dụ. Chương 3: Là nội dung chính của luận văn, chương này trình bày định lý đếm Polya và các ví dụ. Thái Nguyên, ngày 20 tháng 11 năm 2015 Nguyễn Ngọc Chi Email: ngocchigvt@gmail.com
3 Chương 1 Kiến thức chuẩn bị Mục đích của chương này là nhắc lại một số kiến thức về nhóm, nêu và chứng minh định lý Lagrange. Đồng thời cũng nêu định nghĩa tác động nhóm và chứng minh công thức lớp. Kiến thức này là cần thiết cho những áp dụng vào việc chứng minh các định lý ở chương sau. 1.1 Khái niệm và ví dụ về nhóm Định nghĩa 1.1.1. Một nhóm gồm một tập hợp G 6= ∅ và một phép toán G × G → G, (a, b) 7→ a ∗ b thỏa mãn các tiên đề: (G1 ) Tính chất kết hợp: (a ∗ b) ∗ c = a ∗ (b ∗ c), với mọi a, b, c ∈ G. (G2 ) Phần tử đơn vị: tồn tại e ∈ G sao cho e ∗ a = a ∗ e = a với mọi a ∈ G. Phần tử e như vậy được gọi là phần tử đơn vị của G. (G3 ) Phần tử nghịch đảo: với mọi a ∈ G, có một phần tử b ∈ G sao cho a ∗ b = b ∗ a = e. Phần tử b được gọi là phần tử nghịch đảo của a và kí hiệu là a−1 . Một nhóm (G, ∗) được gọi là một nhóm Abel hoặc nhóm giao hoán nếu tiên đề sau đây được thỏa mãn. (G4 ) Tính chất giao hoán: a ∗ b = b ∗ a với mọi a, b ∈ G. Về mặt kí hiệu, bên cạnh kí hiệu tích dạng a ∗ b, người ta còn sử dụng các kí hiệu a + b, ab, a ◦ b, . . . tùy vào từng trường hợp cụ thể. Trong chương này,
4 với nhóm Abel nói chung ta sẽ dùng kí hiệu + để chỉ phép toán, phần tử đơn vị được kí hiệu là 0 và gọi là phần tử trung hòa. Phần tử nghịch đảo của phần tử a khi đó sẽ được kí hiệu là −a và gọi là phần tử đối. Trong trường hợp tổng quát, tích sẽ thường được kí hiệu là ab, phần tử đơn vị đôi khi cũng được kí hiệu là 1. Để chỉ một nhóm, ta dùng kí hiệu (G, ∗) hoặc đơn giản là G. Ví dụ 1.1.1. Sau đây là một số ví dụ về nhóm. a) Tập các số nguyên Z với phép + là một nhóm Abel. Phần tử trung hòa là 0, phần tử đối của n ∈ Z là −n. Tương tự, tập các số hữu tỷ Q, tập các số thực R với phép cộng đều là những nhóm Abel. b) Tập G = {1, −1} ⊂ R với phép nhân. Chú ý (−1)−1 = −1. c) Tập có một phần tử G = {e} với phép toán e ∗ e = e cũng là một nhóm. Nhóm này được kí hiệu là e và gọi là nhóm tầm thường. d) Tập R× := R\{0} với phép nhân. Tương tự đối với tập R+ := {x ∈ R : x > 0}. e) Tập các lớp đồng dư Z/nZ với n ∈ Z cho trước, trong đó phép toán là phép cộng (a + nZ) + (b + nZ) := a + b + nZ. Chú ý rằng các lớp đồng dư a + nZ cũng hay được kí hiệu là a cho gọn. g) Nhóm đối xứng: Xét tập khác rỗng X và đặt SX := {f : X → X là song ánh}. Trên SX có phép hợp thành các ánh xạ (f • g)(x) = f (g(x)) và kí hiệu ánh xạ đồng nhất là idX . Khi đó (SX , •) là một nhóm với phần tử đơn vị là idX . Nhóm này gọi là nhóm đối xứng trên các phần tử của tập X. Đặc biệt nhóm SX là giao hoán khi và chỉ khi |X| = 1, 2. h) Nếu X là tập hữu hạn có n phần tử tức là X = {1, 2, . . . , n} thì nhóm SX còn được kí hiệu là nhóm Sn . Một phần tử của Sn là song ánh ϕ : {1, 2, . . . , n} → {1, 2, . . . , n}. Do đó hoàn toàn xác định ảnh ϕ(1) = a1 , ϕ(2) = a2 , . . . , ϕ(n) = an . Từ đó ta có thể biểu diễn ϕ dưới dạng (a1 a2 . . . an ) là phép hoán vị n phần tử. Ngoài ra ϕ cũng có thể biểu diễn
5   1 2 ... n dưới dạng   là phép thế n phần tử. a1 a2 . . . an Định nghĩa 1.1.2. Cho G là một nhóm. Một tập con H 6= ∅ của G là một nhóm con nếu H với các phép toán trên G hạn chế trên tập đó là một nhóm. Như vậy, nếu H là một nhóm con của G thì e ∈ H, với mọi a, b ∈ H thì a−1 ∈ H, ab ∈ H. Ta có tiêu chuẩn hữu ích sau. Bổ đề 1.1.1. Cho tập H khác rỗng là tập con của G. Những khẳng định sau là tương đương a) H là một nhóm con của G, b) Với mọi a, b ∈ H, a−1 ∈ H, ab ∈ H, c) Với mọi a, b ∈ H, ab−1 ∈ H. Chứng minh. Các quan hệ a) ⇒ b) và b) ⇒ c) là hiển nhiên. Ta chứng minh c) ⇒ a). Với a ∈ H, ta có e = aa−1 ∈ H, suy ra a−1 = e.a−1 ∈ H. Với mọi a, b ∈ H, b−1 ∈ H nên ab = a(b−1 )−1 ∈ H. Như vậy H đóng với phép toán trong G. H thỏa mãn các tiên đề của nhóm (G1 ), (G2 ) như vừa được chứng minh. Tiên đề (G3 ) về tính kết hợp luôn thỏa mãn trên G nên đương nhiên sẽ thỏa mãn trên tập con H. Vậy H là một nhóm con của G. Định nghĩa 1.1.3. Cho G là một nhóm. Cấp của một phần tử a ∈ G, kí hiệu là ord(a) là lực lượng của nhóm xyclic hai. Ví dụ, xét nhóm G := {1, −1} với phép nhân thông thường. Khi đó G là một nhom xyclic sinh bởi phần tử −1.Vậy ord(−1) = 2. Chú ý rằng cấp của một phần tử có thể không hữu hạn và được kí hiệu trong trường hợp đó là ∞.
6 Ví dụ 1.1.2. a) Xét nhóm Sn . Vì mỗi phần tử ϕ ∈ Sn hoàn toàn được xác định khi biết dãy hoán vị (a1 a2 . . . an ). Ta có n! các hoán vị như vậy cấp của nhóm Sn là n!. b) Xét nhóm S3 gồm 6 phần tử             1 2 3 1 2 3 1 2 3 1 2 3 1 2 3  id;   ;   ;   ;   ;   .  2 3 1 3 2 1 1 3 2 1 3 2 2 1 3  Như vậy S3 có cấp 3! = 6. 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 quay quanh tâm của tam giác phép quay τ với góc quay 1200 theo chiều kim đồng hồ và ba phép đối xứng µ1 , µ2 , µ3 qua các trục là đường thẳng nối đỉnh 1, 2, 3 với trung điểm cạnh đối diện thì ta có       1 2 3 1 2 3 1 2 3 id =  ;τ =   ; τ2 =  ; 1 2 3 2 3 1 3 1 2       1 2 3 1 2 3 1 2 3 µ1 =   ; µ2 =   ; µ3 =  . 1 3 2 3 2 1 2 1 3 c) Ta xét nhóm đối xứng Sn một phần tử ϕ ∈ Sn có thể mô tả dưới dạng xích. Với i ∈ {1, 2, . . . , n} cho trước, các phần tử của dãy i, ϕ(i), ϕ2 (i), . . . , không thể hoàn toàn phân biệt. Chọn lũy thừa p nhỏ nhất sao cho ϕp (i) = i, ta có một xích (i, ϕ(i), . . . , ϕp−1 (i)). Một cách tương đương ta cũng có thể định nghĩa một xích (i, j, k, . . . , l) có nghĩa là ϕ chuyển i tới j, j chuyển tới k, . . . và l quay trở về i. Để minh họa ta xét nhóm S3 chẳng hạn ϕ ∈ S3 cho bởi ϕ(1) = 2, ϕ(2) = 3, ϕ(3) = 1, ϕ(4) = 4, ϕ(5) = 5. Khi đó viết dưới dạng xích thì ϕ = (123)(4)(5). Ta chú ý rằng hoán vị vòng tròn các phần tử trong cùng một xích hay thay đổi thứ tự các xích với nhau đều không làm ảnh hưởng đến hoán vị. Chẳng hạn: (123)(4)(5) = (4)(231)(5).
7 Một k - xích hay một xích độ dài k là một xích gồm k phần tử. 1 - xích thường được bỏ đi trong kí hiệu xích. Chẳng hạn trong ví dụ trên thay vì viết (123)(4)(5) ta chỉ viết (123). 1.2 Định lý Lagrange Trong phần này ta nghiên cứu về lớp kề, từ đó đi định nghĩa nhóm thương và áp dụng vào chứng minh định lý Lagrange. Định nghĩa 1.2.1. Cho H là một nhóm con của nhóm G. Lấy một phần tử a ∈ G. a) Lớp kề trái của nhóm con H trong G với phần tử đại diện a là tập hợp aH := {ab ∈ G : b ∈ H}. b) Lớp kề phải của nhóm con H trong G với phần tử đại diện a là tập hợp Ha := {ba ∈ G : b ∈ H}. Mệnh đề sau đây đề cập đến một tính chất quan trọng của các lớp kề, mỗi nhóm con đều ứng với một phân hoạch của nhóm G thông qua các lớp kề. Mệnh đề 1.2.1. Cho H là một nhóm con của nhóm G. a) Với mọi a, b ∈ G hoặc aH = bH hoặc aH ∩ bH = ∅. Trường hợp thứ nhất xảy ra khi và chỉ khi a−1 b ∈ H. b) Tương tự với lớp kề phải, hoặc Ha = Hb hoặc aH ∩ Hb = ∅. Trường hợp thứ nhất xảy ra khi và chỉ khi ab−1 ∈ H. Chứng minh. Do chứng minh cho a) và b) tương tự nhau nên ta chỉ trình bày chứng minh cho khẳng định a). Trước hết, nếu aH = bH thì b = ac ∈ aH với c ∈ H. Do đó c = a−1 b ∈ H. Ngược lại, nếu a−1 b ∈ H thì b ∈ aH. Do đó, theo lập luận trước thì aH = bH.
8 Bây giờ, giả sử aH ∩ bH 6= ∅. Lấy một phần tử ah1 = bh2 ∈ aH ∩ bH với h1 , h2 ∈ H nào đó. Khi đó b = a(h1 h−1 2 ) ∈ aH. Sử dụng lại kết quả đã chứng minh trước ta suy ra aH = bH. Theo Mệnh đề 1.2.1, các lớp kề trái (tương tự kề phải) của H lập thành một phân hoạch trên G. Phân hoạch này khá đều theo nghĩa: Giả sử aH là một lớp kề trái của H. Xét ánh xạ f : H → aH, b 7→ ab. Rõ ràng f là toàn ánh. Luật giản ước suy ra f là đơn ánh, do đó là song ánh. Nói cách khác, mọi lớp kề trái (tương tự kề phải) đều có cùng lực lượng và bằng lực lượng của H. Định nghĩa 1.2.2. Cho H là một nhóm con của nhóm G. Chỉ số của H trong G, kí hiệu là [G : H] là số lớp kề trái của H trong G. Giữa lớp kề trái và kề phải có song ánh aH 7→ (aH)−1 = Ha−1 . Do đó số lớp kề trái và số lớp kề phải là như nhau, ta có thể dùng lớp kề phải để định nghĩa chỉ số [G : H]. Một nhóm G có hữu hạn phần tử được gọi là một nhóm hữu hạn. Khi đó, số phần tử của nhóm được gọi là cấp của G và kí hiệu là |G|. Định lý sau đây của Lagrange cho một quan hệ giữa cấp của G với cấp của nhóm con của nó. Định lí 1.2.1 (Lagrange). Cho H là một nhóm con của nhóm hữu hạn G, ta có |G| [G : H] = . |H| Hệ quả là cấp của H là ước của cấp của G. Nói riêng, mọi phần tử đều có cấp là ước của cấp của nhóm. Chứng minh. Theo Mệnh đề 1.2.1, nhóm G được phân hoạch thành các lớp r kề rời nhau có cùng lực lượng với H. Tức là G = ai H. Với H = |ai H| F i=1 như lập luận ngay sau chứng minh của Mệnh đề 1.2.1 ta có
r
G
|G| =
ai H
= |a1 H| + |a2 H| + · · · + |ar H|,