CH NH H P L P - T H PL P Tr n Th Thanh Hư ng, Tr n ð c Duy, Mai H u Nhân, 11T THPT chuyên Nguy n B nh Khiêm, Vĩnh Long Bài toán m ñ u. Có bao nhiêu cách x p 4 viên bi gi ng nhau vào 3 h p khác nhau. L i gi i. bài toán bày chúng ta có th li t kê các trư ng h p có th x y ra như sau: G i s viên bi x p vào h p 1, h p 2, h p 3, l n lư t là x, y, z . Các trư ng h p có th x y ra ñ i v i ( x, y, z ) là: (4;0;0), (0;4;0), (0;0;4), (1;1;2), (1;2;1), (2;1;1), (1;3;0), (1;0;3), (0;1;3), (0;3;1), (3;0;1), (3;1;0), (0;2;2), (2;2;0), (2; 0; 2). V y có 15 cách x p. Nh n xét. V i bài toán này có th li t kê t t c các trư ng h p, nhưng v i nh ng bài toán tương t như th nhưng s bi và s h p l n hơn r t nhi u thì chúng ta s g p nhi u khó khăn trong vi c li t kê. V y có m t phương pháp nào giúp chúng ta gi i nh ng bài toán như th ñơn gi n hơn không? Sau ñây chúng ta hãy cùng nhau tìm hi u v “T h p l p – Ch nh h p l p”, chúng s giúp chúng ta gi i các bài toán ph c t p m t cách d dàng hơn. 1. Ch nh h p l p a) ð nh nghĩa. Cho t p X g m n (n ∈ N * ) ph n t!. M t dãy có ñ dài m (m ∈ N * ) các ph n t! c"a X , trong ñó m#i ph n t! có th l p l i nhi u l n, s$p x p theo th t nh t ñ nh g i là m t ch nh h p l p ch p m c"a n ph n t!. Ký hi u s ch nh h p l p ch p m c"a n ph n t! là Fnm . b) Công th c. Fnm = n m . Ch ng minh. Cho X = {x1 ; x2 ;......; xn } . Dãy có ñ dài m là a1a2 .......am (m ∈ N * ) . a1 có n cách ch n , a2 cũng có n cách ch n (vì a2 cũng có th gi ng a1 ), ... am cũng có n cách ch n. V y dãy có ñ dài m có n m cách ch n, hay Fnm = n m . c) Các ví d Ví d 1. Bi n ñăng kí ô tô có 6 ch s và 2 ch cái ñ u tiên trong 26 ch cái (không dùng ch O và I ). H&i s ô tô ñư c ñăng kí nhi u nh t là bao nhiêu? L i gi i. G i X là t p h p các ch cái dùng trong b ng ñăng kí, suy ra X có 24 ph n t! ( vì không dùng O và I ). Vì v y ta có F242 = 242 cách ch n cho hai ch cái ñ u tiên. G i Y là t p h p các ch s dùng trong b ng ñăng kí, suy ra Y có 10 ph n t!. Vì v y có F106 = 106 cách ch n cho 6 ch s còn l i. Do ñó có t t c 106.242 bi n s . Ví d 2. H&i có bao nhiêu s có 10 ch s mà 3 ch s ñ u và 3 ch s cu i tương ng gi ng nhau? L i gi i. Ta th y v i 1 cách ch n cho 3 ch s ñ u cũng ch có 1 cách ch n cho 3 ch s cu i ñ chúng tương ng gi ng nhau. Ta có F103 = 103 cách ch n tùy ý cho 3 ch s ñ u. Ta ph i lo i trư ng h p s 0 ñ ng ñ u, suy ra có F102 = 102 cách b lo i. Như v y ta có F103 − F102 = 103 −102 = 900 cách ch n cho 3 ch s ñ u. Nên ta có 900 cách ch n cho 3 ch s ñ u và 3 ch s cu i tương ng gi ng nhau. Ta còn l i 4 ô tr ng, mà t' 4 ô tr ng ñó ta l p ñư c F104 = 104 = 10000 . V y ta có 900.10000 = 9000000 s c n tìm. Nh n xét. T' ñó ta có th t ng quát bài toán lên như sau: Cho n > 2m > 2 (n, m ∈ N * ) . H&i có bao nhiêu s có n ch s mà m ch s ñ u và m ch s cu i tương ng gi ng nhau. L i gi i. Chúng ta cũng lí lu n như trên. Ta có ñư c ( F10m − F10m−1 ).F10n−2 m s c n tìm. 2. T h p l p a) ð nh nghĩa. M#i cách ch n ra k v t t' n lo i v t khác nhau (trong ñó m#i lo i v t có th ñư c ch n l i nhi u l n) ñư c g i là t h p l p ch p k c"a n . S các t l p ch p k c"a n ñư c ký hi u là K nk . b) Công th c. K nk = Cnk+k −1 . 1 c) Các ví d . Ví d( ñ u tiên s là m t h qu quan tr ng. Ví d 1. Gi s! có n viên bi gi ng nhau và m cái h p, ta x p bi vào các h p. G i xi v i i = 1, 2, 3..., m là s bi ) h p i. Ch ng minh r*ng a) S cách x p khác nhau n viên bi vào m cái h p là Cmn +n−1 . b) Trong Cmn +n−1 cách x p ñó có Cnm−−11 cách x p cho t t c các h p ñ u có bi. L i gi i. a) Ta bi u di n m cái h p t' m + 1 g ch th+ng ñ ng, còn các viên bi bi u di n b*ng các ngôi sao (*). Ch+ng h n như |**|*|***|*|…….|***| Như v y ) ngoài cùng luôn luôn là các v ch th+ng ñ ng, còn l i m −1 v ch th+ng ñ ng và n viên bi ñư c s$p x p theo th t tùy ý. Như v y s cách s$p x p khác nhau b*ng s cách ch n n ph n t! trong t p h p m −1 + n ph n t! (c v ch và ngôi sao) ñó chính là Cmn +n−1 . b) Trư ng h p m#i h p có ít nh t 1 viên bi tương ng v i cách bi u di n m#i v ch ph i bao g m gi a hai ngôi sao. Nhưng có t t c n −1 kho ng tr ng gi a n ngôi sao. Vì v y ph i x p m −1 v ch vào n −1 kho ng tr ng ñó. V y có t t c Cnm−−11 cách x p. Nh n xét. T' bài toán trên ta suy ra m t h qu thú v . a) S các nghi m t nhiên c"a phương trình x1 + x2 + ... + xm = n (n, m ∈ N * ) là Cmn +n−1 . b) S các nghi m nguyên dương c"a phương trình x1 + x2 + ... + xm = n ( m ≤ n, n, m ∈ N * ) là Cnm−−11 . ð th y ñư c ng d(ng c"a h qu trên ta xét ví d( sau. Ví d 2. Tìm s nghi m nguyên không âm c"a phương trình x1 + x2 + x3 + x4 = 20 (1) th&a ñi u ki n x1 ≤ 3; x2 ≥ 2; x3 > 4 (*) L i gi i. Ta vi t ñi u ki n ñã cho thành x1 ≤ 3; x2 ≥ 2; x3 ≥ 5 . Xét các ñi u ki n sau x2 ≥ 2; x3 ≥ 5 (**), x1 ≥ 4; x2 ≥ 2; x3 ≥ 5 (***). G i p, q, r l n lư t là các s nghi m nguyên không âm c"a phương trình (1) th&a các ñi u ki n (*), (**), (***). Ta có p = q − r . ð t x1, = x1 ; x2, = x2 − 2; x3, = x3 − 5; x4, = x4 , k t h p v i (**), phương trình (1) tr) thành x1, + x2, + x3, + x4, = 13 (2). S nghi m nguyên không âm c"a phương trình (1) th&a ñi u ki n (**) b*ng s nghi m nguyên không âm c"a phương trình (2). Theo h qu trên s nghi m ñó là K 413 = C413+13−1 = C1613 . V y q = C1613 . Lý lu n tương t , ta có r = K 49 = C49+9−1 = C129 . Suy ra p = q − r = C1613 − C129 = 560 − 220 = 340 . V y s nghi m nguyên không âm c"a phương trình (1) th&a ñi u ki n (*) là 340. Ví d 3. 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 1có nh t 5 bi, bi t r*ng h p 2 và h p 3 không ch a quá 6 bi. L i gi i. Trư c h t ta 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. Nh n xét r*ng ta c n l y 5 bi ñ x p trư c vào h p 1, do ñó s bi còn l i là 25. Suy ra s cách x p trong trư ng h p này b*ng s cách x p 25 bi vào 5 h p mà không có ñi u ki n gì thêm. S cách x p ñó là K 525 = C525+25−1 = C2925 = 23751 . Tương t ta có: - 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 ch a ít nh t 5 bi, h p ch a ít nh t 18 7 bi là K 518 = C518+18−1 = C22 . - 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 ch a ít nh t 5 bi, h p 3 ch a ít 18 nh t 7 bi là K 518 = C518+18−1 = C22 . 2 - 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 ch a ít nh t 5 bi, m#i h p 2 và 3 ch a ít nh t 7 bi là K 511 = C511+11−1 = C1511 . S! d(ng công th c A ∪ B = A + B − A ∩ B ta suy ra 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 ch a ít nh t 5 bi, ñ ng th i h p 2 hay h p 3 ch a ít nh t 7 bi là 18 18 K 518 + K 518 − K 511 = C22 + C22 − C1511 = 13265 (2) Theo yêu c u c"a bài toán, khi x p 30 viên bi vào 5 h p thì h p 1 ph i có ít nh t 5 bi còn m#i h p 2 và 3 ph i có không quá 6 bi. Do ñó s cách x p này s b*ng hi u c"a hai cách x p (1) và (2), t c là b*ng: 23751−13265 = 10486 . 3. Bài t p Bài 1. Tìm s nghi m nguyên không âm c"a phương trình x1 + x2 + x3 + x4 = 40 trong m#i trư ng h p sau a) x1 ≥ 3, x2 ≤ 4 , b) x1 > 3, x2 < 4 , c) 2 ≤ x1 ≤ 8, x2 ≤ 4, x3 > 3, x4 < 6 . Bài 2. [ð thi ñ i h c năm 2007 ] Có bao nhiêu b ba s nguyên không âm ( x1 , x2 , x3 ) th&a ñi u ki n x1 + x2 + x3 ≤ 15 , v i x1 > 2 , x2 < 4 . Bài 3. M#i khóa g m 5 vòng s ghi 0, 1, 2, …..,9. M#i dãy 5 ch s cho m t cách ñ m) khóa. Có bao nhiêu khóa có cách m) khác nhau. Bài 4. Có bao nhiêu cách phát 100 ph n thư)ng gi ng nhau cho 60 h c sinh. M#i h c sinh có ít nh t 1 ph n thư)ng. Bài 5. Có bao nhiêu s có 6 ch s mà a) Ch s ñ u và ch s cu i gi ng nhau. b) Ch s ñ u và ch s cu i gi ng nhau c) Hai ch s ñ u và hai ch s cu i gi ng nhau Bài 6. Có bao nhiêu cách x p kn v t khác nhau thành k nhóm, m#i nhóm có n v t? Bài 7. Ngư i ta làm m t bó hoa t' 18 hoa. Cho bi t không có bó hoa nào dư i 3 hoa. H&i có bao nhiêu cách làm m t bó hoa? Bài 8. Trong t" có n ñôi găng tay. L y t' ñó ra m t cách ng,u nhiên 2r chi c găng tay (2r < n) . Tìm xem có bao nhiêu kh năng trong s t t l y ra a) Không l$p thành m t ñôi nào c . b) Có ñúng 1 ñôi. c) Có ñúng 2 ñôi Tài li u tham kh o [1] Nguy n Vũ Thanh, “Chuyên ñ b i dư ng chuyên toán c p 2-3 S H c”, Nhà xu t b n tr-, 2001 [2] Ngô Th Phi t, “250 bài toán Gi i Tích T H p”, Nhà xu t b n ð ng Nai,1994 [3] TS.Tr n Văn Hoài, “[pdf] T h p và phép ñ m”, 2007–2008 [4] TS. Nguy n Vi t ð ng, “[pdf] T p h p, ánh x , phép ñ m” Và các tài li u trên: www.diendantoanhoc.net www.onthi.com.vn http://en.wikipedia.org/wiki/Combinations “It’s at first you don’t success try. Try again.” 3