Đại số tổ hợp - Chương IV: Tổ hợp

ĐẠI SỐ TỔ HỢP Chương IV TỔ HỢP Có n vật khác nhau, chọn ra k vật khác nhau (0 ≤ k ≤ n) không để ý đến thứ tự chọn. Mỗi cách chọn như vậy gọi là một tổ hợp chập k của n phần tử. Ta thấy mỗi tổ hợp chập k của n phần tử tạo ra được Pk = k! chỉnh hợp chập k của n phần tử. Do đó, nếu kí hiệu là số tổ hợp chập k của n phần tử, ta có : knC = knC k nA k! = n! k!(n k)!− Tính chất : = knC n k nC − = + knC k nC − − 1 1 k nC −1 + + … + = 2n nC 0 nC 1 n nC Ví dụ 1. Có 5 học sinh, cần chọn ra 2 học sinh để đi trực lớp, hỏi có mấy cách chọn ? Giải Đây là tổ hợp chập 2 của 5 phần tử. Vậy có : 25C = 5! 2!3! = 5.4 2 = 10 cách chọn. (Giả sử 5 học sinh là { }a, b, c, d, e thì 10 cách chọn là : { }a, b , { }a, c , { }a, d , { }a, e , { }b, c , { }b, d , { }b, e , { }c, d , { }c, e , { }d, e . Ví dụ 2. Một nông dân có 6 con bò, 4 con heo. Một nông dân khác đến hỏi mua 4 con bò và 2 con heo. Hỏi có mấy cách chọn mua ? Giải Chọn mua 4 con bò trong 6 con bò là tổ hợp chập 4 của 6 phần tử, có : C cách chọn. 4 6 Chọn mua 2 con heo trong 4 con heo là tổ hợp chập 2 của 4 phần tử, có : C cách chọn. 2 4 Vậy, theo qui tắc nhân, số cách chọn mua bò và heo là : = 46C × 24C 6!4!2! × 4! 2!2! = 3 6! (2!) = 6.5.4.3.2.1 8 = 6 × 5 × 3 = 90 cách chọn. Ví dụ 3. Trong một kì thi, mỗi sinh viên phải trả lời 3 trong 5 câu hỏi. a) Có mấy cách chọn. b) Có mấy cách chọn nếu trong 5 câu hỏi có 1 câu hỏi bắt buộc. Giải a) Chọn 3 trong 5 câu hỏi là tổ hợp chập 3 của 5 phần tử. Vậy có : 35C = 5! 3!2! = 5.4 2 = 10 cách chọn. b) Chọn 2 trong 4 câu hỏi còn lại là tổ hợp chập 2 của 4 phần tử Vậy có : 24C = 4! 2!2! = 4.3 2 = 6 cách chọn. Chú ý : – Có thể xem một tổ hợp chập k của n phần tử là một tập con gồm k phần tử của tập n phần tử đã cho. – Cần phân biệt trong mỗi bài toán chọn k vật từ n vật, có hay không hàm ý thứ tự . Nếu có thứ tự, đó là chỉnh hợp, nếu không có thứ tự, đó là tổ hợp. Bài 60. Giải phương trình : x 4 1 C – x 5 1 C = x 6 1 C (*) Giải Điều kiện : x ∈ và x ¥ ≤ 4. (*) ⇔ x!(4 x)! 4! − – x!(5 x)! 5! − = x!(6 x)! 6! − ⇔ (4 x)! 4! − – (5 x)(4 x)! 5 4! − − × = (6 x)(5 x)(4 x)! 6 5 4! − − − × × (do x! > 0) ⇔ 1 – 5 x 5 − = (6 x)(5 x) 30 − − (do (4 – x)! > 0) ⇔ 30 – 6(5 – x) = 30 – 11x + x2 ⇔ x2 – 17x + 30 = 0 ⇔ 1 2 x 2 x 15 (loại so điều kiện x 4) =⎡⎢ = ≤⎣ ⇔ x = 2. Bài 61. Tìm n sao cho n 3 n 1 4 n 1 C A − − + < 3 1 14P (*) Đại học Hàng hải 1999 Giải Điều kiện : n ∈ và n + 1 4 ¥ ≥ ⇔ n ∈ và n 3. ¥ ≥ (*) ⇔ (n 1)! (n 3)!2! (n 1)! (n 3)! − − + − < 1 14 3!× ⇔ (n 1)! 2! − × 1 (n 1)!+ < 1 14 6× ⇔ 1 (n 1)n+ < 1 42 ⇔ n n – 42 < 0 2 + ⇔ –7 < n < 6 Do điều kiện n ∈ và n 3 nên n ¥ ≥ ∈ { }3,4,5 . Bài 62. Tìm x thỏa : 1 2 2 2xA – 2 xA ≤ 6x 3 xC + 10. Đại học Bách khoa Hà Nội 2000 Giải Điều kiện x ∈ và x 3. ¥ ≥ Bất phương trình đã cho ⇔ 1 2 . (2x)! (2x 2)!− – x! (x 2)!− ≤ 6 x . x! 3!(x 3)!− + 10 ⇔ 1 2 .2x(2x – 1) – x(x – 1) ≤ (x – 1)(x – 2) + 10 x2 ≤ x2 – 3x + 12 ⇔ ⇔ x ≤ 4 Kết hợp với điều kiện ta có nghiệm bất phương trình là x = 3 x= 4 ∨ Bài 63. Tìm x, y thỏa y y x x y y x x 2A 5C 90 5A 2C 80 ⎧ + =⎪⎨ − =⎪⎩ Đại học Bách khoa Hà Nội 2001 Giải Điều kiện x, y ∈ N và x y. ≥ Hệ đã cho ⇔ y y x x y y x x 4A 10C 180 25A 10C 400 ⎧ + =⎪⎨ − =⎪⎩ ⇔ y x y y x x 29A 580 4A 10C 180 ⎧ =⎪⎨ + =⎪⎩ ⇔ y x y x A 2 C 10 ⎧ =⎪⎨ =⎪⎩ 0 ⇔ x! 20 (x y)! x! 10 y!(x y)! ⎧ =⎪ −⎪⎨⎪ =⎪ −⎩ ⇔ x! 20 (x y)! 20 10 y! ⎧ =⎪ −⎪⎨⎪ =⎪⎩ ⇔ x! 20 (x y)! y! 2 ⎧ =⎪ −⎨⎪ =⎩ ⇔ x! 20 (x 2)! y 2 ⎧ =⎪ −⎨⎪ =⎩ ⇔ x(x 1) 20 y 2 − =⎧⎨ =⎩ ⇔ 2x x 20 0 y 2 ⎧ − − =⎨ =⎩ ⇔ = ∨ = −⎧⎨ =⎩ x 5 x 4(loại ) y 2 ⇔ x 5 y 2 =⎧⎨ =⎩ thỏa điều kiện x, y ∈ N và x y. ≥ Bài 64. Cho k, n ∈ N thỏa n k 2. ≥ ≥ Chứng minh : k(k – 1) = n(n – 1)knC k 2 n 2C − − . Đại học Quốc gia Hà Nội 1999 Giải Ta có : n(n – 1) = n(n – 1)k 2n 2C − − (n 2)! (k 2)!(n k)! − − − n(n – 1) = k 2n 2C − − n! (k 2)!(n k)!− − = − − − − k(k 1)n! k(k 1)(k 2)!(n k)! = k(k – 1) n! k!(n k)!− = k(k – 1) k nC . Bài 65. Cho 4 k n. Chứng minh : ≤ ≤ + 4 + 6knC k 1 nC − k 2 nC − + 4 k 3nC − + k 4nC − = kn 4C + . Đại học Quốc gia TP. HCM 1997 Giải Áp dụng tính chất của tổ hợp knC = k n 1C − + k 1 n 1C − − Ta có : + 4 + 6knC k 1 nC − k 2 nC − + 4 k 3nC − + k 4nC − = ( ) + 3(knC + k 1 nC − k 1 nC − + k 2nC − ) + 3( k 2nC − + k 3nC − ) + + k 3nC − k 4 nC − = + 3 + 3kn 1C + k 1 n 1C − + k 2 n 1C − + + k 3 n 1C − + = ( + ) + 2(kn 1C + k 1 n 1C − + k 1 n 1C − + + k 2 n 1C − + ) + ( k 2 n 1C − + + k 3 n 1C − + ) = + 2kn 2C + k 1 n 2C − + + k 2 n 2C − + = ( + ) + (kn 2C + k 1 n 2C − + k 1 n 2C − + + k 2 n 2C − + ) = + = kn 3C + k 1 n 3C − + + k n 4C . Bài 66. Tìm k ∈ N sao cho k14C + k 214C + = 2 k 114C + . Cao đẳng Sư phạm TP. HCM 1998 Giải Điều kiện k ∈ N và k 12. ≤ Ta có : = 2k14C + k 2 14C + k 1 14C + ⇔ 14! k!(14 k)!− + 14! (k 2)!(12 k)!+ − = 2 14! (k 1)!(13 k)!+ − ⇔ 1 k!(14 k)!− + 1 (k 2)!(12 k)!+ − = 2 (k 1)!(13 k)!+ − ⇔ (k + 2)(k + 1) + (14 – k)(13 – k) = 2(k + 2)(14 – k) ⇔ 2k2 – 24k + 184 = 2(–k2 + 12k + 28) ⇔ 4k2 – 48k + 128 = 0 ⇔ k = 8 k = 4 (nhận so điều kiện k ∨ ∈ N và k ≤ 12). Bài 67*. Chứng minh nếu k ∈ N và 0 ≤ k ≤ 2000 thì + k2001C k 1 2001C + ≤ + (1) 10002001C 10012001C Đại học Quốc gia Hà Nội khối A 2000 Giải Do + nên (1) knC = k 1 n 1C − − k n 1C − ⇔ k 12002C + ≤ 10012002C Xét dãy { }ku = với k k2002C ∈ [0, 1000] đây là 1 dãy tăng vì uk ≤ uk+1 ⇔ k2002C ≤ k 12002C + ⇔ (2002)! k!(2002 k)!− ≤ (2002)! (k 1)!(2001 k)!+ − ⇔ (k 1)! k! + ≤ (2002 k)! (2001 k)! − − ⇔ k + 1 ≤ 2002 – k ⇔ 2k ≤ 2001 luôn đúng ∀ k ∈ [0, 1000]. Do đó : uk+1 ≤ uk+2 … ≤ ≤ u1001 nên k 12002C + ≤ 10012002C ∀ k ∈ [0, 1000] Mặt khác do = k 12002C + 2001 k 2002C − nên khi k ∈ [1001, 2000] thì (2001 – k) ∈ [1, 1000] Bất đẳng thức (1) vẫn đúng. Vậy (1) luôn đúng k ∈ [0, 2000]. ∀ Bài 68*. Với mọi n, k ∈ N và n ≥ k 0. Chứng minh : ≥ n2n kC + . n 2n kC − ≤ ( )2n2nC . Đại học Y dược TP. HCM 1998 Giải Xét dãy số { }ku = .n2n kC + n2n kC − đây là dãy giảm vì uk ≥ uk+1 ⇔ .n2n kC + n2n kC − ≥ n2n k 1C + + . n2n k 1C − − ⇔ (2n k)! n!(n k)! + + . (2n k)! n!(n k)! − − ≥ (2n k 1)! n!(n k 1)! + + + + . (2n k 1)! n!(n k 1)! − − − − ⇔ (n k 1)! (n k)! + + + . (2n k)! (2n k 1)! − − − ≥ (2n k 1)! (2n k)! + + + . (n k)! (n k 1)! − − − ⇔ (n + k + 1)(2n – k) (2n + k + 1)(n – k) ≥ ⇔ 2n2 + nk – k2 + 2n – k 2n2 – nk – k2 + n – k ≥ ⇔ 2nk + n 0 luôn đúng ≥ ∀ k, n ∈ N Do đó u0 ≥ u1 ≥ u2 … uk uk+1 … un ≥ ≥ ≥ ≥ Vậy u0 ≥ uk ⇔ .n2n 0C + n2n 0C − ≥ n2n kC + . n2n kC − . Bài 69. Cho n nguyên dương cố định và k ∈ { }0,1,2,....,n∈ . Chứng minh rằng nếu đạt giá trị lớn nhất tại ko thì k0 thỏa knC 0 n 1 n 1k 2 2 − +≤ ≤ . Đại học Sư phạm Vinh 2001 Giải Do có tính đối xứng, nghĩa là = knC k nC n k nC − , ta có : = , = , = 0nC n nC 1 nC n 1 nC − 2 nC n 2 nC − … Và dãy { }ku = với k ∈ [0, knC n2 ] đây là 1 dãy tăng nên ta có đạt max ⇔ knC ⇔ k k n n k k n n C C C C + − ⎧ ≥⎪⎨ ≥⎪⎩ 1 1 n! n! k!(n k)! (k 1)!(n k 1)! n! n! k!(n k)! (k 1)!(n k 1)! ⎧ ≥⎪ − + − −⎪⎨⎪ ≥⎪ − − − +⎩ ⇔ (k 1)! (n k)! k! (n k 1)! (n k 1)! k! (n k)! (k 1)! + −⎧ ≥⎪ − −⎪⎨ − +⎪ ≥⎪ − −⎩ ⇔ k 1 n k n k 1 k + ≥ −⎧⎨ − + ≥⎩ ⇔ n 1k 2 n 1k 2 −⎧ ≥⎪⎪⎨ +⎪ ≤⎪⎩ Do đó k thỏa n 1 n 1k 2 2 − +≤ ≤ . Bài 70. Cho m, n ∈ N với 0 < m < n. Chứng minh : a) m = nmnC m 1 n 1C − − b) = + + … + mnC m 1 n 1C − − m 1 n 2C − − m 1 mC − + m 1m 1C − − . Trung tâm Bồi dưỡng Cán bộ Y tế TP. HCM 1998 Giải a) Ta có : n = nm 1n 1C − − (n 1)! (m 1)!(n m)! − − − = n! (m 1)!(n m)!− − = m.n! m(m 1)!(n m)!− − = m. n! m!(n m)!− = m. . m nC b) Với k ∈ N và k m. Ta có ≥ = + mkC m k-1C − − m 1 k 1C ⇔ −−m 1k 1C = – mkC mk-1C Với k = n ta có −− m 1 n 1C = – (1) m nC m n-1C Với k = n – 1 ta có −− m 1 n 2C = m n 1C − – − m n 2C (2) Với k = n – 2 ta có −− m 1 n 3C = m n 2C − – − m n 3C (3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Với k = m + 1 ta có −m 1mC = m m 1C + – (n – m – 1) m mC và −− m 1 m 1C = = 1. m mC Cộng vế theo vế các đẳng thức trên ta được điều phải chứng minh. Bài 71. Chứng minh : + . + … + .02002C . 2001 2002C 1 2002C 2000 2001C k 2002C 2001 k 2002 kC − − + … + = 1001.2 2002. 20012002C . 0 1C Trung tâm Bồi dưỡng Cán bộ Y tế TP. HCM 2001 Giải Vế trái = 200 = 1 k 2001 k 2002 2002 k k 0 C .C −− = ∑ 2001 k 0 2002! k!(2002 k)!= −∑ . (2002 k)! (2001 k)!1! − − = 2001 k 0 2002! k!(2001 k)!= −∑ = 2001 k 0 2002.2001! k!(2001 k)!= −∑ = 2002 = 2002.22001 (do 2001 k 2001 k 0 C = ∑ n kn k 0 C = ∑ = 2n) = 1001.22002 = vế phải. Bài 72. Đề thi trắc nghiệm có 10 câu hỏi, học sinh cần chọn trả lời 8 câu . a) Hỏi có mấy cách chọn tùy ý ? b) Hỏi có mấy cách chọn nếu 3 câu đầu là bắt buộc ? c) Hỏi có mấy cách chọn 4 trong 5 câu đầu và 4 trong 5 câu sau ? Giải a) Chọn tùy ý 8 trong 10 câu là tổ hợp chập 8 của 10 phần tử, có : = 810C 10! 8!2! = 10.9 2 = 45 cách. b) Vì có 3 câu bắt buộc nên phải chọn thêm 5 câu trong 7 câu còn lại, đây là tổ hợp chập 5 của 7 phần tử, có : = 57C 7! 5!2! = 7.6 2 = 21 cách. c) Chọn 4 trong 5 câu đầu, có cách. Tiếp theo, chọn 4 trong 5 câu sau, có cách. Vậy, theo qui tắc nhân, có : 4 5C 4 5C . = 45C 4 5C 25! 4!1! ⎛⎜⎝ ⎠ ⎞⎟ = 25 cách. Bài 73. Có 12 học sinh ưu tú. Cần chọn ra 4 học sinh để đi dự đại hội học sinh ưu tú toàn quốc. Có mấy cách chọn. a) Tùy ý ? b) Sao cho 2 học sinh A và B không cùng đi ? c) Sao cho 2 học sinh A và B cùng đi hoặc cùng không đi? Giải a) Chọn tùy ý 4 trong 12 học sinh, là tổ hợp chập 4 của 12 phần tử. Vậy, có : 412C = 12! 4!8! = 12.11.10.9 2.3.4 = 11.5.9 = 495 cách. b) * Cách 1 : Nếu A, B cùng không đi, cần chọn 4 trong 10 học sinh còn lại. Đây là tổ hợp chập 4 của 10 phần tử, có : 410C = 10! 4!6! = 10.9.8.7 2.3.4 = 10.3.7 = 210 cách. Nếu A đi, B không đi, cần chọn thêm 3 trong 10 học sinh còn lại có : 310C = 10! 3!7! = 10.9.8 2.3 = 5.3.8 = 120 cách. Tương tự, nếu B đi, A không đi, có : 120 cách. Vậy, số cách chọn theo yêu cầu là : 210 + 120 +120 = 450 cách. * Cách 2 : Nếu A và B cùng đi, cần chọn thêm 2 trong 10 học sinh còn lại, có : 210C = 10! 2!8! = 9.5 = 45 cách. Suy ra, số cách chọn theo yêu cầu là : 495 – 45 = 450 cách. c) A và B cùng đi, có = 45 cách. 210C A và B cùng không đi, có = 210 cách. 410C Vậy có : 45 + 210 = 255 cách. Bài 74. Một phụ nữ có 11 người bạn thân trong đó có 6 nữ. Cô ta định mời ít nhất 3 người trong 11 người đó đến dự tiệc. Hỏi : a) Có mấy cách mời ? b) Có mấy cách mời để trong buổi tiệc gồm cô ta và các khách mời, số nam nữ bằng nhau . Giải a) Mời 3 người trong 11 người, có : cách. 311C Mời 4 người trong 11 người, có : cách. 411C Lập luận tương tự khi mời 5, 6, 7, 8, 9, 10, 11 trong 11 người. Vậy, có : + … + = ( + … + ) – ( 311C + 4 11C 11 11C 0 11C + 1 11C 11 11C 0 11C + 1 11C + 2 11C ) = 211 – 1 – 11 – 55 = 1981 cách. b) Mời 1 nữ trong 6 nữ, 2 nam trong 5 nam, có : cách. 16C . 2 5C Mời 2 nữ trong 6 nữ, 3 nam trong 5 nam, có : cách. 26C . 3 5C Mời 3 nữ trong 6 nữ, 4 nam trong 5 nam, có : cách. 36C . 4 5C Mời 4 nữ trong 6 nữ, 5 nam trong 5 nam, có : cách. 46C . 5 5C Vậy, có : 55 = 325 cách. 1 6C . 2 5C + 2 6C . 3 5C + 3 6C . 4 5C + 4 6C . C Bài 75. Một tổ có 12 học sinh. Thầy giáo có 3 đề kiểm tra khác nhau. Cần chọn 4 học sinh cho mỗi đề kiểm tra. Hỏi có mấy cách chọn ? Giải Đầu tiên, chọn 4 trong 12 học sinh cho đề một, có cách. 412C Tiếp đến, chọn 4 trong 8 học sinh còn lại cho đề hai, có cách. 48C Các học sinh còn lại làm đề ba. Vậy, có : 412C . 4 8C = 12! 4!8! . 8! 4!4! = 12.11.10.9 2.3.4 . 8.7.6.5 2.3.4 = (11.5.9).(7.2.5) = 34650 cách. Bài 76. Có 12 học sinh ưu tú của một trường trung học. Muốn chọn một đoàn đại biểu gồm 5 người (gồm một trưởng đoàn, một thư ký, và ba thành viên) đi dự trại quốc tế. Hỏi có bao nhiêu cách chọn ? Có giải thích ? Đại học Quốc gia TP. HCM 1997 Giải Số cách chọn 1 trưởng đoàn : 12 Số cách chọn 1 thư ký : 11 Số cách chọn 3 thành viên : 310C = 10! 3!7! = 10.9.8 6 = 120 Số cách chọn đoàn đại biểu : 12 × 11 × 120 = 15 840. Bài 77. Một đoàn tàu có 3 toa chở khách; toa I, II, III. Trên sân ga có 4 hành khách chuẩn bị đi tàu. Biết rằng mỗi toa có ít nhất 4 chỗ trống. Hỏi : a) Có bao nhiêu cách sắp 4 hành khách lên 3 toa. b) Có bao nhiêu cách sắp 4 hành khách lên tàu để có 1 toa trong đó có 3 trong 4 vị khách. Đại học Luật Hà Nội 1999 Giải a) Đoàn tàu có 3 toa ; hành khách lên 3 toa nghĩa là lên tàu. Mỗi khách có 3 cách lên toa I hoặc II hoặc III. Vậy số cách sắp 4 khách lên 3 toa là : 3 × 3 × 3 × 3 = 81 cách. b) Số cách sắp 3 khách lên toa I : 34C = 4! 3! = 4. Số cách sắp 1 khách còn lại lên toa II hoặc III : 2. Vậy nếu 3 khách ở toa I thì có : 4 × 2 = 8 cách. Lập luận tương tự nếu 3 khách ở toa II, hoặc III cũng là 8. Vậy số cách thỏa yêu cầu bài toán : 8 + 8 + 8 = 24 cách. Bài 78. Có 30 câu hỏi khác nhau gồm 5 câu khó, 10 câu trung bình và 15 câu dễ. Từ 30 câu đó có thể lập bao nhiêu đề kiểm tra, mỗi đề gồm 5 câu khác nhau, sao cho mỗi đề phải có 3 loại (khó, trung bình, dễ) và số câu dễ không ít hơn 2 ? Tuyển sinh khối B 2004 Giải Số đề thi gồm 2 câu dễ, 2 câu trung bình và 1 câu khó .5 = 215C . 2 10C 15! 2!13! . 10! 2!8! × 5 = 23625. Số đề thi gồm 2 câu dễ, 1 câu trung bình và 2 câu khó × 10 × = 10. 215C 25C 15!2!13! . 5! 2!3! = 10500 Số đề thi gồm 3 câu dễ, 1 câu trung bình và 1 câu khó × 10 × 5 = 315C 15!3!12! × 50 = 22750 Vì các cách chọn đôi một khác nhau, nên số đề kiểm tra là : 23 625 + 10 500 + 22 750 = 56875. Bài 79. Một chi đoàn có 20 đoàn viên trong đó 10 nữ. Muốn chọn 1 tổ công tác có 5 người. Có bao nhiêu cách chọn nếu tổ cần ít nhất 1 nữ. Đại học Y Hà Nội 1998 Giải Số cách chọn 5 đoàn viên bất kì 520C . Số cách chọn 5 đoàn viên toàn là nam 510C . Vậy số cách chọn có ít nhất 1 nữ là : 520C – 5 10C = 20! 5!15! – 10! 5!5! = 15252 cách. Bài 80. Một đội xây dựng gồm 10 công nhân, 3 kỹ sư. Để lập 1 tổ công tác cần chọn 1 kỹ sư là tổ trưởng, 1 công nhân làm tổ phó và 3 công nhân làm tổ viên. Hỏi có bao nhiêu cách lập tổ công tác. Đại học Kiến trúc Hà Nội 1998 Giải Số cách chọn 1 kỹ sư làm tổ trưởng : 3 Số cách chọn 1 công nhân làm tổ phó : 10 Số cách chọn 3 công nhân làm tổ viên : . 39C Vậy số cách lập tổ : 3 × 10 × = 3 39C × 10 × 9!3!6! = 2520. Bài 81. Một đội văn nghệ gồm 10 học sinh nam và 10 học sinh nữ. Cô giáo muốn chọn ra 1 tốp ca gồm 5 em trong đó có ít nhất là 2 em nam và 2 em nữ. Hỏi có bao nhiêu cách chọn. Cao đẳng Sư phạm Hà Nội 1999 Giải Số cách chọn 3 em nam và 2 em nữ : 310C . 2 10C Số cách chọn 2 em nam và 3 em nữ : 210C . 3 10C Vậy số cách thỏa yêu cầu bài toán là : 2 = 2310C . 2 10C 10! 3!7! . 10! 2!8! = 2 10 9 8 6 × × . 10 9 2 × = 10.800. Bài 82. Một đội cảnh sát gồm có 9 người. Trong ngày cần 3 người làm nhiệm vụ tại địa điểm A, 2 người làm tại B còn lại 4 người trực đồn. Hỏi có bao nhiêu cách phân công ? Học viện Kỹ Thuật Quân sự 2000 Giải Số cách phân công 3 người tại A : 39C Số cách phân công 2 người tại B : 26C Số cách phân công 4 người còn lại : 1. Vậy số cách phân công là : 39C . 2 6C = 9! 3!6! . 6! 2!4! = 9! 3!2!4! = 9 8 7 6 5 6 2 × × × × × = 1260. Bài 83. Có 5 nhà Toán học nam, 3 nhà Toán học nữ và 4 nhà Vật lí nam. Muốn lập 1 đoàn công tác có 3 người gồm cả nam lẫn nữ, cần có cả nhà toán học lẫn vật lí. Hỏi có bao nhiêu cách chọn. Đại học Y Hà Nội 2000 Giải Số cách chọn 2 nhà Toán học nữ và 1 nhà Vật lí nam là : 23C × 4 = 3!2! × 4 = 12 Số cách chọn 1 nhà Toán học nữ và 2 nhà Vật lí nam là : 3 × = 3 24C × 4!2!2! = 3.4.3 2 = 18 Số cách chọn 1 nhà Toán học nữ, 1 nhà Toán học nam và 1 nhà Vật lí nam là : 5 × 3 × 4 = 60 Vậy có cách chọn đoàn công tác là : 12 + 18 + 60 = 90. Bài 84. Một đội văn nghệ có 10 người trong đó có 6 nữ và 4 nam. Có bao nhiêu cách chia đội văn nghệ : a) Thành 2 nhóm có số người bằng nhau và mỗi nhóm có số nữ bằng nhau. b) Có bao nhiêu cách chọn 5 người trong đó không quá 1 nam. Học viện Chính trị 2001 Giải a) Do mỗi nhóm có số người bằng nhau nên mỗi nhóm phải có 5 người. Do số nữ bằng nhau nên mỗi nhóm phải có 3 nữ. Vậy mỗi nhóm phải có 3 nữ và 2 nam. Số cách chọn là : . = 36C 2 4C 6! 3!3! × 4! 2!2! = 6 5 4 6 × × × 4 3 2 × = 20 × 6 = 120. b) Số cách chọn 5 người toàn nữ là : 56C = 6! 5! = 6. Số cách chọn 4 nữ và 1 nam là : 46C × 4 = 6!4!2! × 4 = 6 5 2 × × 4 = 60 Vậy số cách chọn 5 người mà không quá 1 nam : 6 + 60 = 66. Bài 85. Có 5 tem thư khác nhau và 6 bì thư cũng khác nhau. Người ta muốn chọn từ đó ra 3 tem thư, 3 bì thư và dán 3 tem thư đó lên 3 bì thư đã chọn. Một bì thư chỉ dán 1 tem thư. Hỏi có bao nhiêu cách làm như vậy. Tú tài 1999 Giải Số cách chọn 3 tem từ 5 tem là = 35C 5! 3!2! = 10. Số cách chọn 3 bì thư từ 6 bì thư là = 36C 6! 3!3! = 20. Do các tem đều khác nhau, các bì thư cũng khác nhau, nên số cách dán 3 tem lên 3 bì thư là 3! = 6. Vậy số cách làm là : . .3! = 10.20.6 = 1200 cách. 35C 3 6C Bài 86. Một bộ bài có 52 lá; có 4 loại : cơ, rô, chuồn, bích mỗi loại có 13 lá. Muốn lấy ra 8 lá bài trong đó phải có đúng 1 lá cơ, đúng 3 lá rô và không quá 2 lá bích. Hỏi có mấy cách ? Giải Số cách chọn 1 lá cơ và 3 lá rô : cách. 113C . 3 13C • Trường hợp 1 : Chọn tiếp 4 lá chuồn (nghĩa là không có lá bích nào) có : 413C cách. • Trường hợp 2 : Chọn tiếp 1 lá bích và 3 lá chuồn có : 13. 313C cách. • Trường hợp 3 : Chọn tiếp 2 lá bích và 2 lá chuồn có : 213C . 213C cách. Vậy số cách chọn thỏa yêu cầu đề toán : 13. ( + 13. + . ) = 39 102 206 cách. 313C 4 13C 3 13C 2 13C 2 13C Bài 87. Có 2 đường thẳng song song (d1) và (d2). Trên (d1) lấy 15 điểm phân biệt. Trên (d2) lấy 9 điểm phân biệt. Hỏi số tam giác mà có 3 đỉnh là các điểm đã lấy. Giải (d1) (d2) Bk Bj Ai Có hai loại tam giác tạo thành. a) Một đỉnh trên (d1) và 2 đỉnh trên (d2) Có 15 cách lấy 1 đỉnh trên (d1) Có cách lấy 2 đỉnh trên (d2). 29C Ai Bk (d2) (d1)Aj b) Hai đỉnh trên (d1) và 1 đỉnh trên (d2) Có cách lấy 2 đỉnh trên (d1) 215C 9 cách lấy 1 đỉnh trên (d2). Vậy số tam giác tạo thành : 15 + 9 = 15.29C 2 15C 9! 2!7! + 9. 15! 2!13! = 540 + 945 = 1485. Bài 88. Một lớp có 20 học sinh trong đó có 2 cán bộ lớp. Hỏi có bao nhiêu cách chọn 3 người đi dự hội nghị của trường sao cho trong đó có ít nhất 1 cán bộ lớp. Đại học Giao thông Vận tải 2000 Giải Số cách chọn 3 người trong đó có 1 cán bộ lớp 2 × 218C = 2 × 18!2!16! = 18 × 17 Số cách chọn 3 người trong đó có 2 cán bộ lớp 1 = 18 118C Vậy số cách chọn thỏa yêu cầu bài toán là : 18 × 17 + 18 = 182 = 324. Bài 89. Có 16 học sinh gồm 3 học sinh giỏi, 5 khá, 8 trung bình. Có bao nhiêu cách chia số học sinh thành 2 tổ, mỗi tổ có 8 người, đều có học sinh giỏi và ít nhất 2 học sinh khá. Học viện Quân sự 2001 Giải Vì mỗi tổ đều có học sinh giỏi nên số học sinh giỏi mỗi tổ là 1 hay 2. Vì mỗi tổ đều có ít nhất 2 học sinh khá nên số học sinh khá mỗi tổ 2 hay 3. Do đó nếu xem số học sinh giỏi, khá, trung bình mỗi tổ là tọa độ một vectơ 3 chiều ta có 4 trường hợp đối với tổ 1 là (1, 2, 5) (1, 3, 4), (2, 2, 4), (2, 3, 3). Tương ứng 4 trường hợp đối với tổ 2 là : (2, 3, 3), (2, 2, 4), (1, 3, 4), (1, 2, 5). Ta thấy có 2 trường hợp bị trùng. Vậy chỉ có 2 trường hợp là : Trường hợp 1 : Số cách chọn một tổ nào đó có 1 giỏi, 2 khá và 5 trung bình là : 3 × 25C × 58C Vậy tổ còn lại có 2 giỏi, 3 khá, 3 trung bình thỏa yêu cầu bài toán. Trường hợp 2 : Số cách chọn một tổ có 1 giỏi, 3 khá và 4 trung bình là : 3 × 35C × 48C Vậy tổ còn lại có 2 giỏi, 2 khá và 4 trung bình thỏa yêu cầu bài toán. Do đó số cách chia học sinh làm 2 tổ thỏa yêu cầu bài toán là : 3 + 3 = 325C 5 8C 3 5C 4 8C ⎛ ⎞+ =⎜ ⎟⎝ ⎠ 5! 8! 8! 3780. 2!3! 5!3! 4!4! Bài 90. Một người có 12 cây giống trong đó có 6 cây xoài, 4 cây mít và 2 cây ổi. Người đó muốn chọn 6 cây giống để trồng. Hỏi có bao nhiêu cách chọn sao cho a) Mỗi loại có đúng 2 cây. b) Mỗi loại có ít nhất 1 cây. Trường Hàng không 2000. Giải a) Số cách chọn 2 cây xoài trong 6 cây xoài : 26C Số cách chọn 2 cây mít trong 4 cây mít : 24C Số cách chọn 2 cây ổi trong 2 cây ổi : 1 Vậy số cách chọn mà mỗi loại đúng 2 cây : = 90 cách. 26C . 2 4C b) Chọn 1 cây ổi, 4 mít, 1 xoài : 2 × 1 × 6 = 12 cách. Chọn 1 ổi, 3 mít và 2 xoài có : 2 . = 2 34C 2 6C × 4 × 15 = 120 cách. Chọn 1 ổi, 2 mít và 3 xoài có : 2 = 240 cách. 24C . 3 6C Chọn 1 ổi, 1 mít và 4 xoài có : 2 × 4 × = 120 cách. 46C Chọn 2 ổi, 3 mít và 1 xoài có : 1 × 34C × 6 = 24 cách. Chọn 2 ổi, 2 mít và 2 xoài có : 1 × 24C × = 90 cách. 26C Chọn 2 ổi, 1 mít và 3 xoài có : 1 × 4 × = 80 cách. 36C Vậy số cách chọn mà mỗi loại có ít nhất 1 cây là : 12 + 120 + 240 + 120 + 24 + 90 + 80 = 686 cách. Bài 91. Một lớp học có 30 học sinh nam và 15 học sinh nữ. Có 6 học sinh được chọn để lập 1 tốp ca. Hỏi có bao nhiêu cách chọn khác nhau và phải có ít nhất 2 nữ. Đại học Huế 2000 Giải Số cách chọn 6 học sinh bất kì nam hay nữ : 645C = 45! 6!39! = 8145060. Số cách chọn 6 học sinh toàn nam : 630C = 30! 6!24! = 593775. Số cách chọn 5 nam và 1 nữ : 530C × 15 = 30!25!5! × 15 = 2137590. Vậy có số cách chọn 6 học sinh trong đó phải có ít nhất 2 nữ – ( + 15 ) = 5413695 cách. 645C 6 30C 5 30C Bài 92. Cho tập con gồm 10 phần tử khác nhau. Tìm số tập con khác rỗng chứa 1 số chẵn các phần tử. Đại học Nông nghiệp khối B 2000 Giải Khi tập X có n phần tử thì số tập con của X có k phần tử là knC Do đó n = 10 thì : Số tập con của X có 2 phần tử là 210C Số tập con của X có 4 phần tử là 410C Số tập con của X có 6 phần tử là 610C Số tập con của X có 8 phần tử là 810C Số tập con của X có 10 phần