Luận văn Một số bài toán tổ hợp đếm

tắc nhân ta có : Thay vào (1) ta có . Vậy có 56875 cách chọn đề kiểm tra thỏa mãn bài toán. Bài 19: Một đội thanh niên tình nguyện có 15 người gồm 12 nam, 3 nữ. Hỏi có bao nhiêu cách phân công đội thanh niên tình nguyện đó về giúp đỡ 3 tỉnh miền núi, sao cho mỗi tỉnh có 4 nam và 1 nữ. Giải: Đầu tiên ta chọn 4 nam và 1 nữ cho tỉnh thứ nhất. Theo quy tắc nhân số cách chọn là : Sau đó chọn 4 nam và 1 nữ cho tỉnh thứ 2. 4 nam được chọn trong 8 nam còn lại và 1 nữ sẽ được chọn trong 2 nữ còn lại. Theo quy tắc nhân số cách chọn là : Số còn lại thuộc tỉnh thứ 3. Vậy số cách phân công là Bài 20: Độ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. Cần chọn 4 học sinh đi làm nhiệm vụ, sao cho 4 học sinh không thuộc quá 2 trong 3 lớp trên. Hỏi có bao nhiêu cách chọn như vậy? Giải: Gọi A là tập hợp mọi cách chọn 4 học sinh trong 12 học sinh. Gọi B là tập hợp cách chọn không thỏa mãn yêu cầu đề bài. Gọi C là tập hợp cách chọn thỏa mãn yêu cầu đề bài. Ta có Theo quy tắc cộng ta có Dễ thấy Để tính , ta nhận thấy sẽ chọn 1 lớp có 2 học sinh, hai lớp còn lại mỗi lớp 1 học sinh. Theo quy tắc cộng và quy tắc nhân ta có Thay vào (1) ta có . Vậy có 225 cách chọn. Bài 21: Có bao nhiêu cách phân bố 100 sản phẩm cho 12 cửa hàng biết rằng mỗi cửa hàng phải có ít nhất một sản phẩm. Giải: Ta có thể dùng 99 vách ngăn để ngăn 100 sản phẩm. Chọn 11 vách ngăn trong số 99 vách ngăn trên ta được một cách phân bố sản phẩm cho 12 cửa hàng thỏa mãn bài toán. Vậy có cách phân bố Tổng quát: Số cách phân bố k sản phẩm cho n cửa hàng trong đó mỗi cửa hàng có ít nhất một sản phẩm là Bài 22: Một lớp học có 45 học sinh. Có bao nhiêu cách chọn nhóm 5 bạn vào ban cán sự của lớp sao cho có một bạn làm lớp trưởng. Giải: Trước hết ta chọn 5 học sinh trong 45 học sinh của lớp. Có cách. Sau đó trong 5 học sinh này ta chọn một bạn làm lớp trưởng. Có 5 cách. Vậy có 5. cách chọn thỏa mãn bài toán. Tổng quát: Số cách cách chọn nhóm k bạn trong số n bạn vào một nhóm sao cho có một bạn làm trưởng nhóm là Bài 23: Có bao nhiêu cách chọn một nhóm người trong số n người sao cho có một người làm nhóm trưởng. Giải: Giả sử nhóm có k người (vì phải luôn có một người làm trưởng nhóm). Trước hết ta chọn k người trong n người. Có cách. Sau đó trong k người này ta chọn một bạn làm trưởng nhóm. Có k cách. Do đó có cách chọn nhóm có k người trong đó luôn có một người làm nhóm trưởng. Vậy có cách chọn một nhóm người trong số n người sao cho có một người làm nhóm trưởng. Bài 24: Có bao nhiêu cách chọn một nhóm người trong số n người sao cho có một người làm nhóm trưởng, một người là nhóm phó. Giải: Giả sử nhóm có k người (vì phải luôn có một người làm nhóm trưởng , một người là nhóm phó). Trước hết ta chọn k người trong n người. Có cách. Sau đó trong k người này ta chọn một bạn làm nhóm trưởng . Có k cách. Trong k-1 người còn lại ta chọn một bạn làm nhóm phó. Có k-1 cách. Do đó có cách chọn nhóm có k người trong đó luôn có một người làm nhóm trưởng , một người là nhóm phó. Vậy có cách chọn một nhóm người trong số n người sao cho có một người làm nhóm trưởng , một người là nhóm phó. Bài 25 : ( Hoán vị vòng quanh) a. Tính số hoán vị vòng quanh của n phần tử khác nhau. b. Một hội nghị bàn tròn có phái đoàn của các nước : Anh 3 người, Nga 5 người, Mỹ 2 người, Pháp 3 người, Trung Quốc 4 người. Hỏi có bao nhiêu cách sắp xếp chỗ ngồi cho mọi thành viên sao cho người cùng quốc tịnh thì ngồi cạnh nhau. Giải : Nếu sắp xếp một phần tử vào một vị trí nào đó (chú ý vị trí đầu tiên không đóng vai trò gì do đây là hoán vị theo đường tròn), thì phần tử còn lại được sắp xếp vào vị trí còn lại. Số cách chọn đó là Vậy số hoán vị vòng quanh của n là Nếu một phái đoàn nào ngồi vào chỗ trước thì theo phần a bốn phái đoàn còn lại có 4! Cách sắp xếp. Như vậy có 24 cách sắp xếp các phái đoàn ngồi theo quốc gia mình. Bây giờ ta xem có bao nhiêu cách sắp xếp chỗ ngồi cho nội bộ từng phái đoàn. Từ giả thiết ta có 3! Cách sắp xếp cho phái đoàn Anh. 5! Cách sắp xếp cho phái đoàn Nga. 2! Cách sắp xếp cho phái đoàn Mỹ. 3! Cách sắp xếp cho phái đoàn Pháp. 4! Cách sắp xếp cho phái đoàn Trung Quốc. Theo quy tắc nhân số cách sắp xếp cho hội nghị là cách sắp xếp. Chú ý : Ta có thể mở rộng phần 1 của bài 25 như sau : Số cách sắp xếp m số khác nhau từ tập hợp n số lên một đường tròn bằng . Thật vậy Chọn m phần tử khác nhau trong n phần tử đã cho (không kể thứ tự sắp xếp). Số cách chọn là . Với m phần tử được chọn xếp m số đó lên đường tròn . Theo hoán vị vòng quanh số cách sắp xếp là Theo quy tắc nhân số cách sắp xếp m số khác nhau lên đường tròn là Bài 26: ( Bài toán vui) Một cửa hàng có 10 lon nước giải khát đôi một khác nhau dùng để bày hàng. Người ta xếp các lon đó thành hình quả núi, số lon từ hàng dưới cùng đến hàng trên cùng lần lượt là 4, 3, 2, 1. Hàng ngày người ta đổi vị trí các lon cho nhau sao cho không có hai ngày bày như nhau. Hỏi bắt đầu từ ngày 1.1.2000  thì có thể tiến hành đến ngày nào ? Giải : Có 10 vị trí khác nhau, bày 10 lon nước giải khát đôi một khác nhau, vậy số cách bày là Vậy cần có 3628800 ngày để bày hết tất cả các cách. Do cứ 4 năm thì có một năm nhuận, nên số ngày của chu kì 4 năm là ngày Ta thấy Ta lại lưu ý rằng những năm chia hết cho 400 không phải năm nhuận. như vậy không kể năm 2000, trong 2483. 4 năm có thêm 24 năm chia hết cho 4 mà không phải năm nhuận. Vậy ngày năm năm +66 ngày. Như vậy có thể bày tới ngày thứ 66 của năm 11936. Do năm này là năm nhuận nên . Vậy ngày cuối cùng có thể bày là mồng 6 tháng 3 năm 11936. 2.1.3 Bài toán tương tự Bài 27: Có bao nhiêu số tự nhiên gồm 4 chữ số sao cho không có chữ số nào lặp lại quá 1 lần. Bài 28: Có bao nhiêu số tự nhiên gồm 5 chữ số và chữ số đứng sau bé hơn chữ số đứng trước. Bài 29: Có bao nhiêu số tự nhiên gồm 6 chữ số khác nhau là số lẻ và nhỏ hơn 600000. Bài 30: Có bao nhiêu số tự nhiên gồm 5 chữ số khác nhau là số chẵn và nhỏ hơn 25000. Bài 31: Từ được bao nhiêu số chẵn có 3 chữ số khác nhau và không lớn hơn 789. Bài 32: Có thể lập được bao nhiêu số tự nhiên có 5 chữ số khác nhau được lập từ tập sao cho một trong ba chữ số đầu tiên là 1. Bài 33: Có 20 học sinh (8 nữ trong đó có Lan, 12 nam trong đó có Nam và Tí ). a) Có bao nhiêu cách chọn ra một tổ 7 người trong đó có nhiều nhất 2 trong 3 bạn Tí, Nam và Lan. b) Có bao nhiêu cách xếp thành một hàng dọc sao cho Lan đứng đầu và các bạn nam luôn đứng cạnh nhau nhưng Tí và Nam không đứng cạnh nhau. Bài 34: Một hộp đựng 6 quả cầu xanh đánh số từ 1 đến 6, 5 quả cầu đỏ đánh số từ 1 đến 5, 4 quả cầu vàng đánh số từ 1 đến 4. a) Có bao nhiêu cách lấy ra 3 quả cầu cùng màu, 3 quả cầu cùng số. b) Có bao nhiêu cách lấy ra 3 quả cầu khác màu, 3 quả cầu khác màu và khác số? Bài 35: Trong kỳ thi kết thúc môn toán học rời rạc có 10 câu hỏi. Có bao nhiêu cách gán điểm cho các câu hỏi nếu tổng số điểm là 100 và mỗi câu hỏi ít nhất 5 điểm. Bài 36: Một bàn dài có 2 dãy ghế đối diện nhau, mỗi dãy gồm 6 ghế. Người ta muốn sắp chỗ ngồi cho 6 học sinh nam và 6 học sinh nữ vào bàn nói trên. Hỏi có bao nhiêu cách sắp xếp trong mỗi trường hợp sau: a) Bất kỳ hai học sinh ngồi cùng nhau hoặc đối diện nhau đều không cùng giới tính. b) Bất kỳ hai học sinh ngồi đối diện nhau đều không cùng giới tính. Bài 37: Ở một trường tiểu học có 50 học sinh giỏi toàn diện, trong đó có 4 cặp anh em sinh đôi. Cần chọn ra 3 học sinh trong 50 em nói trên đi dự trại hè. Hỏi có bao nhiêu cách chọn mà trong nhóm 3 em được chọn không có cặp anh em sinh đôi nào.  Bài 38: có 5 nhà toán học nam, 3 nhà toán học nữ và 4 nhà vật lí nam. Lập một đoàn công tác 3 người cần có cả nam và nữ, cần có nhà toán học và nhà vật lí. Hỏi có bao nhiêu cách.  Bài 39:Một hộp đựng 4 viên bi đỏ, 5 viên bi trắng, 6 viên bi vàng. Người ta chọn ra 4 viên bi từ hộp đó. Hỏi có bao nhiêu cách chọn để số bi lấy ra không đủ 3 màu.  Bài 40 :Trong một lớp học có 7 nam sinh và 4 nữ sinh ưu tú ( trongđó có nam sinh Cường và nữ sinh Hoa). Cần lập một ban cán sự lớp gồm 6 người với têu cầu có ít nhất 2 nữ, ngoài ra biết Cường và Hoa không thể làm việc cùng nhau trong ban cán sự. Bài 41: Đội dự tuyển bóng bàn có 10 , 7 nam trong đó có danh thủ nam là Vũ Mạnh Cường và danh thủ nữ là Ngô Thị Thu Thuỷ. Người ta cần lập một đội tuyển bóng bàn quốc gia từ đội dự tuyển nói trên. Đội tuyển quốc gia có 3 nữ và 4 nam. Hỏi có bao nhiêu cách lập đội tuyển quốc gia sao cho trong đội tuyển quốc gia có mặt chỉ một và một trong 2 danh thủ nói trên. Bài 42:Có 6 quả cầu xanh đánh số từ 1 đến 6, 5 quả cầu đỏ đánh số từ 1 đến 5 và 4 quả cầu vàng đánh số từ 1 đến 4. Hỏi có bao nhiêu cách lấy ra 3 quả cầu vừa khác màu, vừa khác số. 2.2 Một số bài toán đếm có lặp Trong các bài toán đếm có lặp, mỗi phần tử cần đếm có thể xuất hiện nhiều lần. Để giải các bài toán đếm có lặp, người ta thường quy về các bài toán đếm không lặp và sử dụng thêm một số kiến thức khác. 2.2.1 Bài toán lập số. Bài 43: Cho tập hợp  Hỏi có thể lập được bao nhiêu số tự nhiên có 5 chữ số được lập từ A? Giải: Vì các chữ số có thể trùng nhau nên mỗi số tương ứng với một phép biến đổi có lặp 5 phần tử bớt đi trường hợp có số 0 đứng đầu (bằng một phép biến đổi có lặp 4 phần tử từ Vậy số các số bằng Bài 44: Cho tập hợp  Hỏi có thể lập được bao nhiêu số có 4 chữ số sao cho mỗi số tạo thành chia hết cho 4. Giải: Ta đã biết để một số có từ hai chữ số trở lên chia hết cho 4 thì điều kiện cần và đủ là hai số cuối của số đó phải chia hết cho 4. Từ tập A có thể lập được các số sau chia hết cho 4: 12, 16,24, 32, 36, 44, 52, 56, 64 Để chọn được các số thỏa mãn yêu cầu đề bài, ta cần tiến hành qua các bước: Bước 1 chọn hai số cuối. Theo trên có 9 cách chọn. Bước 2 chọn số hàng trăm có 6 cách chọn. Bước 3 chọn số hàng nghìn có 6 cách chọn Theo quy tắc nhân số cách chọn là 9.6.6=324 Vậy có 324 số thỏa mãn bài toán. Bài 45: Có thể lập được bao nhiêu số có 6 chữ số sao cho số 1 có mặt tối đa 5 lần, các số 2,3,4 có mặt tối đa 1 lần. Giải: Vì các số 2, 3,4 có mặt tối đa 1 lần nên ta phải lập ra số có 6 chữ số từ nên số 1 phải có mặt tối thiểu 3 lần. Gọi A3 là tập hợp các số có 6 chữ số trong đó số 1 có mặt 3 lần. Khi đó mỗi số 2, 3, 4 có mặt đúng một lần. A4 là tập hợp các số có 6 chữ số trong đó số 1 có mặt 4 lần. Khi đó mỗi số 2, 3, 4 có mặt tối đa một lần. A5 là tập hợp các số có 6 chữ số trong đó số 1 có mặt 5 lần. Khi đó mỗi số 2, 3, 4 có mặt tối đa một lần. Khi đó A3 ,A4 ,A5 đôi một rời nhau nên theo quy tắc cộng là số các số có 6 chữ số thỏa mãn điều kiện đề bài. Tính A3 Bước 1 chọn 3 vị trí trong 6 vị trí để đặt 3 chữ số 1 Số cách chọn là Bước 2 ba vị trí còn lại đặt ba số 2, 3, 4 Số cách chọn Vậy Tính A4 Bước 1 chọn 4 vị trí trong 6 vị trí để đặt 4 chữ số 1. Số cách chọn là Bước 2 hai vị trí còn lại đặt hai trong ba số 2, 3, 4. Số cách chọn Vậy Tính A5 Bước 1 chọn 5 vị trí trong 6 vị trí để đặt 5 chữ số 1. Số cách chọn là Bước 2 một vị trí còn lại đặt một trong ba số 2, 3, 4. Số cách chọn Vậy . Vậy số các số có 6 chữ số cần tìm là 120+90+18=228 số. Bài 46: Cho tập hợp  Cần lập ra các số tự nhiên có 7 chữ số thoả mãn đồng thời các tính chất sau: a. Chữ số ở vị trí thứ 3 ( hàng vạn) là một số chẵn. b. Đó là số không chia hết cho 5. c. Các chữ số ở vị trí 4,5,6 ( hàng nghìn, hàng trăm, hàng chục) đôi một khác nhau. Hỏi có bao nhiêu số như vậy? Giải: Ta giải bài toán đếm có lặp trên bằng quy tắc nhân như sau: Bước 1 chọn số ở vị trí thứ 3 . Có 5 cách chọn. Bước 2 chọn số ở vị trí cuối cùng. Do số cần chọn không chia hết cho 5 nên có 8 cách chọn (loại 0 và 5). Bước 3 chọn số ở vị trí thứ nhất. Có 9 cách chọn (loại 0). Bước 4 chọn số ở vị trí thứ 2. Có 10 cách chọn. Bước 5 chọn ba số ở vị trí 4, 5, 6. Đó là cách chọn 3 phần tử (kể cả thứ tự sắp xếp) trong 10 phần tử. Có cách chọn. Theo quy tắc nhân số các số thỏa mãn là: 5.8.9.10.720=2592000 số thỏa mãn bài toán. Bài 47: Số điện thoại ở một thành phố có 6 chữ số a. Có bao nhiêu số điện thoại mà các chữ số xếp theo thứ tự tăng dần. b. Có bao nhiêu số điện thoại gồm 3 cặp 2 số giống nhau. c. Có bao nhiêu số điện thoại mà số 6 có mặt đúng 2 lần, số 2 và số 5 mỗi số có mặt đúng một lần và hai số còn lại có tổng chia hết cho 3. Giải: Ứng với một cách chọn ra 6 phần tử phân biệt từ tập thì có đúng một cách sắp xếp 6 phần tử ấy theo thứ tự tăng dần. Vì vậy số dãy số có 6 chữ số sắp xếp theo thứ tự tăng dần chính bằng số cách chọn ra 6 phần tử phân biệt tại tập hợp A. Do đó số các số điện thoại mà các chữ số xếp theo thứ tự tăng dần là . Số dãy số gồm 6 chữ số dạng ababab bằng số các dãy số có hai chữ số ab. Đây là phép đếm có lặp nên số dãy số ab là 10.10=100 số. Bước 1 chọn hai vị trí để đặt hai con số 6. Số cách chọn là . Bước 2 chọn hai vị trí trong bốn vị trí còn lại để xếp hai số 2 và 5. Cách xếp này kể cả thứ tự nên số cách chọn là Bước 3 để ý rằng . Tổng hai số trong tập nói trên chia hết cho 3 là các tổng sau Với hai vị trí còn lại có 3 cách đặt hai số 0,0; 3,3; 9,9. Với hai vị trí còn lại có 12 cách đặt các cặp số . Vậy số cách chọn ở bước 3 là: 3+12=15. Theo quy tắc nhân số máy điện thoại có 6 chữ số thỏa mãn yêu cầu là 15.12.15=2700 số 2.2.2 Bài toán đếm sử dụng tổ hợp lặp. Bài 48: Một ông bố có 15 chiếc kẹo định phân phát cho 6 đứa con của mình. Có bao nhiêu cách phát. Có bao nhiêu cách phát sao cho mỗi con nhận được ít nhất một chiếc. Giải Chúng ta giả thiết những chiếc kẹo là giống hệt nhau nên hai cách phân phát được gọi là khác nhau nếu có một vài đứa con nhận được số kẹo khác nhau. Khi đó mỗi cách phân phát tương ứng với một tổ hợp lặp gồm 15 phần tử của tập A gồm 6 đứa con. Ta tìm được số cách phân phát bằng Trước hết ông bố phát cho mỗi đứa con một chiếc kẹo, 9 chiếc còn lại ông bố lại phát cho 6 đứa con như ở phần a. Ta có số cách phân phát là Bài 49: Có bao nhiêu cách phân phát 7 quyển vở và 5 cái bút cho 3 học sinh? Giải Vì những quyển vở được xem là giống hệt nhau và những cái bút cũng được xem là giống hệt nhau nên các cách phân phát được xem là khác nhau nếu có học sinh nhận được số vở khác nhau hoặc số bút khác nhau. Mỗi cách phân phát 7 quyển vở ứng với một tổ hợp lặp 7 phần tử của tập A ứng với 3 em học sinh. Do đó có cách phân phát vở. Mỗi cách phân phát 5 chiếc bút ứng với một tổ hợp lặp 5 phần tử của tập A ứng với 3 em học sinh. Do đó có cách phân phát bút. Vậy số cách phân phát cuối cùng cho 3 học sinh là Bài 50: Một cửa hàng bánh bích quy có 4 loại khác nhau. Có bao nhiêu cách chọn 6 hộp bánh? Giả sử là ta chỉ quan tâm đến loại bánh mà ta không quan tâm đến hộp bánh cụ thể nào và thứ tự chọn chúng. Giải: Số cách chọn 6 hộp bánh bằng số tổ hợp lặp chập 6 của 4 phần tử. Ta có cách chọn 6 hộp bánh bích quy. Bài 51: Giả sử trong một đĩa quả có táo, cam, lê, mỗi loại có ít nhất 4 quả. Tính số cách lấy 4 quả từ đĩa này nếu giả sử rằng thứ tự các quả được chọn không quan trọng, và các quả thuộc cùng một loại là không phân biệt. Giải: Mỗi phương án chọn 4 quả từ 3 loại quả nêu trên là một tổ hợp lặp chập 4 từ tập 3 phần tử {táo, cam, lê} Ta có cách chọn Bài 51: Phương trình x1 + x2 + x3 = 15 có bao nhiêu nghiệm nguyên không âm? Giải Chúng ta nhận thấy mỗi nghiệm của phương trình ứng với một cách chọn 15 phần tử từ một tập có 3 loại, sao cho có x1 phần tử loại 1, x2 phần tử loại 2 và x3 phần tử loại 3 được chọn. Vì vậy số nghiệm bằng số tổ hợp lặp chập 15 từ tập có 3 phần tử và bằng = 136. Bài 52: Phương trình (1) có bao nhiêu nghiệm tự nhiên. Giải: Nếu () là một nghiệm tự nhiên của phương trình (1) thì ta có thể cho ứng với nó một tổ hợp lặp chập n của m phần tử . Đảo lại nếu có một tổ hợp lặp chập n của m phần tử kiểu () thì ta tìm được nghiệm tự nhiên của phương trình đã cho bằng cánh đặt , với . Vậy số nghiệm tự nhiên của (1) là . Bài 53: Tìm số nghiệm tự nhiên của phương trình: (với ) (1) với , . Giải: Ta thấy một nghiệm của phương trình (1) thỏa mãn những điều kiện đã cho ứng với một cách chọn mười một phần tử trong đó phần tử loại một, phần tử loại hai, , phần tử loại m. Trước tiên ta chọn phần tử loại một, phần tử loại hai,..., phần tử loại m. Sau đó chọn thêm () phần tử thuộc một trong loại. Như vậy có: . Bài 54: Một xe đưa công nhân từ xí nghiệp về nhà, xe dừng ở trạm (tại mỗi trạm số công nhân xuống xe từ 0 đến người). Hỏi có bao nhiêu khả năng khác nhau để tất cả các công nhân xuống xe ở trạm. Giải: Ta giả sử trạm là và số người xuống tại mỗi trạm là . Mỗi cách giải phóng người ở trạm có thể biểu diễn bằng đơn thức với . Số khả năng khác nhau để tất cả các công nhân xuống là tổ hợp có lặp chập của phần tử . Có khả năng khác nhau để công nhân xuống xe. Bài 55: Có bao nhiêu số tự nhiên nhỏ hơn và có tổng các chữ số bằng . Giải: Mỗi số có thể đồng nhất với một nghiệm của phương trình = . Ta có số. 2.2.3 Bài toán đếm sử dụng chỉnh hợp lặp. Bài 56: Tính xác suất lấy liên tiếp được 3 quả cầu đỏ ra khỏi bình kín chứa 5 quả cầu đỏ và 7 quả cầu xanh, nếu sau mỗi lần lấy một quả cầu ra lại bỏ nó trở lại bình. Giải: Ta thấy số cách lấy được 3 quả cầu đỏ là 53 , vì mỗi lần lấy ta có 5 quả cầu đỏ trong bình. Số cách lấy 3 quả cầu bất kì trong bình là 123 , vì mỗi lần lấy cầu trong bình đều có 12 quả. Như vậy xác suất cần tìm là Bài 57: Từ bảng chữ cái tiếng Anh có thể tạo ra được bao nhiêu xâu có độ dài n. Giải: Theo quy tắc nhân, vì có 26 chữ cái và vì mỗi chữ có thể được dùng lại nên chúng ta có xâu với độ dài n. 2.2.4 Bài toán đếm sử dụng hoán vị lặp. Bài 58: Có thể nhận được bao nhiêu xâu khác nhau bằng cách sắp xếp lại các chữ cái của từ SUCCESS? Giải Vì một số chữ cái của từ SUCCESS là như nhau nên câu trả lời không phải là số hoán vị của 7 chữ cái được. Từ này chứa 3 chữ S, 2 chữ C, 1 chữ U và 1 chữ E. Để xác định số xâu khác nhau có thể tạo ra được ta nhận thấy có cách chọn 3 chỗ cho 3 chữ S, còn lại 4 chỗ trống. Có cách chọn 2 chỗ cho 2 chữ C, còn lại 2 chỗ trống. Có thể đặt chữ U bằng cách và cách đặt chữ E vào xâu. Theo quy tắc nhân, số các xâu khác nhau có thể tạo được là: ...= = = 420. Bài 59: Có bao nhiêu số có 8 chữ số trong đó số 1 lặp lại 3 lần, số 2 lặp lại 2 lần, còn các chữ số khác có mặt đúng một lần được lập từ tập A={0, 1, ,9}. Giải: Tất cả các số có 8 chữ số trong đó số 1 lặp lại 3 lần, số 2 lặp lại 2 lần, còn các chữ số khác có mặt đúng một lần được lập từ (a,b,c,1,1,1,2,2) là số. Chọn 3 số a, b, c từ A\{1, 2} có cách. Có .3360=188160 số kể cả số 0 đứng đầu. Ta xét trường hợp số 0 đứng đầu: Chọn 2 số trong A\{0, 1, 2} có cách. Trong trường hợp số 0 đứng đầu có số. Có số. 2.2.5 Bài toán phân bố các đồ vật vào trong hộp Một số bài toán đếm có thể giải bằng cách liệt kê những cách đặt các đối tượng khác nhau vào trong những hộp khác nhau. Tùy vào từng bài cụ thể mà chúng ta đặt các đối tượng vào những cái hộp. Định lý 2.2.5 Số cách phân chia n đồ vật khác nhau vào trong k hộp khác nhau sao cho có ni vật được đặt vào hộp thứ i, với i = 1, 2, , k bằng Bài 60: Có bao nhiêu cách chia 6 người vào mỗi toa tàu hạng 1, hạng 2, hạng 3, hạng 4 trong tổng số 48 người đã mua vé. Giải: Trước tiên chúng ta thấy toa tàu hạng 1 có thể nhận được 6 người lên bằng cách, còn lại 42 người. Toa tàu hạng 2 có thể nhận được 6 người lên bằng cách, còn lại 36 người. Toa tàu hạng 3 có thể nhận được 6 người lên bằng cách, còn lại 30 người. Cuối cùng toa tàu hạng 4 có thể nhận được 6 người lên bằng cách. Vì vậy tổng cộng có cách chia. Bài 61: Có bao nhiêu cách chia những xấp bài 5 quân cho mỗi một trong 4 người chơi từ một cỗ bài chuẩn 52 quân? Giải: Trước tiên chúng ta thấy người đầu tiên có thể nhận được 5 quân bài bằng cách Người thứ hai có thể được chia 5 quân bài bằng vì chỉ còn 47 quân. Người thứ ba có thể được chia 5 quân bài bằng vì chỉ còn 42 quân. Cuối cùng người thứ tư nhận được 5 quân bài bằng cách. Vì vậy tổng cộng có cách chia. 2.2.6 Bài toán tương tự Bài 62: Cho tập hợp  Hỏi có thể lập được bao nhiêu số có 5 chữ số sao cho mỗi số tạo thành chia hết cho 8. Bài 63: Có thể lập được bao nhiêu số có 6 chữ số sao cho số 3 có mặt tối đa 3 lần, số 2 có mặt tối đa 2 lần, các số còn lại có mặt tối đa 1 lần. Bài 64: Một bàn cờ hình chữ nhật chứa n cột và p dòng. a. Có bao nhiêu cách đặt vật giống nhau vào ô của bàn cờ sao cho không có hai vật nào ở trong cùng một cột. b. Cũng câu hỏi trên trong trường hợp vật là khác nhau. Bài 65: Tìm số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 có ít nhất 5 bi, biết rằng hộp 2 và hộp 3 không chứa quá 6 bi. Bài 66: Có bao nhiêu cách phân chia 10 người thành 3 nhóm trong đó nhóm 1 có 2 người, nhóm 2 có 3 người, nhóm 3 có 5 người. Bài 67: Có bao nhiêu cách phân bố 6 đồ vật khác nhau cho 6 người (không phân biệt thứ tự các đồ vật mà mỗi người nhận được) sao cho các điều kiện sau thỏa mãn: Người thứ nhất nhận được 1 đồ vật, người thứ hai nhận được 2 đồ vật, người thứ ba nhận được 3 đồ vật, người thứ tư nhận được 1 đồ vật. Hai người còn lại không nhận được đồ vật nào. Bài 68: Có bao nhiêu số có 6 chữ số trong đó số 1 xuất hiện 2 lần, và chữ số hàng nghìn là số chẵn lập từ . Bài 69: Có bao nhiêu số tạo ra từ tất cả các chữ số của số 1234321 sao cho các chữ số lẻ luôn chiếm hàng lẻ. Bài 70: (Đề thi đại học 2007) Có bao nhiêu bộ ba số nguyên không âm thỏa mãn điều kiện với . Bài 71: Tìm số nghiệm nguyên không âm của phương trình , thỏa mãn điều kiện . CHƯƠNG 3 - MỘT SỐ BÀI TOÁN TỔ HỢP SỬ DỤNG PHÉP ĐẾM NÂNG CAO Chương này trình bày một số bài toán sử dụng các phương pháp đếm nâng cao thường gặp trong các đề thi học sinh giỏi, đề thi quốc gia, thi quốc tế. 3.1 Một số bài toán sử dụng nguyên lý bù trừ. 3.1.1 Nguyên lý bù trừ. Khi hai công việc có thể được làm đồng thời, 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ả hai việc. Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc. Ta có thể phát biểu nguyên lý đếm này bằng ngôn ngữ tập hợp. 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ợp hữu hạn A1, A2, A3, ta có: Và bằng quy nạp, với k tập hữu hạn A1, A2, ..., Ak ta có: | A1 È A2 È ... È Ak| = N1 - N2 + N3 - ... + (-1)k-1Nk, 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à 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 vũ trụ hữu hạn U nào đó và đếm xem có bao nhiêu phần tử của U sao cho không thỏa mãn bất kỳ một tính chất Am nào. Gọi là số cần đếm, N là số phần tử của U. Ta có: = N - | A1 È A2 È ... È Ak| = N - N1 + N2 - ... + (-1)kNk, trong đó Nm là tổng các phần tử của U thỏa mãn m tính chất lấy từ k tính chất đã cho. Công thức này được gọi là nguyên lý bù trừ. Nó cho phép tính qua các Nm trong trường hợp các số này dễ tính toán hơn. 3.1.2 Các bài toán giải bằng phương pháp bù trừ. Bài 72: Một chuyến bay có 67 hành khách. Trong đó có 47 người sử dụng tốt Anh, 35 người sử dụng tốt tiếng Đức, 20 người sử dụng tốt tiếng Pháp. Hơn nữa có 23 người sử dụng tốt hai thứ tiếng Anh và Đức, 12 người sử dụng tốt hai tiếng Anh và Pháp, 11 người sử dụng tốt hai tiếng Đức và Pháp. Và có 5 người sử dụng tốt cả ba thứ tiếng. Tìm số hành khách không sử dụng được bất kì ngoại ngữ nào? Giải Gọi A, B, C lần lượt là các hành khách sử dụng tốt ngoại ngữ là tiếng Anh, tiếng Đức, tiếng Pháp. Số các hành khách biết ít nhất một ngoại ngữ là: Vậy số hành khách không sử dụng được bất kì ngoại ngữ nào là 67 – 61 =6 Bài 73: Giáo viên chủ nhiệm của một lớp tiểu học yêu cầu lớp trưởng báo cáo thống kê theo mẫu và đọc trước lớp. Bản báo cáo như sau: Lớp có 45 học sinh, 30 học sinh nam. Lớp có 30 học sinh đạt điểm tốt, trong đó có 16 học sinh nam. Có 28 học sinh chơi thể thao, trong số này có 18 học sinh nam và 17 học sinh đạt điểm tốt. Có 15 em đạt điểm tốt và tham gia chơi thể thao. Hãy chỉ ra rằng lớp trưởng đã thống kê sai. Giải: Đặt R là tập hợp học sinh cả lớp. A là tập hợp học sinh nam. B là tập hợp học sinh có điểm tốt. C là tập hợp học sinh chơi thể thao. Khi đó số học sinh nữ, không chơi thể thao, có kết quả không tốt bằng Kết quả trên là vô lí. Vậy lớp trưởng đó báo cáo sai. Bài 74: Có bao nhiêu cách sắp xếp 8 con xe lên bàn cờ quốc tế đã bị gạch đi một đường chéo chính sao cho không có con nào ăn con nào. Giải: Có 8! Cách sắp xếp 8 con xe lên bàn cờ quốc tế sao cho không có con nào ăn con nào. Ta cần đếm số cách xếp không hợp lệ, tức là số cách xếp có ít nhất một con xe nằm trên đường chéo. Gọi Ai là tập hợp các cách xếp có quân xe nằm ở ô (i,j). ta cần tìm . Nhưng dễ dàng thấy rằng nên theo nguyên lý bù trừ ta có . Như vậy số cách sắp xếp 8 con xe lên bàn cờ quốc tế đã bị gạch đi một đường chéo chính sao cho không có con nào ăn con nào bằng : Bài 75: Có n lá thư và n phong bì ghi sẵn địa chỉ. Bỏ ngẫu nhiên các lá thư vào các phong bì. Hỏi xác suất để xảy ra không một lá thư nào đúng địa chỉ. Giải Mỗi phong bì