intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Toán rời rạc - Chương 2: Bài toán đếm

Chia sẻ: Nguyen Thanh Huu | Ngày: | Loại File: PDF | Số trang:15

Thêm vào BST
Báo xấu
548
lượt xem 158
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Lý thuyết tổ hợp là một phần quan trọng của toán học rời rạc c huyên nghiên cứu sự phân bố các phần tử va2p các tập hợp. Thồng thường các phần tử này là hữu hạn, việc phân bổ chúng phải thỏa mãn những điều kiện nhất định nào đó, tùy theo yêu cầu của bài toán cần nghiên cứu.

Chủ đề:

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

Lưu

Nội dung Text: Toán rời rạc - Chương 2: Bài toán đếm

  1. 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 u s 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 u c 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 trong nh 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 ng tí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 t nhi 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 danh sách tương ng có 23, 15 và 19 bài. Vì v y, theo quy t c c ng có 23 + 15 + 19 = 57 cá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 i bư 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 thi hà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ác vò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 m b 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ày b 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 22
  2. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p t 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àm cù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 n t 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 ng m 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 u nh 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=2600 cá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ãn cho 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 c b 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 nhau có ñ 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 nh c 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 quy t 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ó n ph 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 t c 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 ánh nê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 t a2. 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 n2 23
  3. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p ....................... for ik := 1 to nk k := k+1 Giá tr kh i t o c a k b ng 0. Ta có k vòng l p ñư c l ng nhau. G i Ti là vi c thi hành vòng l p th i. Khi ñó s l n ñi qua vòng l p b ng s cách làm các vi c T1, T2, ..., Tk. S cách th c hi n vi c Tj là nj (j=1, 2,..., k), vì vòng l p th j ñư c duy t v i m i giá tr nguyên ij n m gi a 1 và nj. Theo quy t c nhân vòng l p l ng nhau này ñư c duy t qua n1.n2....nk l n. Vì v y giá tr cu i cùng c a k là n1.n2....nk. Nguyên lý nhân thư ng ñư c phát bi u b ng ngôn ng t p h p như sau. N u A1, A2,..., Ak là các t p h u h n, khi ñó s ph n t c a tích Descartes c a các t p này b ng tích c a s các ph n t c a m i t p thành ph n. Ta bi t r ng vi c ch n m t ph n t c a tích Descartes A1 x A2 x...x Ak ñư c ti n hành b ng cách ch n l n lư t m t ph n t c a A1, m t ph n t c a A2, ..., m t ph n t c a Ak. Theo quy t c nhân ta có: |A1 x A2 x ... x Ak| = |A1|.|A2|...|Ak|. 2.1.2. Nguyên lý bù tr : Khi hai công vi c có th ñư c làm ñ ng th i, ta không th dùng quy t c c ng ñ tính s cách th c hi n nhi m v g m c hai vi c. ð tính ñúng s cách th c hi n nhi m v này ta c ng s cách làm m i m t trong hai vi c r i tr ñi s cách làm ñ ng th i c hai vi c. Ta có th phát bi u nguyên lý ñ m này b ng ngôn ng t p h p. Cho A1, A2 là hai t p h u h n, khi ñó |A1 ∪ A2| = |A1| + |A2| − |A1 ∩ A2|. T ñó v i ba t p h p h u h n A1, A2, A3, ta có: |A1 ∪ A2 ∪ A3| = |A1| + |A2| + |A3| − |A1 ∩ A2| − |A2 ∩ A3| − |A3 ∩ A1| + |A1 ∩ A2 ∩ A3|, và b ng quy n p, v i k t p h u h n A1, A2, ..., Ak ta có: | A1 ∪ A2 ∪ ... ∪ Ak| = N1 − N2 + N3 − ... + (−1)k-1Nk, trong ñó Nm (1 ≤ m ≤ k) là t ng ph n t c a t t c các giao m t p l y t k t p ñã cho, nghĩa là Nm = ∑ | Ai1 ∩ Ai2 ∩ ... ∩ Aim | 1≤i1
  4. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p Thí d 3: Có n lá thư và n phong bì ghi s n ñ a ch . B ng u nhiên các lá thư vào các phong bì. H i xác su t ñ x y ra không m t lá thư nào ñúng ñ a ch . M i phong bì có n cách b thư vào, nên có t t c n! cách b thư. V n ñ còn l i là ñ m s cách b thư sao cho không lá thư nào ñúng ñ a ch . G i U là t p h p các cách b thư và Am là tính ch t lá thư th m b ñúng ñ a ch . Khi ñó theo công th c v nguyên lý bù tr ta có: N = n! − N1 + N2 − ... + (−1) Nn, n trong ñó Nm (1 ≤ m ≤ n) là s t t c các cách b thư sao cho có m lá thư ñúng ñ a ch . Nh n xét r ng, Nm là t ng theo m i cách l y m lá thư t n lá, v i m i cách l y m lá thư, có (n-m)! cách b ñ m lá thư này ñúng ñ a ch , ta nh n ñư c: m n! 1 1 1 Nm = C n (n - m)! = và N = n!(1 − + − ... + (−1)n ), k! 1! 2! n! m n! trong ñó C n = là t h p ch p m c a t p n ph n t (s cách ch n m ñ i m!(n − m)! 1 1 tư ng trong n ñ i tư ng ñư c cho). T ñó xác su t c n tìm là: 1 − + − ... + (−1)n 1! 2! 1 - 1 . M t ñi u lý thú là xác su t này d n ñ n e 1 (nghĩa là còn > ) khi n khá l n. n! 3 S N trong bài toán này ñư c g i là s m t th t và ñư c ký hi u là Dn. Dư i ñây là m t vài giá tr c a Dn, cho ta th y Dn tăng nhanh như th nào so v i n: n 2 3 4 5 6 7 8 9 10 11 Dn 1 2 9 44 265 1854 14833 133496 1334961 14684570 2.2. NGUYÊN LÝ DIRICHLET. 2.2.1. M ñ u: Gi s có m t ñàn chim b câu bay vào chu ng. N u s chim nhi u hơn s ngăn chu ng thì ít nh t trong m t ngăn có nhi u hơn m t con chim. Nguyên lý này dĩ nhiên là có th áp d ng cho các ñ i tư ng không ph i là chim b câu và chu ng chim. M nh ñ (Nguyên lý): N u có k+1 (ho c nhi u hơn) ñ v t ñư c ñ t vào trong k h p thì t n t i m t h p có ít nh t hai ñ v t. Ch ng minh: Gi s không có h p nào trong k h p ch a nhi u hơn m t ñ v t. Khi ñó t ng s v t ñư c ch a trong các h p nhi u nh t là b ng k. ði u này trái gi thi t là có ít nh t k + 1 v t. Nguyên lý này thư ng ñư c g i là nguyên lý Dirichlet, mang tên nhà toán h c ngư i ð c th k 19. Ông thư ng xuyên s d ng nguyên lý này trong công vi c c a mình. Thí d 4: 1) Trong b t kỳ m t nhóm 367 ngư i th nào cũng có ít nh t hai ngư i có ngày sinh nh t gi ng nhau b i vì ch có t t c 366 ngày sinh nh t khác nhau. 25
  5. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 2) Trong kỳ thi h c sinh gi i, ñi m bài thi ñư c ñánh giá b i m t s nguyên trong kho ng t 0 ñ n 100. H i r ng ít nh t có bao nhiêu h c sinh d thi ñ cho ch c ch n tìm ñư c hai h c sinh có k t qu thi như nhau? Theo nguyên lý Dirichlet, s h c sinh c n tìm là 102, vì ta có 101 k t qu ñi m thi khác nhau. 3) Trong s nh ng ngư i có m t trên trái ñ t, ph i tìm ñư c hai ngư i có hàm răng gi ng nhau. N u xem m i hàm răng g m 32 cái như là m t xâu nh phân có chi u dài 32, trong ñó răng còn ng v i bit 1 và răng m t ng v i bit 0, thì có t t c 232 = 4.294.967.296 hàm răng khác nhau. Trong khi ñó s ngư i trên hành tinh này là vư t quá 5 t , nên theo nguyên lý Dirichlet ta có ñi u c n tìm. 2.2.2. Nguyên lý Dirichlet t ng quát: M nh ñ : N u có N ñ v t ñư c ñ t vào trong k h p thì s t n t i m t h p ch a ít nh t ]N/k[ ñ v t. ( ñây, ]x[ là giá tr c a hàm tr n t i s th c x, ñó là s nguyên nh nh t có giá tr l n hơn ho c b ng x. Khái ni m này ñ i ng u v i [x] – giá tr c a hàm sàn hay hàm ph n nguyên t i x – là s nguyên l n nh t có giá tr nh hơn ho c b ng x.) Ch ng minh: Gi s m i h p ñ u ch a ít hơn ]N/k[ v t. Khi ñó t ng s ñ v t là N N ≤ k (] [ − 1) < k = N. k k ði u này mâu thu n v i gi thi t là có N ñ v t c n x p. Thí d 5: 1) Trong 100 ngư i, có ít nh t 9 ngư i sinh cùng m t tháng. X p nh ng ngư i sinh cùng tháng vào m t nhóm. Có 12 tháng t t c . V y theo nguyên lý Dirichlet, t n t i m t nhóm có ít nh t ]100/12[= 9 ngư i. 2) Có năm lo i h c b ng khác nhau. H i r ng ph i có ít nh t bao nhiêu sinh viên ñ ch c ch n r ng có ít ra là 6 ngư i cùng nh n h c b ng như nhau. G i N là s sinh viên, khi ñó ]N/5[ = 6 khi và ch khi 5 < N/5 ≤ 6 hay 25 < N ≤ 30. V y s N c n tìm là 26. 3) S mã vùng c n thi t nh nh t ph i là bao nhiêu ñ ñ m b o 25 tri u máy ñi n tho i trong nư c có s ñi n tho i khác nhau, m i s có 9 ch s (gi s s ñi n tho i có d ng 0XX - 8XXXXX v i X nh n các giá tr t 0 ñ n 9). Có 107 = 10.000.000 s ñi n tho i khác nhau có d ng 0XX - 8XXXXX. Vì v y theo nguyên lý Dirichlet t ng quát, trong s 25 tri u máy ñi n tho i ít nh t có ]25.000.000/10.000.000[ = 3 có cùng m t s . ð ñ m b o m i máy có m t s c n có ít nh t 3 mã vùng. 2.2.3. M t s ng d ng c a nguyên lý Dirichlet. Trong nhi u ng d ng thú v c a nguyên lý Dirichlet, khái ni m ñ v t và h p c n ph i ñư c l a ch n m t cách khôn khéo. Trong ph n nay có vài thí d như v y. 26
  6. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p Thí d 6: 1) Trong m t phòng h p có n ngư i, bao gi cũng tìm ñư c 2 ngư i có s ngư i quen trong s nh ng ngư i d h p là như nhau. S ngư i quen c a m i ngư i trong phòng h p nh n các giá tr t 0 ñ n n − 1. Rõ ràng trong phòng không th ñ ng th i có ngư i có s ngư i quen là 0 (t c là không quen ai) và có ngư i có s ngư i quen là n − 1 (t c là quen t t c ). Vì v y theo s lư ng ngư i quen, ta ch có th phân n ngư i ra thành n −1 nhóm. V y theo nguyên lý Dirichlet t n tai m t nhóm có ít nh t 2 ngư i, t c là luôn tìm ñư c ít nh t 2 ngư i có s ngư i quen là như nhau. 2) Trong m t tháng g m 30 ngày, m t ñ i bóng chuy n thi ñ u m i ngày ít nh t 1 tr n nhưng chơi không quá 45 tr n. Ch ng minh r ng tìm ñư c m t giai ño n g m m t s ngày liên t c nào ñó trong tháng sao cho trong giai ño n ñó ñ i chơi ñúng 14 tr n. G i aj là s tr n mà ñ i ñã chơi t ngày ñ u tháng ñ n h t ngày j. Khi ñó 1 ≤ a1 < a2 < ... < a30 < 45 15 ≤ a1+14 < a2+14 < ... < a30+14 < 59. Sáu mươi s nguyên a1, a2, ..., a30, a1+ 14, a2 + 14, ..., a30+14 n m gi a 1 và 59. Do ñó theo nguyên lý Dirichlet có ít nh t 2 trong 60 s này b ng nhau. Vì v y t n t i i và j sao cho ai = aj + 14 (j < i). ði u này có nghĩa là t ngày j + 1 ñ n h t ngày i ñ i ñã chơi ñúng 14 tr n. 3) Ch ng t r ng trong n + 1 s nguyên dương không vư t quá 2n, t n t i ít nh t m t s chia h t cho s khác. k Ta vi t m i s nguyên a1, a2,..., an+1 dư i d ng aj = 2 j qj trong ñó kj là s nguyên không âm còn qj là s dương l nh hơn 2n. Vì ch có n s nguyên dương l nh hơn 2n nên theo nguyên lý Dirichlet t n t i i và j sao cho qi = qj = q. Khi ñó ai= 2 ki q và aj = k 2 j q. Vì v y, n u ki ≤ kj thì aj chia h t cho ai còn trong trư ng h p ngư c l i ta có ai chia h t cho aj. Thí d cu i cùng trình bày cách áp d ng nguyên lý Dirichlet vào lý thuy t t h p mà v n quen g i là lý thuy t Ramsey, tên c a nhà toán h c ngư i Anh. Nói chung, lý thuy t Ramsey gi i quy t nh ng bài toán phân chia các t p con c a m t t p các ph n t . Thí d 7. Gi s trong m t nhóm 6 ngư i m i c p hai ho c là b n ho c là thù. Ch ng t r ng trong nhóm có ba ngư i là b n l n nhau ho c có ba ngư i là k thù l n nhau. G i A là m t trong 6 ngư i. Trong s 5 ngư i c a nhóm ho c là có ít nh t ba ngư i là b n c a A ho c có ít nh t ba ngư i là k thù c a A, ñi u này suy ra t nguyên lý Dirichlet t ng quát, vì ]5/2[ = 3. Trong trư ng h p ñ u ta g i B, C, D là b n c a A. n u trong ba ngư i này có hai ngư i là b n thì h cùng v i A l p thành m t b ba ngư i b n l n nhau, ngư c l i, t c là n u trong ba ngư i B, C, D không có ai là b n ai c thì ch ng t h là b ba ngư i thù l n nhau. Tương t có th ch ng minh trong trư ng h p có ít nh t ba ngư i là k thù c a A. 27
  7. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 2.3. CH NH H P VÀ T H P SUY R NG. 2.3.1. Ch nh h p có l p. M t cách s p x p có th t k ph n t có th l p l i c a m t t p n ph n t ñư c g i là m t ch nh h p l p ch p k t t p n ph n t . N u A là t p g m n ph n t ñó thì m i ch nh h p như th là m t ph n t c a t p Ak. Ngoài ra, m i ch nh h p l p ch p k t t p n ph n t là m t hàm t t p k ph n t vào t p n ph n t . Vì v y s ch nh h p l p ch p k t t p n ph n t là nk. 2.3.2. T h p l p. M t t h p l p ch p k c a m t t p h p là m t cách ch n không có th t k ph n t có th l p l i c a t p ñã cho. Như v y m t t h p l p ki u này là m t dãy không k th t g m k thành ph n l y t t p n ph n t . Do ñó có th là k > n. k M nh ñ 1: S t h p l p ch p k t t p n ph n t b ng C n+ k −1 . Ch ng minh. M i t h p l p ch p k t t p n ph n t có th bi u di n b ng m t dãy n−1 thanh ñ ng và k ngôi sao. Ta dùng n − 1 thanh ñ ng ñ phân cách các ngăn. Ngăn th i ch a thêm m t ngôi sao m i l n khi ph n t th i c a t p xu t hi n trong t h p. Ch ng h n, t h p l p ch p 6 c a 4 ph n t ñư c bi u th b i: **| * | |*** mô t t h p ch a ñúng 2 ph n t th nh t, 1 ph n t th hai, không có ph n t th 3 và 3 ph n t th tư c a t p h p. M i dãy n − 1 thanh và k ngôi sao ng v i m t xâu nh phân ñ dài n + k − 1 v i k s 1. Do ñó s các dãy n − 1 thanh ñ ng và k ngôi sao chính là s t h p ch p k t t p n + k − 1 ph n t . ðó là ñi u c n ch ng minh. Thi d 8: 1) Có bao nhiêu cách ch n 5 t gi y b c t m t két ñ ng ti n g m nh ng t 1000ñ, 2000ñ, 5000ñ, 10.000ñ, 20.000ñ, 50.000ñ, 100.000ñ. Gi s th t mà các t ti n ñư c ch n là không quan tr ng, các t ti n cùng lo i là không phân bi t và m i lo i có ít nh t 5 t . Vì ta không k t i th t ch n t ti n và vì ta ch n ñúng 5 l n, m i l n l y m t t 1 trong 7 lo i ti n nên m i cách ch n 5 t gi y b c này chính là m t t h p l p ch p 5 t 5 7 ph n t . Do ñó s c n tìm là C 7 +5−1 = 462. 2) Phương trình x1 + x2 + x3 = 15 có bao nhiêu nghi m nguyên không âm? Chúng ta nh n th y m i nghi m c a phương trình ng v i m t cách ch n 15 ph n t t m t t p có 3 lo i, sao cho có x1 ph n t lo i 1, x2 ph n t lo i 2 và x3 ph n t lo i 3 ñư c ch n. Vì v y s nghi m b ng s t h p l p ch p 15 t t p có 3 ph n t và 15 b ng C3+15−1 = 136. 2.3.3. Hoán v c a t p h p có các ph n t gi ng nhau. Trong bài toán ñ m, m t s ph n t có th gi ng nhau. Khi ñó c n ph i c n th n, tránh ñ m chúng hơn m t l n. Ta xét thí d sau. 28
  8. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p Thí d 9: Có th nh n ñư c bao nhiêu xâu khác nhau b ng cách s p x p l i các ch cái c a t SUCCESS? Vì m t s ch cái c a t SUCCESS là như nhau nên câu tr l i không ph i là s hoán v c a 7 ch cái ñư c. T này ch a 3 ch S, 2 ch C, 1 ch U và 1 ch E. ð xác ñ nh s xâu khác nhau có th t o ra ñư c ta nh n th y có C(7,3) cách ch n 3 ch cho 3 ch S, còn l i 4 ch tr ng. Có C(4,2) cách ch n 2 ch cho 2 ch C, còn l i 2 ch tr ng. Có th ñ t ch U b ng C(2,1) cách và C(1,1) cách ñ t ch E vào xâu. Theo nguyên lý nhân, s các xâu khác nhau có th t o ñư c là: 7!4!2!1! 7! C 7 . C 4 . C 1 . C1 = 3 2 2 1 = = 420. 3!.4!.2!.2!.1!.1!.1!.0! 3!.2 !.1!.1! M nh ñ 2: S hoán v c a n ph n t trong ñó có n1 ph n t như nhau thu c lo i 1, n2 ph n t như nhau thu c lo i 2, ..., và nk ph n t như nhau thu c lo i k, b ng n! . n1!.n 2 !....n k ! n Ch ng minh. ð xác ñ nh s hoán v trư c tiên chúng ta nh n th y có C n1 cách gi n1 n ch cho n1 ph n t lo i 1, còn l i n - n1 ch tr ng. Sau ñó có C n −n cách ñ t n2 ph n t 2 1 lo i 2 vào hoán v , còn l i n - n1 - n2 ch tr ng. Ti p t c ñ t các ph n t lo i 3, lo i 4,..., k n lo i k - 1vào ch tr ng trong hoán v . Cu i cùng có C n− n −...−n cách ñ t nk ph n t lo i 1 k −1 k vào hoán v . Theo quy t c nhân t t c các hoán v có th là: n n2 nk n! C n1 . C n −n .... C n − n −...− n = . 1 1 k −1 n1!.n 2 !....n k ! 2.3.4. S phân b các ñ v t vào trong h p. Thí d 10: Có bao nhiêu cách chia nh ng x p bài 5 quân cho m i m t trong 4 ngư i chơi t m t c bài chu n 52 quân? 5 Ngư i ñ u tiên có th nh n ñư c 5 quân bài b ng C52 cách. Ngư i th hai có th 5 ñư c chia 5 quân bài b ng C 47 cách, vì ch còn 47 quân bài. Ngư i th ba có th nh n 5 ñư c 5 quân bài b ng C 42 cách. Cu i cùng, ngư i th tư nh n ñư c 5 quân bài b ng 5 C37 cách. Vì v y, theo nguyên lý nhân t ng c ng có 5 5 5 5 52! C52 . C 47 . C 42 . C37 = 5!.5!.5!.5!.32! cách chia cho 4 ngư i m i ngư i m t x p 5 quân bài. Thí d trên là m t bài toán ñi n hình v vi c phân b các ñ v t khác nhau vào các h p khác nhau. Các ñ v t là 52 quân bài, còn 4 h p là 4 ngư i chơi và s còn l i ñ trên bàn. S cách s p x p các ñ v t vào trong h p ñư c cho b i m nh ñ sau M nh ñ 3: S cách phân chia n ñ v t khác nhau vào trong k h p khác nhau sao cho có ni v t ñư c ñ t vào trong h p th i, v i i = 1, 2, ..., k b ng 29
  9. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p n! . n1!.n2 !....nk !.(n − n1 − ... − nk )! 2.4. SINH CÁC HOÁN V VÀ T H P. 2.4.1. Sinh các hoán v : Có nhi u thu t toán ñã ñư c phát tri n ñ sinh ra n! hoán v c a t p {1,2,...,n}. Ta s mô t m t trong các phương pháp ñó, phương pháp li t kê các hoán v c a t p {1,2,...,n} theo th t t ñi n. Khi ñó, hoán v a1a2...an ñư c g i là ñi trư c hoán v b1b2...bn n u t n t i k (1 ≤ k ≤ n), a1 = b1, a2 = b2,..., ak-1 = bk-1 và ak < bk. Thu t toán sinh các hoán v c a t p {1,2,...,n} d a trên th t c xây d ng hoán v k ti p, theo th t t ñi n, t hoán v cho trư c a1 a2 ...an. ð u tiên n u an-1 < an thì rõ ràng ñ i ch an-1 và an cho nhau thì s nh n ñư c hoán v m i ñi li n sau hoán v ñã cho. N u t n t i các s nguyên aj và aj+1 sao cho aj < aj+1 và aj+1 > aj+2 > ... > an, t c là tìm c p s nguyên li n k ñ u tiên tính t bên ph i sang bên trái c a hoán v mà s ñ u nh hơn s sau. Sau ñó, ñ nh n ñư c hoán v li n sau ta ñ t vào v trí th j s nguyên nh nh t trong các s l n hơn aj c a t p aj+1, aj+2, ..., an, r i li t kê theo th t tăng d n c a các s còn l i c a aj, aj+1, aj+2, ..., an vào các v trí j+1, ..., n. D th y không có hoán v nào ñi sau hoán v xu t phát và ñi trư c hoán v v a t o ra. Thí d 11: Tìm hoán v li n sau theo th t t ñi n c a hoán v 4736521. C p s nguyên ñ u tiên tính t ph i qua trái có s trư c nh hơn s sau là a3 = 3 và a4 = 6. S nh nh t trong các s bên ph i c a s 3 mà l i l n hơn 3 là s 5. ð t s 5 vào v trí th 3. Sau ñó ñ t các s 3, 6, 1, 2 theo th t tăng d n vào b n v trí còn l i. Hoán v li n sau hoán v ñã cho là 4751236. procedure Hoán v li n sau (a1, a2, ..., an) (hoán v c a {1,2,...,n} khác (n, n−1, ..., 2, 1)) j := n − 1 while aj > aj+1 j := j − 1 {j là ch s l n nh t mà aj < aj+1} k := n while aj > ak k := k - 1 {ak là s nguyên nh nh t trong các s l n hơn aj và bên ph i aj} ñ i ch (aj, ak) r := n s := j + 1 while r > s ñ i ch (ar, as) r := r - 1 ; s := s + 1 {ði u này s x p ph n ñuôi c a hoán v sau v trí th j theo th t tăng d n.} 30
  10. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 2.4.2. Sinh các t h p: Làm th nào ñ t o ra t t c các t h p các ph n t c a m t t p h u h n? Vì t h p chính là m t t p con, nên ta có th dùng phép tương ng 1-1 gi a các t p con c a {a1,a2,...,an} và xâu nh phân ñ dài n. Ta th y m t xâu nh phân ñ dài n cũng là khai tri n nh phân c a m t s nguyên n m gi a 0 và 2n − 1. Khi ñó 2n xâu nh phân có th li t kê theo th t tăng d n c a s nguyên trong bi u di n nh phân c a chúng. Chúng ta s b t ñ u t xâu nh phân nh nh t 00...00 (n s 0). M i bư c ñ tìm xâu li n sau ta tìm v trí ñ u tiên tính t ph i qua trái mà ñó là s 0, sau ñó thay t t c s 1 bên ph i s này b ng 0 và ñ t s 1 vào chính v trí này. procedure Xâu nh phân li n sau (bn-1bn-2...b1b0): xâu nh phân khác (11...11) i := 0 while bi = 1 begin bi := 0 i := i + 1 end bi := 1 Ti p theo chúng ta s trình bày thu t toán t o các t h p ch p k t n ph n t {1,2,...,n}. M i t h p ch p k có th bi u di n b ng m t xâu tăng. Khi ñó có th li t kê các t h p theo th t t ñi n. Có th xây d ng t h p li n sau t h p a1a2...ak b ng cách sau. Trư c h t, tìm ph n t ñ u tiên ai trong dãy ñã cho k t ph i qua trái sao cho ai ≠ n − k + i. Sau ñó thay ai b ng ai + 1 và aj b ng ai + j − i + 1 v i j = i + 1, i + 2, ..., k. Thí d 12: Tìm t h p ch p 4 t t p {1, 2, 3, 4, 5, 6} ñi li n sau t h p {1, 2, 5, 6}. Ta th y t ph i qua trái a2 = 2 là s h ng ñ u tiên c a t h p ñã cho th a mãn ñi u ki n ai ≠ 6 − 4 + i. ð nh n ñư c t h p ti p sau ta tăng ai lên m t ñơn v , t c a2 = 3, sau ñó ñ t a3 = 3 + 1 = 4 và a4 = 3 + 2 = 5. V y t h p li n sau t h p ñã cho là {1,3,4,5}. Th t c này ñư c cho dư i d ng thu t toán như sau. procedure T h p li n sau ({a1, a2, ..., ak}: t p con th c s c a t p {1, 2, ..., n} không b ng {n − k + 1, ..., n} v i a1 < a2 < ... < ak) i := k while ai = n − k + i i := i − 1 ai := ai + 1 for j := i + 1 to k aj := ai + j − i 31
  11. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 2.5. H TH C TRUY H I. 2.5.1. Khái ni m m ñ u và mô hình hóa b ng h th c truy h i: ðôi khi ta r t khó ñ nh nghĩa m t ñ i tư ng m t cách tư ng minh. Nhưng có th d dàng ñ nh nghĩa ñ i tư ng này qua chính nó. K thu t này ñư c g i là ñ quy. ð nh nghĩa ñ quy c a m t dãy s ñ nh rõ giá tr c a m t hay nhi u hơn các s h ng ñ u tiên và quy t c xác ñ nh các s h ng ti p theo t các s h ng ñi trư c. ð nh nghĩa ñ quy có th dùng ñ gi i các bài toán ñ m. Khi ñó quy t c tìm các s h ng t các s h ng ñi trư c ñư c g i là các h th c truy h i. ð nh nghĩa 1: H th c truy h i (hay công th c truy h i) ñ i v i dãy s {an} là công th c bi u di n an qua m t hay nhi u s h ng ñi trư c c a dãy. Dãy s ñư c g i là l i gi i hay nghi m c a h th c truy h i n u các s h ng c a nó th a mãn h th c truy h i này. Thí d 13 (Lãi kép): 1) Gi s m t ngư i g i 10.000 ñô la vào tài kho n c a mình t i m t ngân hàng v i lãi su t kép 11% m i năm. Sau 30 năm anh ta có bao nhiêu ti n trong tài kho n c a mình? G i Pn là t ng s ti n có trong tài kho n sau n năm. Vì s ti n có trong tài kho n sau n năm b ng s có sau n − 1 năm c ng lãi su t c a năm th n, nên ta th y dãy {Pn} tho mãn h th c truy h i sau: Pn = Pn-1 + 0,11Pn-1 = (1,11)Pn-1 v i ñi u ki n ñ u P0 = 10.000 ñô la. T ñó suy ra Pn = (1,11)n.10.000. Thay n = 30 cho ta P30 = 228922,97 ñô la. 2) Tìm h th c truy h i và cho ñi u ki n ñ u ñ tính s các xâu nh phân ñ dài n và không có hai s 0 liên ti p. Có bao nhiêu xâu nh phân như th có ñ dài b ng 5? G i an là s các xâu nh phân ñ dài n và không có hai s 0 liên ti p. ð nh n ñư c h th c truy h i cho {an}, ta th y r ng theo quy t c c ng, s các xâu nh phân ñ dài n và không có hai s 0 liên ti p b ng s các xâu nh phân như th k t thúc b ng s 1 c ng v i s các xâu như th k t thúc b ng s 0. Gi s n ≥ 3. Các xâu nh phân ñ dài n, không có hai s 0 liên ti p k t thúc b ng s 1 chính là xâu nh phân như th , ñ dài n − 1 và thêm s 1 vào cu i c a chúng. V y chúng có t t c là an-1. Các xâu nh phân ñ dài n, không có hai s 0 liên ti p và k t thúc b ng s 0, c n ph i có bit th n − 1 b ng 1, n u không thì chúng có hai s 0 hai bit cu i cùng. Trong trư ng h p này chúng có t t c là an-2. Cu i cùng ta có ñư c: an = an-1 + an-2 v i n ≥ 3. ði u ki n ñ u là a1 = 2 và a2 = 3. Khi ñó a5 = a4 + a3 = a3 + a2 + a3 = 2(a2 + a1) + a2 = 13. 2.5.2. Gi i các h th c truy h i. ð nh nghĩa 2: M t h th c truy h i tuy n tính thu n nh t b c k v i h s h ng s là h th c truy h i có d ng: 32
  12. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p an = c1an-1 + c2an-2 + ... + ckan-k , trong ñó c1, c2, ..., ck là các s th c và ck ≠ 0. Theo nguyên lý c a quy n p toán h c thì dãy s th a mãn h th c truy h i nêu trong ñ nh nghĩa ñư c xác ñ nh duy nh t b ng h th c truy h i này và k ñi u ki n ñ u: a0 = C0, a1 = C1, ..., ak-1 = Ck-1. Phương pháp cơ b n ñ gi i h th c truy h i tuy n tính thu n nh t là tìm nghi m dư i d ng an = rn, trong ñó r là h ng s . Chú ý r ng an = rn là nghi m c a h th c truy h i an = c1an-1 + c2an-2 + ... + ckan-k n u và ch n u - - - - - rn = c1rn 1 + c2rn 2 + ... + ckrn k hay rk − c1rk 1 − c2rk 2 − ... − ck-1r – ck = 0. Phương trình này ñư c g i là phương trình ñ c trưng c a h th c truy h i, nghi m c a nó g i là nghi m ñ c trưng c a h th c truy h i. M nh ñ : Cho c1, c2, ..., ck là các s th c. Gi s r ng phương trình ñ c trưng - - rk − c1rk 1 − c2rk 2 − ... − ck-1r – ck = 0 có k nghi m phân bi t r1, r2, ..., rk. Khi ñó dãy {an} là nghi m c a h th c truy h i an = c1an-1 + c2an-2 + ... + ckan-k n u và ch n u an = α1r1n + α2r2n + ... + αkrkn, v i n = 1, 2, ... trong ñó α1, α2, ..., αk là các h ng s . Thí d 14: 1) Tìm công th c hi n c a các s Fibonacci. Dãy các s Fibonacci th a mãn h th c fn = fn-1 + fn-2 và các ñi u ki n ñ u f0 = 0 1+ 5 1− 5 và f1 = 1. Các nghi m ñ c trưng là r1 = và r2 = . Do ñó các s Fibonacci 2 2 1+ 5 n 1− 5 n ñư c cho b i công th c fn = α1( ) + α2( ) . Các ñi u ki n ban ñ u f0 = 0 = 2 2 1+ 5 1− 5 1 α1 + α2 và f1 = 1 = α1( ) + α2( ). T hai phương trình này cho ta α1 = , 2 2 5 1 α2 = - . Do ñó các s Fibonacci ñư c cho b i công th c hi n sau: 5 1 1+ 5 n 1 1− 5 n fn = ( ) - ( ). 5 2 5 2 2) Hãy tìm nghi m c a h th c truy h i an = 6an-1 - 11an-2 + 6an-3 v i ñi u ki n ban ñ u a0 = 2, a1 = 5 và a2 = 15. ða th c ñ c trưng c a h th c truy h i này là r3 - 6r2 + 11r - 6. Các nghi m ñ c trưng là r = 1, r = 2, r = 3. Do v y nghi m c a h th c truy h i có d ng an = α11n + α22n + α33n. Các ñi u ki n ban ñ u a0 = 2 = α1 + α2 + α3 a1 = 5 = α1 + α22 + α33 a2 = 15 = α1 + α24 + α39. Gi i h các phương trình này ta nh n ñư c α1= 1, α2 = −1, α3 = 2. Vì th , nghi m duy nh t c a h th c truy h i này và các ñi u ki n ban ñ u ñã cho là dãy {an} v i 33
  13. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p an = 1 − 2n + 2.3n. 2.6. QUAN H CHIA ð TR . 2.6.1. M ñ u: Nhi u thu t toán ñ quy chia bài toán v i các thông tin vào ñã cho thành m t hay nhi u bài toán nh hơn. S phân chia này ñư c áp d ng liên ti p cho t i khi có th tìm ñư c l i gi i c a bài toán nh m t cách d dàng. Ch ng h n, ta ti n hành vi c tìm ki m nh phân b ng cách rút g n vi c tìm ki m m t ph n t trong m t danh sách t i vi c tìm ph n t ñó trong m t danh sách có ñ dài gi m ñi m t n a. Ta rút g n liên ti p như v y cho t i khi còn l i m t ph n t . M t ví d khác là th t c nhân các s nguyên. Th t c này rút g n bài toán nhân hai s nguyên t i ba phép nhân hai s nguyên v i s bit gi m ñi m t n a. Phép rút g n này ñư c dùng liên ti p cho t i khi nh n ñư c các s nguyên có m t bit. Các th t c này g i là các thu t toán chia ñ tr . 2.6.2. H th c chia ñ tr : Gi s r ng m t thu t toán phân chia m t bài toán c n thành a bài toán nh , n trong ñó m i bài toán nh có c (ñ ñơn gi n gi s r ng n chia h t cho b; trong th c b n n t các bài toán nh thư ng có c [ ] ho c ] [). Gi s r ng t ng các phép toán thêm b b vào khi th c hi n phân chia bài toán c n thành các bài toán có c nh hơn là g(n). Khi ñó, n u f(n) là s các phép toán c n thi t ñ gi i bài toán ñã cho thì f th a mãn h th c truy h i sau: n f(n) = af( ) + g(n) b H th c này có tên là h th c truy h i chia ñ tr . Thí d 15: 1) Thu t toán tìm ki m nh phân ñưa bài toán tìm ki m c n v bài toán tìm ki m ph n t này trong dãy tìm ki m c n/2, khi n ch n. Khi th c hi n vi c rút g n c n hai phép so sánh. Vì th , n u f(n) là s phép so sánh c n ph i làm khi tìm ki m m t ph n t trong danh sách tìm ki m c n ta có f(n) = f(n/2) + 2, n u n là s ch n. 2) Có các thu t toán hi u qu hơn thu t toán thông thư ng ñ nhân hai s nguyên. ñây ta s có m t trong các thu t toán như v y. ðó là thu t toán phân nhanh, có dùng k thu t chia ñ tr . Trư c tiên ta phân chia m i m t trong hai s nguyên 2n bit thành hai kh i m i kh i n bit. Sau ñó phép nhân hai s nguyên 2n bit ban ñ u ñư c thu v ba phép nhân các s nguyên n bit c ng v i các phép d ch chuy n và các phép c ng. Gi s a và b là các s nguyên có các bi u di n nh phân ñ dài 2n là a = (a2n-1 a2n-2 ... a1 a0)2 và b = (b2n-1 b2n-2 ... b1 b0)2. Gi s a = 2 A1 + A0 , b = 2nB1 + B0 , trong ñó n A1 = (a2n-1 a2n-2 ... an+1 an)2 , A0 = (an-1 ... a1 a0)2 B1 = (b2n-1 b2n-2 ... bn+1 bn)2 , B0 = (bn-1 ... b1 b0)2. Thu t toán nhân nhanh các s nguyên d a trên ñ ng th c: 34
  14. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p ab = (22n + 2n)A1B1 + 2n(A1 - A0)(B0 - B1) + (2n + 1)A0B0. ð ng th c này ch ra r ng phép nhân hai s nguyên 2n bit có th th c hi n b ng cách dùng ba phép nhân các s nguyên n bit và các phép c ng, tr và phép d ch chuy n. ði u ñó có nghĩa là n u f(n) là t ng các phép toán nh phân c n thi t ñ nhân hai s nguyên n bit thì f(2n) = 3f(n) + Cn. Ba phép nhân các s nguyên n bit c n 3f(n) phép toán nh phân. M i m t trong các phép c ng, tr hay d ch chuy n dùng m t h ng s nhân v i n l n các phép toán nh phân và Cn là t ng các phép toán nh phân ñư c dùng khi làm các phép toán này. n M nh ñ 1: Gi s f là m t hàm tăng tho mãn h th c truy h i f(n) = af( ) + c v i b m i n chia h t cho b, a ≥ 1, b là s nguyên l n hơn 1, còn c là s th c dương. Khi ñó  O( n logb a ), a > 1 f(n) =  . O(log n), a = 1  n M nh ñ 2: Gi s f là hàm tăng tho mãn h th c truy h i f(n) = af( ) + cnd v i m i b n = bk, trong ñó k là s nguyên dương, a ≥ 1, b là s nguyên l n hơn 1, còn c và d là các s th c dương. Khi ñó O(n logb a ), a > b d   f(n) = O(n d log n), a = b d .  d d O(n ) , a < b  Thí d 16: Hãy ư c lư ng s phép toán nh phân c n dùng khi nhân hai s nguyên n bit b ng thu t toán nhân nhanh. Thí d 15.2 ñã ch ra r ng f(n) = 3f(n/2) + Cn, khi n ch n. Vì th , t M nh ñ 2 ta suy ra f(n) = O( n log 2 3 ). Chú ý là log23 ≈ 1,6. Vì thu t toán nhân thông thư ng dùng O(n2) phép toán nh phân, thu t toán nhân nhanh s th c s t t hơn thu t toán nhân thông thư ng khi các s nguyên là ñ l n. BÀI T P CHƯƠNG II: 1. Trong t ng s 2504 sinh viên c a m t khoa công ngh thông tin, có 1876 theo h c môn ngôn ng l p trình Pascal, 999 h c môn ngôn ng Fortran và 345 h c ngôn ng C. Ngoài ra còn bi t 876 sinh viên h c c Pascal và Fortran, 232 h c c Fortran và C, 290 h c c Pascal và C. N u 189 sinh viên h c c 3 môn Pascal, Fortran và C thì trong trư ng h p ñó có bao nhiêu sinh viên không h c môn nào trong 3 môn ngôn ng l p trình k trên. 35
  15. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 2. M t cu c h p g m 12 ngư i tham d ñ bàn v 3 v n ñ . Có 8 ngư i phát bi u v v n ñ I, 5 ngư i phát bi u v v n ñ II và 7 ngư i phát bi u v v n ñ III. Ngoài ra, có ñúng 1 ngư i không phát bi u v n ñ nào. H i nhi u l m là có bao nhiêu ngư i phát bi u c 3 v n ñ . 3. Ch ra r ng có ít nh t 4 ngư i trong s 25 tri u ngư i có cùng tên h vi t t t b ng 3 ch cái sinh cùng ngày trong năm (không nh t thi t trong cùng m t năm). 4. M t tay ñô v t tham gia thi ñ u giành ch c vô ñ ch trong 75 gi . M i gi anh ta có ít nh t m t tr n ñ u, nhưng toàn b anh ta có không quá 125 tr n. Ch ng t r ng có nh ng gi liên ti p anh ta ñã ñ u ñúng 24 tr n. 5. Cho n là s nguyên dương b t kỳ. Ch ng minh r ng luôn l y ra ñư c t n s ñã cho m t s s h ng thích h p sao cho t ng c a chúng chia h t cho n. 6. Trong m t cu c l y ý ki n v 7 v n ñ , ngư i ñư c h i ghi vào m t phi u tr l i s n b ng cách ñ nguyên ho c ph ñ nh các câu tr l i tương ng v i 7 v n ñ ñã nêu. Ch ng minh r ng v i 1153 ngư i ñư c h i luôn tìm ñư c 10 ngư i tr l i gi ng h t nhau. 7. Có 17 nhà bác h c vi t thư cho nhau trao ñ i 3 v n ñ . Ch ng minh r ng luôn tìm ñư c 3 ngư i cùng trao ñ i m t v n ñ . 8. Trong kỳ thi k t thúc h c ph n toán h c r i r c có 10 câu h i. Có bao nhiêu cách gán ñi m cho các câu h i n u t ng s ñi m b ng 100 và m i câu ít nh t ñư c 5 ñi m. 9. Phương trình x1 + x2 + x3 + x4 + x5 = 21 có bao nhiêu nghi m nguyên không âm? 10. Có bao nhiêu xâu khác nhau có th l p ñư c t các ch cái trong t MISSISSIPI, yêu c u ph i dùng t t c các ch ? 11. M t giáo sư c t b sưu t p g m 40 s báo toán h c vào 4 chi c ngăn t , m i ngăn ñ ng 10 s . Có bao nhiêu cách có th c t các t báo vào các ngăn n u: 1) M i ngăn ñư c ñánh s sao cho có th phân bi t ñư c; 2) Các ngăn là gi ng h t nhau? 12. Tìm h th c truy h i cho s m t th t Dn. 13. Tìm h th c truy h i cho s các xâu nh phân ch a xâu 01. 14. Tìm h th c truy h i cho s cách ñi lên n b c thang n u m t ngư i có th bư c m t, hai ho c ba b c m t l n. 15. 1) Tìm h th c truy h i mà Rn tho mãn, trong ñó Rn là s mi n c a m t ph ng b phân chia b i n ñư ng th ng n u không có hai ñư ng nào song song và không có 3 ñư ng nào cùng ñi qua m t ñi m. b) Tính Rn b ng phương pháp l p. 16. Tìm nghi m c a h th c truy h i an = 2an-1 + 5an-2 - 6an-3 v i a0 = 7, a1 = -4, a2 = 8. 36
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
4=>1