|
|
LOẠI 1: Chọn phần tử từ các tập hợp
Thí dụ 1: Tổ một có 10 người, tổ hai có 9 người. có bao nhiêu cách chọn một nhóm gồm 8 người sao cho mỗi tổ trên có ít nhất là 2 người?
Lời giải: Giả sử ta chọn k người của tổ một và (8 – k) người của tổ hai. Vì mỗi tổ có ít nhất 2 người nên $2 \le k \le 6. $
• Số cách chọn k trong số 10 người của tổ một là $C_{10}^k$ . Ứng với một cách chọn trên, ta có số cách chọn (8 – k) trong 9 người của tổ hai là $C_{9}^{8-k}$ . Theo quy tắc nhân, ta được số cách chọn nhóm 8 người như trên là
$S_k=C_{10}^k.C_{9}^{8-k}$
• Cho k lần lượt bằng 2, 3,..,6 và áp dụng quy tắc cộng, ta được số cách chọn nhóm 8 người thỏa mãn bài toán là
$S=S_2+S_3+\cdots+S_6=C_{10}^2.C_{9}^{6}+C_{10}^3.C_{9}^{5}+\cdots+C_{10}^6.C_{9}^{2}=74088$
Bài toán tổng quát: Cho tập hợp A có n phần tử, tập hợp B có m phần tử. Tính số cách chọn p phần tử từ hai tập hợp trên $(p<m+n)$ và thỏa mãn một điều kiện nào đó.
Cách giải chung
1) Tính trực tiếp : Giả sử ta chọn k phần tử của tập hợp A và (p – k) phần tử của tập hợp B (trường hợp giả thiết cho nhiều tập hợp hơn, ta làm tương tự). Số cách chọn là $S_k=C_{n}^k.C_{m}^{p-k}$. Cho k thay đổi phù hợp với giả thiết của bài toán và lấy tổng của tất cả các số hạng $S_k$ tương tứng, ta được kết quả cần tìm.
2) Tính gián tiếp : Số cách chọn k phần tử từ A,B môt cách bất kỳ là $C_{m+n}^k$. Kết quả phải tìm là hiệu của $C_{m+n}^k$ với tổng các số hạng $S_k$ tương ứng với mỗi giá trị k thỏa mãn gỉa thiết của bài toán.
Thí dụ 2. Người ta sử dụng ba loại sách gồm; 8 cuốn sách về Toán học, 6 cuốn sách về Vật lí và 5 cuốn sách về Hóa học. Mỗi loại đều gồm các cuốn sách đôi một khác loại 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 1 cuốn?
Lời giải: Sử dụng cách tính gián tiếp. số cách chọn 7 trong số 19 cuốn sách một cách bất kì là $C_{19}^7$.
Các cách chọn không đủ 3 loại sách là:
• Số cách chọn 7 trong số 11 cuốn sách Lí và Hóa là $C_{11}^7$ ( không có sách Toán)
• Số cách chọn 7 trong số 13 cuốn sách Hóa và Toán là $C_{13}^7$ (không có sách Lí)
• Số cách chọn 7 trong số 14 cuốn sách Toán và Lí là $C_{14}^7$ ( không có sách Hóa)
• Số cách chọn 7 trong số 8 cuốn sách Toán là $C_{8}^7$ (không có sách Lí và Hóa)
Vì mỗi cách chọn không có sách Lí và Hóa thuộc cả hai phép chọn : không có sách Lí và không có sách Hóa, nên số cách chọn phải tìm là
$C_{19}^7-C_{11}^7-C_{13}^7-C_{14}^7+C_{8}^7=44918.$
Lưu ý. Khi tính theo phương pháp gián tiếp, mỗi số hạng tương ứng với trường hợp không thỏa mãn bài toán được đặt dấu trừ. Số hạng đồng thời thuộc hai trường hợp không thỏa mãn bài toán được đặt sau dấu cộng ( bạn đọc tự suy luận cho số hạng đồng thời thuộc ba trường hợp không thỏa mãn bài toán…)
LOẠI 2: Sắp xếp các thứ tự các vật từ một họ các vật
Thí dụ 3. Có 5 viên bi xanh giống nhau, 4 viên bi trắng giống nhau và 3 viên bi đỏ đôi một khác nhau. Có bao nhiêu cách sắp xếp số bi trên vào 12 ô theo một hàng ngang sao cho mỗi ô có một viên bi?
Lời giải : Nếu tất cả 12 viên bi đều khác nhau thì chúng tạo thành $P_{12}=12!$ hoán vị. Nhưng các hoán vị của 5 bi xanh và các hoán vị của 4 bi trắng cho cùng một cách sắp xếp đối với 12 viên bi nên số cách xếp phải là
$\frac{P_{12}}{P_5.P_4}=\frac{12!}{5!.4!}=166320$
Bài toán tổng quát: Có tất cả n vật trong đó có m vật giống nhau từ hộp A; k vật giống nhau từ hộp B…,$(m+k+\cdots<n)$ . Các vật còn lại đôi một khác nhau thì số cách xếp chúng thành một hang ngang là $\frac{n!}{m!k!\cdots}$.
Thí dụ 4: Có bao nhiêu cách xếp vị trí cho 5 học sinh nam và 3 học sinh nữ quanh một bàn tròn sao cho không có hai học sinh nữ nào cạnh nhau? ( hai cách xếp khác nhau về vị trí nhưng có cùng thứ tự như đối với các học sinh trên được coi là một)
Lời giải: Giả sử đã xếp chỗ cho 5 học sinh nam. Vì 3 học sinh nữ không ngồi cạnh nhau nên họ được chọn 3 trong 5 vị trí xem kẽ giữa các học sinh nam, số cách chọn là $A_5^3$. Vì hai cách xếp vị trí cho 8 người cùng một thứ tự quanh bàn tròn được coi là một nên ta có thể chọn trước vị trí cho một học sinh nam nào đó, số hoán vị của 4 học sinh nam còn lại vào các vị trí là $4!$.
Theo quy tắc nhân, số khả năng phải tìm là $A_5^3.4!=1440$ cách.
Lưu ý. Khi xếp n đối tượng theo một vòng tròn với hai cách xếp khách nhau bởi một phép quay ta có thể coi là một, thì ta có thể đijnh trước một vị trí cho một đối tượng bất kì trong chúng. Sau đó tính số cách xếp vị trí cho (n – 1 ) đối tượng còn lại
LOAỊ 3: Phân chia các vật từ một họ các vật
Thí dụ 5: Có bao nhiêu cách chia 100 đồ vật giống nhau cho 4 người sao cho mỗi người được ít nhất một đồ vật?
Lời
giải. Giả sử 100 đồ vật được xếp thành một hang ngang, giữa chúng có 99
khoảng trống. Đặt một cách bất kỳ 3 vạch vào 3 trong số 99 khoảng trống
đó, ta được một cách chia 100 đồ vật ra thành 4 phần dể lần lượt gán
cho 4 người. Khi đó mỗi người được ít nhất 1 đồ vật và tổng số đồ vật
của 4 người bằng 100 thỏa mãn yêu cầu của bài toán.
Vậy số cách chia là $C_{99}^3=156849$ cách.
Lưu ý. Bằng cách giải tương tự như trên ta có thể chứng minh rằng phương trình $x_1+x_2+\cdots+x_n=m$ (1) có tính chất:
• Với $1 \le n \le m; m,n \in \mathbb{N}$; thì PT(1) có số nghiệm trong tập hợp các sỗ nguyên dương là $C_{m-1}^{n-1}$.
• Với $1 \le n ; m,n \in \mathbb{N}$; thì PT(1) có số nghiệm trong tập hợp số tự nhiên là $C_{m+n-1}^{n-1}$.
Thí dụ 6: Có bao nhiêu cách chia 8 đồ vật đôi một khách nhau cho ba người sao cho có mỗi người được 2 đồ vật và hai người con lại, mỗi người được 3 đồ vât?
Lời giải: Có 3 cách chọn đồ vật. Với mỗi cách chọn trên ta có:
• Số cách chọn 2 trong 8 đồ vật cho người được 2 đồ vật là $C_8^2$; sau đó, số cách chọn 3 trong 6 đồ vật còn lại cho người thứ nhất được 3 đồ vật là $C_6^3$, 3 đồ vật còn lại giành cho người thứ 2 được 3 đồ vật.
• Theo quy tắc nhân, số cách chia phải tìm là: $3.C_8^2.C_6^3=1680$ cách.
Lưu ý. Khi giải bài toán trên, nhiều bạn cho đáp số sai là hoặc $C_8^2C_6^3$ hoặc $3!C_8^2.C_6^3$.
Trường hợp thứ nhất, bạn đã coi vai trò của người được 2 đồ vật và người được 3 đồ vật là như nhau (!). Trường hợp thứ hai, bạn đã coi vai trò của hai người cùng được 3 đồ vật khác nhau(!)
BÀI TẬP LÀM THÊM
Bài 1. Phương trình $x+y+z=100$ có bao nhiêu nghiệm trong tập hợp số tự nhiên?
Bài 2. Đem chia hết 10 đồ vật đôi một khác nhau cho 2 người, sao cho mỗi người được ít nhất 1 đồ vật. Hỏi số cách chia?
Bài 3. Có 5 cuốn sách Toán giống nhau, 7 cuốn sách Lí giống nhau và 8 cuốn sách Hóa giống nhau. Đem làm giải thưởng cho 10 học sinh. Mỗi người được 2 cuốn sách khác loại, tính số cách nhận giải thưởng của 10 học sinh trên.
Bài 4. Có bao nhiêu cách chia 6 người ra thành 3 nhóm, mỗi nhóm 2 người, trong các trường hợp sau
a) Phân biệt thứ tự các nhóm là : nhóm 1, nhóm 2, nhóm 3.
b) Không phân biệt thứ tự của các nhóm.
|