›
›

Bài giảng Toán rời rạc - Chương 3: Phép đếm và hệ thức đệ quy

pdf 62 trang hapham 70
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Chương 3: Phép đếm và hệ thức đệ quy", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_toan_roi_rac_chuong_3_phep_dem_va_he_thuc_de_quy.pdf

Nội dung text: Bài giảng Toán rời rạc - Chương 3: Phép đếm và hệ thức đệ quy

  1. TOÁN RỜI RẠC - HK1 - NĂM 2015 -2016 Chương 3 PHÉP ĐẾM VÀ HỆ THỨC ĐỆ QUY lvluyen@hcmus.edu.vn ∼luyen/trr FB: fb.com/trr2015 lvluyen@hcmus.edu.vnTrường ĐạiChương Học Khoa 3. Phép học đếm Tự và nhiên hệ thức TP đệ Hồ quy Chí Minh3/12/2015 1/62
  2. Nội dung Chương 3. PHÉP ĐẾM VÀ HỆ THỨC ĐỆ QUY 1. Các nguyên lý đếm cơ bản 2. Giải tích tổ hợp 3. Hoán vị lặp, tổ hợp lặp 4. Hệ thức đệ quy lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 2/62
  3. 3.1. Các nguyên lý đếm cơ bản 1 Nguyên lý cộng 2 Nguyên lý nhân 3 Nguyên lý bù trừ 4 Nguyên lý Derichlet lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 3/62
  4. 3.1.1. Nguyên lý cộng Giả sử để làm công việc A ta có 2 phương pháp Phương pháp 1: có n cách làm Phương pháp 2: có m cách làm Khi đó số cách làm công việc A là n + m. Ví dụ. An có 3 áo tay dài, 5 áo tay ngắn. Để chọn một cái áo thì An có mấy cách? Đáp án. 3+5 =8 cách. Ví dụ. Nhà trường cần chọn một sinh viên khoa CNTT năm hai, năm ba hoặc năm tư đi tham gia hội nghị sinh viên thành phố. Biết rằng trường có 501 sinh viên năm hai, 402 sinh viên năm ba, 345 sinh viên năm tư. Hỏi có bao nhiêu cách chọn? Đáp án. 501 + 402 + 345 = 1248 cách. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 4/62
  5. 3.1.2. Nguyên lý nhân Giả sử để làm công việc A cần thực hiện 2 bước Bước 1 có n cách làm Bước 2 có m cách làm Khi đó số cách làm công việc A là n × m. Ví dụ. Hỏi có nhiêu cách đi từ A đến C? Đáp án. 3 × 2 = 6 cách. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 5/62
  6. Ví dụ. Có bao nhiêu chuỗi bit có độ dài 8? Giải. Mỗi bit có thể chọn 1 trong 2 cách: 0 hoặc 1. Theo nguyên lý nhân ta có số lượng chuỗi là 28 = 256. Ví dụ. Cho tập A gồm 6 phần tử và tập B gồm 10 phần tử. Hỏi a) Có bao nhiêu ánh xạ từ A vào B? b) Có bao nhiêu đơn ánh từ A vào B? Giải. a) Với mỗi phần tử x của A ta có 10 cách chọn ảnh của x (vì B có 10 phần tử). Theo nguyên lý nhân, ta có 106 ánh xạ. b) Giải sử A = {x1, x2, . . . , x6}. Ta chia bài toán thành 6 bước: Bước 1. Chọn ảnh của x1 có 10 cách. Bước 2. Chọn ảnh của x2 có 10 − 1 = 9 cách. Bước 6. Chọn ảnh của x6 có 10 − 5 = 5 cách. Vậy số đơn ánh là: 10 × 9 × 8 × 7 × 6 × 5 = 151200. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 6/62
  7. Ví dụ. Cho tập X = {0, 1, 2, 3, 4, 5}. Hỏi có bao nhiêu số tự nhiên có ba chữ số khác nhau mà chia hết cho 2? Giải. Gọi số có ba chữ số là abc. Trường hợp 1. c = 0. Khi đó c có 1 cách chọn a có 5 cách chọn ( a = X \{0} ) b có 4 cách chọn ( b = X \{a, 0} ) Trường hợp 1 có 1 × 4 × 5 = 20 số. Trường hợp 2. c 6= 0. Khi đó c có 2 cách chọn a có 4 cách chọn ( a = X \{c, 0} ) b có 4 cách chọn ( b = X \{a, c} ) Trường hợp 2 có 2 × 4 × 4 = 32 số. Như vậy có 20 + 32 = 52 số. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 7/62
  8. 3.1.3. Nguyên lý bù trừ Ví dụ. Có bao nhiêu chuỗi bit có độ dài 8 hoặc được bắt đầu bằng 1 hoặc kết thúc bằng 00? Cho A và B là hai tập hữu hạn. Khi đó |A ∪ B| = |A| + |B| − |A ∩ B| Giải ví dụ trên. Số lượng chuỗi bit bắt đầu bằng 1 là 27 = 128. Số lượng chuỗi bit kết thúc bằng 00 là 26 = 64. Số lượng chuỗi bit bắt đầu bằng 1 và kết thúc bằng 00 là 25 = 32. Số lượng chuỗi bit thỏa đề bài là 128 + 64 − 32 = 160. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 8/62
  9. Ví dụ. Có 2 bài toán kiểm tra. Trong lớp có 30 sinh viên làm được bài thứ nhất và 20 sinh viên làm được bài thứ hai và chỉ có 10 sinh viên làm được cả 2 bài. Biết rằng mỗi sinh viên đều làm ít nhất một bài, hỏi lớp có bao nhiêu sinh viên? Giải. Ta gọi A là những sinh viên giải được bài 1 B là những sinh viên giải được bài 2 Khi đó A ∩ B là những sinh viên giải được cả 2 bài toán. Bài toán đặt ra là tính số phần tử A ∪ B. Ta có |A ∪ B| = |A| + |B| − |A ∩ B| = 30 + 20 − 10 = 40. Như vậy lớp có 40 sinh viên. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 9/62
  10. |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |A ∩ C| + |A ∩ B ∩ C| Ví dụ.(tự làm) Bài kiểm tra Toán Rời Rạc có 3 bài. Biết rằng, mỗi sinh viên làm được ít nhất 1 bài, trong đó có 20 sinh viên làm được bài 1. 14 sinh viên làm được bài 2. 10 sinh viên làm được bài 3. 6 sinh viên giải được bài 1 và 3. 5 sinh viên giải được bài 2 và bài 3. 2 sinh viên giải được bài 1 và 2. 1 sinh viên giải được cả 3 bài. Hỏi lớp có bao nhiêu sinh viên? lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 10/62
  11. 3.1.4. Nguyên lý Derichlet (chuồng bồ câu) Ví dụ. Trong 1 nhóm có 367 người thì ít nhất có 2 người sinh cùng ngày. Có 20 chim bồ câu ở trong 7 cái chuồng. Khi đó sẽ có ít nhất 1 chuồng có 3 con bồ câu trở lên. Định nghĩa. Giá trị trần của x, ký hiệu là dxe, là số nguyên nhỏ nhất mà lớn hơn hay bằng x. Ví dụ. d2.1e = 3; d1.9e = 2; d4e = 4; d−1.1e = −1. d−2.9e = −2; d−4e = −4. Nguyên lý Derichlet Giả sử có n chim bồ câu ở trong k chuồng. Khi đó tồn tại ít nhất một lnm chuồng chứa từ bồ câu trở lên. k lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 11/62
  12. 100 Ví dụ. Trong 100 người thì có ít nhất = 9 cùng tháng sinh. 12 Ví dụ. Chứng minh rằng trong 10 số tự nhiên bất kỳ có thể chọn hai số có hiệu chia hết cho 9. Giải. Khi chia 10 số bất kỳ cho 9 ta sẽ có mỗi số có một số dư trong 9 số dư: 0, 1, 2, , 7, 8. Do đó theo nguyên lý Dirichlet phải tồn tại ít nhất hai số có cùng số dư. Hiệu của hai số đó sẽ chia hết cho 9. Ví dụ. Trong một lớp học phải có ít nhất bao nhiêu học sinh để cho có ít nhất 6 học sinh có cùng thứ bậc học tập, biết rằng có 5 loại thứ bậc A, B, C, D và E? Giải. Gọi số học sinh của lớp là N. Theo nguyên lý Derichlet ta có N d 5 e = 6. Khi đó 25 < N ≤ 30. Do đó ta có thể chọn N = 26. Vậy lớp phải có ít nhất 26 học sinh. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 12/62
  13. 3.2. Giải tích tổ hợp 1 Hoán vị 2 Chỉnh hợp 3 Tổ hợp lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 13/62
  14. 3.2.1. Hoán vị Định nghĩa. Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt có thứ tự n phần tử của A được gọi là một hoán vị của n phần tử. Ví dụ. Cho A = {1, 2, 3}. Khi đó A có các hoán vị sau: 123, 132, 213, 231, 312, 321 Định nghĩa. Số các hoán vị của n phần tử, ký hiệu là Pn Pn = n! = n × (n − 1) × (n − 2) × × 1 Quy ước 0! = 1. Ví dụ.(tự làm) Cho X = {1, 2, 3, 4, 5}. Hỏi có bao nhiêu số tự nhiên gồm 5 chữ số khác nhau được tạo từ tập X? lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 14/62
  15. Ví dụ. Cần sắp xếp 5 học sinh A, B, C, D, E thành một dãy hàng dọc a) Hỏi có bao nhiêu cách sắp xếp. b) Hỏi có bao nhiêu cách sắp xếp sao cho hai học sinh A và B luôn đứng ở hai đầu hàng ? Giải. a) Để xếp 5 học sinh theo một dãy hàng dọc ta chỉ cần xếp 5 học sinh theo thứ tự. Vậy có P5 = 5! = 120 cách. b) Do 2 bạn A, B đứng đầu hàng nên có 2! = 2 cách xếp 2 bạn đứng đầu. Ba vị trí còn lại ta chọn 3 học sinh còn lại và xếp theo thứ tự nên có 3! = 6 cách. Vậy theo nguyên lý nhân ta có: 2! × 3! = 2 × 6 = 12 cách. Ví dụ. Từ 6 chữ số 1, 2, 3, 4, 5, 6 có thể lập được bao nhiêu số tự nhiên gồm 6 chữ số khác nhau, trong đó có bao nhiêu số lẻ? bao nhiêu số không chia hết cho 5? lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 15/62
  16. Giải. Để có số tự nhiên có 6 chữ số khác nhau ta chọn sắp xếp 6 chữ số đã cho theo thứ tự. Nên có P6 = 6! = 720 số. Gọi x = abcdef là số có 6 chữ số khác nhau. Nếu x là số lẻ thì f ∈ {1, 3, 5} nên f có 3 cách chọn. Năm số còn lại a b c d e là hoán vị của 5 chữ số còn lại (vì đã loại đi số f). Nên có 5! cách chọn. Vậy theo qui tắc nhân ta có 3 × 5! = 360 số lẻ Tương tự như lý luận trên, ta có 5! số chia hết cho 5. Như vậy số không chia hết cho 5 là 6! − 5! = 600. Ví dụ.(tự làm) Cần sắp xếp 3 sinh viên nữ và 5 sinh viên nam thành một hàng dọc. a) Hỏi có bao nhiêu cách sắp xếp nếu 3 sinh viên nữ luôn đứng liền nhau ? b) Hỏi có bao nhiêu cách sắp xếp nếu sinh viên đứng đầu hàng là sinh viên nữ và sinh viên cuối hàng là sinh viên nam ? Đáp án. a) 5! × 6 × 3! = 4320 cách b) 3 × 5 × 6! = 10800 cách lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 16/62
  17. 3.2.2. Chỉnh hợp Định nghĩa. Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k phần tử (1 ≤ k ≤ n) sắp thứ tự của tập hợp A được gọi là một chỉnh hợp chập k của n phần tử. Ví dụ. Cho X = {a, b, c}. Khi đó X có các chỉnh hợp chập 2 của 3 là: ab, ba, ac, ca, bc, cb k Định nghĩa. Số các chỉnh hợp chập k của n, ký hiệu là An, và n! Ak = n × (n − 1) × · · · × (n − k + 1) = n (n − k)! Ví dụ. Có bao nhiêu số tự nhiên khác nhau ngồm 3 chữ số được tạo thành từ 1, 2, 3, 4, 5, 6. 3 Đáp án. A6 số. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 17/62
  18. Ví dụ.(tự làm) Một lớp có 15 học sinh nam và 20 nữ. Trong buổi tập trung lớp đầu năm, giáo viên chọn 3 học sinh làm ban cán sự lớp: 1 lớp trưởng, 1 lớp phó và 1 thủ quỹ. a) Hỏi có bao nhiêu cách chọn ? b) Hỏi có bao nhiêu cách chọn nếu lớp trưởng là nam. c) Hỏi có bao nhiêu cách chọn nếu trong 3 bạn được chọn phải có ít nhất 1 nữ. 3 Đáp án. a) A35 2 b) 15 × A34 3 3 c) A35 − A15 lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 18/62
  19. 3.2.3. Tổ hợp Định nghĩa. Cho tập hợp A gồm n phần tử. Mỗi tập con gồm k phần tử của A được gọi là một tổ hợp chập k của n phần tử. Ví dụ. Cho X = {1, 2, 3, 4}. Tổ hợp chập 3 của 4 phần tử của X là {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4} ! n Định nghĩa. Số tổ hợp chập k của n phần tử được kí hiệu là k k hay Cn, Ak n! Ck = n = n k! k!(n − k)! Ví dụ. Một lớp có 30 học sinh. Hỏi có bao nhiêu cách chọn 10 bạn? 10 Đáp án. C30 cách. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 19/62
  20. Ví dụ.(tự làm) Cho 20 điểm khác nhau nằm trên mặt phẳng. Không có bất cứ 3 điểm nào trong số đó thẳng hàng. Hỏi có thể lập được bao nhiêu tam giác, tứ giác có đỉnh là một trong các điểm đã cho. 3 4 Đáp án. C20 tam giác C20 tứ giác Ví dụ.(tự làm) Một lớp có 40 sinh viên gồm 25 nam và 15 nữ. Ta cần chọn ra 6 sinh viên tham gia hội nghị của trường. Hỏi có bao nhiêu cách chọn nếu: a) Không phân biệt nam nữ ? b) Có 4 nam và 2 nữ ? c) Có ít nhất là 4 sinh viên nam ? 6 4 2 Đáp án. a) C40 b) C25 × C15 4 2 5 1 6 0 c) C25 × C15 + C25 × C15 + C25 × C15 lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 20/62
  21. 3.3. Hoán vị lặp, tổ hợp lặp 1 Hoán vị lặp 2 Tổ hợp lặp 3 Khai triển lũy thừa của đa thức lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 21/62
  22. 3.3.1. Hoán vị lặp Ví dụ. Có bao nhiêu chuỗi kí tự khác nhau bằng cách sắp xếp các chữ cái của từ AAABB? Đáp án. 10 Định nghĩa. Cho n đối tượng trong đó có ni đối tượng loại i (1 < i ≤ k) giống hệt nhau, nghĩa là n1 + n2 + + nk = n. Mỗi cách sắp xếp có thứ tự n đối tượng đã cho gọi là một hoán vị lặp của n. Số hoán vị lăp của n trong trường hợp này là n! n1! × n2! × × nk! lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 22/62
  23. Ví dụ. Có bao nhiêu chuỗi kí tự khác nhau bằng cách sắp xếp các chữ cái của từ SUCCESS? Giải. Trong từ SUCCESS có 3 chữ S, 1 chữ U, 2 chữ C và 1 chữ E. Do đó số chuỗi có được là 7! = 420 3! × 1! × 2! × 1! Ví dụ.(tự làm) Từ các chữ số 1, 2, 3 lập được bao nhiêu số tự nhiên có đúng 5 chữ số 1, 2 chữ số 2 và 3 chữ số 3. Hướng dẫn. Số tự nhiên đó có 10 chữ số, trong đó có đúng 5 chữ số 1, 2 chữ số 2 và 3 chữ số 3. Do đó ta sẽ lập được 10! = 2520 số 5! × 2! × 3! lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 23/62
  24. 3.3.2. Tổ hợp lặp Ví dụ. Có 3 loại nón A, B, C. An mua 2 cái nón. Hỏi An có bao nhiêu cách chọn? Đáp án. An có 6 cách chọn là AA, AB, AC, BB, BC, CC. Định nghĩa. Mỗi cách chọn ra k vật từ n loại vật khác nhau (trong đó mỗi loại vật có thể được chọn lại nhiều lần) được gọi là tổ hợp lặp chập k của n. k Số các tổ hợp lặp chập k của n được ký hiệu là Kn và k k Kn = Cn+k−1. Hệ quả. Số nghiệm nguyên không âm (x1, x2, . . . , xn)(xi ∈ Z, xi ≥ 0) của phương trình x1 + x2 + + xn = k k k là Kn = Cn+k−1. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 24/62
  25. Ví dụ. Tìm số nhiệm nguyên không âm của phương trình x1 + x2 + x3 = 10. 10 10 Giải. Số nghiệm nguyên không âm của phương trình là: K3 = C12 . Ví dụ. Tìm số nghiệm nguyên của phương trình x1 + x2 + x3 + x4 = 20 (∗) thỏa điều kiện x1 ≥ 4; x2 > 2; x3 > 5; x4 ≥ −2 Giải. Ta viết điều kiện đã cho thành x1 ≥ 4; x2 ≥ 3; x3 ≥ 6; x4 ≥ −2. Đặt y1 = x1 − 4; y2 = x2 − 3; y3 = x3 − 6; y4 = x4 + 2. Khi đó yi ≥ 0 (1 ≤ i ≤ 4). Phương trình (∗) trở thành y1 + y2 + y3 + y4 = 9 (∗∗) lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 25/62
  26. Ta có số nghiệm của phương trình (∗) bằng số nghiệm của phương 9 9 trình (∗∗). Do đó số nghiệm của phương trình (∗) là K4 = C12. Ví dụ. Tìm số nghiệm nguyên không âm của phương trình x1 + x2 + x3 + x4 = 20 thỏa điều kiện x1 ≤ 3; x2 ≥ 2; x3 > 4. (∗) Giải. Ta viết điều kiện đã cho thành 0 ≤ x1 ≤ 3; x2 ≥ 2; x3 ≥ 5; x4 ≥ 0. Xét các điều kiện sau: x1 ≥ 0; x2 ≥ 2; x3 ≥ 5; x4 ≥ 0 (∗∗) x1 > 3; x2 ≥ 2; x3 ≥ 5; x4 ≥ 0 (∗ ∗ ∗) Gọi p, q, r lần lượt là các số nghiệm nguyên không âm của phương trình thỏa các điều kiện (∗), (∗∗), (∗ ∗ ∗). Ta có p = q − r. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 26/62
  27. Trước hết ta tìm q. Đặt y1 = x1; y2 = x2 − 2; y3 = x3 − 5; y4 = x4 Phương trình (1) trở thành y1 + y2 + y3 + y4 = 13 (2) Số nghiệm nguyên không âm của phương trình (1) thỏa điều kiện ( ) bằng số nghiệm nguyên không âm của phương trình (2) 13 13 13 13 Số nghiệm đó là K4 = C4+13−1 = C16 . Vậy q = C16 . 9 9 9 Lý luận tương tự ta có r = K4 = C4+9−1 = C12. Như vậy 13 9 p = q − r = C16 − C12 = 560 − 220 = 340. Vậy số nghiệm nguyên không âm của phương trình (1) thỏa điều kiện (∗) là 340. Hệ quả. Số cách chia k vật đồng chất nhau vào n hộp phân biệt cũng chính bằng số tổ hợp lặp chập k của n. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 27/62
  28. Ví dụ.(tự làm) Tìm số cách chia 15 viên bi giống nhau cho 4 đứa trẻ. 15 15 Đáp án. K4 = C18 . Ví dụ. Tìm số nghiêm nguyên không âm của bất phương trình sau: x1 + x2 + x3 ≤ 11. Giải. Thêm ẩn phụ x4 ≥ 0 vào bất phương trình, ta có bất phương trình đã cho tương đương với phương trình x1 + x2 + x3 + x4 = 11 với x1, x2, x3, x4 là các số nguyên không âm. Do đó số nghiệm của bất 11 11 phương trình là: K4 = C14 = 364. Ví dụ.(tự làm) Tìm số nghiệm nguyên của bất phương trình x + y + z ≤ 20, biết x ≥ 1, y ≥ 2, z ≥ 3. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 28/62
  29. Ví dụ.(tự làm) Tìm số nghiệm nguyên của bất phương trình x + y + z ≤ 15 thỏa điều kiện 2 ≤ x ≤ 6, y ≥ 2, z ≥ 3. Ví dụ.(tự làm) Tìm số nghiệm nguyên của phương trình x + y + z + t = 16 thỏa điều kiện 2 ≤ x ≤ 5, y ≥ 1, z ≥ 2, t ≥ 3. Ví dụ.(tự làm) Tìm số nghiệm nguyên không âm của phương trình x1 + x2 + x3 + x4 = 8 biết x1 ≥ 1 hay x2 ≥ 2. Ví dụ.(tự làm) Có bao nhiêu cách chia 18 viên bi giống nhau cho 4 đứa trẻ sao cho mỗi đứa trẻ đều có bi và đứa lớn nhất được ít nhất 6 viên bi. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 29/62
  30. 3.3.3. Khai triển lũy thừa của đa thức Định lý. Cho x, y là biến và n là số tự nhiên. Khi đó n n X k n−k k (x + y) = Cnx y k=0 0 n 1 n−1 n−1 n−1 n n = Cnx + Cnx y + ··· + Cn xy + Cn y . Ví dụ. Khai triển (x + y)4 4 4 X k 4−k k Giải. (x + y) = C4 x y k=0 0 4 1 3 2 2 2 3 3 4 4 = C4 x + C4 x y + C4 x y + C4 xy + C4 y . = x4 + 4x3y + 6x2y2 + 4xy3 + y4. Ví dụ.(tự làm) Khai triển (2x − 3y)5 lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 30/62
  31. Ví dụ. Tìm hệ số của x12y13 trong khai triển (2x − 3y)25? Giải. Dựa vào Định lý, ta có 25 25 h i X k 25−k k 2x + (−3y) = C25(2x) (−3y) . k=0 Do đó hệ số của x12y13 có được khi k = 13. Suy ra hệ số cần tìm là: 13 12 13 C25 2 (−3) = −33959763545702400. Định lý. Cho x1, x2, . . . , xm là các biến và n là số nguyên dương. Khi đó n X n! k1 k2 km (x1 + x2 + ··· + xm) = x1 x2 . . . xm k1! k2! . . . km! k1+k2+···+km=n lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 31/62
  32. Ví dụ. Tìm hệ số của x3y5z trong khai triển (x + 2y − 3z + t)9 Giải. Áp dụng Định lý trên, ta có số hạng chứa x3y5z là 9! x3(2y)5(−3z)1t0 = −48384 x3y5z. 3! 5! 1! 0! Vây hệ số của x3y5z là −48384. Ví dụ.(tự làm) Cho khai triển của (−x + y − 2z + t)10 a) Tìm hệ số của x5y4t. b) Có bao nhiêu số hạng khác nhau trong phép khai triển trên? Hướng dẫn. b) Mỗi số hạng có dạng Mxaybzctd. Suy ra các số hạng khác nhau của khai triển là số nghiệm của phương trình a + b + c + d = 10, 10 10 với a, b, c, d là các số nguyên không âm. Đáp án. K4 = C13 . lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 32/62
  33. 3.4. Hệ thức đệ quy 1 Giới thiệu 2 Hệ thức đệ quy tuyến tính với hệ số hằng 3 Nghiệm của hệ thức đệ quy tuyến tính thuần nhất 4 Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 33/62
  34. 3.4.1. Giới thiệu Ví dụ. Tháp Hà Nội Có 3 cọc A, B, C và n đĩa với đường kính đôi một khác nhau. Nguyên tắc đặt đĩa vào cọc là: mỗi đĩa chỉ được chồng lên đĩa lớn hơn nó. Ban đầu, cả n đĩa được đặt chồng lên nhau ở cọc A, hai cọc B và C để trống. Vấn đề đặt ra là chuyển cả n đĩa ở cọc A sang cọc C (có thể qua trung gian cọc B), mỗi lần chỉ chuyển một đĩa. Gọi xn là số lần chuyển đĩa. Tìm xn? lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 34/62
  35. Giải. Với n = 1, ta có x1 = 1. Với n > 1, trước hết ta chuyển n − 1 đĩa bên trên sang cọc B qua trung gian cọc C (giữ nguyên đĩa thứ n dưới cùng ở cọc A). Số lần chuyển n − 1 đĩa đó là xn−1. Sau đó ta chuyển đĩa thứ n từ cọc A sang cọc C. Cuối cùng ta chuyển n − 1 đĩa từ cọc B sang cọc C. Số lần chuyển n − 1 đĩa đó lại là xn−1. Như vậy số lần chuyển toàn bộ n đĩa từ A sang C là: xn−1 + 1 + xn−1 = 2xn−1 + 1. Nghĩa là  x1 = 1 xn = 2xn−1 + 1 với n > 1 lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 35/62
  36. Ví dụ. Một cầu thang có n bậc. Mỗi bước đi gồm 1 hoặc 2 bậc. Gọi xn là số cách đi hết cầu thang. Tìm xn? Giải. Với n = 1, ta có x1 = 1. Với n = 2, ta có x2 = 2. Với n > 2, để khảo sát xn ta chia thành hai trường hợp loại trừ 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ậc nên số cách đi hết cầu thang là xn−1. Trường hợp 2. Bước đầu tiên gồm 2 bậc. Khi đó, cầu thang còn n − 2 bậc nên số cách đi hết cầu thang trong là xn−2. Theo nguyên lý cộng, số cách đi hết cầu thang là xn−1 + xn−2. Do đó ta có: xn = xn−1 + xn−2 Như vậy  x1 = 1, x2 = 2; xn = xn−1 + xn−2 với n > 2. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 36/62
  37. 3.4.2. Hệ thức đệ quy tuyến tính với hệ số hằng Định nghĩa. Một hệ thức đệ quy tuyến tính cấp k với hệ số hằng là một hệ thức có dạng: a0xn + a1xn−1 + + akxn−k = fn (1) trong đó a0 6= 0, a1, . . . , an là các hệ số thực; {fn} là một dãy số thực cho trước và {xn} là dãy ẩn nhận các giá trị thực. Trường hợp dãy fn = 0 với mọi n thì (1) trở thành a0xn + a1xn−1 + + akxn−k = 0 (2) Ta nói (2) là một hệ thức đệ quy tuyến tính thuần nhất cấp k với hệ số hằng. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 37/62
  38. Ví dụ. 2 2xn − 5xn−1 + 2xn−2 = −n − 2n + 3 −→ tuyến tính cấp 2. n−2 n xn − 3xn−1 + 2xn−3 = 20 + n2 + 3 −→ tuyến tính cấp 3. n 2xn+2 + 5xn+1 + 2xn = (35n + 51)3 −→ tuyến tính cấp 2. xn+2 − 2xn+1 + xn = 0 −→ tuyến tính thuần nhất cấp 2. Định nghĩa. Xét hệ thức đệ quy tuyến tính cấp k a0xn + a1xn−1 + + akxn−k = fn (1) Mỗi dãy {xn} thỏa (1) được gọi là một nghiệm của (1). Nhận xét rằng mỗi nghiệm {xn} của (1) được hoàn toàn xác định bởi k giá trị ban đầu x0, x1, . . . , xk−1. Họ dãy số {xn = xn(C1,C2, ,Ck)} phụ thuộc vào k họ tham số C1,C2, ,Ck được gọi là nghiệm tổng quát của (1) nếu mọi dãy của họ này đều là nghiệm của (1). lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 38/62
  39. Với k giá trị ban đầu y0, y1, . . . , yk−1, tồn tại duy nhất các giá trị của k tham số C1,C2, ,Ck sao cho nghiệm {xn} tương ứng thỏa x0 = y0, x1 = y1, . . . , xk−1 = yk−1 (∗) Khi đó, nghiệm {xn} tương ứng được gọi nghiệm riêng ứng với điều kiện ban đầu (∗). Giải một hệ thức đệ quy là đi tìm nghiệm tổng quát của nó; nhưng nếu hệ thức đệ quy có kèm theo điều kiện ban đầu, ta phải tìm nghiệm riêng thỏa điều kiện ban đầu đó. Ví dụ. 3n 2x − 3x = 0 có nghiêm tổng quát là x = C n n−1 n 2  xn − 5xn−1 + 6xn−2 = 0;  n n x0 = 4; có nghiệm riêng là xn = 3 · 2 + 3 .  x1 = 9. Lưu ý. Trong phạm vi của chương trình ta chỉ xét các hệ thức đệ quy tuyến tính (cấp 1 và 2) với hệ số hằng. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 39/62
  40. 3.4.3. Nghiệm của HTĐQTT thuần nhất Xét hệ thức đệ quy tuyến tính thuần nhất a0xn + a1xn−1 + + akxn−k = 0 (1) Phương trình đặc trưng của (1) là phương trình bậc k định bởi: k k−1 a0λ + a1λ + + ak = 0( ∗) Trường hợp k = 1. Phương trình đặc trưng (∗) trở thành a0λ + a1 = 0 nên có nghiệm là a1 λ0 = − . a0 n Khi đó, (1) có nghiệm tổng quát là: xn = C λ0 . Trường hợp k = 2. Phương trình đặc trưng (∗) trở thành 2 a0λ + a1λ + a2 = 0( ∗) Người ta chứng minh được kết quả sau: lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 40/62
  41. Nếu (∗) có hai nghiệm thực phân biệt λ1 và λ2 thì (1) có nghiệm tổng quát là: n n xn = C1 λ1 + C2 λ2 Nếu (∗) có nghiệm kép thực λ0 thì (1) có nghiệm tổng quát là n xn = (C1 + nC2)λ0 Nếu (∗) có hai nghiệm phức liên hợp được viết dưới dạng λ = r(cos ϕ ± i sin ϕ) thì (1) có nghiệm tổng quát là n xn = r (A cos nϕ + B sin nϕ)  x − 2x = 0 Ví dụ. Giải hệ thức đệ quy n n−1 (1) x0 = 5. Giải. Phương trình đặc trưng là λ − 2 = 0 có nghiệm là λ = 2. Suy ra n (1) có nghiệm tổng quát là xn = C2 . n Từ điều kiện x0 = 5 ta có C = 5. Suy ra nghiệm của (∗) là xn = 5 · 2 . lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 41/62
  42.   xn = 5xn−1 − 6xn−2; Ví dụ. Tìm nghiệm của x0 = 4; (2)  x1 = 9. Giải. xn = 5xn−1 − 6xn−2 ⇔ xn − 5xn−1 + 6xn−2 = 0 Phương trình đặc trưng λ2 − 5λ + 6 = 0 có 2 nghiệm thực phân biệt λ1 = 2 và λ2 = 3. Suy ra (2) có nghiệm tổng quát là n n xn = C1 2 + C2 3 .  C1 + C2 = 4 Vì x0 = 4; x1 = 9 nên Suy ra C1 = 3,C2 = 1. Vậy 2C1 + 3C2 = 9. nghiệm của hệ thức đệ quy là n n xn = 3 · 2 + 3 . lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 42/62
  43.   4xn+1 − 12xn + 9xn−1 = 0; Ví dụ. Tìm nghiệm của x0 = 2; (3)  x1 = 9. Giải. Phương trình đặc trưng 4λ2 − 12λ + 9 = 0 có 1 nghiệm thực kép là λ0 = 3/2 và λ2 = 3. Suy ra (3) có nghiệm tổng quát là 3n x = (C + nC ) . n 1 2 2 ( C1 = 2 Vì x = 2; x = 9 nên 3 Suy ra C = 2,C = 4. Vậy 0 1 (C + C ) = 9. 1 2 2 1 2 nghiệm của hệ thức đệ quy là 3n x = (2 + 4n) . n 2 lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 43/62
  44.   xn+2 − 2xn+1 + 4xn = 0; Ví dụ. Tìm nghiệm của x0 = 1; (4)  x1 = 4. Giải. Phương trình đặc trưng λ2 − 2λ + 4 = 0 có 2 nghiệm phức liên hợp là √  π π  λ = 1 ± i 3 = 2 cos ± i sin . 3 3 Suy ra (4) có nghiệm tổng quát là  nπ nπ  x = 2n A cos + B sin . n 3 3  A = 1  √ ! Vì x = 1; x = 4 nên 1 3 Suy ra 0 1 2 A + B = 4.  2 2 √ A = 1,B = 3. Vậy nghiệm của hệ thức đệ quy là  nπ √ nπ  x = 2n A cos + 3 sin . n 3 3 lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 44/62
  45. 3.4.4. Nghiệm của HTĐQTT không thuần nhất Xét hệ thức đệ quy tuyến tính không thuần nhất a0xn + a1xn−1 + + akxn−k = fn (1) Hệ thức đệ quy tuyến tính thuần nhất tương ứng là a0xn + a1xn−1 + + akxn−k = 0 (2) Phương trình đặc trưng của (2) là: k k−1 a0λ + a1λ + + ak = 0( ∗) Khi đó Để tìm một nghiệm riêng của (1), ta xem xét các dạng đặc biệt của vế trái fn như sau: lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 45/62
  46. n Dạng 1. fn = β Pr(n), trong đó Pr(n) là một đa thức bậc r theo n; β là một hằng số. Dạng 2. fn = fn1 + fn2 + + fns , trong đó các fn1 , fn2 , . . . , fns thuộc dạng 1. n Dạng 1. fn = β Pr(n). Có ba trường hợp xảy ra: TH 1. Nếu β không là nghiệm của phương trình đặc trưng (∗) thì (1) có một nghiệm riêng dạng: n xn = β Qr(n) TH 2. Nếu β là nghiệm đơn của phương trình đặc trưng (∗) thì (1) có một nghiệm riêng dạng: n xn = nβ Qr(n) TH 3. Nếu β là nghiệm kép của phương trình đặc trưng (∗) thì (1) có một nghiệm riêng dạng: 2 n xn = n β Qr(n) lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 46/62
  47. r r−1 Chú ý Qr(n) = Arn + Ar−1n + + A0 là đa thức có cùng bậc r với Pr(n), trong đó Ar,Ar−1, ,A0 là r + 1 hệ số cần xác định. Để xác định các hệ số trên ta cần thế xn, xn−1, . . . , xn−k vào (1) và cho n nhận r + 1 giá trị nguyên nào đó hoặc đồng nhất các hệ số tương ứng ở hai vế để được một hệ phương trình. Các hệ số trên là nghiệm của hệ phương trình này. Dạng 2. fn = fn1 + fn2 + + fns . Bằng cách như trên ta tìm được nghiệm riêng xni (1 ≤ i ≤ s) của hệ thức đệ quy a0xn + a1xn−1 + + akxn−k = fni Khi đó xn = xn1 + xn2 + + xns là một nghiệm riêng của (1). lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 47/62
  48. Ví dụ. Cho hệ thức đệ quy xn − 5xn−1 + 6xn−2 = fn (1). Khi đó hệ thức đệ quy tuyến tính thuần nhất tương ứng là: xn − 5xn−1 + 6xn−2 = 0 (2) Phương trình đặc trưng của (2) là: λ2 − 5λ + 6 = 0 (∗) có hai nghiệm thực là λ1 = 2 và λ2 = 3. (p) Nếu fn = 2n + 1 thì (1) có nghiệm riêng dạng xn = An + B. n 2 (p) n 2 Nếu fn = 5 (3n + 2n + 1) thì xn = 5 (An + Bn + C). n (p) n Nếu fn = 5 , thì xn = 5 A. n (p) n Nếu fn = 3 thì xn = n3 A. n (p) n Nếu fn = 2 (3n + 1) thì xn = n2 (An + B). lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 48/62
  49. Ví dụ. Cho hệ thức đệ quy xn − 6xn−1 + 9xn−2 = fn (1). Khi đó hệ thức đệ quy tuyến tính thuần nhất tương ứng là: xn − 6xn−1 + 9xn−2 = 0 (2) Phương trình đặc trưng của (2) là: λ2 − 6λ + 9 = 0 (∗) có nghiệm kép là λ0 = 3. n (p) 2 n Nếu fn = 3 thì (1) có nghiệm riêng dạng xn = n 3 A. n (p) 2 n Nếu fn = 3 (5n + 1) thì xn = n 3 (An + B). n (p) n Nếu fn = 2 (5n + 1) thì xn = 2 (An + B). lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 49/62
  50.  x − 5x + 6x = 2n + 1; Ví dụ. Tìm nghiệm của n n−1 n−2 x0 = 1; x1 = 3. Giải. Hệ thức đệ quy tuyến tính thuần nhất tương ứng là: xn − 5xn−1 + 6xn−2 = 0 (2) Phương trình đặc trưng của (2) là: λ2 − 5λ + 6 = 0 (∗) có hai nghiệm thực là λ1 = 2 và λ2 = 3. Do đó nghiệm tổng quát của (2) là: n n xn = C1 2 + C2 3 (3) Bây giờ ta tìm một nghiệm riêng của (1). Vế phải của (1) là n fn = 2n + 1 có dạng β Pr(n) với β = 1 và Pr(n) là đa thức bậc r = 1. Vì β = 1 không là nghiệm của phương trình đặc trưng (∗) nên (1) có một nghiệm riêng dạng: xn = an + b (4) lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 50/62
  51. Thế (4) vào (1) ta được: (an + b) − 5[a(n − 1) + b] + 6[a(n − 2) + b] = 2n + 1. Cho n lần lượt nhận hai giá trị n = 0; n = 1 ta được hệ:  −7a + 2b = 1; −5a + 2b = 3. Giải hệ trên ta được a = 1; b = 4. Thế vào (4) ta tìm được một nghiệm riêng của (1) là: xn = n + 4 (5) Từ (3) và (5) ta suy ra nghiệm tổng quát của (1) là: n n xn = C1 2 + C2 3 + n + 4 Thay điều kiện x0 = 1 và x1 = 3 vào (6) ta được  C1 + C2 = −3 2C1 + 3C2 = −2. Từ đó ta có C1 = −7 và C2 = 4. Thế vào (6) ta được n n xn = −7 · 2 + 4 · 3 + n + 4. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 51/62
  52. Ví dụ. Giải hệ thức đệ quy 2xn − 3xn−1 + xn−2 = 4n + 1. (1) Giải. Hệ thức đệ quy tuyến tính thuần nhất tương ứng là: 2xn − 3xn−1 + xn−2 = 0 (2) Phương trình đặc trưng của (2) là: 2λ2 − 3λ + 1 = 0 (∗) có hai nghiệm thực là λ1 = 1 và λ2 = 1/2. Do đó nghiệm tổng quát của (2) là: 1n x = C + C n 1 2 2 Bây giờ ta tìm một nghiệm riêng của (1). Vế phải của (1) là n fn = 4n + 1 có dạng β Pr(n) với β = 1 và Pr(n) là đa thức bậc r = 1. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 52/62
  53. Vì β = 1 là nghiệm đơn của phương trình đặc trưng (∗) nên (1) có một nghiệm riêng dạng: xn = n(an + b) (4) Thế (4) vào (1) ta được: 2n(an + b) − 3(n − 1)[a(n − 1) + b] + (n − 2)[a(n − 2) + b] = 4n + 1. Cho n lần lượt nhận hai giá trị n = 0; n = 1 ta được hệ:  a + b = 1; 3a + b = 5. Giải hệ trên ta được a = 2; b = −1. Thế vào (4) ta tìm được một nghiệm riêng của (1) là: xn = n(2n − 1) (5) Từ (3) và (5) ta suy ra nghiệm tổng quát của (1) là: 1n x = C + C + n(2n − 1) n 1 2 2 lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 53/62
  54.  x − 6x + 9x = (18n + 12)3n; Ví dụ. Tìm nghiệm của n+1 n n−1 (1) x0 = 2; x1 = 0. Giải. Hệ thức đệ quy tuyến tính thuần nhất tương ứng là: xn+1 − 6xn + 9xn−1 = 0 (2) Phương trình đặc trưng của (2) là: λ2 − 6λ + 9 = 0 (∗) có nghiệm kép là λ0 = 3. Do đó nghiệm tổng quát của (2) là: n xn = (C1 + nC2)3 (3) Bây giờ ta tìm một nghiệm riêng của (1). Vế phải của (1) là n n fn = (18n + 12)3 có dạng β Pr(n) với β = 3 và Pr(n) là đa thức bậc r = 1. Vì β = 3 là nghiệm kép của phương trình đặc trưng (∗) nên (1) có một nghiệm riêng dạng: 2 n xn = n 3 (an + b) (4) Thế (4) vào (1) ta được: lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 54/62
  55. (n + 1)23n+1[a(n + 1) + b] − 6n23n(an + b)+ 9(n − 1)23n−1[a(n − 1) + b] = (18n + 12)3n. Cho n lần lượt nhận hai giá trị n = 0; n = 1 ta được hệ:  6b = 12; 54a + 18b = 90. Giải hệ trên ta được a = 1; b = 2. Thế vào (4) ta tìm được một nghiệm riêng của (1) là: 2 n xn = n (n + 2)3 (5) Từ (3) và (5) ta suy ra nghiệm tổng quát của (1) là: n 2 n xn = (C1 + nC2)3 + n (n + 2)3 (6) Thay điều kiện x0 = 2 và x1 = 0 vào (6) ta được  C1 = 2 3C1 + 3C2 + 9 = 0. Từ đó ta có C1 = 2 và C2 = −5. Thế vào (6) ta được n 2 n n 3 2 xn = (2 − 5n)3 + n (n + 2)3 = 3 (n + 2n − 5n + 2) lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 55/62
  56. Ví dụ. Tìm nghiệm của hệ thức đệ quy n−2 n xn − 4xn−1 + 3xn−2 = 20 + (2 − n)2 + 3 · 4 (1) Giải. Hệ thức đệ quy tuyến tính thuần nhất tương ứng là: xn − 4xn−1 + 3xn−2 = 0 (2) Phương trình đặc trưng của (2) là: λ2 − 4λ + 3 = 0 (∗) có hai nghiệm thực là λ1 = 1 và λ2 = 3. Do đó nghiệm tổng quát của (2) là: n xn = C1 + C2 3 (3) Bây giờ ta tìm một nghiệm riêng của (1). Vế phải của (1) là n−2 n fn = 20 + (2 − n)2 + 3 · 4 thuộc Dạng 2. Ta xét các hệ thức đệ quy sau: lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 56/62
  57. xn − 4xn−1 + 3xn−2 = 20 (1a) n−2 xn − 4xn−1 + 3xn−2 = (2 − n)2 (1b) n xn − 4xn−1 + 3xn−2 = 3 · 4 (1c) Bằng cách giải tương tự như Dạng 1, ta có các nghiệm riêng của (1a) là xn1 = −10n n (1b) là xn2 = n2 n+2 (1c) là xn3 = 4 Như vậy, (1) có nghiệm riêng là: n n+2 xn = −10n + n2 + 4 (4) Từ (3) và (4), ta suy ra nghiệm tổng quát của (1) là n n n+2 xn = C1 + C2 3 − 10n + n2 + 4 lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 57/62
  58. Ví dụ. Với n ≥ 1, đặt n X k sn = k(k + 1)2 . k=1 Tính tổng sn theo n bằng cách thiết lập một hệ thức đệ quy có điều kiện đầu và tìm nghiệm của hệ thức đệ quy đó.  n 2 sn − sn−1 = 2 (n + n) n 2 Đáp án. ; sn = −4 + 2 (2n − 2n + 4) s1 = 4. Ví dụ. Cho x0 = 1 và x1 = 2. Tìm nghiệm của hệ thức đệ quy xn+1 − 3xn + 2xn−1 = n, với n ≥ 1. 1 3 Đáp án. x = 3 · 2n − n2 − n − 2 n 2 2 Ví dụ.(tự làm) Gọi xn là số chuỗi bit có chiều dài n mà không có 2 bit 0 đứng liền nhau. Hãy lập hệ thức đệ quy của xn và tìm xn. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 58/62
  59. Ví dụ.(tự làm) a) Tìm nghiệm tổng quát của hệ thức đệ quy: an = 6an−1 − 9an−2. b) Tìm một nghiệm riêng của hệ thức đệ quy sau n−1 an = 6an−1 − 9an−2 + (18n − 6)3 . c) Tìm nghiệm thỏa điều kiện đầu: a0 = 2, a1 = 9 của hệ thức đệ quy: n+1 an = 6an−1 − 9an−2 + n3 . n 2 n Đáp án. a) xn = 3 (C1 + C2 · n) b) xn = n 3 (n + 2) 1 3  c) x = 3n n3 + n2 − n + 2 n 2 2 Ví dụ.(tự làm) Cho x0 = 1 và x1 = 6. Tìm nghiệm của hệ thức đệ quy xn − 4xn−1 + 8xn−2 = 0, với n ≥ 2. lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 59/62
  60. √  nπ nπ  Đáp án. x = (2 2)n cos + 2 sin n 4 4 Ví dụ.(tự làm) a) Tìm nghiệm tổng quát của hệ thức đệ quy: xn − xn−1 − 2xn−2 = 0 n−1 b) Tìm nghiệm của hệ thức đệ quy: xn − xn−1 − 2xn−2 = (6n − 5)2 thỏa điều kiện đầu x0 = 7, x1 = 4. n n n n 2 Đáp án. a) xn = C1 (−1) + C2 2 b) xn = 4 · (−1) + 2 (n + 3) Ví dụ.(tự làm) a) Tìm nghiệm tổng quát của hệ thức đệ quy: an = an−1 + 6an−2. b) Tìm nghiệm thỏa điều kiện đầu a0 = 8, a1 = 5 của hệ thức đệ quy: n n−1 an = an−1 + 6an−2 + 10n(−2) − 3(−2) n Đáp án. a) an = C1 · (−2)n + C2 · 3 n n 2 b) an = 7 · 3 + (−2) (2n + 5n + 1) lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 60/62
  61. Bài tập. Giải các hệ thức đệ quy sau  x + 4x − 5x = 12n + 8; a) n n−1 n−2 x0 = 0, x1 = −5.  2x + 5x + 2x = (35n + 51)3n; b) n+2 n+1 n x0 = 3, x1 = 0.  x − 2x + x = 2; c) n+2 n+1 n x0 = 1, x1 = 0.  2x − 5x + 2x = −n2 − 2n + 3; d) n n−1 n−2 x0 = 1, x1 = 3.  x − 16x + 64x = 128 · 8n; e) n+2 n+1 n x0 = 2, x1 = 32.  x − 8x + 15x = 2 · 5n+1; f) n+2 n+1 n x0 = −1, x1 = −2. Xem đáp án ở slide kế tiếp lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 61/62
  62. Đáp án. 5 5 a) x = − + (−5)n + n2 + 4n n 3 3  1n b) x = 2 − + (−2)n + 3nn n 2 2 c) xn = n − 2n + 1 n 2 d) xn = −3 · 2 + n + 4n + 4 n 2 e) xn = 8 (n + n + 2) n n f) xn = 3 + 5 (n − 2) lvluyen@hcmus.edu.vn Chương 3. Phép đếm và hệ thức đệ quy 3/12/2015 62/62