Một số ví dụ khó hơn về tổ hợp

§2. MỘT SỐ VÍ DỤ KHÓ HƠN VỀ TỔ HỢP

Ví dụ 2.

Có bao nhiêu cách phân phối 5 đồ vật khác nhau cho 3 người, sao cho:

a) Một người nhận được 1 đồ vật, còn hai người kia mỗi người nhận được 2 đồ vật ?

b) Mỗi người nhận được ít nhất một đồ vật ?

Giải.

a) Nếu người thứ nhất nhận 1 đồ vật thì người đó có $C_{5}^{1}$ cách nhận. Sau đó người thứ hai có thể nhận 2 đồ vật trong số 4 đồ vật còn lại theo $C_{4}^{2}$ cách và người thứ ba chỉ có một cách nhận 2 đồ vật còn lại. Vậy trong trường hợp này theo quy tắc nhân, số cách là :

Nhưng người thứ hai và thứ ba cũng có thể nhận 1 đồ vật như người thứ nhất . Vậy theo quy tắc cộng tổng số cách phân phối theo yêu cầu đề bài là:

30 + 30 + 30 = 3 x 30 = 90 cách.

b) Có 2 khả năng:

b1) Một người nhận 1 đồ vật, hai người kia, mỗi người nhận 2 đồ vật.

b2) Một người nhận 3 đồ vật, hai người kia, mỗi người nhận 1 đồ vật.

Khả năng b1) đã được giải quyết ở phần a). Xét khả năng b2). Nếu người thứ nhất nhận 3 đồ vật thì người đó có $C_{5}^{3}$ cách nhận. Khi đó, người thứ hai có thể nhận một đồ vật trong số 2 đồ vật còn lại theo $C_{2}^{1}$ cách và người thứ ba chỉ có 1 cách nhận đồ vật còn lại. Vậy trong trường hợp này, theo quy tắc nhân có :

Nhưng người thứ hai và thứ ba cũng có thể nhận 3 đồ vật như người thứ nhất. Vậy theo quy tắc cộng, tổng số cách phân phối theo khả năng b2) là :

20 + 20 + 20 = 3.20 = 60 cách.

Tóm lại, có cả thảy 60 + 90 = 150 cách phân phối 5 đồ vật cho 3 người sao cho mỗi người được nhận ít nhất một đồ vật.

Ví dụ 3.

Một thầy giáo có 12 cuốn sách đôi một khác nhau trong đó có 5 cuốn sách văn học, 4 cuốn sách âm nhạc và 3 cuốn sách hội hoạ. Ông lấy ra 6 cuốn và đem tặng cho 6 học sinh A, B, C, D, E, F mỗi người 1 cuốn.

a) Giả sử thầy giáo chỉ muốn tặng cho các học sinh trên những cuốn sách thuộc hai loại sách văn học và âm nhạc. Hỏi có bao nhiêu cách tặng ?.

b) Giả sử thầy giáo muốn rằng sau khi tặng sách xong, mỗi một trong 3 thể loại văn học, âm nhạc, hội hoạ đều còn lại ít nhất 1 cuốn. Hỏi có bao nhiêu cách tặng ?

Giải.

a) Số sách thuộc hai loại văn học và âm nhạc là 5 + 4 = 9. Lấy 6 trong số 9 cuốn sách nói trên ta có $C_{9}^{6}$ trường hợp. Đem 6 cuốn sách đã chọn tặng cho 6 học sinh, có 6! cách tặng.

Vậy có cách tặng.

b) Chọn 6 trong số 12 cuốn sách một cách ngẫu nhiên. Có tất cả $C_{12}^{6}$ cách chọn.

Bây giờ, ta xét trường hợp sau khi tặng 6 cuốn sách xong, thì trái với ý định của thầy giáo. Ta sẽ tính số S các cách làm xảy ra trường hợp này. Như thế, số cách thỏa mãn ý định của thầy giáo sẽ bằng $C_{12}^{6}$ - S.

Các phương án xảy ra trường hợp trái ý định của thầy giáo như sau:

+ Chọn tất cả 5 cuốn sách văn và 1 cuốn sách tùy ý là nhạc hay hoạ trong 7 cuốn còn lại (chọn như thế sẽ không còn cuốn sách văn nào nữa, trái ý định của thầy giáo). Có tất cả 7 cách.

+ Chọn hết 4 cuốn sách nhạc và 2 cuốn sách văn hay hội hoạ trong 8 cuốn còn lại (chọn như thế sẽ không còn cuốn sách nhạc nào nữa, trái ý định của thầy giáo). Có tất cả $C_{8}^{2}$ cách.

+ Chọn 3 cuốn sách hội hoạ và 3 cuốn sách còn lại tùy ý chọn trong 9 cuốn gồm các sách văn hay nhạc (chọn như thế sẽ không còn cuốn sách hội họa nào nữa, trái ý định của thầy giáo). Có tất cả $C_{9}^{3}$ cách.

Như vậy, số cách chọn sách để tặng sao cho mỗi loại sách còn lại ít nhất 1 cuốn (như ý định thầy giáo) là

Đem số sách đã chọn tặng cho mỗi học sinh một cuốn. Vậy có 6! = 720 cách tặng.

Theo quy tắc nhân, ta có có 805.720 = 579600 cách chọn thỏa mãn yêu cầu đề bài.

Ví dụ 4. (Đề thi vào ĐHSP Vinh, 2000)

Có bao nhiêu số khác nhau gồm 7 chữ số sao cho tổng các chữ số của mỗi số là một số chẵn?

Giải.

Trước hết, có 9.$10^{6}$ số khác nhau gồm 7 chữ số.

Ta gọi số "bù" của số $\overline{a_{1}a_{2}a_{3}a_{4}a_{5}a_{6}a_{7}}$ là số $\overline{a'_{1}a'_{2}a'_{3}a'_{4}a'_{5}a'_{6}a'_{7}}$ với $a'_{i}$ = 9 - $a_{i}$ (i = 1, 2, ...,7). Tổng các chữ số của 2 số bù nhau là 63, đây là số lẻ. Vậy nếu một số có tổng các chữ số là số chẵn thì số bù của nó có tổng các chữ số là số lẻ. Mặt khác, mọi số đều có duy nhất một số bù. Vậy số các số có tổng chẵn bằng số các số có tổng lẻ. Vậy số các số có tổng chẵn bằng