Chương 3: Các qui tắc đếm

Chia sẻ: Bach Thanh Trung | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

192
lượt xem 14
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Định nghĩa ánh xạ: một ánh xạ f từ tập hợp A vào tập hợp B là ghép tương ứng liên kết với mỗi phân tử x của A một phần tử duy nhất y của B mà ta ký hiệu là f(x) và gọi là ảnh của x bởi f

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 3: Các qui tắc đếm

Chöông 3. Caùc Qui taéc Ñeám 3. CAÙC QUI TAÉC ÑEÁM. 3.1. AÙNH XAÏ. 3.1.1. ÑÒNH NGHÓA. Moät aùnh xaï f töø taäp hôïp A vaøo taäp hôïp B laø pheùp töông öùng lieân keát vôùi § moãi phaàn töû x cuûa A moät phaàn töû duy nhaát y cuûa B maø ta kyù hieäu laø f(x) vaø goïi laø aûnh cuûa x bôûi f. Ta vieát f: A →B x → f (x) Hai aùnh xaï f, g töø A vaøo B ñöôïc noùi laø baèng nhau neáu: § ∀ x ∈ A, f(x) = g(x). Neáu E laø moät taäp hôïp con cuûa A thì aûnh cuûa E bôûi f laø taäp hôïp: § f(E) = {y ∈ B/ ∃ x ∈ B, y = f(x)} T a cuõng vieát § f(E) = {f(x)/ x ∈ B} Neáu F laø moät taäp hôïp con cuûa B thì aûnh ngöôïc cuûa F laø taäp hôïp § f-1(F) = {x ∈ A / f(x) ∈ F } Chuù yù. 1. Neáu y ∈ B , ta vieát f -1({y}) = f -1(y). 2. Neáu f-1(y) = ∅ thì y khoâng naèm trong aûnh f(A) cuûa A. 3. Neáu f-1(y) = {x} thì x laø phaàn töû duy nhaát coù aûnh laø y. Goïi f laø moät aùnh xaï töø taäp hôïp A vaøo taäp hôïp B. Khi aáy ta noùi § 1. Pheùp laø toaøn aùnh neáu f(A) = B. 2. F laø ñôn aùnh neáu hai phaàn töû khaùc nhau baát kyø cuûa A coù aûnh khaùc nhau. 3. F laø song aùnh neáu noù ñoàng thôøi laø ñôn aùnh vaø toaøn aùnh. Tröông Myõ Dung 20
Chöông 3. Caùc Qui taéc Ñeám Cho hai aùnh xaï § f: A → B vaø g : B→C Aùnh xaï hôïp h töø A vaøo C xaùc ñònh bôûi: h: A →C x → h(x) = g(f(x)). 3.1.2. TÍNH CHAÁT. Giaû söû f laø moät aùnh xaï töø X vaøo Y, A vaø B laø hai taäp con tuøy yù cuûa B. Ta coù: f (A∪B) = f(A) ∪ f (B). § f (A∩B) ⊂ f(A) ∩ f (B). § f (A∪B) -1 = f -1(A) ∪ f -1(B). § f-1(A ∩B) ⊂ f-1(A) ∩ f-1(B). § 3.2. PHEÙP ÑEÁM CAÙC PHAÀN TÖÛ CUÛA MOÄT TAÄP HÔÏP. 3.2.1. THUÛ TUÏC ÑEÁM. Böôùc 0. Neáu A = ∅ ta noùi soá phaàn töû A baèng khoâng. § Ngöôïc laïi chuyeån qua böôùc 1. Böôùc 1. Choïn tuøy yù moät phaàn töû a ∈ A roài gaùn a töông öùng vôùi phaàn töû 1 § ∈ N. Neáu A= {a} ta noùi ta coù 1 phaàn töû. Neáu khoâng chuyeån qua böôùc 2. Böôùc 2. Do A ≠ { a}, toàn taïi moät phaàn töû b ∈ A vaø b ≠ a. Ta gaùn b § töông öùng vôùi phaàn töû 2 ∈N. Ta coù song aùnh: {a,b} ↔ {1,2} Neáu A = {a, b}, ta noùi A coù 2 phaàn töû, neáu khoâng cöù tieáp tuïc. Hai tröôøng hôïp coù theå xaõy ra: 1. Thuû tuïc döøng ôû moät böôùc n naøo ñoù, nghóa laø toàn taïi moät song aùnh giöõa A vaø {1.2,…n} ⊂ N. Ta noùi A coù n phaàn töû. 2. Thuû tuïc khoâng bao giôø döøng. Ta noùi A coù voâ soá phaàn töû hay A laø moät taäp hôïp voâ haïn. Tröông Myõ Dung 21
Chöông 3. Caùc Qui taéc Ñeám 3.2.2. ÑÒNH NGHÓA TAÄP HÖÕU HAÏN & TAÄP HÔÏP VOÂ HAÏN. Moät taäp hôïp A ñöôc noùi laø höõu haïn vaø coù n phaàn töû neáu toàn taïi moät song § aùnh giuõa A vaø taäp hôïp con {1,2,…n} cuûa N. T avieát Card(A) = n. Neáu A khoâng höõu haïn, ta noùi A voâ haïn. § 3.2.3. NGUYEÂN LYÙ COÄNG (QUI TAÉC 1). Giaû söû B laø moät taäp con cuûa moät taäp hôïp höõu haïn A. Goïi B la phaàn buø cuûa B trong A. Khi aáy, ta coù Card(A) = Card(B) + Card(B). 3.3. QUI TAÉC ÑEÁM 2 (QUI TAÉC NHAÂN). Giaû söû ta thöïc hieän n cuoäc thöû nghieäm khaùc nhau: − Cuoäc thöû nghieäm thöù nhaát coù k1 keát quaû khaùc nhau. − Cuoäc thöû nghieäm thöù hai coù k2 keát quaû khaùc nhau. − ..... − Cuoäc thöû nghieäm thöù n coù kn keát quaû khaùc nhau. Khi ñoù soá caùc keát quaû xaûy ra sau n cuoäc thöû nghieäm ñoù laø : k1 × k2 × . . .× kn khaùc nhau Thí duï . Giaû söû caùc baûng soá xe gaén maùy 2 baùnh töø 50cc trôû xuoáng goàm : Phaàn 1: Moät trong soá laø 57 hoaëc 58 Phaàn 2: Moät soá töø 00 ñeán 999 Phaàn 3: Hai maãu töï baát kyø. Vaäy soá caùc baûng soá xe coù theå cung caáp laø : 2 × 999 × (26 × 26) = 1.350.648 3.4. QUI TAÉC ÑEÁM 3. Giaû söû moät cuoäc thöû nghieäm cho moät trong k keát quaû khaùc nhau. Neáu cuoäc thöû nghieäm ñoù ñöôïc laëp laïi n laàn thì soá caùc keát quaû coù theå coù laø: k × k × . . . × k = kn n laàn Thí duï 1. Khi thaáy moät ñoàng tieàn, keát quaû coù theå laø maët saáp hoaëc maët ngöûa. Vaäy k = 2. Neáu ta thaáy ñoáng tieàn ñoù 10 laàn vaø ghi laïi keát quaû ôû moãi laàn thaáy thì soá caùc tröôøng hôïp coù theå xaûy ra laø : 210 = 1024 . Tröông Myõ Dung 22
Chöông 3. Caùc Qui taéc Ñeám Thí duï 2. Neáu ta thaáy moät con suùc saéc coù 6 maët 2 laàn thì soá caùc keát quaû coù theå xaûy ra laø: 62 = 36 . 3.5. QUI TAÉC ÑEÁM 4 (SOÁ HOAÙN VÒ). Giaû söû coù n vaät khaùc nhau. Soá caùch saép xeáp n vaät ñoù (coù keå thöù töï) ñöôïc cho bôûi: n! = n(n-1) . . 1 n! 0! = 1 Kyù hieäu ñoïc laø n giai thöøa vôùi qui öôùc Thí duï 1. Coù 6 quyeån saùch khaùc nhau ñöôïc ñaët treân moät keäï haøng. Soá caùch saép ñaët 6 quyeån saùch treân seõ laø : 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720 Thí duï 2. Coù 6 chöõ soá 1, 2, 3, 4, 5, 6. Tính toång cho caùc soá coù ñöôïc baèng caùch hoaùn vò caùc chöõ soá noùi treân. Goïi N laø 1 soá trong soá 720 soá coù ñöôïc thí duï N = 341526. Ta coù theå tìm ñöôïc soá moät N cuõng do hoaùn vò 6 chöõ soá ñoù vôùi tính chaát toång cuûa 2 chöõ soá ôû cuøng vò trí cuûa N vaø N’ baèng 7 vôùi N = 341526 thì N’ = 436251 Nhö vaäy ta coù 720/2 = 360 caëp soá N vaø N’ coù toång baèng 777777. Do ñoù, toång cuûa 720 soá coù ñöôïc do hoaùn vò 6 chöõ soá 1, 2, 3, 4, 5, 6 laø : 777 777 × 360 = 279.999.720 3.6. QUI TAÉC ÑEÁM 5 (SOÁ CHÆNH HÔÏP). Giaû söû ta coù moät taäp hôïp coù n phaân töû , soá taäp hôïp con coù k phaân töû (coù keå thöù töï ) ruùt ra töø taäp hôïp noùi treân baèng Ak = n! / (n -k)! = n(n -1)..(n – k + 1) Thí duï 1. Coù taát caû 6 cuoán saùch nhöng chæ coù theå xeáp 4 cuoán saùch leân keä, Vaäy soá saùch coù theå xeáp 4 quyeån saùch leân keä laø : Tröông Myõ Dung 23
Chöông 3. Caùc Qui taéc Ñeám 6! / (6 - 4)! = 6! /2! = 6 × 5 × 4 × 3 = 3 60 Thí duï 2. Xeùt taäp hôïp caùc soá goàm 3 chöõ soá khaùc nhau. Coù bao nhieâu chöõ soá nhö vaäy? Chuù yù raèng soá 0 khoâng theå ôû vò trí caùc chöõ soá haøng traêm. Goïi a, b, c, laø 3 chöõ soá khaùc nhau trong caùc chöõ soá 1, 2,...,9 Caùc soá ta ñang xeùt coù theå phaân hoaïch thaønh 5 loaïi : a. Caùc soá coù daïng abc coù taát caû laø: 9! / (9 - 3)! = 9!/ 6! = 9×8× 7= 504 soá b. Caùc soá coù daïng acb coù taát caû laø: 9! / (9 - 2)! = 9! / 7! = 9×8 = 72 soá c. Caùc soá coù daïng abc coù taát caû laø: 9! / (9 - 2)! = 72 soá Vaäy toång coù : 504 + 72 + 72 = 648 soá goàm 3 chöõ soá khaùc nhau. Caùch khaùc : Duøng qui taéc nhaân - Coù 9 caùch choïn 1 chöõ soá haøng traêm. - Coù 9 caùch choïn 1 chöõ soá haøng chuïc. - Coù 8 caùch choïn 1 chöõ soá haøng ñôn vò. Vaäy coù 9 × 9 × 8 = 648 caùch choïn 1 soá coù 3 chöõ soá khaùc nhau. 3.7. QUI TAÉC ÑEÁM 6 (SOÁ TOÅ HÔÏP). Trong moät taäp hôïp coù n vaät, soá taäp hôïp con coù k vaät ruùt ra töø taäp hôïp noùi treân (khoâng keå thöù töï ) baèng k = n! / (k! (n -k)! ) n Thí duï : Moät toå chöùc coù 20 hoäi vieân goàm 12 nam vaø 8 nöõ, muoán baàu ra moät Ban ñaïi dieän goàm 5 ngöôøi trong ñoù phaûi coù ít 2 nam vaø 2 nöõ. Coù bao nhieâu caùch thaønh laäp moät Ban ñaïi dieän nhö vaäy trong moãi tröôøng hôïp sau ñaây : a) Moïi ngöôøi ñeàu coù tham gia vaøo Ban ñaïi dieän . b) Oâng X vaø baø Y khoâng chòu ngoài chung trong moät Ban ñaïi dieän. Giaûi . a ) Coù 2 tröôøng hôïp: − Ban Ñaïi dieän coù 3 nam vaø 2 nöõ. Soá caùch ñeå thaønh laäp moät Ban Ñaïi dieän nhö vaäy baèng 3 2 = 12! / (3! 9!) x 8!/(2! 6!) = 6 160 12 8 Tröông Myõ Dung 24
Chöông 3. Caùc Qui taéc Ñeám − Ban ñaïi dieän coù 2 nam vaø 3 nöõ. Soá caùch ñeå thaønh laäp moät Ban Ñaïi dieän nhö vaäy baèng 3 2 = 12! / (2! 10!) x 8!/(3! 5!) =3 696 8 12 Vaäïy soá Ban ñaïi dieän coù theå thaønh laäp ñöôïc laø 6 160 + 3 603 = 9856. b) Tröôùc heát ta tìm soá caùch laäp moät Ban ñaïi dieän coù caû oâng X vaø baø Y. − Tröôøng hôïp 3 nam vaø 2 nöõ. Choïn 2 nam trong 11 nam (ñaõ coù OÂ.X). Choïn 1 nöõ trong 7 nöõ (ñaõ coù Baø Y). 1 2 = 11! / (2! 9!) x 7 = 385 7 11 − Tröôøng hôïp coù 2 nam vaø 3 nö õ 1 2 = 11 x 7! / (2! 5!) = 231 11 7 Vaäïy coù 385 + 231 = 616 caùch laäïp moäït Ban ñaïi dieän trong ñoù coù oâng X vaø baø Y ngoài chung. Do ñoù, soá caùch laäïp Ban ñaïi dieän khoâng coù oâng X vaø baø Y ngoài chung laø 9856 - 616 = 9240. 3 .8. SOÁ CAÙ C H PHAÂ N HOAÏ C H MOÄ T TAÄ P HÔÏ P . X laø moät taäp hôïp coù n phaân töû. Ta muoán phaân hoaïch X thaønh k lôùp (coù keå thöù töï caùc lôùp). Lôùp thöù 1 coù n1 phaân töû, Lôùp thöù 2 coù n2 phaân töû, … Lôùp thöù k coù nk phaân töû. Vaø (n 1 + n2 + ...+ nk = n). Soá phaân hoaïch coù theå laø: Tröông Myõ Dung 25
Chöông 3. Caùc Qui taéc Ñeám n1 n2, …,nk = n! / (n1 ! n2 ! …nk ! ) n Thí duï 1 . Coù bao nhieâu caùch phaân boá 8 sinh vieân vaøo 3 phoøng troï bieát raèng: Phoøng soá 1 coù 3 giöôøng Phoøng soá 2 coù 3 giöôøng Phoøng soá 3 coù 2 giöôøng Giaûi. Moãi caùch phaân boá caùc sinh vieân vaøo caùc phoøng laø moäït phaân hoaïch cuûa moäït taäp hôïp coù 8 phaân töû thaønh 3 lôùp Lôùp 1 coù n1 = 3 phaân töû Lôùp 2 coù n2 = 3 phaân töû Lôùp 3 coù n3 = 2 phaân töû Vaäïy soá phaân hoaïch laø: 3, 3, 2 = 8! / (3! 3! 2! ) = 560 8 Thí duï 2. Tranh giaûi voâ ñòch quoác gia moäït ñoäi boùng A phaûi thi ñaáu vôùi 6 ñoäi khaùc nhau. Coù bao nhieâu caùch saép xeáp ñeå keát quaû sau 6 traän ñaáu treân goàm 2 thaéng, 3 thua, 1 hoøa. Giaûi. Soá caùch saép xeáp = Soá phaân hoaïch 1 taäp hôïp coù 6 phaân töû ( caùc ñoäi boùng thi ñaáu vôùi ñoäi A ) Thaønh 3 lôùp: Lôùp thöù 1 goàm caùc ñoäi thua A ( coù 2 ñoäi ). Lôùp thöù 2 goàm caùc ñoäi thaéng A ( coù 3 ñoäi ). Lôùp thöù 3 goàm caùc ñoäi hoøa A ( coù ù ñoäi ). Vaäïy soá caùch saép xeáp laø 2, 3, 1 = 6 / (2! 3! 1! ) = 60 6 Chuù yù neáu phaân hoaïch coù thöù töï moät taäp hôïp coù n phaân töû thaønh 2 lôùp: Tröông Myõ Dung 26
Chöông 3. Caùc Qui taéc Ñeám Lôùp 1 coù k phaân töû . Lôùp 2 coù n - k phaân töû . thì Soá phaân hoaïch : k, n -k k = n! / (k! (n -k )! = n n = (Soá taäp hôïp con coù k phaân töû trong n phaân töû). 3.9. Khai trieån nhò thöùc . Coâng thöùc khai trieån nhò thöùc : n (x + y) (n laø soá nguyeân töï nhieân) ñöôïc cho bôûi : n-1 1 n n n -1 n-1 n (× + y ) = x + x y+..+ n ×y +y n Caùc heä soá k , k = 1 . . n -1 ñöôïïc cho bôûi tam giaùc PASCAL n n=1 1 1 n=2 1 2 1 n=3 1 3 3 1 n=4 1 4 6 4 1 n=5 1 5 10 10 5 1 5 5 4 3 2 2 3 2 5 Thí duï . (x + y ) = x + 5x y + 10x y +10x y +5xy + y 3.10. Khai trieån boäi thöùc . n Khai trieån cuûa (x 1 + x 2 + ....+x k ) goàm toång taát caû caùc soá haïng coù daïng : n1 n2, …,nk n1 n2 nk X X ….X n vôùi n1 + n2 + ...+ n k! = n. 3 3 3 3 2 2 2 Thí duï. (x + y + z ) = x + y + z +3x y +3yz + 3x z +6xyz Tröông Myõ Dung 27