Chương 1 Những bài toán đếm Chương này ta sẽ nhắc lại một số lý thuyết về tập hợp cũng như lý thuyết cơ bản của tổ hợp như hoán vị, chỉnh hợp, tổ hợp, một số nguyên lý đếm và các bài tập có liên quan trong chương trình phổ thông.1 Cơ sở lý thuyết tổ hợp 1.1 Quy tắc cộng và quy tắc nhân 1. Quy tắc cộng Giả sử một công việc có thể thực hiện theo phương án A hoặc phương án B , trong đó có n cách thực hiện phương án A, m cách thực hiện phương án B. Khi đó công việc có thể được thực hiện bởi n + m cách. Tổng quát, giả sử môt công việc có thể thực hiện theo một trong k phương án A1 , A2 ,.
, Ak , trong đó có n1 cách thực hiện phương án A1 , n2 cách thực hiện phương án A2 , ., nk cách thực hiện phương án Ak. Khi đó công việc có thể được thực hiện bởi n1 + n2 + · · · + nk cách. Biểu diễn dưới dạng tập hợp. Số phần tử của tập hữu hạn A được kí hiệu là |A|.
, An là n tập hữu hạn, từng đôi một không giao nhau thì |A1 ∪ A2 ∪. ∪ An | = |A1 | + |A2 | + · · · + |An | hay n [ n X Ak = |Ak |. k=1 k=1 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Quy tắc nhân Giả sử công việc nào đó bao gồm hai công đoạn A và B , trong đó công đoạn A có thể làm theo n cách, công đoạn B có thể làm theo m cách.
Khi đó công việc có thể thực hiện theo nm cách. Tổng quát, giả sử một công việc nào đó bao gồm k công đoạn A1 , A2 ,. , Ak , ông đoạn A1 có thể thực hiện theo n1 cách, công đoạn A2 có thể thực hiện theo n2 cách, công đoạn A3 có thể thực hiện theo n3 cách, ., công đoạn Ak có thể thực hiện theo nk cách. Khi đó công việc có thể thực hiện theo n1 n2.
Biểu diễn dưới dạng tập hợp. , An là n tập hữu hạn với |Ak | = mk (k = 1, 2,. Khi đó n Y |A1 × A2 × · · · × An | = m1 × m2 × · · · × mn = mk .2 Giai thừa và hoán vị 1. Giai thừa Định nghĩa 1.
n giai thừa, kí hiệu là n! là tích của n số tự nhiên liên tiếp từ 1 đến n. Hoán vị Định nghĩa 2. Cho tập hợp A gồm n phần tử (n ≥ 1). Một cách sắp thứ tự n phần tử của tập hợp A được gọi là một hoán vị của n phần tử đó.
Kí hiệu Pn là số các hoán vị của n phần tử Pn = n! = 1 · 2 · · · (n − 1)n.3 Chỉnh hợp Định nghĩa 3. Cho tập hợp A gồm n phần tử (n ≥ 1). Kết quả của việc lấy k phần tử khác nhau từ n phần tử của tập hợp A và sắp xếp chúng theo một thứ tự nào đó được gọi là một chỉnh hợp chập k của n phần tử đã cho. 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Công thức n! Akn = = n(n − 1)(n − k + 1) (với 1 ≤ k ≤ n).
Một chỉnh hợp chập n của n phần tử là một hoán vị của n phần tử Ann = Pn = n!.4 Tổ hợp Định nghĩa 4. Giả sử tập A gồm n phần tử n ≥ 1. Mỗi tập con gồm k phần tử của A được gọi là một tổ hợp chập k của n phần tử đã cho (1 ≤ k ≤ n). Kí hiệu Cnk (1 ≤ k ≤ n) là số các tổ hợp chập k của n phần tử.
Công thức n! Cnk =. Cn0 = 1 Cnk = Cnn−k (0 ≤ k ≤ n) k+1 Cnk + Cnk+1 = Cn+1 (1 ≤ k ≤ n).5 Chỉnh hợp có lặp, hoán vị có lặp và tổ hợp có lặp 1. Chỉnh hợp có lặp Định nghĩa 5. Giả sử tập A gồm n phần tử (n ≥ 1).
Mỗi dãy có độ dài k các phần tử của A, mà mỗi phần tử có thể lặp lại nhiều lần và được sắp xếp theo một thứ tự nhất định được gọi là một chỉnh hợp lặp chập k của n phần tử. Số các chỉnh hợp lặp chập k của n phần tử là nk. Hoán vị lặp Định nghĩa 6. Hoán vị trong đó mỗi phần tử xuất hiện ít nhất một lần được gọi là hoán vị lặp.
Số hoán vị lặp của n phần tử thộc k loại, mà các phần tử từ loại i (1 ≤ i ≤ k) xuất hiện n lần được kí hiệu là P (n1 , n2 ,. , nk ) và được tính bằng công thức n! P (n1 , n2 ,. nk ! 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Tổ hợp lặp Định nghĩa 7.
Giả sử tập A gồm n phần tử (n ≥ 1). Một tổ hợp chập m (m không nhất thiết phải nhỏ hơn n) của n phần tử thuộc A là một bộ gồm m phần tử, mà mỗi phần tử này là một trong các phần tử của A. Số tổ hợp có lặp chập m của n phần tử là m n−1 Cnm = Cn+m−1 = Cn+m−1 .2 Các dạng toán đếm 1.1 Các phương pháp đếm 1. Phương pháp đếm trực tiếp Tùy theo bài toán ta có thể chia trường hợp hay không chia trường hợp để đếm các trường hợp thỏa mãn yêu cầu bài toán.
Phương pháp đếm vị trí + B1. Chọn vị trí cho số thứ nhất theo yêu cầu bài toán, suy ra số vị trí cho các số tiếp theo. Sắp xếp các số còn lại. Phương pháp đếm loại trừ + B1.
Đếm số phương án xảy ra bất kỳ ta có kết quả n1. Đếm số phương án không thỏa mãn yêu cầu bài toán ta có kết quả n2. Số phương án đúng là n = n1 − n2. Ta sử dụng phương pháp đếm loại trừ khi phương pháp đếm trực tiếp có quá nhiều trường hợp.
Phương pháp lấy trước rồi xếp sau + B1. Chọn ra trước cho đủ số lượng và thỏa mãn tích chất mà bài toán yêu cầu. Sắp xếp Phương pháp này dùng cho các bài toán có sự sắp xếp, cạnh nhau, có mặt. Phương pháp tạo vách ngăn + B1.
Sắp xếp m đối tượng vào m vị trí sẽ tạo ra m + 1 vách ngăn. 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Sắp xếp đối tượng khác nhau theo yêu cầu bài toán vào m + 1 vách ngăn trên. Công thức bao hàm loại trừ Cho A1 , A2 là hai tập hữu hạn, khi đó |A1 ∪ A2 | = |A1 | + |A2 | − |A1 ∩ A2 |.
Từ đó với ba tập hữu hạn A1 , A2 , A3 ta có |A1 ∪ A2 ∪ A3 | = |A1 | + |A2 | + |A3 | − |A1 ∩ A2 | − |A1 ∩ A3 | − |A2 ∩ A3 | + |A1 ∩ A2 ∩ A3 |. Bằng quy nạp, với k tập hữu hạn A1 , A2 ,. + (−1)k−1 Nk , trong đó Nm (1 ≤ m ≤ k ) là tổng phần tử của tất cả các giao m tập lấy từ k tập đã cho, nghĩa là X Nm = |Ai1 ∩ Ai2 ∩ .<im ≤k Bây giờ, ta đồng nhất tập Am (1 ≤ m ≤ k) với tính chất Am cho trên tập hữu hạn A nào đó và đếm xem có bao nhiêu phần tử của A “không thỏa mãn một tính chất Am nào”. Gọi N là số cần đếm, N là số phần tử của A.
+ (−1)k Nk , trong đó Nm là tổng các phần tử của A thỏa mãn m tính chất lấy từ k tính chất đã cho. Công thức này gọi là công thức bao hàm và loại trừ. Hầu nết các bài toán tổ hợp đều sử dụng một trong các phương pháp trên để giải quyết, tuy nhiên sự linh hoạt của phương pháp tùy thuộc vào khả năng của học sinh. Đối với bài toán ban đầu có số 0, ta xét trường hợp xem số 0 là một số có nghĩa, được kết quả n1 ; xét trường hợp số 0 đứng đầu, ta được kết quả là n2 , kết quả cần tìm sẽ là n1 − n2.
8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Các bài toán đếm 1. Chọn một nhóm phần tử từ một hay nhiều tập hợp Bài tập 1. Một lớp học có 40 em gồm 25 nam, 15 nữ. Cần chọn một ban cán sự gồm 4 người.
Hỏi có bao nhiêu cách chọn nếu a) Ban cán sự có ít nhất một nam? b) Ban cán sự có ít nhất một nam và một nữ? Lời giải. a) Nếu trong ban cán sự lớp có ít nhất 1 bạn nam thì có 4 khả năng xảy ra 1 · C 3 cách chọn. 1 nam và 3 nữ có C25 15 2 · C 2 cách chọn. 2 nam và 2 nữ có C25 15 3 · C 1 cách chọn.
3 nam và 1 nữ có C25 15 4 cách chọn. 4 nam và không có nữ có C25 Vậy có tất cả 1 3 2 2 3 1 4 C25 · C15 + C25 · C15 + C25 · C15 + C25 = 469576 cách. Nếu ban cán sự gồm toàn b) Nếu ban cán sự gồm toàn nam có C25 4 cách chọn. Ban cán sự gồm 4 người bất kỳ có C 4 cách chọn.
Vậy số nữ có C15 40 cách chọn thỏa mãn yêu cầu đề bài là 4 4 4 C40 − C25 − C15 = 77375 cách. Người ta sử dụng 3 loại sách gồm 8 cuốn sách về Toán, 6 cuốn sách về Lí và 5 cuốn sách về Hóa. Mỗi loại đều gồm các cuốn sách đôi một khác nhau. Có bao nhiêu cách chọn 7 cuốn sách trong số sách trên để làm giải thưởng sao cho mỗi loại có ít nhất một cuốn? 7.
Bây giờ, ta tính số Lời giải. Số cách chọn 7 trong số 19 cuốn sách bất kỳ là C19 cách chọn sao cho không có đủ 3 loại sách. Chọn 7 trong số 11 cuốn sách Lí và 7 cách. Chọn 7 trong số 13 cuốn sách Toán và Hóa có C 7 cách.
Chọn Hóa có C11 13 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Chọn 7 trong số 8 cuốn sách 7 trong số 14 cuốn sách Toán và Lí có C14 Toán có C87 cách. Áp dụng công thức bao hàm loại trừ, số cách chọn phải tìm là 7 7 7 7 C19 − C11 − C13 − C14 − C87 = 44918 cách. Đội thanh niên xung kích của một trường phổ thông có 12 học sinh gồm 5 học sinh lớp T, 4 học sinh lớp L và 3 học sinh lớp H.