Header Page of 126 ĐẠI HỌC THÁI NGUN TRƯỜNG ĐẠI HỌC KHOA HỌC PHẠM THỊ THU HIỀN SỐ TỔ HỢP SUY RỘNG VÀ MỘT VÀI PHƯƠNG PHÁP XÂY DỰNG BÀI TỐN TỔ HỢP Chun ngành: PHƯƠNG PHÁP TỐN SƠ CẤP MÃ SỐ: 60.46.01.13 LUẬN VĂN THẠC SĨ TỐN HỌC Thái Ngun - 2013 Footer Page of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page of 126 ĐẠI HỌC THÁI NGUN TRƯỜNG ĐẠI HỌC KHOA HỌC PHẠM THỊ THU HIỀN TỔ HỢP SUY RỘNG VÀ MỘT VÀI PHƯƠNG PHÁP XÂY DỰNG BÀI TỐN TỔ HỢP Chun ngành: PHƯƠNG PHÁP TỐN SƠ CẤP MÃ SỐ: 60.46.01.13 LUẬN VĂN THẠC SĨ TỐN HỌC Người hướng dẫn khoa học: PGS.TS ĐÀM VĂN NHỈ Thái Ngun - 2013 Footer Page of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page of 126 Mục lục Mở đầu Chương Tổ hợp suy rộng 1.1 Phép chứng minh quy nạp 1.1.1 Quan hệ tương đương quan hệ thứ tự 1.1.2 Ngun lý quy nạp 1.2 Hốn vị, chỉnh hợp tổ hợp 1.2.1 Quy tắc đếm 1.2.2 Hốn vị chỉnh hợp 1.2.3 Tổ hợp 1.2.4 Cơng thức khai triển nhị thức Newton 1.3 Hốn vị, chỉnh hợp tổ hợp suy rộng 1.3.1 Chỉnh hợp có lặp 1.3.2 Tổ hợp có lặp 1.3.3 Hốn vị tập hợp có phần tử giống 1.3.4 Số cách phân bố đồ vật vào hộp 1.4 Xây dựng tốn tổ hợp 1.4.1 Phương pháp đạo hàm tích phân 1.4.2 Phương pháp hệ phương trình 1.4.3 Phương pháp số phức 1.4.4 Phương pháp song ánh Chương Một vài biểu diễn qua tổ hợp 2.1 Định lý Hilbert Định lý Cantor biểu diễn số 2.2 Khai triển đa đơn thức 2.3 Sử dụng số cơng thức chuyển đổi ngược 2.4 Đồng thức Newton 2.5 Định lý Fermat Định lý Wilson Footer Page of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ 6 12 12 13 17 20 22 22 22 25 26 27 27 30 38 41 45 45 48 50 56 60 Header Page of 126 Kết luận Tài liệu tham khảo Footer Page of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ 64 65 Header Page of 126 Mở đầu Tổ hợp phần quan trọng Tốn học rời rạc, chun nghiên cứu xếp phân bố đối tượng tính số cách xếp Chủ đề nghiên cứu từ lâu, kỷ 17, xét trò chơi may rủi Thơng thường, số phần tử hữu hạn việc phân bố chúng phải thỏa mãn điều kiện định đấy, tùy theo u cầu vấn đề nghiên cứu Do việc đếm đối tượng diễn đạt tốn dạng xếp, có kể thứ tự khơng, phần tử tập hợp, nên ta thường gặp tốn tổ hợp dạng sau: Bài tốn đếm: Đây tốn nhằm trả lời câu hỏi "có cách xếp phần tử thỏa mãn điều kiện nêu?" Phương pháp đếm thường dựa vào số ngun lý số tính tốn khơng q phức tạp Bài tốn liệt kê: Đây tốn xét tất khả nhằm trả lời câu hỏi "thuật tốn vét hết khả xếp có cách xếp phần tử thỏa mãn điều kiện nêu?" Bài tốn tối ưu: Đây tốn xét cách xếp tốt nhất, theo nghĩa đó, số cách xếp Bài tốn tồn tại: Đây tốn xét tồn hay khơng tồn cách xếp phần tử theo u cầu đặt Một vấn đề dễ thấy tốn tổ hợp thường xuất kỳ thi Đại học Cao đẳng, kỳ thi Học sinh giỏi cấp quốc gia hay quốc tế Chúng tốn khó Đặc biệt, để phục vụ tốt cho việc giảng dạy chương "Tổ hợp Xác xuất" lớp 11, giúp học sinh thi Đại học Cao đẳng với mong muốn tìm hiểu sâu tốn tổ hợp nên chúng tơi chọn đề tài "Tổ hợp suy rộng Footer Page of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page of 126 vài phương pháp xây dựng tốn tổ hợp." Luận văn tập trung tìm hiểu Bài tốn đếm Bài tốn liệt kê (dạng đơn giản) Ngồi phần mở đầu, kết luận, luận văn chia làm chương Chương Tổ hợp suy rộng Chương tập trung trình bày phương pháp quy nạp Mục1.1; hốn vị, chỉnh hợp, tổ hợp, nhị thức Newton Mục 1.2; chỉnh hợp tổ hợp suy rộng Mục 1.3; số phương pháp xây dựng tốn tổ hợp trình bày Mục 1.4 Chương Một vài ứng dụng tổ hợp Trong chương chúng tơi tập trung trình bày số ứng dụng tổ hợp để biểu diễn vài tốn Mục 2.1 trình bày cách vận dụng tổ hợp hốn vị để biểu diễn số qua Định lí Hilbert Định lí Cantor Mục 2.2 trình bày cơng thức khai triển đa đơn thức Nó cơng thức khai triển nhị thức Newton tổng qt Trong Mục 2.3 chúng tơi trình bày phương pháp sử dụng số cơng thức chuyển đổi ngược Đồng thức Newton trình bày Mục 2.4 cuối việc chứng minh Định lí Fermat Định lí Wilson Luận văn hồn thành với hướng dẫn bảo tận tình PGS -TS Đàm văn Nhỉ - Trường ĐHSP1- Hà nội Từ đáy lòng mình, em xin bày tỏ lòng biết ơn sâu sắc quan tâm, động viên bảo hướng dẫn Thầy Em xin trân trọng cảm ơn tới Thầy Cơ Trường Đại Học Khoa Học - Đại Học Thái Ngun, phòng Đào Tạo Trường Đại Học Khoa Học Đồng thời tơi xin gửi lời cảm ơn tới tập thể lớp Cao Học Tốn K5A Trường Đại Học Khoa Học động viên giúp đỡ tơi q trình học tập làm luận văn Tơi xin cảm ơn Sở Giáo dục Đào tạo Tỉnh Hà Giang, Ban Giám hiệu, đồng nghiệp Trường THPT Hùng An - Huyện Bắc Quang tạo điều kiện giúp đỡ tơi hồn thành kế hoạch học tập Footer Page of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page of 126 Tuy nhiên, hiểu biết thân khn khổ luận văn, nên luận văn khơng tránh khỏi thiếu sót Tơi mong nhận dẫn góp ý Thầy Cơ, bạn bè để tơi hồn thành tốt luận văn Thái Ngun, ngày 02 tháng 04 năm 2013 Tác giả Phạm Thị Thu Hiền Footer Page of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page of 126 Chương Tổ hợp suy rộng Nội dung chương tập trung bàn tổ hợp suy rộng Chúng ta bắt đầu chương cách trình bày phương pháp quy nạp 1.1 1.1.1 Phép chứng minh quy nạp Quan hệ tương đương quan hệ thứ tự Giả thiết tập X = ∅ Tích đề X × X định nghĩa đây: X × X = {(x, y)|x, y ∈ X} Định nghĩa 1.1 Tập S X × X quan hệ hai ngơi X Nếu (x, y) ∈ S ta nói x quan hệ S với y viết xSy Định nghĩa 1.2 Giả thiết X = ∅ S = ∅ quan hệ hai ngơi X Quan hệ S gọi quan hệ tương đương X thỏa mãn ba điều kiện sau đây: (i) (Phản xạ) Với x ∈ X có xSx (ii) (Đối xứng) Với x, y ∈ X, có xSy có ySx (iii) (Bắc cầu) Với x, y, z ∈ X, có xSy ySz có xSz Khi S quan hệ tương đương X ta thường kí hiệu ∼ thay cho S Đặt C(x) = {y ∈ X|y ∼ x} gọi lớp tương đương với x làm đại diện Dễ dàng tính chất sau: Tính chất 1.1 Giả sử ∼ quan hệ tương đương X Khi đó: (i) Với x ∈ X có x ∈ C(x) (ii) Với y, z ∈ C(x) có y ∼ z, y ∼ x z ∼ x (iii) Với x, y ∈ X, có C(x) ∩ C(y) = ∅ C(x) = C(y) (iv) Tập thương X/ ∼ tập lớp tương đương khơng giao Footer Page of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page of 126 Ví dụ 1.1 Tính tổng tất số gồm chữ số phân biệt lập từ số 1, 2, , 8, Bài giải: Tập số thỏa mãn đầu phân làm lớp phân biệt lực lượng: Lớp C(i) = {a1 a2 a3 a4 a5 a6 a7 a8 i|ak ∈ {1, 2, , 9} \ {i}} gồm tất số lập qua việc viết chữ số i vào cuối số a1 a2 a3 a4 a5 a6 a7 a8 với ak ∈ {1, 2, , 9} \ {i} Thấy lực lượng C(i) 8! Vậy tổng chữ số hàng đơn số thỏa mãn đầu 8!(1 + + · · · + + 9) = 45.8! Từ có tổng số 109 − cần tính S = 45.8!(1 + 10 + · · · + 108 ) = 45.8! = 5(109 − 1).8! Định nghĩa 1.3 Giả thiết X = ∅ S = ∅ quan hệ hai ngơi X Quan hệ S gọi quan hệ thứ tự X thỏa mãn ba điều kiện sau đây: (i) (Phản xạ) với x ∈ X có xSx (ii) (Phản đối xứng) Với x, y ∈ X, có xSy ySx x = y (iii) (Bắc cầu) Với x, y, z ∈ X, có xSy ySz có xSz Tập X gọi tập xắp thứ tự có quan hệ thứ tự X Khi S quan hệ thứ tự X ta thường viết thay cho S Với x, y ∈ X, thay cho việc viết xSy ta viết x y đọc x nhỏ y viết y x đọc y lớn x Từ ta định nghĩa x < y x y, x = y; y > x y x, y = x Định nghĩa 1.4 Giả thiết X tập xắp thứ tự với quan hệ thứ tự Phần tử a ∈ X gọi phần tử bé X thỏa mãn a x với x ∈ X Phần tử b ∈ X gọi phần tử lớn X thỏa mãn x b với x ∈ X Định nghĩa 1.5 Tập xắp thứ tự X gọi tập xắp thứ tự tốt phận khác rỗng X có phần tử bé Hai kết sau chứng minh giáo trình số học Footer Page of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 10 of 126 Mệnh đề 1.1 Tập tất số tự nhiên N quan hệ thứ tự tập xắp thứ tự tốt Mệnh đề 1.2 Nếu tập M ⊂ N có tính chất: ∈ M n + ∈ M n ∈ M, M = N Ví dụ 1.2 Xác định số ngun dương k để cho tập hợp X = {2012, 2012 + 1, 2012 + 2, , 2012 + k} phân làm hai tập A B thỏa mãn A ∩ B = ∅, A ∪ B = X tổng số thuộc tập A tổng số thuộc tập B Bài giải: Trước tiên ta tìm điều kiện cho k Giả sử có hai tập A B thỏa mãn đầu Đặt s tổng tất số thuộc tập A Khi tập B có tổng số s tập X có tổng tất số 2s Vậy 4s = 2[2012 + (2012 + 1) + (2012 + 2) + · · · + (2012 + k)] = 4024(k + 1) + k(k + 1) Như k(k + 1) chia hết cho từ suy k ≡ 3(mod 4) k ≡ 0(mod 4) Xét trường hợp (1): k ≡ 3(mod 4) Dễ dàng suy ra: Số phần tử thuộc tập X phải bội Hiển nhiên, số tự nhiên liên tiếp n, n+1, n+2, n+3 ln thỏa mãn n + n + = n + + n + {n, n + 3} ∩ {n + 1, n + 2} = ∅ Tập X thỏa mãn tính chất đòi hỏi Trường hợp (2): k ≡ 0(mod 4) Trong trường hợp này, số phần tử tập X phải số lẻ Giả sử X phân làm hai tập rời A B A ∩ B = ∅ Ta giả thiết Card(A) > Card(B) Đặt k = 4m với số tự nhiên m Khi Card(A) 2m + 1, Card(B) 2m Ta có s 2012 + (2012 + 1) + · · · + (2012 + 2m) s < (2012 + 2m + 1) + · · · + (2012 + 4m) Như vậy, ta có 2012 + (2012 + 1) + · · · + (2012 + 2m) s < (2012 + 2m + 1) + · · · + (2012 + 4m) hay 2012 < 2m.2m hay m 23 k = 4m 23.4 = 92 Khi k = 92 : Ta xét A1 = {2012, 2012 + 1, , 2012 + 46} với tổng số a1 = 2012 + (2012 + 1) + · · · + (2012 + 46); B1 = {(2012 + 47) + · · · + (2012+92) với tổng số b1 = (2012+47)+· · ·+(2012+92) Ta có b1 − a1 = 46.46 − 2012 = 104 Thế số 2012 + 52 B1 số 2012 số 2012 A1 số 2012+52 Khi A = A1 \{2012}∪{2012+52} B = B1 \ {2012 + 52} ∪ {2012} thỏa mãn đề Footer Page 10 of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 54 of 126 52 n (iii) Ln = n j (−1)n−j j=1 (L2j − 2) Bài √ giải: (i) √Bằng phương pháp quy nạp theo n, với x1 = 1− 1+ , x2 = ta có biểu diễn Ln = xn2 + xn1 2 (ii) Vì + x2 = x22 , + x1 = x21 nên ta biến đổi đây: n n Lj = j j=0 = n j=0 x2n n (xj2 + xj1 ) = (1 + x2 )n + (1 + x1 )n j + x2n = L2n n n j Vậy có cơng thức L2n = j=0 Lj n (−1)j nj j=0 n (iii) Theo Định lý 2.5, Ln = f (j) = Lj , g(n) = L2n Vì L0 = = −2 n g(j) = j=0 (−1)j j=1 n dàng suy cơng thức Ln = (−1)n−j j=1 n n minh n! = + k=2 n k (−1)k Ví dụ 2.11 Cho dãy Dn = k=0 n k Dk với n Bài giải: Ta có (−1)n Dn = n n j n j (−1)n−k k L2j với nên dễ (L2j − 2) (n − k)! với n Chứng n n−k n (n − k)! = (−1)k k=0 k n Đặt fk = (−1) Dk gk = (−1) k! Khi f (n) = n Theo Định lý 2.5, ta nhận gn = hay (−1)n n! = n n! = + (−1)n−k k=0 n (−1)n nk k=0 (−1)n k=2 n k n k n fk = k=0 (−1)n k=0 n k k! n k gk n k Dk Dk Vì D0 = theo quy ước D1 = nên Dk Ví dụ 2.12 Đặt an = 1n + 2n + · · · + mn , n, m ∈ N+ Khi m+1 n (−1)n+j n+1 [(m + 1)j − 1] an = j+1 n + j=1 Footer Page 54 of 126 n j k=0 với n (−1)j Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 55 of 126 53 Bài giải: Ta có (x+1) n+1 n+1 −x n+1 = j=1 n+1 cộng tất lại, (m + 1) n+1 j xn+1−j Cho x = 1, , m, n j=1 j n j − = (n + 1)[ an+1−1 ] + m n (m + 1)n+1 − (m + 1) n = j n + − j aj Theo Định lý 2.5, với n+1 j=1 aj (m + 1)n+1 − (m + 1) f (j) = , g(n) = ta có an = f (n) = n+1−j n+1 m+1 n n+1 (−1)n+j [(m + 1)j − 1] n + j=1 j+1 Vậy Ví dụ 2.13 Tính số phép f n phần tử, khơng có phần tử cố định, có nghĩa: f (i) = i Bài giải: Gọi số phép qn Đặt pn = n! số tất phép n phần tử Xét tất phép pn , có qn phép khơng có phần tử chiếm lại vị trí xuất phát Số phép có phần tử chiếm lại vị trí xuất phát C1n qn−1 Tương tự, số phép có hai phần tử chiếm lại vị trí xuất phát C2n qn−2 , v.v Cuối cùng, số phép có tất phần tử chiếm n lại vị trí xuất phát Cnn q0 = Vậy pn = n Định lý 2.5, ta có qn = (−1)k Ckn pk = k=0 n Ckn qn−k Theo k=0 (−1)k Ckn k! k=0 Ví dụ 2.14 Xét ma trận vng cấp n  a11 a12 a13 · · ·  a a a ···  21 22 23  A =  a31 a32 a33 · · ·   an1 an2 an3 · · · a1n a2n a3n ann        với tất phần tử thuộc R akk = 0, k = 1, 2, , n, aij = i = j Xác định số số hạng khác khai triển định thức det(A) Bài giải: Hiển nhiên det(A) = sgn(π)aπ(1)1 aπ(2)2 aπ(n)n có n! π∈Sn số hạng Sn nhóm đối xứng Vì aπ(1)1 aπ(2)2 aπ(n)n = Footer Page 55 of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 56 of 126 54 có k để π(k) = k nên số số hạng khác n khai triển định thức det(A) qn = (−1)k Ckn k! theo Ví dụ k=0 2.13 Ví dụ 2.15 Có cách xếp n chữ khác vào r cho có chữ Bài giải: Số cách xếp n chữ khác vào r số ánh xạ từ tập n phần tử vào tập r phần tử số rn Ký hiệu số cách xếp n chữ vào r cho có chữ qn Trong số rn cách xếp phần đầu, ta xét cách xếp để có chữ Số cách xếp qn Sau xét tất cách xếp có trống Số C1r qr−1 Tiếp theo xét tất cách xếp có hai trống Số C2r rqr−2 , v v Vậy rn + = C0r qr + C1r qr−1 + · · · + Cr−1 q1 + Crr q0 Theo r r Định lý 2.5, qr = r (−1)k Ckr (r − k)n + = k=0 r (−1)k Ckr (r − k)n k=0 (−1)k Ckr = (1 − 1)r = k=0 Với cách thức chuyển đổi ngược, xét thi vơ địch quốc tế sau: Ví dụ 2.16 Ký hiệu pn (k) số phép tập gồm n phần tử, n có k phần tử cố định Chứng minh n 1987] kpn (k) = n! [IMO k=0 (k − 1)2 pn (k) = n! k=0 Bài giải: Hiển nhiên kpn (k) = k Ckn qn−k = n Ck−1 n−1 qn−1−(k−1) Từ quan hệ pn−1 = C0n−1 qn−1 + C1n−1 qn−2 + · · · + Cn−1 n−1 q0 ta suy hệ thức sau n n k Ckn qn−k = n(n − 1)! = n! kpn (k) = k=0 Ta có (k − k=0 1)2 pn (k) = (k − 1)2 Ckn qn−k Xét quan hệ đa thức đây: (p + x)n = (q + + x)n = n(p+x)n−1 = 1)k−1 q n−k + n n Ckn (x + 1)k q n−k Lấy đạo hàm hai vế, k=0 k Ckn (x+1)k−1 q n−k Vậy n(p+x)n−1 = k=0 n (k −1) Ckn (x+ k=1 Ckn (x + 1)k−1 q n−k Lấy đạo hàm hai vế cho x = ta k=1 Footer Page 56 of 126 n Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 57 of 126 55 nhận hệ thức sau đây: n n (k − 1) n! = Ckn q n−k (k − 1) Ckn q n−k + k=2 n k=2 n (k − 1) Ckn q n−k (k − 1) npn (k) − qn + = k=0 n k=2 n n k Ckn q n−k (k − 1) npn (k) + = k=0 n Ckn q n−k − k=0 k=0 (k − 1)2 npn (k) + n! − n! = k=0 n theo chứng minh Tóm lại (k − 1)2 pn (k) = n! k=0 Ví dụ 2.17 Dãy (an ) xác định sau: a1 = 0, a2 = an = nan−1 n(n − 1)an−2 n + +(−1)n (1− ) với n Xác định cơng thức tường 2 minh cho fn = an +2 C1n an−1 +3 C2n an−2 +· · ·+(n−1) Cn−2 a2 +n Cn−1 a1 n n Bài giải: Bằng quy nạp theo n ta an = nan−1 + (−1)n 1 1 Vậy an = n!(1 − + − + · · · + (−1)n ) Viết an dạng sau 1! 2! 3! n! n đây: an = Cnn n! + Cn−1 (−1) (n − 1)! + · · · + C n n (−1) (n − n)!; ta viết cách hình thức ak bk = k! qua ak bk tương ứng an = (b − 1)n với số ngun n với quy ước a0 = Xét quan hệ đa thức n sau: x(b − + x)n = x(a + x)n = Ckn an−k xk+1 Lấy đạo hàm hai vế, k=0 n nx(b − + x)n−1 + (b − + n)n = k = Ckn an−k xk Với x = ta có k=0 n bn +nbn−1 = (k+1) Ckn an−k k=0 n−1 n−1 hay n!+n(n−)! = (k+1) Ckn an−k +n+1 k=0 (k + 1) Ckn an−k = 2n! − n − Từ ta suy fn = k=0 Chú ý 2.2 Từ x2 (b − + x)n = x2 (a + x)n = n Ckn an−k xk+2 , lấy đạo k=0 n hàm hai vế nx2 (b−1+x)n−1 +2x(b−1+n)n = (k+2) Ckn an−k xk+1 k=0 Footer Page 57 of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 58 of 126 56 n Với x = ta có 2bn + nbn−1 = (k + 2) Ckn an−k hay 2n! + n(n−)! = k=0 n−1 (k+2) Ckn an−k +n+2 Từ ta suy k=0 2.4 n−1 (k+2) Ckn an−k = 3n!−n−2 k=0 Đồng thức Newton Sử dụng chuỗi lũy thừa hình thức để chứng minh đồng thức liên quan đến đa thức đối xứng Giả sử x1 , , xn n tham số Ký hiệu   δ1 = x1 + x2 + · · · + xn      δ2 = x1 x2 + x1 x3 + · · · + xn−1 xn      δn = x1 x2 xn      Nt = xt1 + xt2 + · · · + xtn , t = 1, 2, , N0 = n      xi11 xi22 · · · xinn ph = ph (x1 , , xn ) = i1 +···+in =h Định lý 2.6 [Newton] Ta có đồng thức sau đây: Nt − Nt−1 δ1 + · · · + (−1)t−1 N1 δt−1 + (−1)t tδt = 0, t n, Nt − Nt−1 δ1 + · · · + (−1)n−1 Nt−n+1 δn−1 + (−1)n Nt−n δn = 0, t > n Chứng minh: Với f (x) = (x − x1 )(x − x2 ) (x − xn ) ta nhận f (x) 1 1 = + ··· + = [ + · · · + xn ] Vậy f (x) x − x1 x − xn x − x1 1− x x ∞ xt + xt + · · · + xt ∞ N ∞ N f (x) f (x) f (x) t t n = = hay = Từ t+1 f (x) xt+1 xn−1 xn t=0 xt t=0 t=0 x δ1 δ2 δn−1 có đồng thức n−(n−1) +(n−2) −· · ·+(−1)n−1 n−1 x x x δ1 δ2 δ δ δ n t = [1 − + − · · · + (−1)n n ][n + + · · · + t + · · · ] So sánh hệ số x x x x x t hai vế ta có đồng thức Newton x Hệ 2.2 Giả sử hai hệ số thực a1 , , an b1 , , bn thỏa mãn Footer Page 58 of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 59 of 126 57 n ask = k=1 n bsk với s = 1, 2, , n Khi có phép hốn vị π thuộc k=1 nhóm đối xứng Sn để ak = bπ(k) với k = 1, 2, , n Chứng minh: Sử dụng Định lý 2.6, qua quy nạp theo s nhận đồng thức δs (a1 , , an ) = δs (b1 , , bn ) với s = 1, 2, , n n Từ suy n (x − ak ) = k=1 (x − bk ) Vậy có phép hốn vị π thuộc k=1 nhóm đối xứng Sn để ak = bπ(k) với k = 1, 2, , n Định lý 2.7 Đặt ui = (−1)i+1 δi với i n Ta có đồng t(λ1 + λ2 + · · · + λn − 1)! λ1 λ2 thức Nt = u1 u2 · · · uλnn , tổng lấy λ1 !λ2 ! · · · λn ! theo tất hệ (λ1 , λ1 , , λn ) số ngun khơng âm thỏa mãn λ1 + 2λ2 + · · · + nλn = t Chứng minh: Với f (x) = (x − x1 )(x − x2 ) (x − xn ) ta nhận t t t f (x) Nt ∞ x1 + x2 + · · · + xn ∞ = t=0 = t=0 t+1 , (1) Dễ dàng thấy f (x) xt+1 x n n−1 n−2 f (x) = x − u1 x − u2 x − · · · − un Biểu diễn f (x) = xn − g(x) f (x) g(x) Ta có n = − n x x Viết thành chuỗi lũy thừa hình thức ∞ f (x) f (x) = f (x) xn f (x) g(x) = n ( n )t g(x) x t=0 x 1− n x ∞ f (x) δ1 δ2 n−1 δn t = − + · · · + (−1) , (2) xn t=0 x x2 xn Từ (1),(2) ta suy ∞ t=0 ∞ = t=0 ∞ = t=0 Footer Page 59 of 126 Nt f (x) = xt+1 xn ∞ t=0 u1 u2 un + + ··· + n x x x t u1 u2 un t n (n − 1)u1 un−1 + + ··· + n ( − − · · · − ) x x x x x2 xn t!uλ1 uλ2 · · · uλnn (n − 1)u1 un−1 (n − − · · · − ) λ1 !λ2 ! λn !xh+1 x xn−1 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 60 of 126 58 Ở tổng lấy theo tất số ngun khơng âm thỏa mãn λ1 + 2λ2 + · · · + nλn = h λ1 + λ2 + · · · + λn = t Vậy ∞ t=0 Nt = xt+1 ∞ (λ1 + · · · + λn )!uλ1 uλ2 · · · uλnn λ1 !λ2 ! λn !xλ1 +2λ2 +···+nλn +1 t=0 (n − un−1 (n − 1)u1 − · · · − n−1 ) x x Ở tổng lấy theo tất hệ (λ1 , λ1 , , λn ) số ngun khơng âm So sánh hệ số t+1 hai vế ta có hệ số uλ1 uλ2 · · · uλnn x (λ1 + · · · + λn )!n (λ1 + · · · + λn − 1)!(n − 1) − − λ1 !λ2 ! λn ! (λ1 − 1)!λ2 ! λn ! (λ1 + · · · + λn − 1)!1 ··· − λ1 !λ2 ! (λn−1 − 1)!λn ! với λ1 + 2λ2 + · · · + nλn = t Biến đổi số hạng ta có hệ số uλ1 uλ2 · · · uλnn (λ1 + · · · + λn − 1)![λ1 + 2λ2 + · · · + nλn ] t(λ1 + · · · + λn − 1)! = λ1 !λ2 ! λn ! λ1 !λ2 ! λn ! t(λ1 + λ2 + · · · + λn − 1)! λ1 λ2 Tóm lại, Nt = u1 u2 · · · uλnn , tổng λ1 !λ2 ! · · · λn ! lấy theo tất hệ (λ1 , λ1 , , λn ) số ngun khơng âm thỏa mãn λ1 + 2λ2 + · · · + nλn = t Ví dụ 2.18 Ta có x3 x1 x31 + x32 + x33 − 3x1 x2 x3 = x21 +x22 +x23 −x1 x2 −x2 x3 − x1 + x2 + x3 Bài giải: Theo Định lý 2.6 ta có N3 − N2 δ1 + N1 δ2 − 3δ3 = Vậy N3 − 3δ3 = N2 − δ2 nhận đồng thức N1 Ví dụ 2.19 Nếu x1 , x2 , x3 thỏa mãn hệ thức x31 + x32 + x33 + x1 x2 x3 = x41 + x42 + x43 + (x21 + x22 + x23 )(x1 x2 + x2 x3 + x3 x1 ) = Bài giải: Theo Định lý 2.6 ta có N4 − N3 δ1 + N2 δ2 − N1 δ3 = Vậy N4 + N2 δ2 = N1 (N3 + δ3 ) = nhận đồng thức Footer Page 60 of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 61 of 126 59 Ví dụ 2.20 Các số x1 , x2 , x3 thỏa mãn x1 + x2 + x3 = Khi tính x2 − x3 x3 − x1 x1 − x2 x1 x2 x3 (i) T = + + + + x1 x2 x3 x2 − x3 x3 − x1 x1 − x2 (ii) Chứng minh x61 + x62 + x62 = 3x21 x22 x23 − 2(x1 x2 + x2 x3 + x3 x1 )3 δ13 − 4δ1 δ2 + 9δ3 Bài giải:(i) Phân tích giản ước T = = δ3 (ii) Dễ thấy x1 , x2 , x3 nghiệm x3 + δ2 x − δ3 = Do ta có N3 = 3δ3 , N4 = δ3 N1 − δ2 N2 = −δ2 N2 Như N6 = −N4 δ2 + N3 δ3 = 3δ32 + δ22 N2 = 3δ32 − 2δ23 , N2 = −2δ2 Ví dụ 2.21 Đặt δ δ3 p0 = Từ = p0 = Khi p + δ2 p −   δ0 p3 − δ p1 δ1 suy δ3 = det  p2 p1  p3 = det  δ2 δ1  p3 p2 p1 δ3 δ2 δ1 Bài giải: Đặt δk = k > Viết hàm sinh δ(t) = ∞ k k δk t = (1 + txi ) p(t) = pk t = Ta có i=1 i=1 + txi k=0 k=0 δ(t)p(−t) = Khai triển δ(t)p(−t), hệ số tj , j 1, ∞ (−1)k δk p3−k = Từ quan hệ suy hệ phương trình k=0   1.p1 − δ1 = tuyến tính: 1.p2 − δ1 p1 + δ2 = Hệ có nghiệm (1, −δ1 , δ2 )   1.p3 − δ1 p2 + δ2 p1 = δ3   p1 Qua việc tính hệ số ta suy quan hệ det  p2 p1  = p3 p2 p1     δ1 det  p1  = δ3 p3 = det  δ2 δ1  chứng minh hồn δ3 p2 p1 δ3 δ2 δ1 tồn tương tự Vậy Ví dụ 2.22 Chứng minh a, b, c, d ∈ R thỏa mãn ab + ac + ad + bc+bd+cd = a3 +b3 +c3 +d3 −3 bcd+cda+dab+abc = (a+b+c+d)3 Footer Page 61 of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 62 of 126 60   δ1 = a + b + c + d      δ2 = ab + ac + ad + bc + bd + cd Bài giải: Đặt δ3 = abc + abd + acd + bcd     δ4 = abcd    Nt = at + bt + ct + dt , t = 1, 2, , N0 = Theo Định lý 2.6 ta có N3 − N2 δ1 + N1 δ2 − 3δ3 = Vậy N3 − 3δ3 = N2 δ1 − N1 δ2 = δ13 − 3δ1 δ2 Vậy δ2 = nên a3 + b3 + c3 + d3 − bcd + cda + dab + abc = (a + b + c + d)3 Ví dụ 2.23 Đa thức T = 2(x7 + y + z ) − 7xyz(x4 + y + z ) có nhân tử x + y + z Bài giải: Đặt A = x + y + z, B = xy + yz + zx, C = xyz Đặt an = xn + y n + z n Khi x, y, z ba nghiệm t3 − At2 + Bt − C = an+3 = Aan+2 − Ban+1 + Can với số ngun n a0 = Chú ý a0 = a1 = A a2 = A2 − 2B a3 = Aa2 − Ba1 + Ca0 = A3 − 3AB + 3C = Ak3 + 3C a4 = Aa3 − Ba2 + Ca1 = Ak4 + 2B a5 = Ak5 − 5BC a6 = Ak6 − B + 3C a7 = Ak7 + 7B C Vậy T = 2a7 − 7Ca4 = A(2k7 − 7k4 C) có nhân tử A = x + y + z 2.5 Định lý Fermat Định lý Wilson Bổ đề 2.1 Với số ngun dương n, đặt f (x) = (1 + x)(2 + x) (n + x) Giả sử f (x) = b0 + b1 x + b2 x2 + · · · + bn xn Chứng minh (n − k)bk = Cn+1−k + Cn−k bn−1 + Cn−1−k bn−2 + · · · + C2k+2 bk+1 n n+1 n−1 Chứng minh: Từ (1+x)(2+x) (n+x) = b0 +b1 x+b2 x2 +· · ·+bn xn ta suy (2 + x)(3 + x) (n + + x) = b0 + b1 (x + 1) + · · · + bn (x + 1)n Footer Page 62 of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 63 of 126 61 qua việc thay x x + Ta có bn = 1, bn−1 = + + · · · + n = n(n + 1) hệ thức(1 + x)(2 + x) (n + x)(n + + x) = 2! b0 (x + 1) + b1 (x + 1)2 + b2 (x + 1)3 + · · · + bn (x + 1)n Từ (n+1+x)f (x) = (x+1)f (x+1) suy (n+1+x)(b0 +b1 x+· · ·+bn xn ) = b0 (x + 1) + b1 (x + 1)2 + b2 (x + 1)3 + · · · + bn (x + 1)n+1 Như  bn =      (n + 1)bn−1 + bn−2 = C2n+1 bn + C1n bn−1 + C0n−1 bn−2      (n + 1)bn−2 + bn−3 = Cn+1 bn + Cn bn−1 + Cn−1 bn−2 + Cn−2 bn−3 ···   n−2   (n + 1)b2 + b1 = Cn−1 bn−1 + Cn−3 n+1 bn + Cn n−1 bn−2 + · · · + C3 b2 + C2 b1     (n + 1)b1 + b0 = Cnn+1 bn + Cn−1 bn−1 + Cn−2  n n−1 bn−2 + · · · + C2 b1 + C1 b0    n n−1 (n + 1)b0 = Cn+1 n+1 bn + Cn bn−1 + Cn−1 bn−2 + · · · + C2 b1 + C1 b0 có  bn =     n(n + 1)    bn−1 =   2!    2bn−2 = C + C2 bn−1 n+1 n ···      (n − 2)b2 = Cn−1 + Cn−2 bn−1 + Cn−3 bn−2 + · · · + C24 b3 n n+1 n−1      (n − 1)b1 = Cnn+1 + Cn−1 bn−1 + Cn−2 n n−1 bn−2 + · · · + C3 b2    n n−1 nb0 = Cn+1 n+1 + Cn bn−1 + Cn−1 bn−2 + · · · + C2 b1 Do (n − k)bk = Cn+1−k + Cn−k bn−1 + Cn−1−k bn−2 + · · · + C2k+2 bk+1 n n+1 n−1 Hệ 2.3 [MO British 1974] Với số ngun tố lẻ p, đặt f (x) = (1+x)(2+x) (p−1+x) Giả sử f (x) = b0 +b1 x+b2 x2 +· · ·+bp−1 xp−1 Chứng minh (i) p | bk với k = 1, 2, , p − p |(b0 + 1) (ii) Với số ngun n ta có p | (n + 1)(n + 2) (n + p − 1) − np−1 + Từ suy p | (p − 1)! + p | np−1 − (n, p) = Chứng minh: (i) Qua cơng thức tính tốn ta có Footer Page 63 of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 64 of 126 62   bp−1 =     p(p − 1)   b =  p−2   2!  2bp−3 = Cp + C2p−1 bp−2   ···    p−3   (p − 2)b1 = Cp−1 + Cp−2  p p−1 bp−2 + Cp−2 bp−3 + · · · + C3 b2   (p − 1)b = Cp + Cp−1 b + Cp−2 b + · · · + C2 b p p−1 p−2 p−2 p−3 Sử dụng cơng thức quy nạp theo k có p | bk với k = 1, 2, , p − Từ hệ thức cuối suy hệ thức p.b0 = (b0 + 1) + bp−2 + bp−3 + · · · + b1 b0 + chia hết cho p (ii) Vì p | bk với k = 1, 2, , p − b0 + chia hết cho p nên p | (n + 1)(n + 2) (n + p − 1) − np−1 + với số ngun n Từ suy p | (p − 1)! + p | np−1 − (n, p) = Từ kết ta suy ba kết sau đây: Định lý 2.8 Với số ngun tố p số ngun n thỏa mãn (n, p) = 1, ta ln có (i) [Fermat nhỏ] np−1 ≡ 1(mod p) (ii) [Wilson] (p − 1)! + ≡ 0(mod p) (iii) Nếu số ngun tố p có dạng 4k + p−1 ! 2 + ≡ 0(mod p) Ví dụ 2.24 Tìm tất nghiệm ngun phương trình x3 + y = z + Bài giải: Nếu phương trình có nghiệm Z có nghiệm Z7 Khi tồn x, y, z ∈ Z7 thỏa mãn x3 + y = z + Vì x3 , y ∈ {0, 1, −1} nên x3 +y ∈ {0, ±1, ±2}, z +3 ∈ {3, 4} Vậy phương trình xét vơ nghiệm trong Z Ví dụ 2.25 Tìm tất nghiệm ngun phương trình x2 + 4y = z + Bài giải: Nếu phương trình có nghiệm Z có nghiệm Z7 Khi tồn x, y, z ∈ Z8 thỏa mãn x2 + 4y = z + Trong Footer Page 64 of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 65 of 126 63 2 2 2 Z8 có hệ thức = 0, = 1, = 4, = 1, = 0, = 1, = 4, = Vậy x2 hoặc 4y Qua kiểm tra ta có x3 + 4y 0, 1, 2, 4, Nhưng z + + = + = Điều chứng tỏ phương trình vơ nghiệm Footer Page 65 of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 66 of 126 64 Kết luận Luận văn đạt số kết sau: Trình bày số kiến thức tổ hợp tổ hợp suy rộng với chứng minh đầy đủ ví dụ áp dụng Trình bày số phương pháp xây dựng tốn tổ hợp, chẳng hạn: Sử dụng đạo hàm tích phân; sử dụng hệ phương trình; sử dụng số phức sử dụng song ánh với ví dụ minh họa Đã chứng minh số định lý có liên quan đến tổ hợp, chẳng hạn: Đồng thức Newton, Định lý Hilbert Định lý Cantor biểu diễn số, Định lí Fermat Định lí Wilson đồng dư Đã trình bày số tốn xuất kì thi học sinh giỏi cấp quốc gia quốc tế Đã xây dựng số tốn có liên quan đến tổ hợp Footer Page 66 of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 67 of 126 65 Tài liệu tham khảo [1] D Faddéev et I Sominski, Recueil D’Exercices D’Algèbre Supérieure, Editions Mir-Moscou 1977 [2] R Merris, Combinatorics, PWS publishing company 20 Park Plaza, Boston, MA 02116-4324 [3] M B Nathanson, Elementary Methods in Number Theory, SpringerVerlag New-York Berlin-Heidelberg SPIN 10742484 [4] Đ V Nhỉ, Số phức giải Tốn sơ cấp, Tạp chí Khoa học ĐHSP Hà Nội số 2006, 40-48 [5] K H Wehrhahn, Combinatorics-An Introduction, Carslaw Publications 1992 [6] Kenneth H Rosen, Tốn rời rạc ứng dụng tin học, (Bản dịch), NXB Khoa học Kỹ thuật Hà Nội 1998 [7] D Q Việt Đ V Nhỉ, Giáo trình Đại số Sơ cấp, Nhà Xuất Bản ĐHSP Hà Nội 2007 [8] Tuyển tập: The IMO Compendium 1959-2004 [9] T N Dũng, Tạp chí Tốn học tuổi trẻ Footer Page 67 of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ Header Page 68 of 126 66 Luận văn chỉnh sửa theo ý kiến hội đồng chấm luận văn ngày 22 tháng năm 2013 Tại trường Đại học Khoa học- Đại học Thái Ngun Hà nội, ngày 22 tháng 06 năm 2013 Người hướng dẫn khoa học PGS.TS Đàm Văn Nhỉ Footer Page 68 of 126 Số hóa Trung tâm Học liệu http://www.lrc.tnu.edu.vn/ ... trình bày phương pháp quy nạp Mục1.1; hốn vị, chỉnh hợp, tổ hợp, nhị thức Newton Mục 1.2; chỉnh hợp tổ hợp suy rộng Mục 1.3; số phương pháp xây dựng tốn tổ hợp trình bày Mục 1.4 Chương Một vài ứng... NGUN TRƯỜNG ĐẠI HỌC KHOA HỌC PHẠM THỊ THU HIỀN TỔ HỢP SUY RỘNG VÀ MỘT VÀI PHƯƠNG PHÁP XÂY DỰNG BÀI TỐN TỔ HỢP Chun ngành: PHƯƠNG PHÁP TỐN SƠ CẤP MÃ SỐ: 60.46.01.13 LUẬN VĂN THẠC SĨ TỐN HỌC Người... of 126 vài phương pháp xây dựng tốn tổ hợp. " Luận văn tập trung tìm hiểu Bài tốn đếm Bài tốn liệt kê (dạng đơn giản) Ngồi phần mở đầu, kết luận, luận văn chia làm chương Chương Tổ hợp suy rộng