ĐẠi học quốc gia hà NỘI
Một số bài toán đếm có lặp
tải về 0.86 Mb.
|
- Điều hướng trang này:
- 2.2.1 Bài toán lập số.
- 2.2.2 Bài toán đếm sử dụng tổ hợp lặp.
- 2.2.3 Bài toán đếm sử dụng chỉnh hợp lặp.
- 2.2.4 Bài toán đếm sử dụng hoán vị lặp.
- 2.2.5 Bài toán phân bố các đồ vật vào trong hộp
- 2.2.6 Bài toán tương tự
2.2 Một số bài toán đếm có lặpTrong 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.
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.
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
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.
Giải:
Do đó số các số điện thoại mà các chữ số xếp theo thứ tự tăng dầ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ố
Bài 48: Một ông bố có 15 chiếc kẹo định phân phát cho 6 đứa con của ḿnh.
Giải
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
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 tŕ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 tŕ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 tŕ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 tŕ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 tŕnh đă cho bằng cánh đặt , với . Vậy số nghiệm tự nhiên của (1) là .
Giải:
Ta thấy một nghiệm của phương tŕ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 tŕnh = . Ta có số.
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 ḱ 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à
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.
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ố.
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.
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.
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 ḍ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.
|