Chương I - PHƯƠNG PHÁP ĐẾM

Chia sẻ: AN TON | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

161
lượt xem 26
download

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

Định nghĩa: Một tập hợp là một bộ sưu tập các vật mà ta còn gọi là các phần tử của tập hợp đó. 1. Nhắc lại về tập hợp và ánh xạ KHÁI NIỆM VỀ TẬP HỢP 1.2. Ký hiệu: Ta dùng – các chữ in: A, B, C, ..., X, Y, Z, ... để chỉ các tập hợp. – các chữ nhỏ: a, b, c, ..., x, y, z, ... để chỉ các phần tử. – ký hiệu x ∈ A để chỉ x là một phần tử của tập hợp A. Ký hiệu x ∉ A để chỉ...

Chủ đề:

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

Lưu

Nội dung Text: Chương I - PHƯƠNG PHÁP ĐẾM

1. Nhắc lại về tập hợp và ánh xạ Chương I PHƯƠNG PHÁP KHÁI NIỆM VỀ TẬP HỢP ĐẾM 1.1. Định nghĩa: Một tập hợp là một bộ sưu tập các vật mà ta còn gọi là các phần tử của tập hợp đó. 23/06/2009 2 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ạ KHÁI NIỆM VỀ TẬP HỢP KHÁI NIỆM VỀ TẬP HỢP 1.3. Biểu diễn một tập hợp: 1.2. Ký hiệu: Ta dùng Để biểu diễn một tập hợp ta thường dùng một trong – các chữ in: A, B, C, ..., X, Y, Z, ... để chỉ hai phương pháp sau: các tập hợp. 1)Liệt kê: Các phần tử của tập hợp sẽ được liệt kê đúng một lần giữa hai dấu { }; giữa hai phần tử khác nhau sẽ – các chữ nhỏ: a, b, c, ..., x, y, z, ... để chỉ các có dấu ngăn cách (thường là dấu phẩy, hay chấm phẩy ;) phần tử. nhưng thứ tự giữa các phần tử này là không quan trọng. – ký hiệu x ∈ A để chỉ x là một phần tử của Ví dụ: A = {1, 2, 3, 4}, tập hợp A. Ký hiệu x ∉ A để chỉ x không N = {0, 1, 2, 3, ...}, phải là một phần tử của tập hợp A. Z = {0, ±1, ±2, ...}, ... 23/06/2009 23/06/2009 3 4 1 PDF created with pdfFactory Pro trial version www.pdffactory.com
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ạ KHÁI NIỆM VỀ TẬP HỢP KHÁI NIỆM VỀ TẬP HỢP 1.3. Biểu diễn một tập hợp: 1.4. Tập hợp rỗng: 2) Nêu tính chất đặc trưng: Tập hợp sẽ được mô tả như Tập hợp rỗng, ký hiệu bởi Φ, là tập hợp là một bộ sưu tập gồm tất cả các phần tử x thỏa mãn không chứa phần tử nào. tính chất đặc trưng p(x) nào đó dưới dạng: Ví dụ: A = {x | p(x)} hay A = {x ∈ B | p(x)}. Ví dụ: Các tập hợp A = {x ∈ R | x2 – 4x + 5 = 0} 1) Tập hợp A = {x ∈ R | x2 – 4x + 3 = 0} chính là tập và B = {x ∈ Z | 2x – 1 = 0} hợp A = {1, 3}. đều là các tập hợp rỗng. 2) Tập hợp các số hữu tỉ được mô tả như sau: Q = { Z, n ≠ 0} 23/06/2009 23/06/2009 5 6 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ạ KHÁI NIỆM VỀ TẬP HỢP KHÁI NIỆM VỀ TẬP HỢP 1.5. Tập hợp con và tập hợp bằng nhau: 1.5. Tập hợp con và tập hợp bằng nhau: 2) A bằng B, ký hiệu A = B, nếu A là tập hợp con của B và ngược Cho hai tập hợp A và B. Ta nói: lại, i.e. nếu mọi phần tử của A đều là các phần tử của B và 1) A là tập hợp con của B, ký hiệu A ⊂ B hay B ⊃ A nếu ngược lại. Như vậy, theo định nghĩa, ta có: mọi phần tử của A đều là các phần tử của B. Như vậy, A = B ⇔ (A ⊂ B) và (B ⊂ A). theo định nghĩa, ta có: ⇔ (∀x ∈ A, x ∈ B) và (∀x ∈ B, x ∈ A). A ⊂ B ⇔ ∀x ∈ A, x ∈ B. Ký hiệu A ≠ B để chỉ A không bằng B. Ký hiệu A ⊄ B hay B A để chỉ A không phải là tập con Ví dụ: Xét các tập hợp của B. A = {x ∈ R | x2 – 4x + 3 = 0}, B = {x ∈ R | x(x –1)(x – 3) = 0}, C = {0; 1; 2}, D = {0; 1; 2; 3}. Ta thấy A ⊂ B, B ≠ C, C ⊂ D, nhưng B ⊄ A, D ⊄ C. 23/06/2009 23/06/2009 7 8 2 PDF created with pdfFactory Pro trial version www.pdffactory.com
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ẬP HỢP KHÁI NIỆM VỀ TẬP HỢP Cho A và B là hai tập hợp con của tập hợp X. 1.6. Tập hợp các tập hợp con: Cho tập hợp X. Tập hợp tất cả các tập hợp con của X được ký 1.6 Phép giao: hiệu là P(X). Như vậy: P(X) = {A | A ⊂ B} Phần giao của A và B, ký hiệu bởi A ∩ B, là tập hợp tất Kết quả quen thuộc sau đây có thể được chứng minh bằng cả các phần tử của X vừa thuộc A vừa thuộc B. Như vậy, quy nạp theo n: “Nếu tập hợp X có đúng n phần tử thì tập hợp theo định nghĩa, ta có: tất cả các tập hợp con P(X) của X sẽ có đúng 2n phần tử”. A ∩ B = {x ∈ X | x ∈ A và x ∈ B}. Ví dụ: Cho X = {a, b, c}. Ta có: Nói cách khác ∀x ∈ X, x ∈ A ∩ B ⇔ x ∈ A và x ∈ B. P(X) = {∅; {a}; {b}; {c}; {a, b}; {b, c}; {a, c}; {a, b, c}}. Suy ra ∀x ∈ X, x ∉ A ∩ B ⇔ x ∉ A hay x ∉ B. 23/06/2009 23/06/2009 9 10 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ẬP HỢP CÁC PHÉP TOÁN TẬP HỢP 1.7. Phép hợp: 1.8. Phép hiệu: Phần hợp của A và B, ký hiệu bởi A ∪ B, là tập hợp tất Phần hiệu của A và B, ký hiệu bởi A \ B, là tập hợp tất cả cả các phần tử (của X) thuộc A hay thuộc B. Như vậy, các phần tử (của X) thuộc A nhưng không thuộc B. Như theo định nghĩa, ta có: vậy, theo định nghĩa, ta có: A ∪ B = {x ∈ X | x ∈ A hay x ∈ B}. A \ B = {x ∈ X | x ∈ A và x ∉ B}. Nói cách khác ∀x ∈ X, x ∈ A ∪ B ⇔ x ∈ A hay x ∈ B. Nói cách khác ∀x ∈ X, x ∈ A \ B ⇔ x ∈ A và x ∉ B. Suy ra ∀x ∈ X, x ∉ A ∪ B ⇔ x ∉ A và x ∉ B. Suy ra ∀x ∈ X, x ∉ A \ B ⇔ x ∉ A hay x ∈ B. 23/06/2009 23/06/2009 11 12 3 PDF created with pdfFactory Pro trial version www.pdffactory.com
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ẬP HỢP CÁC PHÉP TOÁN TẬP HỢP Ví dụ: 1.9. Phép bù: Xét các tập hợp X = {0; 1; 2; 3; 4; 5; 6}; Với A là một tập con của X, phần bù của A trong X, ký hiệu bởi A hay CX(A), là tập hợp X\A. Như vậy, theo A = {0; 1; 2; 3}; định nghĩa, ta có: B = {1; 2; 4; 5}. X\A = {x ∈ X | x ∉ A}. Ta có: Nói cách khác ∀x ∈ X, x ∈ A ⇔ x ∉ A. A ∩ B = {1, 2}; A ∪ B = {0; 1; 2; 3; 4; 5}; Suy ra ∀x ∈ X, x ∉ A ⇔ x ∈ A. A \ B = {0; 3}; B \ A = {4; 5}; CX(A) = {4; 5; 6}; CX(B) = {0; 3; 6}. 23/06/2009 23/06/2009 13 14 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ẬP HỢP CÁC PHÉP TOÁN TẬP HỢP 1.10. Định lý (tính chất của các phép toán): 1.10. Định lý (tính chất của các phép toán): Cho A, B, C là các tập hợp con của tập hợp X. Khi đó 4) Tính phân phối: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) ta có: 1) Tính lũy đẳng: và A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∩ A = A và A ∪ A = A 5) Công thức De Morgan: 2) Tính giao hoán: A∩ B = A∪ B& A∪ B = A∩ B A ∩ B = B ∩ A và A ∪ B = B ∪ A. Suy ra: 3) Tính kết hợp: A \ (B ∩ C) = (A \ B) ∪ (A \ C) (A ∩ B) ∩ C = A ∩ (B ∩ C) và A \ (B ∪ C) = (A \ B) ∩ (A \ C) và (A ∪ B) ∪ C = A ∪ (B ∪ C) 6) Các công thức A = A & A \ B = A ∩ B 23/06/2009 23/06/2009 15 16 4 PDF created with pdfFactory Pro trial version www.pdffactory.com
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ĨA VÀ KÝ HIỆU ÁNH XẠ ĐỊNH NGHĨA VÀ KÝ HIỆU ÁNH XẠ 1.11. Định nghĩa 1.13. Ảnh và ảnh ngược: Cho hai tập hợp X, Y ≠ ∅. Một ánh xạ f từ X vào Y là quy Cho ánh xạ f từ X vào Y và A ⊂ X, B ⊂ Y. Ta định nghĩa: tắc cho ứng với mỗi phần tử x của X một phần tử duy nhất y 1) Ảnh của A qua f là tập hợp: của Y mà ta ký hiệu là f(x) và gọi là ả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 a f(x) Như vậy theo định nghĩa, ta có: 1.12. Định nghĩa ∀y ∈ Y, y ∈ f(A) ⇔ ∃x ∈ A, y = f(x); Hai ánh xạ f và g từ X vào Y được gọi là bằng nhau nếu: ∀y ∈ Y, y ∉ f(A) ⇔ ∀x ∈ A, y ≠ f(x). ∀x ∈ X, f(x) = g(x) 23/06/2009 23/06/2009 17 18 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ĨA VÀ KÝ HIỆU ÁNH XẠ ĐỊNH NGHĨA VÀ KÝ HIỆU ÁNH XẠ 1.13. Ảnh và ảnh ngược: 1.13. Ảnh và ảnh ngược: Chú ý: 2) Ảnh ngược hay tạo ảnh của B bởi f là tập hợp: 1) Ta thường dùng ký hiệu Imf để chỉ tập hợp f(X) và còn gọi f–1(B) = {x ∈ X | f(x) ∈ B} là ảnh của f. Như vậy theo định nghĩa, ta có: 2) Với y ∈ B ta dùng ký hiệu f–1(y) thay cho f–1({y}). Đó ∀x ∈ X, x ∈ f–1(B) ⇔ f(x) ∈ B; chính là tập hợp các phần tử x ∈ X thỏa f(x) = y (ta thường ∀x ∈ X, x ∉ f–1(B) ⇔ f(x) ∉ B. gọi đây là tập hợp tất cả các nghiệm x trong X của phương trình f(x) = y). Lưu ý rằng tập hợp f–1(y) có thể rỗng hay khác rỗng (gồm một hay nhiều phần tử). 23/06/2009 23/06/2009 19 20 5 PDF created with pdfFactory Pro trial version www.pdffactory.com
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Ạ ĐỊNH NGHĨA VÀ KÝ HIỆU ÁNH XẠ Xét ánh xạ f : X → Y. 1.14 Định lý: 1.15. Đơn ánh: Giả sử f là một ánh xạ từ X vào Y. Với A1 và A2 là hai tập Ta nói f : X → Y là một đơn ánh nếu hai phần tử khác nhau hợp con tùy ý của X, B1 và B2 là hai tập con tùy ý của Y. Ta bất kỳ của X đều có ảnh khác nhau, nghĩa là: có: ∀x, x' ∈ X, x ≠ x' ⇒ f(x) ≠ f(x') 1. f(A1 ∪ A2) = f(A1) ∪ f(A2); Những tính chất sau được suy trực tiếp từ định nghĩa. 2. f(A1 ∩ A2) ⊂ f(A1) ∩ f(A2); f : X → Y là một đơn ánh 3. f(A1 \ A2) ⊃ f(A1) \ f(A2); ⇔ (∀x, x' ∈ X, f(x) = f(x') ⇒ x = x'). 4. f–1(B1 ∪ B2) = f–1(B1) ∪ f–1(B2); ⇔ (∀y ∈ Y, f–1(y) có nhiều nhất một phần tử). 5. f–1(B1 ∩ B2) = f–1(B1) ∩ f–1(B2); ⇔ (∀y ∈ Y, phương trình f(x) = y (y được xem như tham 6. f–1(B1 \ B2) = f–1(B1) \ f–1(B2). số) có nhiều nhất một nghiệm x ∈ X. 23/06/2009 23/06/2009 21 22 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.15. Đơn ánh: 1.16. Toàn ánh: Ta nói f : X → Y là một toàn ánh nếu Imf = Y. Suy ra: f : X → Y không là một đơn ánh Những tính chất sau được suy trực tiếp từ định nghĩa. ⇔ (∃x, x' ∈ X, x ≠ x' và f(x) = f(x')). f : X → Y là một toàn ánh ⇔ (∃y ∈ Y, phương trình f(x) = y (y được xem như tham ⇔ (∀y ∈ Y, ∃x ∈ X, y = f(x)) số) có ít nhất hai nghiệm x ∈ X. ⇔ (∀y ∈ Y, f–1(y) ≠ ∅); ⇔ ∀y ∈ Y, phương trình f(x) = y (y được xem như tham số) có nghiệm x ∈ X. 23/06/2009 23/06/2009 23 24 6 PDF created with pdfFactory Pro trial version www.pdffactory.com
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.17. Song ánh và ánh xạ ngược: 1.16. Toàn ánh: Ta nói f : X → Y là một song ánh hay là một tương ứng 1-1 Suy ra: f : X → Y không là một toàn ánh nếu f vừa là đơn ánh vừa là toàn ánh. ⇔ (∃y ∈ Y, ∀x ∈ X, y ≠ f(x)); Những tính chất sau được suy trực tiếp từ định nghĩa. f : X → Y là một song ánh ⇔ (∃y ∈ Y, f–1(y) = ∅); ⇔ (∀y ∈ Y, ∃!x ∈ X, y = f(x)); ⇔ ∀y ∈ Y, phương trình f(x) = y (y được xem như tham ⇔ (∀y ∈ Y, f–1(y) có đúng một phần tử); số) vô nghiệm trong X. ⇔ ∀y ∈ Y, phương trình f(x) = y (y được xem như tham số) có duy nhất một nghiệm x ∈ X. 23/06/2009 23/06/2009 25 26 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.18. Song ánh và ánh xạ ngược: 1.18. Song ánh và ánh xạ ngược: Xét f : X → Y là một song ánh. Khi đó, theo tính chất trên, Suy ra: với mọi y ∈ Y, tồn tại duy nhất một phần tử x ∈ X thỏa f(x) f : X → Y không là một song ánh = y. Do đó tương ứng y ax là một ánh xạ từ Y vào X. Ta gọi ⇔ f không là một đơn ánh hay không là một toàn ánh; đây là ánh xạ ngược của f và ký hiệu f–1. Như vậy: ⇔ ∀y ∈ Y, phương trình f(x) = y (y được xem như tham số) f–1 : Y → X vô nghiệm hoặc có ít nhất hai nghiệm x ∈ X. y a f–1(y) = x với f(x) = y. 23/06/2009 23/06/2009 27 28 7 PDF created with pdfFactory Pro trial version www.pdffactory.com
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.19. Định nghĩa: Cho hai ánh xạ 1.20. Định lý: f : X → Y và g : Y' → Z Xét f : X → Y là một song ánh. Khi đó: trong đó Y ⊂ Y'. Ánh xạ tích h của f và g là ánh xạ từ X vào Z xác f o f–1 = IdY định bởi: f–1 o f = IdX h:X→Z trong đó ký hiệu IdX để chỉ ánh xạ đồng nhất X → X x a 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ất trên X, tương tự IdY là ánh xạ đồng nhất trên Y. h=gof:X→Y→Z x a f(x)a h(x) = g(f(x)) 23/06/2009 23/06/2009 29 30 2. Phép đếm 2. Phép đếm Nguyên lý Cộng và Nguyên lý Nhân Nguyên lý Cộng và Nguyên lý Nhân 1) Nguyên lý Cộng: 2) Nguyên lý Nhân: Giả sử để hoàn thành một công việc ta phải tiến hành theo trình tự Giả sử để một hiện tượng xảy ra, có k trường hợp k bước có tác dụng độc lập. Biết rằng: lớn loại trừ lẫn nhau. Biết rằng ở mỗi trường hợp – Có n1 cách thực hiện buớc 1. lớn thứ j lại có nj trường hợp nhỏ. Khi đó, số – Sau khi thực hiện bước 1 xong, dù bằng bất cứ cách nào, trường hợp nhỏ nói chung để hiện tượng trên xảy luôn luôn có một số lượng không đổi n2 cách để thực hiện bước 2. ra là: – ………… n = n1 + n2 + … + nk. – Cuối cùng, sau khi thực hiện xong bước thứ k-1, luôn luôn có một số lượng không đổi nk cách để thực hiện bước thứ k. Khi đó, số cách để hoàn thành công việc đã cho là: n = n1n2… nk. 23/06/2009 23/06/2009 31 32 8 PDF created with pdfFactory Pro trial version www.pdffactory.com
2. Phép đếm 2. Phép đếm Giải tích tổ hợp Giải tích tổ hợp 2.1. Chỉnh hợp 2.2. Hoán vị k Gọi An là số chỉnh hợp chập k của n phần tử. Ta Gọi Pn là số hoán vị của n phần tử. Ta có công có công thức: thức: Pn = n! Định lý. Số hoán vị của n phần tử, trong đó có n1 n! A nk = phần tử giống nhau thuộc loại 1, n2 phần tử giống ( n − k )! nhau thuộc loại 2,…, nk phần tử giống nhau thuộc loại k, là: n! n1 ! n 2 !...n k ! 23/06/2009 23/06/2009 33 34 2. Phép đếm 2. Phép đếm Giải tích tổ hợp Giải tích tổ hợp 2.3. Tổ hợp 2.3. Tổ hợp Nhận xét: Từ kết quả trên ta suy ra số tập con gồm k Gọi Cnk là số tổ hợp chập k của n phần tử. Ta có phần tử của tập hợp gồm n phần tử là Cnk công thức: Định lý. a) Cn −k = Cn n! với mọi 0 ≤ k ≤ n; n k C nk = k ! ( n − k )! với mọi 1 ≤ k ≤ n b) Cnk + Cnk −1 = Cnk+1 Công thức nhị thức Newton: Với x, y ∈ R va n là số nguyên dương ta có: n ∑C x n−k y k ( x + y)n = k n k =0 23/06/2009 23/06/2009 35 36 9 PDF created with pdfFactory Pro trial version www.pdffactory.com
2. Phép đếm 2. Phép đếm Giải tích tổ hợp Giải tích tổ hợp 2.4. Tổ hợp lặp 2.4. Tổ hợp lặp Có thể xem một tổ hợp lặp chập k của n loại phần tử a1, Hệ quả: Số nghiệm nguyên không âm (x1,x2,…,xn) (mỗi a2,…, an là một nhóm không thứ tự gồm k phần tử có thể xi đều nguyên không âm) của phương trình trùng nhau được rút ra từ tập {a1, a2,…, an}. x1+ x2+…+ xn= k k Gọi K n là số tổ hợp lặp chập k của n loại phần tử. Ta có là: công thức: K n = Cn+k −1 K n = Cn+k −1 k k k k 23/06/2009 23/06/2009 37 38 2. Phép đếm 3. Hệ thức đệ quy Moät heä thöùc ñeä quy tuyeán tính caáp k laø moät heä 2.5. Nguyên lý Dirichlet thöùc coù daïng: Giả sử có n vật cần đặt vào k hộp. Khi đó tồn tại ít nhất một hộp chứa từ  n / k  vật trở lên, trong đó   xn = a1xn-1 +… + akxn-k + fn (1)  n / k  là số nguyên nhỏ nhất lớn hơn hay bằng   n/k. Hơn nữa,  n / k  là số nguyên lớn nhất thỏa   trong ñoù: tính chất trên. • ak ≠ 0, a1,…, ak-1 laø caùc heä soá thöïc • {fn} laø moät daõy soá thöïc cho tröôùc • {xn} laø daõy aån nhaän caùc giaù trò thöïc. 23/06/2009 40 23/06/2009 39 10 PDF created with pdfFactory Pro trial version www.pdffactory.com
3. Hệ thức đệ quy 3. Hệ thức đệ quy Nghieäm toång quaùt Tröôøng hôïp daõy fn= 0 vôùi moïi n thì (1) trôû thaønh: Ø Moãi daõy {xn} thoûa (1) ñöôïc goïi laø moät nghieäm cuûa (1). xn = a1xn-1 +… +akxn-k (2) • Nhaän xeùt raèng moãi nghieäm {xn} cuûa (1) ñöôïc hoaøn toaøn xaùc ñònh bôûi k giaù trò ban ñaàu x0, Ta noùi (2) laø moät heä thöùc ñeä quy tuyeán tính thuaàn x1,…, xk-1. nhaát caáp k. Ø Hoï daõy soá {xn = xn(C1, C2,…,Ck)} phuï thuoäc vaøo k hoï tham soá C1, C2,…, Ck ñöôïc goïi laø nghieäm toång quaùt cuûa (1) neáu moïi daõy cuûa hoï naøy ñeàu laø nghieäm cuûa (1). 23/06/2009 23/06/2009 41 42 3. Hệ thức đệ quy 3. Hệ thức đệ quy Nghieäm rieâng Muïc ñích giaûi heä thöùc ñeä quy Cho {xn} laø nghiệm tổng quaùt của (1) vaø vôùi moïi k • Giaûi moät heä thöùc ñeä quy laø ñi tìm nghieäm toång giaù trò ban ñaàu y0, y1,…, yk-1, toàn taïi duy nhaát caùc quaùt cuûa noù. giaù trò cuûa k tham soá C1, C2,…,Ck sao cho nghieäm {xn} töông öùng thoûa: • Neáu heä thöùc ñeä quy coù keøm theo ñieàu kieän ban x0 = y0, x1 = y1,…, xk-1 = yk-1 (*) ñaàu, ta phaûi tìm nghieäm rieâng thoûa ñieàu kieän ban Khi ñoù, nghieäm {xn} töông öùng ñöôïc goïi nghieäm ñaàu ñoù. rieâng öùng vôùi ñieàu kieän ban ñaàu (*). 23/06/2009 23/06/2009 43 44 11 PDF created with pdfFactory Pro trial version www.pdffactory.com
3. Hệ thức đệ quy 3. Hệ thức đệ quy Ví dụ: Vôùi n = 1, ta coù x1 = 1. Moät caàu thang coù n baäc. Moãi böôùc ñi goàm 1 hoaëc 2 baäc. Goïi xn laø soá caùch ñi heát caàu Vôùi n = 2, ta coù x2 = 2 thang. Tìm moät heä thöùc ñeä quy cho xn. Vôùi n > 2, ñeå khaûo saùt xn ta chia thaønh hai tröôøng hôïp loaïi tröø laãn nhau: Tröôøng hôïp 1: Böôùc ñaàu tieân goàm 1 baäc. Khi ñoù, caàu thang coøn n-1 baäc neân soá caùch ñi heát caàu thang trong tröôøng hôïp naøy laø xn-1. 23/06/2009 23/06/2009 45 46 3. Hệ thức đệ quy 3. Hệ thức đệ quy Tröôøng hôïp 2: Böôùc ñaàu tieân goàm 2 baäc. Vaäy ta coù heä thöùc ñeä quy tuyeán tính thuaàn nhaát caáp 2: Khi ñoù, caàu thang coøn n-2 baäc neân soá caùch ñi heát caàu thang trong tröôøng hôïp naøy laø xn-2. Theo nguyeân lyù coäng, soá caùch ñi heát caàu thang laø xn-1 + xn-2 . Do ñoù ta coù:  xn = xn−1 + xn −2  xn = xn-1 + xn-2  x1 = 1, x2 = 2. 23/06/2009 23/06/2009 47 48 12 PDF created with pdfFactory Pro trial version www.pdffactory.com
3. Hệ thức đệ quy 3. Hệ thức đệ quy Hanoi Tower Baøi toaùn Thaùp Haø Noäi 264= 18446744073709551615 (500 billion years) Coù 3 coïc A, B, C vaø n ñóa (coù loã ñeå ñaët vaøo coïc) vôùi ñöôøng kính ñoâi moät khaùc nhau. Nguyeân taéc ñaët ñóa vaøo coïc laø: moãi ñóa chæ ñöôïc choàng leân ñóa lôùn hôn noù. Ban ñaàu, caû n ñóa ñöôïc ñaët choàng leân nhau ôû coïc A, hai coïc B vaø C ñeå troáng. Vaán ñeà ñaët ra laø chuyeån caû n ñóa ôû coïc A sang coïc C (coù theå qua trung gian coïc B), moãi laàn chæ chuyeån moät ñóa. Goïi xn laø soá laàn chuyeån ñóa. Tìm moät heä thöùc ñeä quy cho xn 23/06/2009 23/06/2009 49 50 3. Hệ thức đệ quy 3. Hệ thức đệ quy Vôùi n = 1 ta coù x1 = 1. Nhö vaäy soá laàn chuyeån toaøn boä n ñóa töø A sang C laø: Vôùi n >1, tröôùc heát ta chuyeån n-1 ñóa beân treân sang xn-1+ 1 + xn-1 = 2xn-1 + 1. coïc B qua trung gian coïc C (giöõ nguyeân ñóa thöù n Nghóa laø xn = 2xn-1 + 1, ta coù heä thöùc ñeä quy döôùi cuøng ôû coïc A). Soá laàn chuyeån n-1 ñóa ñoù laø xn-1. tuyeán tính khoâng thuaàn nhaát caáp 1: Sau ñoù ta chuyeån ñóa thöù n töø coïc A sang coïc C. Cuoái cuøng ta chuyeån n-1 ñóa töø coïc B sang coïc C. Soá laàn chuyeån n-1 ñóa ñoù laïi laø xn-1.  xn = 2 xn−1 + 1;   x1 = 1. 23/06/2009 23/06/2009 51 52 13 PDF created with pdfFactory Pro trial version www.pdffactory.com
3. Hệ thức đệ quy 3. Hệ thức đệ quy Hệ thức đệ quy tuyến tính thuần nhất Tröôøng hôïp k = 1 Xeùt heä thöùc ñeä quy tuyeán tính thuaàn nhaát xn = a1xn-1 +… + akxn-k (2) Phöông trình ñaëc tröng (*) trôû thaønh λ - a1 = 0 neân coù nghieäm laø λ0 = a1 Phöông trình ñaëc tröng cuûa (2) laø phöông trình baäc k ñònh bôûi: Khi ñoù, (2) coù nghieäm toång quaùt laø: xn = C λ0n λk - a1λk-1 -… - ak = 0 (*) 23/06/2009 23/06/2009 53 54 3. Hệ thức đệ quy 3. Hệ thức đệ quy Ví dụ: Hệ thức đệ quy Phöông trình ñaëc tröng: 2λ - 3 = 0 coù nghieäm laø λ0 = 3/2  2 xn − 3 xn −1 = 0;   x1 = 1. Do ñoù nghieäm toång quaùt laø: laø moät heä thöùc ñeä quy tuyeán tính thuaàn nhaát caáp 1 n  3 xn = C    2 23/06/2009 23/06/2009 55 56 14 PDF created with pdfFactory Pro trial version www.pdffactory.com
3. Hệ thức đệ quy 3. Hệ thức đệ quy Tröôøng hôïp k = 2: Töø ñieàu kieän ban ñaàu x1 = 1, ta coù : Phöông trình ñaëc tröng (*) trôû thaønh: 3 C ∗ =1 λ2 - a1λ - a2 = 0 (*) 2 Suy ra: 2 C= a) Neáu (*) coù hai nghieäm thöïc phaân bieät λ1 3 vaø λ2 thì (2) coù nghieäm toång quaùt laø: Do ñoù nghieäm cuûa heä thöùc ñeä quy ñaõ cho laø: n −1 xn = Aλ1n + Bλ2n 3 xn =   2 23/06/2009 23/06/2009 57 58 3. Hệ thức đệ quy 3. Hệ thức đệ quy c) Neáu (*) coù hai nghieäm phöùc lieân hôïp ñöôïc vieát döôùi daïng löôïng giaùc : b) Neáu (*) coù nghieäm keùp thöïc λ0 thì (2) coù λ = r (cos ϕ ± i sin ϕ ) nghieäm toång quaùt laø: thì (2) coù nghieäm toång quaùt laø: xn = ( A + nB )λ n 0 xn = r n ( A cos nϕ + B sin nϕ ) 23/06/2009 23/06/2009 59 60 15 PDF created with pdfFactory Pro trial version www.pdffactory.com
3. Hệ thức đệ quy 3. Hệ thức đệ quy Ví duï 1: Giaûi caùc heä thöùc ñeä quy sau: (1) 2 xn − 3 xn−1 + xn−2 = 0 2 xn − 3 xn −1 + xn −2 = 0 Ví duï 1 Phöông trình ñaëc tröng cuûa (1) laø: 2λ2 - 3λ + 1 = 0 (*)  4 xn +1 − 12 xn + 9 xn −1 = 0; Ví duï 2  coù hai nghieäm thöïc laø λ1 = 1 vaø λ2 = 1/2.  x0 = 2; x1 = 4. Do ñoù nghieäm toång quaùt cuûa (1) laø:  xn+ 2 − 2 xn +1 + 4 xn = 0; Ví duï 3  xn = A + B(1/2)n  x1 = 4; x2 = 4. 23/06/2009 23/06/2009 61 62 3. Hệ thức đệ quy 3. Hệ thức đệ quy Ví duï 2: Töø ñieàu kieän ban ñaàu x0 = 2; x1 = 4 ta suy ra:  4 xn +1 − 12 xn + 9 xn −1 = 0 (2)   x0 = 2; x1 = 4. A = 2  Phöông trình ñaëc tröng cuûa (2) laø: 3  2 ( A + B) = 4  4λ2 - 12λ + 9 = 0 Suy ra A = 2 vaø B = 2/3 coù nghieäm thöïc keùp laø λ0 = 3/2. Do ñoù Vaäy nghieäm cuûa (2) laø: nghieäm toång quaùt cuûa (2) laø: xn = (A + nB)(3/2)n xn = (3 + n)(3/2)n-1 23/06/2009 23/06/2009 63 64 16 PDF created with pdfFactory Pro trial version www.pdffactory.com
3. Hệ thức đệ quy 3. Hệ thức đệ quy Ví duï 3: Do ñoù nghieäm toång quaùt cuûa (3) laø  xn+ 2 − 2 xn +1 + 4 xn = 0 ( 3) nπ nπ  xn = 2n (C1 cos + C2 sin )  x1 = 4; x2 = 4 3 3 Töø ñieàu kieän ban ñaàu x1 = 4; x2 = 4 ta suy ra: Phöông trình ñaëc tröng cuûa (3) laø: 1 λ2 - 2λ + 4 = 0 3  2( C1 + C2 ) = 4 (*) 2 C1 = 1, C2 = 3 2 Suy ra:  λ = 1± i 3 coù hai nghieäm phöùc lieân hôïp laø  4( − 1 C + 3 C ) = 4   Ta vieát hai nghieäm treân döôùi daïng löôïng giaùc: 1 2 2 2 π π nπ nπ λ = 2(cos ± i sin ) xn = 2n (cos + 3 sin ) Vậy nghiệm của (3) là : 3 3 3 3 23/06/2009 23/06/2009 65 66 17 PDF created with pdfFactory Pro trial version www.pdffactory.com