Các bài Toán về nguyên lý số đếm

Mời các em và giáo viên tham khảo về các bài Toán về nguyên lý số đếm sẽ giúp bạn định hướng kiến thức ôn tập và rèn luyện kỹ năng giải bài tập tốt hơn.
Nội dung trích xuất từ tài liệu:
Các bài Toán về nguyên lý số đếm Các bài toán v nguyên lý m CÁC BÀI TOÁN V NGUYÊN LÝ MI. TÓM T T LÝ THUY T1. Ch nh h pCho m t t p h p g m n ph n t ( 1 ≤ n ∈ » ) . M i b s p th t g m k ph n ttrong s n ph n t ã cho ư c g i là m t ch nh h p ch p k c a n phân t ó. kS các ch nh h p ch p k c a n ph n t là: An = n ( n − 1) ... ( n − k + 1) = n! ( n − k )!2. Hoán v : M t ch nh h p ch p n c a n ph n t ư c g i là m t hóan v c a n nph n t ó. S các hoán v c a n ph n t là: Pn = An = n ( n − 1) ....2.1 = n !3. T h p: Cho m t t p h p n ph n t phân bi t. M i t p con g m k ph n tphân bi t không s p th t ( 0 ≤ k ≤ n ), l y trong s n phân t ã cho là m t th p ch p k c a n ph n t .S các t h p ch p k c a n ph n t là: C n = 1 ⋅ An = k k n! k! k !( n − k ) !4. Qui t c c ngCho X 1 , X 2 ,..., X n là các t p h p h u h n không giao nhau: X i ∩ X j = ∅ thì X 1 ∪ X 2 ... X n −1 ∪ X n = X 1 + X 2 + ... + X n −1 + X n v i X i là s ph n t . Ý nghĩa s h c:Gi s m t phép ch n ư c th c hi n qua n bư c c l p v i nhau trong ó:Bư c 1 có p1 cách th c hi n; Bư c 2 có p 2 cách; … Bư c n có p n cách.Khi ó có p1 + p 2 + ... + p n cách khác nhau th c hi n phép ch n.5. Qui t c nhânCho Cho X 1 , X 2 ,..., X n là các t p h p h u h n v i s ph n t : X i = p i , khi ó: X 1 × X 2 × ... × X n −1 × X n = p1 × p 2 × ... × p n −1 × p n Ý nghĩa s h c:Gi s m t phép ch n ư c th c hi n qua n bư c liên ti p trong ó:Bư c 1 có p1 cách th c hi n; Bư c 2 có p 2 cách ; … Bư c n có p n cách .Khi ó có p1 × p 2 × ... × p n −1 × p n cách khác nhau th c hi n phép ch n. 251Chương III. T h p, Xác su t và S ph c − Tr n PhươngII. CÁC D NG BÀI T P CƠ B N TRONG NGUYÊN LÝ MII.1. PHƯƠNG PHÁP CHUNG GI I BÀI TOÁN V C UT OSGi s m, n là các s nguyên dương v i m ≤ n thì: m1) S cách vi t m trong n ch s khác nhau vào m v trí nh trư c là An m2) S cách vi t m ch s khác nhau trong n v trí nh trư c là An( n − m v trí còn l i không thay i ch s )3) S cách vi t m ch s gi ng nhau trong n v trí nh trư c là C n − m = C n n m4) Cho t p h p g m n ch s , trong ó có ch s 0, s các s có m ch s t o mthành t chúng là ( n − 1) An −−1 1Th c v y, có ( n − 1) cách ch n ch s ng u, sau ó áp d ng m nh 2.Sau ây là các d ng toán thư ng g p.A. D ng 1. S T O THÀNH CH A CÁC CH S NH TRƯ C.Cho t p h p g m n ch s , trong ó có ch s 0, t chúng vi t ư c bao nhiêus có m ch s khác nhau sao cho trong ó có k ch s nh trư c (thu c nch s trên) v i k < m ≤ n .Cách gi i: S t o thành g m m v trí a1 a 2 ...a m . G i t p h p k ch s inhtrư c là X. Ta xét hai bài toán nh theo các kh năng c a gi thi t v t p h p Xvà ch s 0 như sau:1) Trong X ch a ch s 0Ta có ( m − 1) cách ch n v trí cho s 0;S cách ch n ( k − 1) ch s khác 0 thu c X trong ( m − 1) v trí còn l i là Am −1k m−theo m nh (1) .Theo qui t c nhân, ta ư c s các s ó là S = ( m − 1) Am−1 ⋅ An −−kk k −1 m2) Trong X không ch a ch s 0Bư c 1: Tính s các s t o thành ch a ch s 0.L n lư t có ( m − 1) cách ch n v trí cho 0 ;252 Các bài toán v nguyên lý m kS cách vi t k ch s thu c X vào ( m − 1) v trí còn l i là Am −1 theo m nh 2;S cách ch n ( m − k − 1) trong s ( n − k − 1) ch s khác 0 mà không thu c Xvào ( m − k − 1) v trí còn l i là An −−kk−−1 theo m nh m 1 1. Theo qui t c nhân, ta ư c s các s ó là: S1 = ( m − 1) Am −1 ⋅ An −−kk−−1 k m 1Bư c 2: Tính s các ...