[Giáo trình Toán rời rạc] - Chương2 - Bài Toán Đếm

Tài liệu " [Giáo trình Toán rời rạc] - Chương2 - Bài Toán Đếm " mang tính chất tham khảo, giúp ích cho các bạn tự học, ôn thi, với phương pháp học hay, thú vị, rèn luyện kỹ năng giải đề, nâng cao vốn kiến thức cho các bạn trong các kỳ thi sắp tới. Tác giả hy vọng tài liệu này sẽ giúp ích cho các bạn.
Nội dung trích xuất từ tài liệu:
[Giáo trình Toán rời rạc] - Chương2 - Bài Toán Đếm http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p CHƯƠNG II BÀI TOÁN ð M Lý thuy t t h p là m t ph n quan tr ng c a toán h c r i r c chuyên nghiên c us phân b các ph n t vào các t p h p. Thông thư ng các ph n t này là h u h n vàvi c phân b chúng ph i tho mãn nh ng ñi u ki n nh t ñ nh nào ñó, tùy theo yêu c uc a bài toán c n nghiên c u. M i cách phân b như v y g i là m t c u hình t h p. Chñ này ñã ñư c nghiên c u t th k 17, khi nh ng câu h i v t h p ñư c nêu ra trongnh ng công trình nghiên c u các trò chơi may r i. Li t kê, ñ m các ñ i tư ng có nh ngtính ch t nào ñó là m t ph n quan tr ng c a lý thuy t t h p. Chúng ta c n ph i ñ m cácñ i tư ng ñ gi i nhi u bài toán khác nhau. Hơn n a các k thu t ñ m ñư c dùng r tnhi u khi tính xác su t c a các bi n c .2.1. CƠ S C A PHÉP ð M.2.1.1. Nh ng nguyên lý ñ m cơ b n:1) Quy t c c ng: Gi s có k công vi c T1, T2, ..., Tk. Các vi c này có th làm tương ng b ng n1, n2, ..., nk cách và gi s không có hai vi c nào có th làm ñ ng th i. Khi ñós cách làm m t trong k vi c ñó là n1+n2+ ... + nk.Thí d 1: 1) M t sinh viên có th ch n bài th c hành máy tính t m t trong ba danhsách tương ng có 23, 15 và 19 bài. Vì v y, theo quy t c c ng có 23 + 15 + 19 = 57cách ch n bài th c hành.2) Giá tr c a bi n m b ng bao nhiêu sau khi ño n chương trình sau ñư c th c hi n? m := 0 for i1 := 1 to n1 m := m+1 for i2 :=1 to n2 m := m+1 ....................... for ik := 1 to nk m := m+1 Giá tr kh i t o c a m b ng 0. Kh i l nh này g m k vòng l p khác nhau. Sau m ibư c l p c a t ng vòng l p giá tr c a k ñư c tăng lên m t ñơn v . G i Ti là vi c thihành vòng l p th i. Có th làm Ti b ng ni cách vì vòng l p th i có ni bư c l p. Do cácvòng l p không th th c hi n ñ ng th i nên theo quy t c c ng, giá tr cu i cùng c a mb ng s cách th c hi n m t trong s các nhi m v Ti, t c là m = n1+n2+ ... + nk. Quy t c c ng có th phát bi u dư i d ng c a ngôn ng t p h p như sau: N u A1,A2, ..., Ak là các t p h p ñôi m t r i nhau, khi ñó s ph n t c a h p các t p h p nàyb ng t ng s các ph n t c a các t p thành ph n. Gi s Ti là vi c ch n m t ph n t t 22http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t pt p Ai v i i=1,2, ..., k. Có |Ai| cách làm Ti và không có hai vi c nào có th ñư c làmcùng m t lúc. S cách ch n m t ph n t c a h p các t p h p này, m t m t b ng s ph nt c a nó, m t khác theo quy t c c ng nó b ng |A1|+|A2|+ ... +|Ak|. Do ñó ta có: |A1 ∪ A2 ∪...∪ Ak| = |A1| + |A2| + ... + |Ak|.2) Quy t c nhân: Gi s m t nhi m v nào ñó ñư c tách ra thành k vi c T1, T2, ..., Tk.N u vi c Ti có th làm b ng ni cách sau khi các vi c T1, T2, ... Ti-1 ñã ñư c làm, khi ñócó n1.n2....nk cách thi hành nhi m v ñã cho.Thí d 2: 1) Ngư i ta có th ghi nhãn cho nh ng chi c gh trong m t gi ng ñư ng b ngm t ch cái và m t s nguyên dương không vư t quá 100. B ng cách như v y, nhi unh t có bao nhiêu chi c gh có th ñư c ghi nhãn khác nhau? Th t c ghi nhãn cho m t chi c gh g m hai vi c, gán m t trong 26 ch cái vàsau ñó gán m t trong 100 s nguyên dương. Quy t c nhân ch ra r ng có 26.100=2600cách khác nhau ñ gán nhãn cho m t chi c gh . Như v y nhi u nh t ta có th gán nhãncho 2600 chi c gh .2) Có bao nhiêu xâu nh phân có ñ dài n. M i m t trong n bit c a xâu nh phân có th ch n b ng hai cách vì m i bit ho cb ng 0 ho c b ng 1. B i v y theo quy t c nhân có t ng c ng 2n xâu nh phân khác nhaucó ñ dài b ng n.3) Có th t o ñư c bao nhiêu ánh x t t p A có m ph n t vào t p B có n ph n t ? Theo ñ nh nghĩa, m t ánh x xác ñ nh trên A có giá tr trên B là m t phép tương ng m i ph n t c a A v i m t ph n t nào ñó c a B. Rõ ràng sau khi ñã ch n ñư c nhc a i - 1 ph n t ñ u, ñ ch n nh c a ph n t th i c a A ta có n cách. Vì v y theo quyt c nhân, ta có n.n...n=nm ánh x xác ñ nh trên A nh n giá tr trên B.4) Có bao nhiêu ñơn ánh xác ñ nh trên t p A có m ph n t và nh n giá tr trên t p B có nph n t ? N u m > n thì v i m i ánh x , ít nh t có hai ph n t c a A có cùng m t nh, ñi uñó có nghĩa là không có ñơn ánh t A ñ n B. Bây gi gi s m ≤ n và g i các ph n tc a A là a1,a2,...,am. Rõ ràng có n cách ch n nh cho ph n t a1. Vì ánh x là ñơn ánhnên nh c a ph n t a2 ph i khác nh c a a1 nên ch có n - 1 cách ch n nh cho ph n ta2. Nói chung, ñ ch n nh c a ak ta có n - k + 1 cách. Theo quy t c nhân, ta có n! n(n − 1)(n − 2)...(n − m + 1) = ( n − m)!ñơn ánh t t p A ñ n t p B.5) Giá tr c a bi n k b ng bao nhiêu sau khi chương trình sau ñư c th c hi n? m := 0 for i1 := 1 to n1 for i2 := 1 to n ...