Luận văn Nguyên lý bao hàm & loại trừ và ứng dụng

1 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG TRẦN LÊ HẠNH ĐOAN NGUYÊN LÝ BAO HÀM & LOẠI TRỪ VÀ ỨNG DỤNG Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60.46.40 TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC Đà Nẵng - Năm 2011 2 Công trình ñược hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: PGS.TSKH.Trần Quốc Chiến Phản biện 1: TS. Cao Văn Nuôi Phản biện 2: PGS. TS. Trần Đạo Dõng 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. Có thể tìm hiểu luận văn tại: - 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. 3 MỞ ĐẦU 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 tin, lý thuyết tổ hợp ñã trở thành lĩnh vực toán học quan trọng và cần thiết cho nhiều lĩnh vực khoa học và ứng dụng. Nhiều bài toán hiện nay ñược giải quyết bằng cách quy chúng về các bài toán tổ hợp. 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. Công thức xác ñịnh số phần tử của hợp một số tập hữu hạn thường ñược dùng trong nhiều bài toán ñếm. Một trong những công thức ñó là nguyên lý bao hàm và loại trừ của tập hợp. Sử dụng 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 chẳng hạn phương pháp ánh xạ, ta có thể giải một số dạng toán. Trong lý thuyết tổ hợp, nguyên lý bao hàm và loại trừ là phương pháp ñếm nâng cao giải các bài toán ñếm, nó có nhiều ứng dụng hay. Trong các kỳ thi học sinh giỏi quốc gia, thi Olympic toán quốc tế, thi Olympic sinh viên giữa các trường ñại học và cao ñẳng 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. 4 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 toán tương tự cụ thể. 3. Đối tượng nghiên cứu Đối tượng nghiên cứu: nguyên lý bao hàm và loại trừ. Phạm vi nghiên cứu: nội dung của nguyên lý bao hàm và loại 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 Đề 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. 6. Nội dung luận văn 1) Mở ñầu 2) Chương 1. Đại cương về tổ hợp 3) Chương 2. Nguyên lý bao hàm và loại trừ 4) Chương 3. Ứng dụng của nguyên lý bao hàm và loại trừ 5) Kết luận 5 CHƯƠNG 1. ĐẠI CƯƠNG VỀ TỔ HỢP 1.1 Sơ lược lịch sử 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 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 và A 2 có cùng số các phần tử. Giả sử A 1 , A 2 ,...A n là các tập hữu hạn bất kỳ. Ta ñịnh nghĩa 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ự ( )1 2, , ..., na a a gồm n thành phần 1 2 , , ..., n a a a sao cho 1 1 2 2 , ,..., n n a A a A a A∈ ∈ ∈ 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ì nn AAAAAA ...... 2121 =××× 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à i J A A φ∩ = nếu i j≠ thì nn AAAAAA +++=∪−∪∪ ...... 2121 Ở ñây i A là lực lượng ( số các phần tử ) của tập A i 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 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. 6 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ì AR (n, k) = nk 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ử 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 không ñược lặp lại. Chỉnh hợp không lặp ñơn giản gọi là chỉnh hợp. 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ó ( ) ( ) ! !, 0 n khi k n n kA n k khi k n  ≤ −=   > 1.3.3 Hoán vị không 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 ( ) n Q ñược tính bằng công thức ( 1)! n Q 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 ñã 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ử khác nhau là một tập con có k phần tử từ n phần tử ñã cho. 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, k) thì ( ) ( )      > ≤≤ −= nkkhi nkkhi knk n knC 0 1 !! ! , 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 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 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 rỗng nên ta có thể ñịnh nghĩa một cách tự nhiên rằng C(n, 0) = 1. Khi ñó ñẳng thức !( , ) !( )! n C n k k n k = − cũng ñúng cho cả k = 0. 1.4 Cấu hình tổ hợp mở rộng 1.4.1 Hoán vị lặp • Định nghĩa. Hoán vị lặp là hoán vị trong ñó mỗi phần tử ñượ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ử 1 2 , , . . . , n a a a với tham số lặp 1 2 , , ..., n m m m là ( )1 2; , , ..., nP m m m m . • Đị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 1 m lần, phần tử thứ hai lặp 2 m lần, ... , phần tử thứ n lặp n m lần là P (m; m1, m2,...mn) = m! m1!m2!...mn! 8 với 1 2 ... n m m m m= + + + . • Hệ quả. Giả sử tập S có n phần tử, trong ñó có 1 n phần tử kiểu 1, 2 n phần tử kiểu 2, ... , k n phần tử kiểu k. Khi ñó số các hoán vị n phần tử của S là ( )1 2 1 2 ! ; , , . . . , ! ! . . . ! k k n P n n n n n n n = 1.4.2 Tổ hợp lặp • Định nghĩa. Tổ hợp lặp chập k từ n phần tử khác nhau là 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ử ñã cho, trong ñó các phần tử có thể ñược lặp lại. • Định lý 2. Giả sử X có n phần tử khác nhau. Khi ñó số tổ hợp lặp chập k từ n phần tử của X, ký hiệu CR(n, k), là CR(n, k) = C(k + n – 1, n - 1) = C(k + n – 1, k). 1.4.3 Phân hoạch của tập hợp. Số Sterling loại 2 và số Bell Giả sử A là tập hữu hạn với A n= , còn k là 1 số nguyên dương. Ta cũng giả sử 1 A A= . S là sơ ñồ sắp xếp “tập { }1 2, , ... , kX X X với 1 2, , ... , kX X X cũng là các “tập” ñể ta xếp các phần tử của A 1 vào ”, 1 R 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” 1 2 , , ... , k X X X ”, 2 R là ñiều kiện “với mọi i = 1, ... , k có ít nhất một phần tử của 1 A ñược xếp vào i X ”. 9 Khi ñó, một cấu hình tổ hợp trên 1 A theo S thỏa mãn các ñiều kiện 1 R và 2 R ñượ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 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ố ( )( , 1) , 2 ... ( , ) n T S n S n 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à n T 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 { }1 2, , ... , nS S S 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à phân hoạch thứ tự của X. Cho các số nguyên dương 1 2 , , ... , k n n n thỏa 1 2 ... k n n n r+ + + = . Số các phân hoạch thứ tự tổ hợp chập r của X dạng { }1 2, , ... , kS S S có 1 1 2 2, , ... , k kS n S n S n= = = ñược ký hiệu là C ( )1 2; , , ... , kn n n n . • Định lý3. C ( ) ( )1 2 1 21 2 ! ; , , ... , ( ; , , ..., , ) !. !... ! ! k k k n n n n n P n n n n n r n n n n r = = − − C ( )1 2; , , ... , kn n n n ñược gọi là hệ số ña thức. 10 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 1 2 , , ... , k n n n và 1 2 , , ... , k p p p thỏa 1 1 2 2 ... k k n p n p n p n+ + + = Một hệ thống các tập con của X gồm 1 p tập lực lượng 1 n , 2 p tập lực lượng 2 n , ... , k p tập lực lượng k n 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 1 p tập lực lượng 1 n , 2 p tập lực lượng 2 n , ... , k p tập lực lượng k n là ( ) ( ) ( ) ( ) kpkkppk kk npnpnp n ppp nnnnnnnC !!...!!!! ! !!...! ,...,,,...,,...,; 21 221121 2211 = (trong tử số ( )1 1 2 2; , ..., , , ... , , , ... ,k kC n n n n n n n số 1n lặp lại 1p lần, số 2 n lặp lại 2 p lần,..., số k n lặp lại k p lần). ◊ Ví dụ 9 (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à ( ) ( )3 21! 21; 7, 7, 7 7! C = (phân hoạch thứ tự) (ii) Số cách chia 21 học sinh thành 3 tổ, mỗi tổ 7 học sinh là ( ) ( )3 21; 7, 7, 7 21! 3! 7! 3! C = (phân hoạch không thứ tự). 11 CHƯƠNG 2. NGUYÊN LÝ BAO HÀM VÀ LOẠI TRỪ 2.1 Nguyên lý bao hàm và loại trừ dạng kinh ñiển 2.1.1 Công thức 1 (Nguyên lý bao hàm và loại trừ cho hai tập hợp) Có bao nhiêu phần tử trong hợp của hai tập hữu hạn phần tử? Số các phần tử trong hợp hai tập A và B bằng tổng các phần tử của mỗi tập trừ ñi số phần tử của giao hai tập hợp, tức là A B A B A B∪ = + − ∩ Nếu A là một thành phần của X, phần bù của A trong X kí hiệu A . Nếu A, B là hai thành phần của X thì ( ) ( ) ( ) ( ) ( ) ( )[ ] ( )BAnbnAnXnBAnXnBAn ∩++−=∪−=∪ Nhưng ( )A B A B∪ = ∩ , vì vậy ( ) ( ) ( ) ( )( )n A B n X n A n B n A B∩ = − + + ∩   2.1.2 Công thức 2 (Nguyên lý bao hàm và loại trừ cho ba tập hợp) Với 3 tập A, B, C thì CBAACCBBACBACBA ∩∩+∩−∩−∩−++=∪∪ Cho tập hợp A và các tập con 1 2 3 , ,A A A A⊂ . Khi ñó 3213121321 321 AAAAAAAAAAA AAA ∩∩−∩+∩+−−− =∩∩ 12 2.1.3 Công thức 3 (Nguyên lý bao hàm và loại trừ dạng kinh ñiển) 1 1 2 1 1 2 1 2 1 2 1 2 1 1 1 1 1 2 1 ... ... ... ( 1) ... ... ( 1) ... ≤ ≤ ≤ < ≤ + + ≤ < < ≤ ∪ ∪ ∪ = − ∩ + + − ∩ ∩ ∩ + + − ∩ ∩ ∩ ∑ ∑ ∑ k k n i i i i n i i n k n i i i n i i i n X X X X X X X X X X X X Hay 11 2 1 ... ( 1) ( , )− = ∪ ∪ ∪ = −∑ n k n k X X X X n k Trong ñó: X (n, k) = kn k iii nii XXX ∩∩∩∑ ≤<<≤ ... 2 1 ...1 Trong tổng X(n, k), bộ 1 2( , ,..., )ki i i lấy tất cả các tổ hợp chập k của n và như vậy X(n, k) là tổng của C(n, k) số hạng. Nói riêng ta có 1 2 ( , 1) ... n X n X X X= + + + và 1 2 ( , ) ... n X n n X X X= ∩ ∩ ∩ 2.1.4 Công thức 4 (Sieve) 1 2 0 . . . ( 1) ( , ) = ∩ ∩ ∩ = −∑ n k n k X X X X n k Trong ñó: X(n, 0) = X Và X(n, k) = 1 2 11 ... ... k k i i i i i n X X X ≤ < < ≤ ∩ ∩ ∩∑ ∀ k = 1,,n 2.1.5 Tổ hợp lặp tổng quát • Định nghĩa. Tổ hợp lặp tổng quát chập k từ n phần tử khác nhau là nhóm không phân biệt thứ tự gồm k phần tử trích từ n phần tử ñã cho, trong ñó phần tử thứ i lặp lại không quá i k lần (i = 1,..., n), với 1 ... n k k k+ + ≥ . 13 Nếu kí hiệu tổ hợp lặp tổng quát chập k từ n phần tử trong ñó phần tử thứ i lặp lại không quá i k lần (i = 1,..., n), với 1 ... n k k k+ + ≥ là ( )1 , ...,kn nC k k ta có ( ) ( ) ( ) ( )( ) 1 1 1 1 1 ... , ..., 1, 1 1 ... , 1 m m n mk n n i i m i i n C k k C k n k C n k k k m n = ≤ < < ≤   = + − + − − + − + + + −    ∑ ∑ 2.2 Nguyên lý bao hàm và loại trừ dạng tổng quát Cho tập X và tập { }1 ,..., mα αΠ = gồm m tính chất ñối với các phần tử của X. Với tập k ( )1 k m≤ ≤ tính chất { } 1 ,..., k i i α α ⊂ Π , ký hiệu 1 ,..., k i i X là tập phần tử trong X thỏa các tính chất 1 ,..., k i i α α và ( ) 1 1 ,..., ,..., k k i i i i n Xα α = Tiếp theo, ký hiệu 0 s X= ( ) 1 1 1 .... ,..., , 1, 2, ... , k k k i i i i m s n k mα α ≤ < < ≤ = ∀ = =∑ k e là số phần tử thỏa mãn ñúng k tính chất, k = 0, 1, ..., m Và k f là số phần tử thỏa mãn ít nhất k tính chất, k = 0, 1, ..., m • Công thức 5 ( ) ( ) ( ) ( )1 21, 1 . 2, 2 . ... 1 , . k m k k k k m e s C k s C k s C m m k s − + += − + + + − + − − • Công thức 6 k k f s= − ( ) ( ) ( ) ( )1 2, 1 . 1, 2 . ... 1 1, .m kk k mC k s C k s C m m k s−+ ++ + − + − − − 14 CHƯƠNG 3. ỨNG DỤNG CỦA NGUYÊN LÝ BAO HÀM VÀ LOẠI TRỪ Dựa vào nguyên lý bao hàm và loại trừ ta có thể ñếm ñược số phần tử trong một tập X không thoả mãn bất kỳ một tính chất nào trong n tính chất. Thật vậy, với mọi k = 1, 2 , n kí hiệu X k = { x X∈ / x thoả mãn tính chất k }. Khi ñó kX = { x X∈ / x không thoả mãn tính chất }. Như vậy, số phần tử trong X không thoả mãn một tính chất nào trong n tính chất bằng số phần tử của tập hợp 1 n i i X = I . Ta có thể tính ñược 1 n i i X = I bằng cách sử dụng công thức Sieve. Theo ý tưởng của nguyên lý bao hàm và loại trừ , có một số bài toán, việc ñếm trực tiếp các cấu hình thoả yêu cầu nhiều khi phức tạp, khi ñó ta thường giải bài toán ngược (hay bài toán lấy phần bù) ñể từ ñó suy ra kết quả yêu cầu. Ta có ví dụ sau: Ví dụ Một túi ñựng 15 quả cầu ñỏ, 7quả cầu xanh. Chọn ngẫu nhiên 10 quả cầu. Hỏi có bao nhiêu cách chọn ñể trong 10 quả ñó có nhiều nhất là 6 quả màu xanh? Giải. Chọn 10 quả cầu bất kỳ trong 22 quả cầu, số cách chọn là 22!(22,10) 646.646 10!(22 10)!C = =− Chọn 10 quả cầu trong ñó có ñúng 7 quả cầu xanh và 3 quả cầu ñỏ, số cách chọn là C(7,7).C(3,15) = 455 15 Vậy số cách chọn ñể trong 10 quả ñó có nhiều nhất là 6 quả màu xanh là: 646646 – 455 = 646191 (Chú ý: Nếu giải một cách trực tiếp thì ta phải chia thành 7 trường hợp) 3.1. Bài toán ñếm số nguyên dương không chia hết cho một số Có bao nhiêu số nguyên dương từ 1 ñến 1000 mà không chia hết cho 2, không chia hết cho 3 và cũng không chia hết cho 7? Giải. Ký hiệu A ={1, 2, 3,,1000}, 2A = {a A∈ / a không chia hết cho 2}, A 3 = {a A∈ / a không chia hết cho 3}, A 7 = {a A∈ / a không chia hết cho 7}. Khi ñó 2 3 7\ ( )A A A A∪ ∪ là tập tất cả các số từ 1 ñến 1000 mà không chia hết cho 2, không chia hết cho 3 và cũng không chia hết cho 7. Theo nguyên lý bao hàm và loại trừ , ta có 2 3 7 2 3 7\ ( )A A A A A A A A∪ ∪ = − ∪ ∪ = 1000 -714 =286 3.2. Bài toán xác ñịnh số nghiệm nguyên của một phương trình với một số ràng buộc nào ñó Phương trình 1 2 3 11x x x+ + = có bao nhiêu nghiệm, trong ñó x 1 , x 2 và x 3 là các số nguyên không âm với 1 3x ≤ , 2 4x ≤ và x 3 6≤ ? Giải. Để áp dụng nguyên lý bao hàm và loại trừ, gọi tổng số nghiệm là A ; nghiệm có tính chất A 1 là 1 3x > , có tính chất A 2 là 16 2 4x > và có tính chất A 3 là 3 6x > . Khi ñó số nghiệm thỏa mãn các bất ñẳng thức 1 3x ≤ , 2 4x ≤ và x 3 6≤ bằng 1 2 3 A A A∩ ∩ = 1 2 3 1 2 1 3 2 3 1 2 3 A A A A A A A A A A A A A− − − + ∩ + ∩ + ∩ − ∩ ∩ = 78 - 36 - 28 - 15 + 6 + 1 + 0 – 0 = 6. 3.3. Sàng Eratosthenes Nguyên lý bù trừ cũng có thể ñược dùng ñể tìm số các số nguyên tố nhỏ hơn một số nguyên dương nào ñó. Cần nhớ rằng một hợp số chia hết cho một số nguyên tố không lớn hơn căn bậc hai của nó. Do ñó, ñể tìm các số nguyên tố không vượt quá 100 thì ñiều cần chú ý ñầu tiên là một hợp số nhỏ hơn 100 phải có một thừa số nguyên tố không lớn hơn 10. Vì nhỏ hơn 10 chỉ có các số nguyên tố là 2, 3, 5, 7, nên các số nguyên tố không vượt quá 100 gồm bốn số nguyên tố trên và tất cả các số nguyên dương nhỏ hơn 100 không chia hết cho 2, 3, 5, 7. Để áp dụng nguyên lý bao hàm và loại trừ , ta gọi 1 A là tính chất chia hết cho 2, 2 A là tính chất chia hết cho 3, 3 A là tính chất chia hết cho 5, 4 A là tính chất chia hết cho 7. Vậy số nguyên tố không vượt quá 100 là 1 2 3 4 A A A A∩ ∩ ∩ + 4 = 21 + 4 = 25 Do ñó có 25 số nguyên tố không vượt quá 100. 3.4. Bài toán ñếm số các số nguyên dương nhỏ hơn số nguyên dương n và nguyên tố cùng nhau với n ( ϕ - hàm Euler) Hai số nguyên ñược gọi là nguyên tố cùng nhau nếu chúng không có ước số chung khác 1. Với mỗi số nguyên dương n, ký hiệu 17 bằng ( )nϕ số các số nguyên dương nhỏ hơn hoặc bằng n mà nguyên tố cùng nhau với n. Hàm ( )nϕ ñược gọi là ϕ - hàm Euler. Bài toán: Hãy tính giá trị của ( )nϕ theo n. Giải. Giả sử n = 1 21 2 ... αα α k kp p p là phân tích chính tắc của n thành tích các thừa số nguyên tố, ở ñây 1 2, ,..., kα α α là các số nguyên dương. Ta cũng giả sử A = {1, 2, ,n}, A { / ip a A= ∈ a chia hết cho p i }, i = 1, 2, ,k. Khi ñó , ip i nA p = ( ),... i jp p i j nA A i j p p ∩ = ≠ Áp dụng nguyên lý bao hàm và loại trừ , ta ñược 1 1 ( ) \ ( ... ) ... k kp p p p n A A A A A Aϕ = ∪ ∪ = − ∪ ∪ 1 1 1 2 1 1 2... 1 2 ... ... ... ( 1) 1 1 11 1 .... 1 k k k k k k n n n n n n p p p p p p p p p n p p p + −   = − + + − − − + + −        = − − −         3.5. Bài toán tìm số xáo trộn của một hoán vị có n phần tử Trước tiên ta lưu ý: Cho tập hợp có n phần tử. Khi ñó mỗi hoán vị của n phần tử trên sao cho không có phần tử nào ở nguyên vị trí ban ñầu ñược gọi là một xáo trộn của tập n phần tử ñã cho. Số tất cả các xáo trộn ñược gọi là số mất thứ tự. Ví dụ hoán vị 21453 là một xáo trộn của 12345 vì không có số nào ở nguyên vị trí ban ñầu của nó. Tuy nhiên, 21543 không phải là một xáo trộn của 12345 vì hoán vị này ñể số 4 ở nguyên vị trí ban ñầu của nó. 18 Giả sử kí hiệu D n là số mất thứ tự của một tập có n phần tử. Bây giờ ta xét bài toán sau: Bài toán: Hãy tìm số mất thứ tự của một tập có n phần tử. Giải . Giả sử A là tập tất cả các hoán vị của tập X, {iA a A= ∈ / ix là ñiểm bất ñộng của a}. Khi ñó A\ ( 1 ... nA A∪ ∪ ) là tập tất cả các hoán vị của x mà không có ñiểm bất ñộng nào. Theo nguyên lý bao hàm và loại trừ , ta có 1 1 1 1 1 ... ... ( 1) ... ,nn i i j n i n i j n A A A A A A A+ ≤ ≤ ≤ < ≤ ∪ ∪ = − ∩ + + − ∩ ∩∑ ∑ Vậy 1 1\ ( ... ) ...n n nD A A A A A A= ∪ ∪ = − ∪ ∪ 1 1 1 1! 1 ... ( 1) 1! 2! 3! !   = − + − + + −    nn n 3.6. Bài toán bỏ thư. Có n lá thư và n phong bì ghi sẵn ñịa chỉ. Bỏ ngẫu nhiên các thư vào các phong bì sao cho mỗi phong bì chỉ chứa một thư. a) Hỏi xác suất ñể không lá thư nào ñúng ñịa chỉ bao nhiêu ? b) Hỏi xác suất ñể ñúng r lá thư ñúng ñịa chỉ là bao nhiêu ( )r n≤ ? Sử dụng nguyên lý bao hàm và loại trừ, ta có a) Xác suất cần tìm là 1 1 1 11 ... ( 1) 1! 2! 3! !   − + − + + −    n n b) Xác suất cần tìm là 1 1 1 1 ( 1)1 ... ! 1! 2! 3! ( )! − − − + − + +  −  n r r n r 19 3.7. Bài toán ñếm số các hàm toàn ánh. Nguyên lý bù trừ cũng có thể ñược dùng ñể xác ñịnh số các hàm toàn ánh từ tập có n phần tử ñến tập có k phần tử. Bài toán: Cho hai tập hợp X và Y có X n= , ,Y k= n k≥ . Hãy ñếm số toàn ánh từ tập X vào tập Y. Giải. Ký hiệu T là tập hợp tất cả các toàn ánh từ X vào Y. Theo nguyên lý bao hàm và loại trừ , ta có 0 ( 1 ) ( , ) ( ) = = − −∑ k r n r T C k r k r 3.8. Bài toán xếp n cặp vợ chồng (Lucas) Một bàn tròn có 2n ghế. Cần sắp n cặp vợ chồng sao cho ñàn ông ngồi xen kẽ ñàn bà và không có cặp vợ chồng nào ngồi cạnh nhau (có tính ñến vị trí ghế và thứ tự chỗ ngồi). Hỏi có bao nhiêu cách xếp? Giải. Gọi số phải tìm là n M . Theo nguyên lý bao hàm và loại trừ, ta có. 0 2 2. !. ( 1) (2 , ).( )! 2 kn n k n M n C n k k n k n k = = − − − − ∑ 3.9. Bài toán tính số Sterling loại 2 Bài toán: Tính số Sterling loại hai S ( ),n k qua n và k. Giải. Mỗi phân hoạch k khối của tập X có n phần tử có thể xem như một phân bố n phần tử của tập X vào k thùng 1,..., kB B (không kể thứ tự) sao cho thùng nào cũng có phần tử của X. Hoán vị các thùng 1,..., kB B , ta thấy một phân bố như vậy sẽ sinh k! hàm toàn ánh từ tập X vào tập { }1,..., kB B . Suy ra 20 0 0 1! ( , ) ( 1) ( , )( ) ( , ) ( 1) ( , )( ) ! k k r n r n r r k S n k C k r k r S n k C k r k r k = = = − − ⇒ = − −∑ ∑ 3.10. Một số bài toán sử dụng nguyên lý bao hàm và loại trừ trong kỳ thi Olympic quốc tế, thi học sinh giỏi quốc gia và tạp chí toán học tuổi trẻ. Bài 1 Một hoán vị { }1 2, , , ... , nx x x của tập hợp { }1, 2, ... , 2n với n nguyên dương, ñược gọi là có tính chất P nếu 1i i x x n+− = , với ít nhất một giá trị { }1, 2, ... , 2 1i n∈ − . Chứng minh rằng với mỗi số n, số hoán vị có tính chất P lớn hơn số hoán vị không có tính chất P. Giải. Đặt M = { }1, 2, ... , , 1, 2, ... ,2n n n n+ + . Lưu ý ( )1 1n n− + = và ( )2 2n n− + = . Gọi kA là tập tất cả các hoán vị của M sao cho trong các hoán vị ñó, hai phần tử k và k + n ñứng kề nhau. Gọi A là tập tất cả các hoán vị có tính chất P. Ta thấy k k A A=U nên ... k k k h k h m k k h k h mk A A A A A A A A < < < = = − ∩ + ∩ ∩∑ ∑ ∑U Vì ñây là tổng các số hạng của dãy ñơn ñiệu giảm và ñan dấu nhau nên k k h k k h A A A A < ≥ − ∩∑ ∑ Ngoài ra ( )2 2 1 !kA n= − và ( )4 2 2 !k hA A n∩ = − Do ñó ( ) ( 1)2 2 ! 2 (2 1) .4 2 n n A n n n − ≥ − − −   21 = 2n 2 (2n - 2)! > ( )2 ! 2 n Bài 2 Cho hai số nguyên dương m và n sao cho n + 2 chia hết cho m. Hãy tính các bộ ba số nguyên dương ( ), ,x y z sao cho tổng x y z+ + chia hết cho m, trong ñó mỗi số x, y, z ñều không lớn hơn n. Giải. Đặt k = *2n N m + ∈ . Ta có n = km – 2. Xét các tập hợp: D = { }1,km km− ; E = { }1, 2,..., ;km ( ){ }, , , , \ ;A x y z x y z E D x y z m= ∈ + + M ; ( ){ }, , , , ; ;B x y z x y z E x y z m= ∈ + + M ( ){ , , , , ;C x y z x y z E x D= ∈ ∈ hoặc y D∈ hoặc ;z D∈ }; .x y z m+ + M Ta có A B C= − • Tính B . Có km cách chọn x ∈ E. Với mỗi cách chọn x ∈ E, ta có km cách chọn y ∈ E. Với mỗi cách chọn x và y như trên, ta có k cách chọn z∈ E sao cho x + y + z M m. Do ñó B = km.km.k = 3 2 k m . • Tính C . Đặt ( ){ }, , , , , ,X x y z x D y E z E x y z m= ∈ ∈ ∈ + + M 22 ( ){ }, , , , , ,Y x y z y D x E z E x y z m= ∈ ∈ ∈ + + M ( ){ }, , , , , ,Z x y z z D x E y E x y z m= ∈ ∈ ∈ + + M Khi ñó C X Y Z= ∪ ∪ . Do ñó C X Y Z X Y X Z Y Z X Y Z= + + − ∩ − ∩ − ∩ + ∩ ∩ Tương tự 22X Y Z k m= = = , 4 ,X Y X Z Y Z k∩ = ∩ = ∩ = ( ) ( ) 4 2 1, 2, 3 1 3 m khi m X Y Z m khi m τ − = ∩ ∩ = = ∗ > Do ñó ( )26 12C k m k mτ= − + . Thay k = 2n m + ñược ( ) 3 8n A B C m m τ + = − = − với ( )mτ xác ñịnh bởi ( )∗ Bài 3 (VMO-1995, Bảng B). Hỏi từ các số 1, 2, 3, 4, 5 có thể lập ñược bao nhiêu số có 10 chữ số thỏa mãn ñồng thời các ñiều kiện sau: 1) Trong mỗi số, mỗi chữ số có mặt ñúng hai lần; 2) Trong mỗi số, hai chữ số giống nhau không ñứng cạnh nhau ? Giải. Gọi s là số cần tìm và A là tập gồm tất cả các số có 10 chữ số, lập ñược từ các chữ số 1, 2, 3, 4, 5 thỏa mãn ñiều kiện 1 của ñề bài. Khi ñó, theo nguyên lý bao hàm và loại trừ ta tính ñược: 5 10! 2 A = 1 2 3 4 5 5 5 55 4 3 2 1 0 10! 9! 8! 7! 6! 5! 39480 2 2 2 2 2 2 s C C C C= − + − + − = 23 Bài 4 Một cuộc hội thảo toán học quy tụ 1990 nhà toán học trên toàn thế giới. Cho biết cứ mỗi nhà toán học ñều ñã có dịp làm chung với 1327 nhà toán học khác tham dự hội thảo. Chứng minh rằng ta có thể tìm ñược 4 nhà toán học từng ñôi một ñã làm việc chung với nhau. Giải. Mỗi nhà toán học ñược xem như là một ñiểm. Hai nhà toán học ñã làm việc chung với nhau xem như 2 ñiểm ñược nối với nhau bởi một ñoạn thẳng. Lý luận tương tự như bài toán trên ñây, gọi 1 v và 2 v là 2 ñiểm ñược nối với nhau. Gọi A là tập hợp các ñiểm khác v 2 ñược nối với v 1 và B là tập hợp các ñiểm khác v 1 ñược nối với v 2 . Lúc ñó: 2 1326 1998 664A B A B A B∩ = + − ∪ = × − = Nghĩa là ta có thể tìm ñược nhà toán học 3 v ñã làm việc chung với 1 v và v 2 . Gọi C là tập hợp các ñiểm ñược nối với v 3 nhưng không nối với 1 v và v 2 . Ta có 1325C ≥ , vậy ( )1998 A B C A B C A B C≥ ∩ ∪ = ∩ + − ∩ ∩ Nghĩa là 1998 664 1325 1988 1 0A B C A B C∩ ∩ ≥ ∩ + − ≥ + − = > Vậy A B C∩ ∩ ≠ ∅ và ta tìm ñược 4 v A B C∈ ∩ ∩ . Tập hợp gồm 4 nhà toán học 1 2 3 4 , , ,v v v v ñã làm việc với nhau từng ñôi một và ñó là ñpcm. Bài 5 Cho 167 tập hợp 1 2 167 , , ...A A A thỏa mãn các ñiều kiện sau: 24 ( ) 167 1 1 | | 2004; i i A = =∑ ( )2 j i i jA A A A= ∩ với mọi i, j { }1, 2, ....,167∈ và i j≠ Tính 167 1 i i A = U . Giải. • Ta có . j i j i A A A A= ∩ ; . i j i j A A A A= ∩ Suy ra 2 . i i i j A A A A= ∩ Nếu 0 i A = thì từ ( )2 suy ra 0,jA j i= ∀ ≠ . Điều này mâu thuẫn với (1). Vậy 0 i A ≠ . Do ñó ( )1i jA A i j∩ = ≠ và i jA A= . Do ñó 12, i A i= ∀ • Xét tập A 1 . Mỗi tập 2 167 , ... ,A A ñều chứa và chỉ chứa 1 phần tử của A 1 . Không giảm tổng quát giả sử 14 tập 2 15 , ... ,A A cùng chứa phần tử 1 a A∈ . Ta sẽ chứng minh a i A∈ , i∀ . Thật vậy, giả sử tồn tại i > 15; i a A∉ . Đặt { }\i iB A a= Khi ñó với mỗi A ( )2, ... 15j j = ta có 1j iA A∩ = do ñó 1 j i A B∩ = . Giả sử j i j A B b∩ = . Ta có 1 2 j j b b≠ vì nếu 25 1 2 j j b b= thì hai tập hợp A 1 j và A 2 j có 2 phần tử chung là a và b 1 j trái với 1 i j A A∩ = . Như vậy 2 15 , ...,b b là 14 phần tử thuộc i A . Điều này không xảy ra vì 12. i A = Vậy với mọi i j≠ ta có { }i jA A a∩ = . Đặt { }\i iB A a= với mọi i thì i jB B∩ = ∅ với mọi i, j mà i j≠ . Do vậy: { } { }167 167 167 11 1 167.11 1 1838 i i i ii i A B a B a == = = ∩ = + = + =∑U U 26 KẾT LUẬN Đề tài nguyên lý bao hàm & loại trừ và ứng dụng bước ñầu ñã hệ thống hóa ñược một mảng kiến thức về giải các bài toán tổ hợp từ những dạng cơ bản ñến phức tạp hơn. Thông qua nghiên cứu lý thuyết về nguyên lý bao hàm và loại trừ, ñề tài ñã ứng dụng trong việc giải các bài toán tổ hợp có liên quan. Đặc biệt là những bài toán ứng dụng phương pháp sử dụng nguyên lý bao hàm và loại trừ. Từ nguyên lý bao hàm và loại trừ ta có thể giải ñược lớp các bài toán có nhiều ứng dụng trong thực tiễn, ñời sống. Bằng cách thay ñổi các tập hợp, số lượng tập hợp và quan hệ giữa các phần tử ta có thể tạo ra nhiều bài toán khác nhau về nguyên lý bao hàm và loại trừ mà việc giải chúng giúp học sinh rèn luyện việc sử dụng linh hoạt các cấu hình tổ hợp cơ bản và mở rộng. Hơn nữa ñề tài cũng có hướng mở ñể tiếp tục nghiên cứu ứng dụng trong giải các bài toán phức tạp và các bài toán ứng dụng trong lĩnh vực tin học. Đây là một vấn ñề nghiên cứu khá hay, trong thời gian ñến tôi sẽ tiếp tục dành thời gian cho việc nghiên cứu vấn ñề này.