Chuyên đề Tổ hợp - Nguyên lý bù trừ

Nội dung text: Chuyên đề Tổ hợp - Nguyên lý bù trừ

1. MỞ ĐẦU Lý thuyết tổ hợp là một phần quan trọng của toán học rời rạc chuyên nghiên cứu sự sắp xếp các đối tượng.Thông thường các phần tử này là hữu hạn và việc phân bố chúng phải thoả mãn những điều kiện nhất định nào đó, tùy theo yêu cầu của bài toán cần nghiên cứu. Chủ đề này được nghiên cứu từ thế kỷ 17 khi những câu hỏi về tổ hợp được nêu ra trong những công trình nghiên cứu của các trò chơi may rủi. Liệt kê, đếm, sắp xếp các đối tượng có những tính chất nào đó là một phần quan trọng của lý thuyết tổ hợp. Một bài toán khác trong lý thuyết tổ hợp là việc tạo ra các cách sắp xếp theo một kiểu nào đó. Vấn đề này rất quan trọng trong các mô phỏng máy tính. Chúng ta cũng sẽ đưa ra những thuật toán tạo các cách sắp xếp theo nhiều kiểu khác nhau. Các bài toán tổ hợp có đặc trưng bùng nổ tổ hợp với số cấu hình tổ hợp khổng lồ. Việc giải chúng đòi hỏi một khối lượng tính toán khổng lồ (có trường hợp mất hàng chục năm). Vì vậy trong thời gian dài, khi mà các ngành toán học như phép tính vi phân, phép tính tích phân, phương trình vi phân phát triển như vũ bảo, thì nó như nằm ngoài sự phát triển và ứng dụng của toán học. Tình thế thay đổi từ khi xuất hiện máy tính và sự phát triển của toán học hữu hạn. Nhiều vấn đề tổ hợp đã được giải quyết trên máy tính. Từ chỗ chỉ nghiên cứu các trò chơi, tổ hợp đã trở thành ngành toán học phát triển mạnh mẽ, có nhiều ứng dụng trong các lĩnh vực toán học phát triển mạnh mẽ, có nhiều ứng dụng trong lĩnh vực toán học, tin học Khi hai công việc có thể được làm đồng thời, chúng ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả 2 việc cộng số cách làm mỗi việc sẽ dẫn đến sự trùng lập, vì những cách làm cả hai việc sẽ được tính 2 lần. Để tính đúng số cách thực hiện nhiệm vụ này cộng số cách làm mỗi 1 trong 2 việc rồi trừ đi số cách làm đồng thời cả 2 việc. Đó là nguyên lý bù trừ. 2
2. Chương I: ĐẠI CƯƠNG VỀ TỔ HỢP I. Sơ lược về toán học tổ hợp 1.1 Một số nguyên lý cơ bản 1.1.1. Nguyên lý nhân Giả sử một cấu hình tổ hợp được xây dựng qua k bước, bước 1 có thể được thực hiện n1 cách, bước 2 có thể được thực hiện n 2 cách, , bước k có thể được thực hiện n k cách. Khi đó số cấu hình tổ hợp là n1. n2 . nk 1.1.2. Nguyên lý cộng Giả sử {X1, X2, ,Xn} là một phân hoạch của tập S. Khi đó S X1 X2 Xn 1.2. Các cấu hình tổ hợp đơn giản Những cấu hình này thường được làm cơ sở cho phép đếm 1.2.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. Một chỉnh hợp lặp chập k của n có thể xem như một phần tử của tích Đề-Các Xk, với X là tập n phần tử. Như vậy số tất cả các chỉnh hợp lặp chập k của n là nk 1.2.2. Chỉnh hợp không lặp Định nghĩa: Một chỉnh lợ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. Một chỉnh hợp không lặp chập k của n có thể được xây dựng qua k bước kế tiếp như sau: Chọn thành phần đầu tiên: có n khả năng Chọn thành phần thứ hai: có n -1 khả năng Chọn thành phần thứ k: có n – k + 1 khả năng Như vậy theo nguyên lý nhân, số tất cả chỉnh hợp không lặp chập k của n phần tử là n! A(n,k) = n(n - 1) . (n – k + 1) = (n k)! 3
3. 1.2.3. Hoán vị Đị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 như 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.2.4. 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ử đã 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. Ký hiệu số tổ hợp chập k của n phần tử là C(n, k). Ta có A(n, k) = C(n, k).k! Suy ra n! C(n, k) = k!(n k)! 1.2.5. 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 số lần lặp cho trước. Định lí Số hoán vị lặp của k phần tử khác nhau trong đó số phần tử thứ nhất lặp n 1 lần, số phần tử thứ 2 lặp n2 lần, , số phần tử thứ k lặp nk lần là n! P( n; n1, n2, nk ) = n1 !n2 ! nk ! Hệ quả Giả sử tập S có n phần tử khác nhau, trong đó có n 1 phần tử kiểu 1, n 2 phần tử kiểu 2, , nk phần tử kiểu k. Khi đó số các hoán vị n phần tử của tập S là n! P( n; n1, n2, , nk ) = n1 !n2 ! nk ! 1.2.6. Tổ hợp lặp: Định nghĩa: 4
4. Tổ hợp lặp chập k từ n phần tử 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ể lặp lại. Định lý: 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) 5
5. Chương II: NGUYÊN LÝ BÙ TRỪ Công thức 1: Cho 2 tập hợp A,B. Theo nguyên lý cộng ta có: A  B = A +B - A  B Công thức 2: Cho tập hợp X và n tập con X1, X2 , , Xn, ta có: n k 1 X 1  X 2   X n = ( 1) X (n,k) k 1 Trong đó: X(n,k)= x  x   x  i1 i2 ik 1 i1 ik n Trong tổng X(n,k), bộ (i 1,i2, ,ik) 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ó X(n,1) =X1 +X 2 + + X n và X(n,n) = X1  X 2   X n Từ công thức 2,sử dụng tính chất: X1  X 2   X n X1  X 2   X n = X X1  X 2   X n Ta nhận được công thức sau: n k Công thức 3 (Sieve): X 1  X 2   X n  ( 1) X (n, k) k 0 Trong đó: X(n,0) = X X(n,k)= X  X   X k 1 ,n  i1 i2 ik 1 i1 ik n Bây giờ: ta cho các tính chất 1, , n trên tập X. Xét bài toán: * Bài toán đếm số phần tử trong X không thỏa mãn một tính chất k nào cả Giải: Với mọi k =1, .,n ta có ký hiệu: Xk= x X x thỏa mãn k  Như vậy phần bù của Xk là: 6
6. X k = x X x không thỏa mãn k  Ký hiệu N là số cần đếm, theo công thức 3 ta có: n k N=X1  X 2   X n X ( 1) X (n,k ) k 1 trong đó X(n,k)= X  X   X k 1 ,n  i1 i2 ik 1 i1 ik n 7
7. Chương III: MỘT SỐ VÍ DỤ VÀ BÀI TOÁN ỨNG DỤNG 3.1. Các ví dụ : Ví dụ 1: Lớp 10A có 40 học sinh. Nhà trường bắt buộc mỗi học sinh trong lớp phải học ít nhất một trong hai môn học tự chọn là Tin học hoặc Ngoại ngữ. Có 30 học sinh đăng kí học tin học, 20 học sinh đăng kí học Ngoại ngữ. Hỏi có bao nhiêu học sinh đăng kí học cả hai môn Tin học và Ngoại ngữ ? Giải: Gọi A là tập các học sinh đăng kí học môn Tin học, B là tập các học sinh đăng kí học môn Ngoại ngữ. Khi đó, tổng số học sinh của lớp 10A là A  B và số học sinh đăng kí học cả hai môn Tin học và Ngoại ngữ là A  B . Vì vậy: A  B = A +B - A  B A B A B A B 30 20 40 10 Vậy có 10 học sinh đăng kí học cả hai môn Tin học và Ngoại ngữ. Ví dụ 2: Đề thi học sinh giỏi toán của một trường phổ thông gồm 3 bài: hình học , đại số và tổ hợp. Có 100 em tham gia dự thi. Kết quả cho thấy có 80 em giải được bài hình học, 70 em giải được bài đại số, 50 em giải được bài tổ hợp, 60 em giải được bài hình học và đại số, 50 em giải được bài hình học và tổ hợp, 40 em giải được bài đại số và tổ hợp, 30 em giải được cả ba bài. Hỏi có bao nhiêu em giải được ít nhất một bài thi. Giải : Gọi A là tập các học sinh giỏi toán của trường . A1 là tập các học sinh giải được bài hình học. A2 là tập các học sinh giải được bài đại số. A3 là tập các học sinh giải được bài tổ hợp. Khi đó: A1  A2 là tập các học sinh giải được bài hình học và đại số A2  A3 là tập các học sinh giải được bài đại số và tổ hợp A1  A3 là tập các học sinh giải được bài hình học tổ hợp Số học sinh giải được ít nhất một bài thi là : A1  A2  A3 A1 A2 A3 ( A1  A2 A2  A3 A1  A3 ) A1  A2  A3 = 80 + 70 + 50 - 60 - 50 - 40 + 30 = 80 8
8. Ví dụ 3 : Trong tập hợp X = {1; 2; 3; ;10000} có bao nhiêu số không chia hết cho bất kỳ số nào trong các số 3;4;7? Giải : Gọi A1 là tập hợp các số thuộc tập X chia hết cho 3. A2 là tập hợp các số thuộc tập X chia hết cho 4 A3 là tập hợp các số thuộc tập X chia hết cho 7 Khi đó: A1  A2 là tập các số thuộc tập X chia hết cho 3 và 4 A2  A3 là tập các số thuộc tập X chia hết cho 4 và 7 A1  A3 là tập các số thuộc tập X chia hết cho 3 và 7 Khi đó: A1  A2  A3 là số phần tử thuộc tập X chia hết cho 3, hoặc 4 hoặc 7. Vậy số phần tử thuộc tập X không chia hết cho bất kỳ số nào trong các số 3;4;7 là: A1  A2  A3 A \ A1  A2  A3 A1  A2  A3 . 10000 10000 10000 Ta có: A1 3333, A2 2500, A3 1428 3 4 7 10000 10000 10000 A1  A2 833, A1  A3 476, A2  A3 357 3 4 3 7 4 7 10000 A1  A2  A3 119 3 4 7 Áp dụng công thức 3 (Sieve), ta có: A1  A2  A3 A ( A1 A2 A3 ) A1  A2 A1  A3 A2  A3 A1  A2  A3 = 10000 - ( 3333 + 2500 +1428 ) + 833 + 476 + 357 - 119 = 4286 Vậy số phần tử thuộc tập X không chia hết cho bất kỳ số nào trong các số 3;4;7 là 4286 Ví dụ 4 : Một cuộc hội thao cấp Tỉnh có 4 môn thi gồm : cầu lông, bóng bàn, chạy và cờ tướng. Đoàn A có 100 người bao gồm vận động viên và cổ động viên tham gia trong đó: môn cầu lông có 18 vận động viên, môn bóng bàn có 26 vận động viên, môn chạy có 19 vận động viên, môn cờ tướng có 24 vận động viên, có 5 người tham gia cả cầu lông và bóng bàn, 2 người tham gia cả cầu lông và chạy, 3 người tham gia cả cầu lông và cờ tướng, 5 người tham gia cả bóng bàn và chạy,4 người tham gia cả bóng bàn và cờ 9
9. tướng, 3 người tham gia cả cờ tướng và chạy, 2 người tham gia cả cầu lông, chạy và cờ tướng, 4 người tham gia cả bóng bàn, chạy và cờ tướng, 1 người tham gia cả bốn môn. Hỏi đoàn A có bao nhiêu người chỉ là cổ động viên. Giải : Gọi A là tập các vận động viên và cổ động viên tham gia hội thao. A1 là tập các vận động viên cầu lông. A2 là tập các vận động viên bóng bàn. A3 là tập các vận động viên chạy. A4 là tập các vận động viên cờ tướng. Khi đó: A1  A2  A3  A4 là số vận động viên tham gia ít nhất một môn. A1  A2  A3  A4 A \ A1  A2  A3  A4 A1  A2  A3  A4 là số cổ động viên. Áp dụng công thức 3 (Sieve): A1  A2  A3  A4 A ( A1 A2 A3 A4 ) A1  A2 A1  A3 A1  A4 A2  A3 A2  A4 A3  A4 ( A1  A2  A3 A1  A2  A4 A1  A3  A4 A2  A3  A4 ) A1  A2  A3  A4 100 (18 26 19 24) (5 2 3 5 4 3) (2 3 2 4) 1 25 Vậy đoàn A có 25 người chỉ là cổ động viên. Ví dụ 5 : Đếm số nghiệm nguyên không âm của phương trình x + y + z = 11, với 0 x 3, 0 y 4, 0 z 6 Giải : Gọi A là tập tất cả các nghiệm không âm của phương trình. A1 là tập nghiệm nguyên không âm của phương trình với x ≥ 4, A2 là tập nghiệm nguyên không âm của phương trình với y ≥ 5, A3 là tập nghiệm nguyên không âm của phương trình với z ≥ 7, Vậy số nghiệm cần tìm là A1  A2  A3 A1  A2  A34 A \ A1  A2  A3 A1  A  A =A -|A |-|A |-|A | + |A A | +|A A | +|A A |-|A A A | 2 3 1 2 3 1 2 1 3 2 3 1 2 3 Ta có A =C(13,2), |A1|+|A2|+|A3|=79, A1A2| +|A1A3| +|A2A3|=7 10
10. |A A A | = 0. Vậy A1  A  A = 6 1 2 3 2 3 3.2.Bài toán ứng dụng : 3.2.1.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 lá thư vào phong bì. i) Hỏi xác suất để không lá thư nào đúng địa chỉ là bao nhiêu ? ii) Hỏi xác suất để đúng r lá thư đúng địa chỉ là bao nhiêu ( r n) ? Giải: i) Gọi X là tập hợp tất cả các cách bỏ thư. Ta cóX n .! Gọi k(k là tính chất lá thư k gửi đúng địa chỉ, Xk là tập hợp cách bỏ thư sao cho lá thư k không gửi đúng địa chỉ (k = 1, .,n). Ký hiệu N(n,r) là só cách bỏ thư sao cho có đúng r lá thư đúng địa chỉ (r = 0, 1, ., n). Như vậy theo nguyên lý bù trừ số cách bỏ thư sao cho không có lá thư nào gửi đúng địa chỉ là. N(n,0) ( 1) k X (n,k) Trong đó N(n, 0) = X = n ! X (n,k) X  X   X k 1, ,n  i1 i2 ik 1 ik ik n Với mỗi bộ k lá thư i1, i2 , , ik ta có (n-k)! cách bỏ thư, tức hoán vị các lá thư còn lại, sao cho các lá thư i1 , i2, , ik bỏ đúng địa chỉ. Như vậy ta có: n ! X (n,k) = C(n,k).(n - k)! = k ! 1 1 1 1 Suy ra N(n,0) = n! 1 ( 1) n 1! 2! 3! n! 1 1 1 1 Như vậy xác suất cần tìm là: 1 ( 1) n 1! 2! 3! n! 11
11. Một điều lý thú là xác suất trên tiến đến 1/ e khi n . Số N(n,0) trên cũng chính là tổng số hoán vị f(i) của tập (1, 2, , n) thỏa mãn f(i) i . Vì vậy N(n,0) được gọi là số mất thứ tự và được ký hiệu là Dn. ii) Cho tổ hợp i1 , i2 , , ir Số cách bỏ thư để chỉ các lá thư i1 , i2 , , ir gửi đúng địa chỉ đúng bằng N(n-r, 0). Như vậy số cách bỏ thư để có đúng r lá thứ gửi đúng địa chỉ là: 1 1 n r 1 N(n,r) C(n,r).N(n r,0) C(n,r).(n r)! 1 ( 1) 1! 2! (n r)! n! 1 1 n r 1 1 ( 1) r! 1! 2! (n r)! 1 1 1 1 n r 1 Suy ra xác suất cần tìm là: 1 ( 1) r! 1! 2! 3! (n r)! 3.2.2. Bài toán xếp khách (Lucas): Một bàn tròn 2n ghế. Cần sắp n cặp vợ chồng sao cho đàn ông ngồi xen kẽ với đàn bà và không có cặp 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à M n . Xếp các bà trước (cứ một ghế xếp thì dể một ghế trống dành cho các ông). Với n ghế chẵn ta có n! cách xếp và với n ghế lẻ ta cũng có n! cách xếp. Như vậy số cách xếp các bà là 2.n !. Gọi số cách xếp các ông ứng với một cách xếp các bà là Un , ta có: Mn = 2.n ! Un Bây giờ ta đi tính Un Đánh số các bà (đã xếp) từ 1 đến n. Đánh số các ông tương ứng với các bà (ông i là chồng bà i). Đánh số các ghế trống theo nguyên tắc: ghế số i nằm giữa bà i và i + 1 (quy ước n +1 = 1). Mỗ cách xếp các ông được biểu diễn bằng một hoán vị f(i) của tập {1, 2, ,n} , tức ghế i được xếp cho ông f(i) . Để thỏa mãn yêu cầu bài toán f(i) phải thỏa mãn 12
12. f (i) i & f (i) i 1 (*) Như vậy số Un là số các hoán vị thỏa mãn (*). Số Un gọi là số phân bố. Xét tập hợp X các hoán vị f của {1, 2, .,n} . Ta gọi Pi là tính chất f(i) = i và Qi là tính chất f(i) = i +1 Ký hiệu P n+i là tính chất Q i. Tiếp theo ký hiệu Xi là các số hoán vị của trong X thỏa mãn tính chất Pi , i = 1, , 2n. Như vậy theo nguyên lý bù trừ số cách xếp chỗ là: 2n k U n ( 1) X (2n,k) k 0 Trong đó X (2n, 0) = X = n ! Và X(2n,k) = X  X   X k 1, ,2n  i1 i2 ik 1 i1 ik 2n Chú ý rằng không thể xảy ra đồng thời Pi và Qi hoặc đồng thời Pi+1 và Qi tức là: X i  X n i  & X i 1  X n i  i 1, ,n Như vậy ta có: X (2n,k) 0 k n n k Và kéo theo U n ( 1) X (2n,k) k 0 Gọi g(2n,k) là số cách lấy ra k tính chất thỏa mãn không thể xảy ra đồng thời P i và Qi hoặc đồng thời P i+1và Qi (g(2n,0) = 1). Và với mỗi cách lấy k tính chất như vậy ta có (n-k)! cách phân bố các tính chất còn lại. Như vậy ta có: n k U n ( 1) g(2n,k).(n k)! k 0 13
13. Bây giờ ta còn phải tính g(2n,k). Nếu xếp theo vòng tròn P 1 , Q1 , P2 , Q2 , ., Pn , Qn ta thấy g(2n,k) chính là số cách lấy ra k phần tử sao cho không có hai phần tử kề nhau. Đây chính là số cách xếp k số 0 với (2n - k) số 1 sao cho không có hai số 0 kề nhau. Ta có: 2n g(2n,k) = C(2n - k,k) 2n - k Như vậy số phân bố: n k 2n U n ( 1) .C(2n k,k).(n k)! k 0 2n k 3.2.3. Bài toán đếm số toàn ánh : Cho hai tập X, Y cóX n ,Y k,n k . Hãy đếm số toàn ánh từ X vào Y. Giải: Cho Y = {y1 , .,yk}. Ký hiệu là tập hợp tất cả các ánh xạ từ X vào Y, T là tập hợp tất cả toàn ánh từ X vào Y . Hiển nhiên S k n . Ký hiệu: Si f S / yi f (X ) i 1, ,k Theo nguyên lý bù trừ ta có: k T ( 1) r X (k,r). r 0 Trong đó: X (k, 0) = S = kn Và X (k,r) S  S   S r 1, ,k  i1 i2 ir 1 i1 ir k Do S  S   S là tập hợp các ánh xạ từ X vào Y \{y , , y }, nên i1 i2 ir 1 r n Si  Si   S (k r) 1 2 ir 14
14. Mặt khác, với mỗi r ta có C(k,r) bộ S , S , , S  r 1, ,k i1 i2 ir k Suy ra: T ( 1) r C(k,r).(k r) n r 0 15
15. KẾT LUẬN Nguyên lý bù trừ và ứng dụng là một phần quan trọng, hấp dẫn và lí thú của lý thuyết tổ hợp, nó khơi dậy khả năng toán học cho người học, đồng thời nó cũng kích thích được óc sáng tạo và tư duy định hướng cho người học. Bài toán này đã cuốn hút được sự quan tâm của nhiều người bởi tính đa dạng và sự ứng dụng của nó. Do vậy, việc học tập, nghiên cứu chủ đề này là rất bổ ích vì nó có thể giải quyết được nhiều vấn đề nảy sinh từ thực tế cuộc sống. Trong đề tài này, mặt dù nhóm em đã dành nhiều thời gian nghiên cứu, thảo luận, và được sự hướng dẫn chu đáo của Thầy PGS.TSKH.Trần Quốc Chiến nhưng do khả năng có hạn nên chắc chắn đề tài không tránh khỏi thiếu sót. Kính mong Thầy và các học viên trong lớp góp ý, bổ sung, chỉnh sửa để đề tài được hoàn thiện hơn. Thay mặt nhóm, em xin chân thành cảm ơn sự giúp đỡ và hướng dẫn nhiệt tình, tận tuỵ của Thầy PGS.TSKH.Trần Quốc Chiến, cũng như sự động viên, khích lệ của tập thể lớp để nhóm em hoàn thành tốt đề tài này. 16
16. TÀI LIỆU THAM KHẢO [1] Trần Quốc Chiến, Giáo trình lý thuyết tổ hợp [2] Nguyễn Văn Mậu (2008), Chuyên đề chọn lọc Tổ hợp và Toán rời rạc, NXB Giáo dục. [3] Tạp chí Toán học và tuổi trẻ 17