Tóm tắt luận văn Thạc sĩ Khoa học: Nguyên lý bao hàm & loại trừ và ứng dụng

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

Thêm vào BST

Báo xấu

131
lượt xem 10
download

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

Đề tài góp phần nghiên cứu, hỗ trợ học sinh khi học phần tổ hợp, giải một số bài toán số học mà việc giải chúng có nhiều ứng dụng trong trong các lĩnh vực toán học, tin học. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt luận văn Thạc sĩ Khoa học: Nguyên lý bao hàm & loại trừ và ứng dụng

1 2 BỘ GIÁO DỤC VÀ ĐÀO TẠO Công trình ñược hoàn thành tại ĐẠI HỌC ĐÀ NẴNG ĐẠI HỌC ĐÀ NẴNG TRẦN LÊ HẠNH ĐOAN Người hướng dẫn khoa học: PGS.TSKH.Trần Quốc Chiến NGUYÊN LÝ BAO HÀM & LOẠI TRỪ VÀ Phản biện 1: TS. Cao Văn Nuôi ỨNG DỤNG Phản biện 2: PGS. TS. Trần Đạo Dõng Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60.46.40 Luận văn sẽ ñược bảo vệ tại Hội ñồng chấm Luận văn tốt nghiệp thạc sĩ khoa học tại Đại học Đà Nẵng ngày 29 tháng 05 năm 2011. TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC Có thể tìm hiểu luận văn tại: Đà Nẵng - Năm 2011 - Trung tâm thông tin - Học liệu, Đại học Đà Nẵng - Thư viện trường Đại học sư phạm, Đại học Đà Nẵng. 4 3 MỞ ĐẦU 2. Mục ñích nghiên cứu Từ các ứng dụng nguyên lý bao hàm và loại trừ giải lớp các bài 1. Lý do chọn ñề tài Cùng với sự phát triển với tốc ñộ nhanh của công nghệ thông toán tương tự cụ thể. tin, lý thuyết tổ hợp ñã trở thành lĩnh vực toán học quan trọng và cần 3. Đối tượng nghiên cứu thiết cho nhiều lĩnh vực khoa học và ứng dụng. Nhiều bài toán hiện Đối tượng nghiên cứu: nguyên lý bao hàm và loại trừ. nay ñược giải quyết bằng cách quy chúng về các bài toán tổ hợp. Phạm vi nghiên cứu: nội dung của nguyên lý bao hàm và loại Lý thuyết tổ hợp nghiên cứu việc phân bố, sắp xếp các phần tử của một hoặc nhiều tập hợp, thoả mãn một số ñiều kiện nào ñó. Các bài toán tổ hợp rất phong phú và ña dạng: bài toán tồn tại, bài toán ñếm, bài toán liệt kê và bài toán tối ưu. Trong các bài toán ñó thì bài toán ñếm ñược ứng dụng rộng rãi và ña dạng. Từ các cấu hình tổ hợp cơ bản người ta hình thành nên hệ thống các cấu hình tổ hợp mở rộng và nâng cao. trừ, ứng dụng của nguyên lý này. 4. Phương pháp nghiên cứu Gián tiếp thông qua các tài liệu: sách, giáo trình, tạp chí toán học tuổi trẻ, truy cập các trang web. Trực tiếp thông qua sự hướng dẫn của thầy và việc trao ñổi thảo luận với các bạn. 5. Ý nghĩa khoa học và thực tiễn Công thức xác ñịnh số phần tử của hợp một số tập hữu hạn Đề tài góp phần nghiên cứu, hỗ trợ học sinh khi học phần tổ thường ñược dùng trong nhiều bài toán ñếm. Một trong những công hợp, giải một số bài toán số học mà việc giải chúng có nhiều ứng thức ñó là nguyên lý bao hàm và loại trừ của tập hợp. Sử dụng dụng trong trong các lĩnh vực toán học, tin học. nguyên lý này và phối hợp một số phương pháp khác trên tập hợp 6. Nội dung luận văn chẳng hạn phương pháp ánh xạ, ta có thể giải một số dạng toán. 1) Mở ñầu Trong lý thuyết tổ hợp, nguyên lý bao hàm và loại trừ là 2) Chương 1. Đại cương về tổ hợp phương pháp ñếm nâng cao giải các bài toán ñếm, nó có nhiều ứng 3) Chương 2. Nguyên lý bao hàm và loại trừ dụng hay. Trong các kỳ thi học sinh giỏi quốc gia, thi Olympic toán 4) Chương 3. Ứng dụng của nguyên lý bao hàm và loại trừ quốc tế, thi Olympic sinh viên giữa các trường ñại học và cao ñẳng 5) Kết luận các bài toán liên quan ñến dạng này hay ñược ñề cập và thường thuộc loại rất khó. Chính vì các lý do trên, tôi ñã nghiên cứu và chọn: “NGUYÊN LÝ BAO HÀM & LOẠI TRỪ VÀ ỨNG DỤNG ” làm ñề tài luận văn thạc sĩ của mình. 6 5 CHƯƠNG 1. ĐẠI CƯƠNG VỀ TỔ HỢP Nếu ta ký hiệu số chỉnh hợp có lặp chập k của n phần tử của A bằng AR (n, k) thì 1.1 Sơ lược lịch sử AR (n, k) = nk 1.2 Các quy tắc ñếm cơ bản 1.2.1 Quy tắc tương ứng một – một. Nếu tồn tại tương ứng 1.3.2 Chỉnh hợp không lặp • Định nghĩa. Một chỉnh hợp không lặp chập k của n phần tử một – một giữa các phần tử của các tập hữu hạn A 1 và A 2 , thì A 1 khác nhau là một bộ có thứ tự gồm k thành phần lấy từ n phần tử ñã và A 2 có cùng số các phần tử. cho. Các thành phần không ñược lặp lại. Chỉnh hợp không lặp ñơn Giả sử A 1 , A 2 ,...A n là các tập hữu hạn bất kỳ. Ta ñịnh nghĩa giản gọi là chỉnh hợp. tích Đề-các của A 1 , A 2 ,...A n , kí hiệu là A 1 × A 2 ...× A n , là tập bao gồm tất cả các bộ có thứ tự ( a1 , a2 , ..., an ) gồm n thành phần a1 , a2 , ..., an sao cho a1 ∈ A1 , a2 ∈ A2 ,..., an ∈ An 1.2.2 Quy tắc nhân. Nếu A 1 , A 2 ,...A n là các tập hữu hạn bất kỳ và A 1 × A 2 ...× A n là tích Đề các của các tập ñó thì A1 × A2 × ... × An = A1 A2 ... An 1.2.3 Quy tắc cộng. Nếu A 1 , A 2 ,...A n là các tập hữu hạn ñôi một rời nhau, tức là Ai ∩ AJ = φ nếu i ≠ j thì Kí hiệu số các chỉnh hợp chập k của n phần tử của A là A(n, k) ta có  n!  A ( n, k ) =  ( n − k ) !  0 1.3 Cấu hình tổ hợp cơ bản 1.3.1 Chỉnh hợp lặp • Định nghĩa. Một hoán vị của n phần tử khác nhau là một cách sắp xếp thứ tự các phần tử ñó. Hoán vị có thể coi là trường hợp riêng của chỉnh hợp không lặp chập k của n trong ñó k = n. Ta có số hoán vị là P(n) = n! 1.3.4 Hoán vị vòng quanh Số hoán vị vòng quanh của n phần tử khác nhau ( Qn ) ñược tính bằng công thức Qn = (n − 1)! • Định nghĩa. Một chỉnh hợp lặp chập k của n phần tử khác nhau là một bộ có thứ tự gồm k thành phần lấy từ n phần tử ñã cho. Các thành phần có thể ñược lặp lại. khi k > n 1.3.3 Hoán vị không lặp A1 ∪ A2 ∪ ... − ∪ An = A1 + A2 + ... + An Ở ñây Ai là lực lượng ( số các phần tử ) của tập A i khi k ≤ n 1.3.5 Tổ hợp • Định nghĩa. Một tổ hợp chập k của n phần tử khác nhau là một bộ không kể thứ tự gồm k thành phần khác nhau lấy từ n phần tử 7 8 ñã cho. Nói cách khác ta có thể coi một tổ hợp chập k của n phần tử với m = m1 + m2 + ... + mn . khác nhau là một tập con có k phần tử từ n phần tử ñã cho. • Hệ quả. Giả sử tập S có n phần tử, trong ñó có n1 phần tử Nếu ta ký hiệu số tổ hợp chập k của n phần tử của A bằng C(n, kiểu 1, n2 phần tử kiểu 2, ... , nk phần tử kiểu k. Khi ñó số các hoán k) thì vị n phần tử của S là  n! khi 1 ≤ k ≤ n  C (n, k ) =  k!(n − k )! 0 khi k > n  P ( n ; n 1 , n 2 , . .. , n k Mỗi tổ hợp chập k của n phần tử của A có thể xem như là 1 tập ) = n! n 1 ! n 2 ! . . .n k ! 1.4.2 Tổ hợp lặp con lực lượng k của A. Vì vậy C(n, k) chính bằng số các tập con lực • Định nghĩa. Tổ hợp lặp chập k từ n phần tử khác nhau là lượng k của A. Với k = 0, vì chỉ có 1 tập con của A lực lượng 0 là tập một nhóm không phân biệt thứ tự gồm k phần tử trích từ n phần tử ñã rỗng nên ta có thể ñịnh nghĩa một cách tự nhiên rằng C(n, 0) = 1. Khi cho, trong ñó các phần tử có thể ñược lặp lại. ñó ñẳng thức C (n, k ) = • Định lý 2. Giả sử X có n phần tử khác nhau. Khi ñó số tổ n! cũng ñúng cho cả k = 0. k !(n − k )! hợp lặp chập k từ n phần tử của X, ký hiệu CR(n, k), là 1.4 Cấu hình tổ hợp mở rộng CR(n, k) = C(k + n – 1, n - 1) = C(k + n – 1, k). 1.4.1 Hoán vị lặp 1.4.3 Phân hoạch của tập hợp. Số Sterling loại 2 và số Bell • Định nghĩa. Hoán vị lặp là hoán vị trong ñó mỗi phần tử Giả sử A là tập hữu hạn với A = n , còn k là 1 số nguyên ñược ấn ñịnh một số lần lặp lại cho trước. Ký hiệu số các hoán vị có lặp của các phần tử a 1 , a 2 , ... , a n với tham số lặp m1 , m2 , ..., mn là P ( m; m1 , m2 , ..., mn ) . • Định lý 1. Số hoán vị lặp của n phần tử khác nhau, trong ñó phần tử thứ nhất lặp m1 lần, phần tử thứ hai lặp m2 lần, ... , phần tử dương. Ta cũng giả sử A1 = A . S là sơ ñồ sắp xếp “tập { X1 , X 2 , ... , X k } với X1 , X 2 , ... , X k cũng là các “tập” ñể ta xếp các phần tử của A 1 vào ”, R1 là ñiều kiện “mọi phần tử của A 1 ñều ñược sắp xếp vào một trong các “tập” X1 , X 2 , ... , X k ”, R2 là ñiều kiện “với mọi i = 1, ... , k có ít nhất một phần tử của thứ n lặp mn lần là m! P (m; m1, m2,...mn) = m !m !...m ! 1 2 n A1 ñược xếp vào Xi ”. 10 9 Khi ñó, một cấu hình tổ hợp trên A1 theo S thỏa mãn các ñiều kiện R1 và R2 ñược gọi là một phân hoạch của A thành k khối. Số tất cả các phân hoạch thành k khối của một tập A lực lượng 1.4.5 Phân hoạch không thứ tự tổ hợp • Định nghĩa. Cho X là tập n phần tử khác nhau, các số nguyên dương n1 , n2 , ... , nk và p1 , p2 , ... , pk thỏa n1 p1 + n 2 p 2 + ... + n k p k = n n ñược gọi là số Sterling loại 2 và ñược ký hiệu là S(n, k). Dễ thấy rằng S(n, k) = 0 nếu k > n. Ta cũng quy ước rằng S(n, 0) = 0. Số Tn = S(n, 1) + S ( n, 2 ) + ... + S(n, n) ñược gọi là số Bell. Như vậy, số Bell chính là số tất cả các phân hoạch của tập A lực lượng n. Việc tính S(n, k) và Tn sẽ ñược trình bày trong phần ứng dụng của nguyên lý bao hàm và loại trừ. 1.4.4 Phân hoạch thứ tự tổ hợp • Định nghĩa. Cho X là tập n phần tử khác nhau, r ≤ n và S ⊂ X có r phần tử. Một phân hoạch {S1 , S2 , ... , Sn } có thứ tự của S gọi là 1 phân hoạch thứ tự tổ hợp chập r của X. Nếu r = n, thì gọi là các số nguyên dương n1 , n2 , ... , nk thỏa n1 + n2 + ... + nk = r . Số các phân hoạch thứ tự tổ hợp chập r của X dạng {S1 , S2 , ... , Sk } có S1 = n1 , S2 = n2 , ... , Sk = nk ñược ký hiệu là C ( n; n1 , n2 , ... , nk ) . • Định lý3. C ( n; n1 , n2 , ... , nk ) tập lực lượng n2 , ... , pk tập lực lượng nk gọi là phân hoạch không thứ tự của X. • Định lý 4. Số phân hoạch không thứ tự của X với p1 tập lực lượng n1 , p2 tập lực lượng n2 , ... , pk tập lực lượng nk là C (n; n1 ..., n1 , n2 ,..., n2 , nk ,..., nk ) n! = p1 p p p1! p2 !... pk ! p1!(n1!) p2 !(n2 !) 2 ... p k !(nk !) k (trong tử số C ( n; n1 , ..., n1 , n2 , ... , n2 , nk , ... , nk ) số n1 lặp lại p1 lần, số n2 lặp lại p2 lần,..., số nk lặp lại pk lần). ◊ Ví dụ 9 phân hoạch thứ tự của X. Cho Một hệ thống các tập con của X gồm p1 tập lực lượng n1 , p2 n! = = P(n; n1 , n2 , ..., nk , n − r ) n1 !.n2 !...nk ! ( n − r )! C ( n; n1 , n2 , ... , nk ) ñược gọi là hệ số ña thức. (i) Số cách chia 21 học sinh vào 3 lớp học buổi sáng, buổi chiều và buổi tối, mỗi lớp 7 sinh viên là C ( 21; 7, 7, 7 ) = 21! ( 7!) (phân hoạch thứ tự) 3 (ii) Số cách chia 21 học sinh thành 3 tổ, mỗi tổ 7 học sinh là C ( 21; 7, 7, 7 ) 3! = 21! ( 7!) 3 3! (phân hoạch không thứ tự).