Bài giảng Toán rời rạc - Chương 1: Phương pháp đếm

{x ∈ X | x ∈ A và x ∉ B}. A =X\A = {x ∈ X | x ∉ A}. Nói cách khác Nói cách khác ∀x ∈ X, x ∈ A \ B ⇔ x ∈ A và x ∉ B. ∀x ∈ X, x ∈⇔A x ∉ A. Suy ra Suy ra ∀x ∈ X, x ∉ A \ B ⇔ x ∉ A hay x ∈ B. ∀x ∈ X, x ∉⇔A x ∈ A. 25/03/2010 14 25/03/2010 15 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ CÁC PHÉP TOÁN TẬPHỢP CÁC PHÉP TOÁN TẬPHỢP Ví dụ: 1.12. Định lý (tính chấtcủa các phép toán): Xét các tậphợp X = {0; 1; 2; 3; 4; 5; 6}; ChoA,B,ClàcáctậphợpconcủatậphợpX.Khiđó A={0;1;2;3}; ta có: B={1;2;4;5}. 1) Tính lũy đẳng: Ta có: A ∩ A = A và A ∪ A = A A ∩ B = {1, 2}; 2) Tính giao hoán: A ∩ B = B ∩ A và A ∪ B = B ∪ A. A ∪ B={0;1;2;3;4;5}; 3) Tính kếthợp: A \ B = {0; 3}; B \ A = {4; 5}; (A ∩ B) ∩ C=A∩ (B ∩ C) C (A)={4;5;6};C (B) = {0; 3; 6}. X X và (A ∪ B) ∪ C = A ∪ (B ∪ C) 25/03/2010 16 25/03/2010 17 4 25/03/2010 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ CÁC PHÉP TOÁN TẬPHỢP CÁC PHÉP TOÁN TẬPHỢP 1.12. Định lý (tính chấtcủa các phép toán): 1.13. Mở rộng: 4) Tính phân phối: Cho {Ai}i∈I là mộthọ các tậphợp. Ta định nghĩaphần A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) giao và phầnhợpcủahọ {Ai}i∈I như sau: và A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) Aii=∀∈∈{,}xiIxA 5) Công thức De Morgan: iI∈ ABAB∩=∪& ABAB ∪=∩ A = {,}xi∃∈ Ix ∈ A 6) Các công thức ii iI∈ A ==∩AABAB&\ 25/03/2010 18 25/03/2010 19 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ CÁC PHÉP TOÁN TẬPHỢP TÍCH DESCARTRES 1.13. Mở rộng: 1.14. Định nghĩa: Khi đó ta có công thức De Morgan suy rộng như sau: Cho hai tậphợpAvàB.TíchDescartescủa A và B, ký hiệubởiA× B, là tậphợptấtcả các cặp(x,y)cóthứ tự Aii= A xtrước, y sau, trong đóxthuộcAvàythuộcB.Như iI∈∈ iI vậy, theo định nghĩa, ta có: A × B = {(x, y) | x ∈ A và y ∈ B}. AA= ii Nói cách khác iI∈∈ iI (x, y) ∈ A × B ⇔ x ∈ A và y ∈ B. Suy ra (x, y) ∉ A × B ⇔ x ∉ A hay y ∉ B. 25/03/2010 20 25/03/2010 21 5 25/03/2010 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ TÍCH DESCARTRES TÍCH DESCARTRES 1.14. Định nghĩa: 1.15. Tích Descartes củantậphợp: A n Ta có: (x, y) = (x', y') ⇔ x = x' và y = y'. Cho{}i i=1 là mộtdãygồmntậphợp. Ta định nghĩatích A n Do đó: (x, y) ≠ (x', y') ⇔ x ≠ x' hay y ≠ y'. Descartres củanh{}i i=1 ư sau: A1 × A2 × ... × An ={(x1,x2, ..., xn) |∀1 ≤ i ≤ n, xi ∈ Ai} n n A A 2 Ta còn ký hiệu tích Descartes củabởib{}i i=1 ởi.∏ i Ký hiệu A để chỉ tích Descartes A × A. Tức là: i=1 A2 = {(x, y ) | x ∈ AàA và y ∈ A} Ký hiệu An để chỉ tích Descartes A × A × ... × A (n lần). Tứclà: n A = {(x1, x2, ..., xn) |∀1 ≤ i ≤ n, xi ∈ A} 25/03/2010 22 25/03/2010 23 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ TÍCH DESCARTRES VỊ TỪ VÀ LƯỢNG TỪ 1.16. Mở rộng: 1.17. Định nghĩa: A n Cho{}i i=1 là mộthọ các tậphợp. Ta định nghĩa tích Cho A là mộttậphợpkhácrỗng. Giả sử, ứng vớimỗix A n Descartes củahọ{}i i=1 như sau: =a∈ Atacómộtmệnh đề p(a). Khi đó, ta nói p = p(x) là mộtvị từ theo mộtbiến (xác định trên A). A =∀∈∈()xiIxA , ∏ iiiIii{ ∈ } Tổng quát, cho A1,A2,A3là n tậphợpkhácrỗng. Giả iI∈ sử rằng ứng vớimỗi(x1,x2,...,xn)=(a1,a2,...,an) ∈A1×A2× ... ×An,tacómộtmệnh đề p(a1,a2,.,an). Khi đó ta nói p = p(x1,x2,.,xn)làmộtvị từ theo n biến(xác định trên A1×A2× ... ×An) 25/03/2010 24 25/03/2010 25 6 25/03/2010 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ VỊ TỪ VÀ LƯỢNG TỪ VỊ TỪ VÀ LƯỢNG TỪ Ví dụ 1: 1.18. Định nghĩa: Xétp(n)=“n>2”làmộtvị từ mộtbiếnxácđịnh trên Cho trước các vị từ p(x), q(x) theo mộtbiếnx∈ A. Khi ấy, tập các số tự nhiên N. i. Phủđịnh củavị từ p(x) ký hiệulà¬p(x) là vị từ mà khi Ta thấyvớin=3,4tađược các mệnh đề đúng p(3), thay x bởi1phầntử cốđịnh củaAthìtađượcmệnh đề p(4), còn vớin=0,1tađượcmệnh đề sai p(0), p(1). ¬(p(a)). Ví dụ 2: ii. Phép nốiliền(tương ứng nốirời, kéo theo) củap(x) và q(x) đượckýhiệu bởi p(x)∧q(x) (tương ứng là Xét p(x,y) = “x2 +y=1”làmộtvị từ theo hai biếnxác 2 p(x)∨q(x), p(x)→q(x)) là vị từ theo biến x mà khi thay x định trên R ,tathấyp(0,1)làmộtmệnh đề đúng, trong bởiphầntử cốđịnh a ∈ Atađượcmệnh đề p(a)∧q(a) ( khi p(1,1) là mộtmệnh đề sai. tương ứng là p(a) ∨q(a), p(a)→q(a)). 25/03/2010 26 25/03/2010 27 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ VỊ TỪ VÀ LƯỢNG TỪ VỊ TỪ VÀ LƯỢNG TỪ 1.19. Định nghĩa: 1.20. Định lý: Cho p(x) là mộtvị từ theo mộtbiếnxácđịnh trên A. Ta định Cho p(x, y) là mộtvị từ theo hai biếnx,yxácđịnh trên nghĩa các mệnh đề lượng từ hóa củap(x)như sau: A×B, các mệnh đề sau là đúng: i. Mệnh đề “VớimọixthuộcA,p(x)”,kýhiệubởi“∀x ∈ A, p(x)”, là mệnh đề được định bởi“∀x ∈ A, p(x)” i. [∀x ∈ A,∀y ∈ B, p(x, y)] ↔ [∀y ∈ B, ∀x ∈ A, p(x, y)] đúng khi và chỉ khi p(a) luôn đúng vớimọi giá trị a ∈ A. ii. [∃x ∈ A, ∃y ∈ B,p(x, y)] ↔ [∃y ∈ B, ∃x ∈ A,p(x, y)] ii. Mệnh đề “Tồntại(ítnhất) (hay có (ít nhất)) mộtxthuộc A, p(x))” ký hiệubởi“∃x ∈ A, p(x)”, là mệnh đề được iii. [∃x ∈ A, ∀y ∈ B, p(x, y)] → [∀y ∈ B, ∃x ∈ A, p(x, y)] định bởi“∃x ∈ A, p(x)” đúng khi và chỉ khicóítnhất một giá trị x=a0 nào đósaochomệnh đề p(a0) đúng. 25/03/2010 28 25/03/2010 29 7 25/03/2010 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ VỊ TỪ VÀ LƯỢNG TỪ VỊ TỪ VÀ LƯỢNG TỪ 1.21. Định lý: 1.22. Định lý: Trong mộtmệnh đề lượng từ hoá từ mộtvị từ theo i. Vớip(x)làmộtvị từ theo mộtbiếnxácđịnh trên A, nhiềubiến độclập, nếutahoánvị hai lượng từđứng ta có: cạnh nhau thì: ∀∈x Apx,,() ⇔∃∈ x Apx() i. Mệnh đề mớivẫn còn tương đương logic vớimệnh ∃∈x Apx,,() ⇔∀∈ x Apx() đề cũ nếu hai lượng từ này cùng loại. ii. Phủ định của mệnh đề lượng từ hóa từ vị từ p(x1, x2, ii. Mệnh đề mớinàysẽ là mộthệ quả logic củamệnh ..., xn)cóđượcbằng cách thay lượng từ ∀ bằng đề cũ nếuhailượng từ trước khi hoán vị có dạng ∃ lượng từ ∃ và ngượclại, và thay vị từ p(x1,x2,..., p xx, ,..., x ∀ xn)bằng vị từ ()12 n 25/03/2010 30 25/03/2010 31 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ VỊ TỪ VÀ LƯỢNG TỪ VỊ TỪ VÀ LƯỢNG TỪ 1.23. Quy tắc đặcbiệt hóa phổ dụng: 1.24. Quy tắctổng quát hóa phổ dụng: Nếumộtmệnh đề đúng có dạng lượng từ hóa trong đó Nếu trong mộtmệnh đề lượng từ hóa, khi thay mộtbiến mộtbiếnx∈ Abị buộcbởilượng từ phổ dụng ∀, khi ấy buộcbởilượng từ ∀ bằng mộtphầntử cốđịnh nhưng nếu thay thế x bởi a ∈ A ta sẽ được một mệnh đề đúng. tùy ý của tập hợp tương ứng mà mệnh đề nhận được có chân trị 1thìbảnthânmệnh đề lượng từ hoá ban đầu cũng có chân trị 1. 25/03/2010 32 25/03/2010 33 8 25/03/2010 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ ĐỊNH NGHĨAVÀKÝHIỆU ÁNH XẠ ĐỊNH NGHĨAVÀKÝHIỆU ÁNH XẠ 1.25. Định nghĩa: 1.27. Ảnh và ảnh ngược: Cho hai tậphợpX,Y≠∅.Mộtánhxạ ftừ X vào Y là quy Cho ánh xạ ftừ XvàoYvàA⊂ X, B ⊂ Y. Ta định nghĩa: tắcchoứng vớimỗiphầntử xcủaXmộtphầntử duy nhấty 1) Ảnh của A qua f là tậphợp: củaYmàtakýhiệulàf(x)vàgọilàảnh của x qua ánh xạ f. f(A) = {y ∈ Y |∃x ∈ A, y = f(x)} Ta viết: Ta cũng viết: f : X → Y f(A) = {f(x) | x ∈ A} x f(x) Như vậytheođịnh nghĩa, ta có: 1.26. Định nghĩa: ∀y ∈ Y, y ∈ f(A) ⇔∃x ∈ A, y = f(x); Hai ánh xạ fvàgtừ XvàoYđượcgọilàbằng nhau nếu: ∀y ∈ Y, y ∉ f(A) ⇔∀x ∈ A, y ≠ f(x). ∀x ∈ X, f(x) = g(x) 25/03/2010 34 25/03/2010 35 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ ĐỊNH NGHĨAVÀKÝHIỆU ÁNH XẠ ĐỊNH NGHĨAVÀKÝHIỆU ÁNH XẠ 1.27. Ảnh và ảnh ngược: 1.27. Ảnh và ảnh ngược: 2) Ảnh ngượchaytạo ảnh củaBbởiflàtậphợp: Chú ý: f–1(B) = {x ∈ X | f(x) ∈ B} 1) Ta thường dùng ký hiệuImfđể chỉ tậphợp f(X) và còn Như vậytheođịnh nghĩa, ta có: gọilàảnh củaf. ∀x ∈ X, x ∈ f–1(B) ⇔ f(x) ∈ B; 2) Vớiy∈ B ta dùng ký hiệuf–1(y) thay cho f–1({y}). Đó ∀x ∈ X, x ∉ f–1(B) ⇔ f(x) ∉ B. chính là tậphợpcácphầntử x ∈ Xthỏaf(x)=y(tathường gọi đây là tậphợptất cả các nghiệm xtrongXcủa phương trình f(x) = y). Lưuýrằng tậphợpf–1(y) có thể rỗng hay khác rỗng (gồmmột hay nhiềuphầntử). 25/03/2010 36 25/03/2010 37 9 25/03/2010 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ ĐỊNH NGHĨAVÀKÝHIỆU ÁNH XẠ PHÂN LOẠI ÁNH XẠ Xét ánh xạ f : X → Y. 1.28 Định lý: 1.29. Đơn ánh: Giả sử flàmộtánhxạ từ XvàoY.VớiA và A là hai tập 1 2 Tanóif:X→ Ylàmột đơnánhnếuhaiphầntử khác nhau hợpcontùyýcủaX,B và B là hai tậpcontùyýcủaY.Ta 1 2 bấtkỳ củaXđềucóảnh khác nhau, nghĩalà: có: ∀x, x' ∈ X, x ≠ x' ⇒ f(x) ≠ f(x') 1. f(A ∪ A ) = f(A ) ∪ f(A ); 1 2 1 2 Những tính chấtsauđượcsuytrựctiếptừđịnh nghĩa. 2. f(A ∩ A ) ⊂ f(A ) ∩ f(A ); 1 2 1 2 f : X → Y là một đơn ánh 3. f(A \A) ⊃ f(A ) \ f(A ); 1 2 1 2 ⇔ (∀x, x' ∈ X, f(x) = f(x') ⇒ x=x'). 4. f–1(B ∪ B )=f–1(B ) ∪ f–1(B ); 1 2 1 2 –1 –1 –1 –1 ⇔ (∀y ∈ Y, f (y) có nhiềunhấtmộtphầntử). 5. f (B1 ∩ B2)=f (B1) ∩ f (B2); 6. f–1(B \B)=f–1(B )\f–1(B ). ⇔ (∀y ∈ Y, phương trình f(x) = y (y đượcxemnhư 1 2 1 2 tham số) có nhiềunhấtmột nghiệmx∈ X. 25/03/2010 38 25/03/2010 39 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ PHÂN LOẠI ÁNH XẠ PHÂN LOẠI ÁNH XẠ Xét ánh xạ f : X → Y. Xét ánh xạ f : X → Y. 1.29. Đơn áhánh: 1.30. Toàn áhánh: Suy ra: Ta nói f : X → Ylàmột toàn ánh nếuImf=Y. f:X→ Y không là một đơnánh Những tính chấtsauđượcsuytrựctiếptừđịnh nghĩa. ⇔ (∃x, x' ∈ X, x ≠ x' và f(x) = f(x')). f:X→ Ylàmột toàn ánh ⇔ (∃y ∈ Y, phương trình f(x) = y (y đượcxemnhư ⇔ (∀y ∈ Y, ∃x ∈ X, y = f(x)) tham số)cóítnhất hai nghiệmx∈ X. ⇔ (∀y ∈ Y, f–1(y) ≠∅); ⇔∀y ∈ Y, phươngtrìnhf(x)=y(yđượcxemnhư tham số) có nghiệmx∈ X. 25/03/2010 40 25/03/2010 41 10 25/03/2010 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ PHÂN LOẠI ÁNH XẠ PHÂN LOẠI ÁNH XẠ Xét ánh xạ f : X → Y. Xét ánh xạ f : X → Y. 1.30. Toàn áhánh: 1.31. Song áhánh và áhánh xạ ngược: Suy ra: Tanóif:X→ Ylàmột song ánh hay là mộttương ứng 1-1 f:X→ Y không là một toàn ánh nếufvừalàđơnánhvừa là toàn ánh. ⇔ (∃y ∈ Y, ∀x ∈ X, y ≠ f(x)); Những tính chấtsauđượcsuytrựctiếptừđịnh nghĩa. ⇔ (∃y ∈ Y, f–1(y) = ∅); f:X→ Ylàmột song ánh ⇔∀y ∈ Y, phương trình f(x) = y (y đượcxemnhư tham ⇔ (∀y ∈ Y, ∃!x ∈ X, y = f(x)); số) vô nghiệm trong X. ⇔ (∀y ∈ Y, f–1(y) có đúng mộtphầntử); ⇔∀y ∈ Y, phương trình f(x) = y (y đượcxemnhư tham số) có duy nhấtmột nghiệmx∈ X. 25/03/2010 42 25/03/2010 43 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ PHÂN LOẠI ÁNH XẠ PHÂN LOẠI ÁNH XẠ Xét ánh xạ f : X → Y. Xét ánh xạ f : X → Y. 1.31. Song áhánh và áhánh xạ ngược: 1.31. Song áhánh và áhánh xạ ngược: Suy ra: Xétf:X→ Ylàmột song ánh. Khi đó, theo tính chấttrên, f:X→ Y không là một song ánh vớimọiy∈ Y, tồntại duy nhấtmộtphầntử x ∈ Xthỏaf(x) ⇔ f không là một đơn ánh hay không là một toàn ánh; =y.Dođótương ứng y x là mộtánhxạ từ YvàoX.Ta gọi đây là ánh xạ ngượccủa f và ký hiệuf–1.Như vậy: ⇔∀y ∈ Y, phương trình f(x) = y (y đượcxemnhư tham f–1 : Y → X số) vô nghiệmhoặccóítnhất hai nghiệmx∈ X. yf–1(y) = x với f(x) = y. 25/03/2010 44 25/03/2010 45 11 25/03/2010 1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ TÍCH CÁC ÁNH XẠ TÍCH CÁC ÁNH XẠ 1.32. Định nghĩa: Cho hai ánh xạ 1.33. Định lý: f : X → Y và g : Y' → Z Xét f : X → Ylàmột song ánh. Khi đó: –1 trong đó Y ⊂ Y'. Ánh xạ tích h của f và g là ánh xạ từ X fof =IdY vào Z xác định bởi: –1 f of=IdX h : X → Z trong đókýhiệuIdX để chỉ ánh xạđồng nhấtX→ X x h(x) = g(f(x)) định bởi IdX(x) = x, ∀x ∈ X; ta gọi IdX là ánh xạ đồng Ta viết: nhấttrênX,tương tự IdY là ánh xạđồng nhấttrênY. h = g o f : X → Y → Z x f(x) h(x) = g(f(x)) 25/03/2010 46 25/03/2010 47 2. Phép đếm 2. Phép đếm NGUYÊN LÝ CỘNG & NGUYÊN LÝ NHÂN NGUYÊN LÝ CỘNG & NGUYÊN LÝ NHÂN 2.1. Nguyên lý Cộng: 2.2. Nguyên lý Nhân: Giả sửđểmộthiệntượng xảyra,cóktrường hợp Giả sửđể hoàn thành một công việctaphảitiếnhànhtheotrìnhtự k bướccótácdụng độclập. Biếtrằng: lớnloạitrừ lẫn nhau. Biếtrằng ở mỗitrường hợp –Cón1 cách thựchiệnbuớc1. lớnthứ jlạicónj trường hợpnhỏ.Khiđó, số – Sau khi thựchiệnbước 1 xong, dù bằng bấtcứ cách nào, trường hợpnhỏ nói chung để hiệntượng trên xảy luôn luôn có mộtsố lượng không đổin2 cách để thựchiện ra là: bước2. – n = n1 + n2 + + nk. –Cuối cùng, sau khi thựchiện xong bướcthứ k-1, luôn luôn có mộtsố lượng không đổink cách để thựchiệnbướcthứ k. Khi đó, số cách để hoàn thành công việc đãcholà:n= n1n2nk. 25/03/2010 48 25/03/2010 49 12 25/03/2010 2. Phép đếm 2. Phép đếm GIẢITÍCHTỔ HỢP GIẢITÍCHTỔ HỢP 2.3. Hoán vị: 2.4. Chỉnh hợp: Cho tậphợpAgồmnphầntử.Mỗicáchsắp đặtcóthứ Cho A là tậphợpgồmnphầntử.Mỗibộ gồmk tự nphầntử củaAđượcgọilàmột hoán vị củanphần tử.Số các hoán vị củanphầntử ký hiệulàPn phầntử (1 ≤ k ≤n) sắpthứ tự củatậphợpAđược P = n! n gọilàmột chỉnh hợpchậpkcủanphầntử.Số Định lý. Số hoán vị của n phần tử, trong đó có n1 phần k tử giống nhau thuộcloại1,n2 phầntử giống nhau thuộc các chỉnh hợpchậpkcủa n ký hiệulà An loại2,,n phầntử giống nhau thuộcloạik,là: k n ! n ! A k = n nk− ! nn12!!...! nk () 25/03/2010 50 25/03/2010 51 2. Phép đếm 2. Phép đếm GIẢITÍCHTỔ HỢP GIẢITÍCHTỔ HỢP 2.5. Tổ hợp: 2.5. Tổ hợp: Nhậnxét:Từ kếtquả trên ta suy ra số tập con gồmk Cho tậphợpAgồmnphầntử.Mỗitập con gồm k phầntử củatậphợpgồmnphầntử làCn kphầntử củaAđượcgọilàmột tổ hợpchậpk Định lý: a)nk− k vớimọi0≤ k ≤ n; củanphầntử. Số các tổ hợpchậpkcủanphần CCnn= b) CCkk+=−1 C k với mọi 1 ≤ k ≤ n tửđựơckýhiệulàC k nn n+1 n Công thứcnhị thứcNewton:Vớix,y∈ R và n là số k n ! nguyên dương ta có: C = n n nknkk− knk!!()− ()x +=yCxy∑ n k =0 25/03/2010 52 25/03/2010 53 13 25/03/2010 2. Phép đếm 2. Phép đếm GIẢITÍCHTỔ HỢP GIẢITÍCHTỔ HỢP 2.6. Tổ hợplặp: 2.6. Tổ hợplặp: Có thể xem mộttổ hợplặpchậpkcủanloạiphầntử a1, Hệ quả: Số nghiệm nguyên không âm (x1,x2,,xn) a2,, an là một nhóm không thứ tự gồmkphầntử có (mỗixi đều nguyên không âm) củaphương trình thể trùng nhau được rút ra từ tập{a1,a2,, an}. x1+ x2++ xn= k k Gọi Kn là số tổ hợp lặp chập k của n loại phần tử. Ta có là: kk công thức: KCnnk= + −1 kk KCnnk= +−1 25/03/2010 54 25/03/2010 55 2. Phép đếm 3. Hệ thức đệ quy 2.7. Nguyên lý Dirichlet Mộthệ thức đệ quy tuyếntínhcấpklàmộthệ Giả sử cónvậtcần đặtvàokhộp. Khi đótồntại thứccódạng: ít nhấtmộthộpchứatừ ⎢⎥⎡⎤nk/ vậttrở lên, trong đó xn =a1xn-1 + + akxn-k +fn (1) ⎢⎥⎡⎤nk/ là số nguyên nhỏ nhấtlớnhơnhaybằng trong đó: n/k. Hơnnữa,nk/ là số nguyên lớnnhấtthỏa ⎢⎥⎡⎤ –a≠ 0, a ,, a là các hệ số thực tính chấttrên. k 1 k-1 – {fn} là một dãy số thựcchotrước –{xn}làdãyẩnnhận các giá trị thực. 25/03/2010 56 25/03/2010 57 14 25/03/2010 3. Hệ thức đệ quy 3. Hệ thức đệ quy Nghiệmtổng quát Trường hợpdãyfn=0vớimọi n thì (1) trở thành: •Mỗidãy{xn}thỏa(1)đượcgọilàmột nghiệm của (1). •Nhậnxétrằng mỗi nghiệm{xn}của(1)được xn =a1xn-1 + +akxn-k (2) hoàn toàn xác định bởi k giá trị ban đầux0, x1,, xk-1. Ta nói (2) là một hệ thức đệ qqyuy tuyếntính • Họ dãy số {x = x (C , C ,,C )} phụ thuộc thuầnnhấtcấpk. n n 1 2 k vào k họ tham số C1,C2,, Ck đượcgọilà nghiệmtổng quát của (1) nếumọidãycủahọ này đều là nghiệmcủa (1). 25/03/2010 58 25/03/2010 59 3. Hệ thức đệ quy 3. Hệ thức đệ quy Nghiệmriêng Mục đích giảihệ thức đệ quy •Cho{xn} là nghiệmtổng quát của (1) và với •Giảimộthệ thức đệ quy là đi tìm nghiệmtổng mọi k giá trị ban đầuy0,y1,, yk-1,tồntại quát của nó. duy nhất các giá trị củakthamsố C1, C2,,Ck sao cho nghiệm{xn}tương ứng •Nếuhệ thức đệ quy có kèm theo điềukiện thỏa: ban đầu, ta phải tìm nghiệm riêng thỏa điều x0 = y0, x1 = y1,, xk-1 = yk-1 (()*) kiện ban đầu đó. •Khiđó, nghiệm{xn}tương ứng đượcgọi nghiệmriêngứng với điềukiệnbanđầu (*). 25/03/2010 60 25/03/2010 61 15 25/03/2010 3. Hệ thức đệ quy 3. Hệ thức đệ quy Ví dụ: Vớin=1,tacóx =1. Một cầu thang có n bậc. Mỗi bước đi gồm 1 1 hoặc2bậc. Gọixn là số cách đihếtcầu thang. Vớin=2,tacóx2 =2 Tìm mộthệ thức đệ quy cho xn. Vớin>2,để khảosátxn ta chia thành hai trường hợploạitrừ lẫn nhau: Trường hợp 1: Bước đầu tiên gồm 1 bậc. Khi đó, cầu thang còn n-1 bậcnênsố cách đi hếtcầu thang trong trường hợpnàylàxn-1. 25/03/2010 62 25/03/2010 63 3. Hệ thức đệ quy 3. Hệ thức đệ quy Trường hợp2:Bước đầu tiên gồm2bậc. Vậytacóhệ thức đệ quy tuyếntínhthuầnnhất Khi đó, cầu thang còn n-2 bậc nên số cách đi cấp 2: hếtcầu thang trong trường hợpnàylàxn-2. Theo nguyên lý cộng, số cách đihếtcầu thang ⎧xnn= xx−12+ n− là xn-1 +xn-2 .Dođótacó: ⎨ ⎩xx12==1, 2. xn =xn-1 +xn-2 25/03/2010 64 25/03/2010 65 16 25/03/2010 3. Hệ thức đệ quy 3. Hệ thức đệ quy Bài toán Tháp Hà Nội Hanoi Tower Có 3 cọcA,B,Cvànđĩa(cólỗđểđặtvàocọc) 264= 18446744073709551615 (500 billion years) với đường kính đôi một khác nhau. Nguyên tắc đặt đĩavàocọclà:mỗi đĩachỉđượcchồng lên đĩalớnhơn nó. Ban đầu, cả n đĩa được đặt chồng lên nhau ở cọcA,haicọc B và C để trống.Vấn đề đặt ra là chuyểncả n đĩa ở cọcA sang cọcC(cóthể qua trung gian cọcB),mỗi lầnchỉ chuyểnmột đĩa. Gọixn là số lần chuyển đĩa. Tìm mộthệ thức đệ quy cho xn. 25/03/2010 66 25/03/2010 67 3. Hệ thức đệ quy 3. Hệ thức đệ quy Với n = 1 ta có x1 = 1. Như vậysố lần chuyểntoànbộ n đĩatừ Asang C là: Vớin>1,trướchết ta chuyểnn-1đĩa bên trên xn-1+ 1 + xn-1 = 2xn-1 + 1. sang cọc B qua trung gian cọcC(giữ nguyên Nghĩalàxn =2xn-1 +1,tacóhệ thức đệ quy đĩathứ ndưới cùng ở cọcA).Số lần chuyểnn- tuyến tính không thuầnnhấtcấp1: 1 đĩa đólàxn-1.Sauđó ta chuyển đĩathứ ntừ cọc A sang cọc C. Cuối cùng ta chuyểnn-1 đĩa ⎧xxnn= 21;−1 + từ cọc B sang cọcC.Số lần chuyểnn-1đĩa đó ⎨ x = 1. lạilàxn-1. ⎩ 1 25/03/2010 68 25/03/2010 69 17 25/03/2010 3. Hệ thức đệ quy 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính thuần nhất Hệ thức đệ quy tuyến tính thuần nhất Xét hệ thức đệ quy tuyến tính thuần nhất Trường hợp k = 1 xn = a1xn-1 + + akxn-k (2) Phương trình đặc trưng (*) trở thành λ -a1 = 0 Phương trình đặctrưng của (2) là phương trình nên có nghiệm là λ0 = a1 bậckđịnh bởi: Khi đó, (2) có nghiệm tổng quát là: k k-1 λ - a1λ -- ak = 0 (()*) n xn = Cλ0 25/03/2010 70 25/03/2010 71 3. Hệ thức đệ quy 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính thuần nhất Hệ thức đệ quy tuyến tính thuần nhất Ví dụ: Hệ thức đệ quy Phương trình đặc trưng: 2λ - 3 = 0 có nghiệm ⎧23xxnn−=−1 0; là λ0 =3/2 ⎨ ⎩x1 = 1. Do đó nghiệm tổng quát là: là một hệ thức đệ quy tuyến tính thuần nhất cấp n 1 ⎛⎞3 xCn = ⎜⎟ ⎝⎠2 25/03/2010 72 25/03/2010 73 18 25/03/2010 3. Hệ thức đệ quy 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính thuần nhất Hệ thức đệ quy tuyến tính thuần nhất Trường hợpk=2: Từ điều kiện ban đầu x1 = 1, ta có : Phương trình đặctrưng (*) trở thành: 3 2 C ∗=1 λ -a1λ -a2 = 0 (*) 2 Suy ra: 2 a) Nếu (*) có hai nghiệmthực phân biệt λ C = 1 3 và λ2 thì (2) có nghiệmtổng quát là : Do đó nghiệm của hệ thức đệ quy đã cho là: nn xn =+ABλ12λ n−1 ⎛⎞3 xn = ⎜⎟ ⎝⎠2 25/03/2010 74 25/03/2010 75 3. Hệ thức đệ quy 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính thuần nhất Hệ thức đệ quy tuyến tính thuần nhất c) Nếu (*) có hai nghiệmphức liên hợp được viết dướidạng lượng giác : b) Nếu (*) có nghiệmképthực λ0 thì (2) có nghiệmtổng quát là: λ = ri(cosϕϕ± sin ) n xAnBn =+()λ0 thì (2) có nghiệmtổng quát là: n xn =+rA(cos nϕ B sin) nϕ 25/03/2010 76 25/03/2010 77 19 25/03/2010 3. Hệ thức đệ quy 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính thuần nhất Hệ thức đệ quy tuyến tính thuần nhất Giải các hệ thức đệ quy sau: Ví dụ 1: 2xxxnn−+= 3−−12 n 0 ( 1) Ví dụ 1 23xxxnn−+=−−12 n 0 Phương trình đặc trưng của (1) là: ⎧41290;xxxnnn+−11−+ = 2 Ví dụ 2 ⎨ 2λ -3λ +1= 0 (*) ⎩xx01==2; 4. có hai nghiệm thựclà λ1 =1vàλ2 =1/2. xxx240; Do đó nghiệm tổng quát của (1) là: ⎧ nnn++21−+= n Ví dụ 3 ⎛⎞1 ⎨ =+AB xx==4; 4. x n ⎜⎟ ⎩ 12 ⎝⎠2 25/03/2010 78 25/03/2010 79 3. Hệ thức đệ quy 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính thuần nhất Hệ thức đệ quy tuyến tính thuần nhất Ví dụ 2: Từđiềukiệnbanđầux0 =2;x1 =4tasuyra: 41290xxx−+ = ⎧ nnn+−11 ⎧A = 2 ⎨ () 2 ⎪ ⎩xx01==2; 4. ⎨3 ()4AB+ = Phương trình đặctrưng của (2) là: ⎩⎪2 3 2 Suy ra A = 2 và B = 4λ -12λ +9= 0 2 có nghiệmthựcképlàλ0 =3/2.Dođónghiệm Vậy nghiệmcủa (2) là: n −1 tổng quát của (2) là: n ⎛⎞3 ⎛⎞3 =+(3n ) =+()AnB x n ⎜⎟ x n ⎜⎟ ⎝⎠2 ⎝⎠2 25/03/2010 80 25/03/2010 81 20 25/03/2010 3. Hệ thức đệ quy 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính thuần nhất Hệ thức đệ quy tuyến tính thuần nhất Ví dụ 3: Do đó nghiệm tổng quát của (3) là nnπ π ⎧xnnn++21−+=240xx xC=+2n ( cos C sin ) ⎨ () 3 n 1233 ⎩xx12==4; 4 Từ điều kiện ban đầu x = 4; x = 4 Phương trình đặc trưng của (3) là: 1 2 ta suy ra: λ2 -2λ + 4 = 0 (*) ⎧ 13 ⎪2(CC12+= ) 4 ⎪ 22 ⎨ Suy ra: CC==1, 3 có hai nghiệm phức liên hợp là λ =±13i 13 12 ⎪4(−+CC ) = 4 Ta viết hai nghiệm trên dưới dạng lượng giác: ⎩⎪ 2212 π π n nnπ π λ =±2(cosi sin ) Vậy nghiệm của (3) là :xn =+2(cos 3sin ) 25/03/2010 33 82 25/03/2010 3383 3. Hệ thức đệ quy 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính không thuần nhất Hệ thức đệ quy tuyến tính không thuần nhất Xét hệ thức đệ quy tuyến tính không thuầnnhất Nghiệm tổng quát x = a x + + a x + f (1) n 1 n-1 k n-k n của (2) Hệ thức đệ quy tuyến tính thuầnnhấttương ứng Nghiệm tổng quát của (1) = + là: Một nghiệm riêng xn = a1xn-1 ++a+ + akxn-k (2) của(1)a (1) Phương trình đặc trưng của (2) là: k k-1 λ -a1λ - - ak = 0 (*) 25/03/2010 84 25/03/2010 85 21 25/03/2010 3. Hệ thức đệ quy 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính không thuần nhất Hệ thức đệ quy tuyến tính không thuần nhất Cách tìm mộtnghiệm riêng của (1) khi vế phải n Dạng 1: fn = β Pr(n) fn của (1) có dạng đặcbiệtnhư sau: n Khi đótaxétλ0 = β.Có3trường hợpnhỏ: Dạng 1: fn = β Pr(n), trong đóPr(n) là một đathức bậcrtheon;β là mộthằng số Trường hợp1:β không là nghiệmcủaphương trình đặctrưng Dạng 2: fn =Pm(n)cosnϕ +Ql(n)sinnϕ, trong đó Pm(n), Ql(n) lầnlượtlàcácđathứcbậcm,l theo n; Trường hợp2:β là nghiệm đơncủa phương trình ϕ là hằng số (ϕ≠kπ). đặctrưng Dạng 3: fn =fn1 +fn2 ++ fns, trong đócácfn1, Trường hợp3:β là nghiệmképcủaphương trình fn2,, fns thuộc2dạng đã xét ở trên. đặctrưng 25/03/2010 86 25/03/2010 87 3. Hệ thức đệ quy 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính không thuần nhất Hệ thức đệ quy tuyến tính không thuần nhất n n Dạng 1: fn = β Pr(n) Dạng 1: fn = β Pr(n) Trường hợp1 Trường hợp2 Nếu λ0 = β không là nghiệmcủaphương trình Nếu λ0 = β là nghiệm đơncủaphương trình đặctrưng (*) thì (1) có một nghiệmriêng đặctrưng (*) thì (1) có một nghiệmriêng dạng: dạng: n n xn = β Qr(n) xn = nβ Qr(n) 25/03/2010 88 25/03/2010 89 22 25/03/2010 3. Hệ thức đệ quy 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính không thuần nhất Hệ thức đệ quy tuyến tính không thuần nhất n Chú ý: Dạng 1: fn = β Pr(n) r r-1 Trường hợp3 Qr(n) = Arn +Ar-1n ++ A0 là đathứctổng quát có cùng bậcrvớiPr(n), trong đóAr,Ar-1,, A0 là r+1 hệ Nếu λ0 = β là nghiệmképcủaphương trình số cầnxácđịnh. đặctrưng (*) thì (1) có một nghiệmriêng dạng: Để xác định các hệ số trên ta cầnthế xn,xn-1,, xn-k vào (1) và cho n nhậnr+1giátrị nguyên nào đóhoặc 2 n xn = n β Qr(n) đồng nhất các hệ số tương ứng ở hai vếđểđượcmộthệ phương trình. Các hệ số trên là nghiệmcủahệ phương trình này 25/03/2010 90 25/03/2010 91 3. Hệ thức đệ quy 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính không thuần nhất Hệ thức đệ quy tuyến tính không thuần nhất Dạng 2: fn = Pm(n)cosnϕ + Ql(n)sinnϕ Dạng 2: fn = Pm(n)cosnϕ + Ql(n)sinnϕ Trường hợp1 Khi đótaxétλ0 =cosϕ ± isinϕ.Có2trường hợpnhỏ: Nếu λ0 =cosϕ ±isinϕ không là nghiệmcủa phương trình đặctrưng (*) thì (1) có một Trường hợp1:λ0 =cosϕ ±isinϕ không là nghiệm của phương trình đặctrưng. nghiệm riêng dạng: Trường hợp2:λ0 =cosϕ ±isinϕ là nghiệmcủa xn = Rk(n)cosnϕ + Sk(n)sinnϕ phương trình đặctrưng. 25/03/2010 92 25/03/2010 93 23 25/03/2010 3. Hệ thức đệ quy 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính không thuần nhất Hệ thức đệ quy tuyến tính không thuần nhất Chú ý: Dạng 2: fn = Pm(n)cosnϕ + Ql(n)sinnϕ Trường hợp2 Rk(n), Sk(n) là các đathứctổng quát theo n có bậck=max{m,l}với 2k+2 hệ số cầnxácđịnh: Nếu λ0 =cosϕ ±isinϕ là nghiệmcủaphương trình đặctrưng (*) thì (1) có một nghiệmriêng R (n) = A nk + A nk-1 ++ A dạng: k k k-1 0 S (n) = B nk + B nk-1 ++ B xn = n(Rk(n)cosnϕ + Sk(n)sinnϕ) k k k-1 0 25/03/2010 94 25/03/2010 95 3. Hệ thức đệ quy 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính không thuần nhất Hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Dạng 3: f = f + f ++ f n n1 n2 ns 23xxxnn−+−−12++ n= 41 n+ (2) Hệ thức đệ quy tuyến tính thuầnnhấtlà: Bằng cách như trên ta tìm được nghiệmriêng xni (1≤ i ≤ s) củahệ thức đệ quy: 23xxxnn− −−12+= n 0 a0xn + a1xn-1 + + akxn-k = fni Phương trình đặc trưng của (2) là: 2λ2 -3λ +1= 0 (*) Khi đóxn =xn1 +xn2++ xns là một nghiệm riêng của (1). có ha