›
›

Ch2_phep_dem_348_102290_20180619_111318

pdf 66 trang hapham 2670
Download
Bạn đang xem 20 trang mẫu của tài liệu "Ch2_phep_dem_348_102290_20180619_111318", để 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:

  • pdfch2_phep_dem_348_102290.pdf

Nội dung text: Ch2_phep_dem_348_102290_20180619_111318

  1. ChươngLOGO 2 Lê Văn Luyện email: lvluyen@yahoo.com TỐN RỜI RẠC www.math.hcmus.edu.vn/~lvluyen/trr
  2. Phép đếm Chương II: PHÉP ĐẾM - Các nguyên lý - Giải tích tổ hợp - Hốn vị lặp, tổ hợp lặp - Hệ thức đệ qui
  3. Phép đếm I. Các nguyên lý 1. Nguyên lý cộng Giả sử để làm cơng việc A 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 1 cái áo thì An cĩ mấy cách
  4. Phép đếm I. Các nguyên lý 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ụ: A B C Cĩ 3.2 =6 con đường đi từ A đến C
  5. Phép đếm I. Các nguyên lý Ví dụ: Cho tập X ={1,2,3,4,5,0} Hỏi cĩ bao nhiêu số tự nhiên cĩ 3 chữ số khác nhau mà chia hết cho 2 Giải. Gọi số cĩ 3 chữ số là abc TH1 . c=0. Khi đĩ c cĩ 1 cách chọn a cĩ 5 cách chọn ( a X\{0} ) TH1 cĩ 1.4.5 =20 b cĩ 4 cách chọn ( b X\{a, 0} ) TH2 . c≠0. Khi đĩ c cĩ 2 cách chọn a cĩ 4 cách chọn ( a X\{c, 0} ) TH2 cĩ 2.4.4 =32 b cĩ 4 cách chọn ( b X\{a, c} ) Vậy cĩ 20+32 =52
  6. Phép đếm I. Các nguyên lý 3. Nguyên lý chuồng bồ câu (Derichlet) Gọi x là số nguyên nhỏ nhất lớn hơn hay bằng x. Giả sử cĩ n chim bồ câu ở trong k chuồng. Khi đĩ tồn tại ít nhất một chuồng chứa từ nk/ bồ câu trở lên. Ví dụ. 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 - Trong 1 nhĩm cĩ 367 người thì ít nhất cĩ 2 người sinh cùng ngày
  7. Phép đếm I. Các nguyên lý Ví dụ. Cho tập X ={1,2,3,4,5,6,7,8,9}. Lấy A là tập hợp con của X gồm 6 phần tử. Khi đĩ trong A sẽ cĩ hai phần tử cĩ tổng bằng 10. Giải. Ta lập các chuồng như sau: {1,9} {2,8} {3,7} {4,6} {5} Do A cĩ 6 phần tử nên trong 6 phần tử đĩ sẽ cĩ 2 phần tử trong 1 chuồng. Suy ra đpcm
  8. Phép đếm I. Các nguyên lý 4. Nguyên lý bù trừ. Cho A và B là hai tập hữu hạn. Khi đĩ |A  B|= |A|+|B| - |A  B| A A  B B
  9. Cơ sở Logic I. Các nguyên lý C A  C BC A  B  C A B A  B |A  B  C|=?
  10. Phép đếm I. Các nguyên lý Ví dụ. Trong một lớp ngoại ngữ Anh Pháp. Cĩ 24 HS học Tiếng Pháp, 26 học sinh học Tiếng Anh. 15 học sinh học Tiếng Anh và Tiếng Pháp. Hỏi lớp cĩ bao nhiêu người Giải. Gọi A là những học sinh học Tiếng Pháp B là những học sinh học Tiếng Anh Khi đĩ. Số học sinh của lớp là |A  B |. Theo nguyên lý bù trừ ta cĩ |A  B|= |A|+|B| - |A  B|=24+26-15=35
  11. Phép đếm II. Giải tích tổ hợp 1. Hố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 hốn vị của n phần tử. Số các hố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ụ. Cho A ={a,b,c}. Khi đĩ A cĩ các hốn vị sau abc,acb, bac,bca, cab,cba
  12. Phép đếm Ví dụ. Nếu A là tập hợp n phần tử thì số song ánh từ A vào A là n! 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 5!
  13. Phép đếm II. Giải tích tổ hợp 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ử. k Số các chỉnh hợp chập k của n ký hiệu là An - Cơng thức n! Ak n nk ! Ví dụ. Cho X ={abc}. Khi đĩ X cĩ các chỉnh hợp chập 2 của 3 là: ab, ba, ac, ca, bc, cb.
  14. Phép đếm II. Giải tích tổ hợp Ví dụ. Cĩ bao nhiêu số tự nhiên gồm 3 chữ số được tạo thành từ 1,2,3,4,5,6. 3 Kết quả: A6
  15. Phép đếm II. Giải tích tổ hợp 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ử. k n Số tổ hợp chập k của n phần tử được kí hiệu là C hay n k n! C k n k!! n k n k k CCCk k 1 k Tính chất CCnn n n n 1
  16. Phép đếm II. Giải tích tổ hợp 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} Một lớp cĩ 30 học sinh. Hỏi cĩ bao nhiêu cách chọn 10 bạn 10 - Số cách chọn là tổ hợp chập 10 của 30. C30
  17. Phép đếm III. Hốn vị lặp, tổ hợp lặp 1. Hốn vị lặp Định nghĩa. Cho n đối tượng trong đĩ cĩ ni đối tượng loại i giống hệt nhau (i =1,2, ,k ; 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 hốn vị lặp của n. Số hốn vị của n đối tượng, trong đĩ cĩ n1 đối tượng giống nhau thuộc loại 1, n! n2 đối tượng giống nhau thuộc loại 2, , n12! n ! nk ! nk đối tượng giống nhau thuộc loại k, là
  18. Phép đếm II. Giải tích tổ hợ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ừ 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!
  19. Phép đếm III. Hốn vị lặp, tổ hợp lặp 2. Tổ hợp lặp Đị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 Số các tổ hợp lặp chập k của n được ký hiệu là k Kn kk KCn n k 1
  20. Phép đếm III. Hốn vị lặp, 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. Ta cĩ mỗi cách chọn là mỗi tổ hợp lặp chập 2 của 3. Cụ thể AA, AB, AC, BB, BC, CC 2 2 2 KCC3 3 2 1 4 6
  21. Phép đếm Hệ quả. Số nghiệm nguyên khơng âm (x1,x2, ,xn) (mỗi xi đều nguyên khơng âm) của phương trình x1+ x2+ + xn = k là kk KCn n k 1 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 kk KCn n k 1
  22. Phép đếm III. Hốn vị lặp, tổ hợp lặp Ví dụ. Tìm số nghiệm nguyên khơng âm của phương trình x1+ x2 + x3 + x4 = 20 (1) Thỏa điều kiện x1 3; x2 2; x3 > 4 ( ). Giải. Ta viết điều kiện đã cho thành x1 3; x2 2; x3 5. Xét các điều kiện sau: x2 2; x3 5 ( ) x1 4; x2 2; x3 5 ( ) 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 (1) thỏa các điều kiện ( ), ( ), ( ). Ta cĩ:
  23. Phép đếm III. Hốn vị lặp, tổ hợp lặp p = q – r. Trước hết ta tìm q. Đặt x1’ = x1; x2’ = x2 – 2; x3’ = x3 - 5; x4’ = x4 Phương trình (1) trở thành x1’+ x2’ + x3’ + x4’ = 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)
  24. Phép đếm III. Hốn vị lặp, tổ hợp lặp 13 13 13 Số nghiệm đĩ là KCC 4 4 13 1 . 16 13 Vậy qC 16 . 9 9 9 Lý luận tương tự, ta cĩ r K 4 C . 4 9 1 C 12 13 9 p q r C16 C 12 560 220 340. Suy ra. 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
  25. Phép đếm III. Hốn vị lặp, tổ hợp lặp 13 13 13 Số nghiệm đĩ là KCC 4 4 13 1 . 16 13 Vậy qC 16 . 9 9 9 Lý luận tương tự, ta cĩ r K 4 C . 4 9 1 C 12 13 9 p q r C16 C 12 560 220 340. Suy ra. 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
  26. Hệ thức đệ qui Tháp Hà Nội A B C
  27. Phép đếm Tháp Hà Nội Gọi xn là số lần duy chuyển đĩa trong trường hợp cĩ n đĩa. Khi đĩ ta cĩ xxnn 2 1 1; x1 1. n  xn 21
  28. Phép đếm IV. Hệ thức đệ qui 1. Định nghĩa Một hệ thức đệ qui tuyến tính cấp k là một hệ thức cĩ dạng: a0xn + a1xn-1 + akxn-k = fn (1) trong đĩ a0 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 đệ qui tuyến tính thuần nhất cấp k.
  29. Phép đếm IV. Hệ thức đệ qui Ví dụ 2 2xn 5 x n 12 2 x n n 2 n 3 nn 2 xn 3 x n 12 2 x n 20 n 2 3 n 2xn 21 5 x n 2 x n (35 n 51)3 xn 21 20 x n x n
  30. Phép đếm IV. Hệ thức đệ qui a0xn + a1xn-1 + akxn-k = fn (1) 2. Nghiệm tổng quát và nghiệm riêng. 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 hồn tồ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)
  31. Phép đếm IV. Hệ thức đệ qui 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 đệ qui là đi tìm nghiệm tổng quát của nĩ; nhưng nếu hệ thức đệ qui 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 đĩ.
  32. 2xn 3 x n 12 x n 0 Phép đếm IV. Hệ thức đệ qui Ví dụ. n 3 2xx 3 0 cĩ nghiệm tổng quát xCn nn 1 2 cĩ nghiệm tổng quát 2xn 3 x n 12 x n 0 n 1 xn C 1 C 2 2
  33. Phép đếm IV. Hệ thức đệ qui 3. Một số ví dụ Ví dụ 1. 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 một hệ thức đệ qui cho 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:
  34. Phép đếm IV. Hệ thức đệ qui - 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 trong trường hợp này 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 trường hợp này 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 hay xn - xn-1 - xn-2 = 0
  35. 2xn 3 x n 12 x n 0 Phép đếm IV. Hệ thức đệ qui xn - xn-1 - xn-2 = 0 Vậy ta cĩ hệ thức đệ qui tuyến tính thuần nhất cấp 2: xn x n 12 x n 0; xx12 1, 2.
  36. 2xn 3 x n 12 x n 0 Phép đếm IV. Hệ thức đệ qui Ví dụ 2. Tháp Hà Nội A B C
  37. Phép đếm IV. Hệ thức đệ qui Cĩ 3 cọc A, B, C và n đĩa (cĩ lỗ để đặt vào cọc) 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 một hệ thức đệ qui cho xn
  38. IV. Hệ thức đệ qui 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.
  39. Phép đếm IV. Hệ thức đệ qui Như vậy số lần chuyển tịan bộ n đĩa từ A sang C là: xn-1+ 1 + xn-1 = 2xn-1 + 1. Nghĩa là xn = 2xn-1 + 1, ta cĩ hệ thức đệ qui tuyến tính khơng thuần nhất cấp 1: xxnn 2 1 1; x1 1.
  40. Phép đếm IV. Hệ thức đệ qui 4. Hệ thức đệ qui tuyến tính thuần nhất Xét hệ thức đệ qui tuyến tính thuần nhất a0xn + a1xn-1 + + akxn-k = 0 (2) Phương trình đặc trưng của (2) 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à 0 = - a1/a0. Khi đĩ, (2) cĩ nghiệm tổng quát là: n xCn 0
  41. Phép đếm IV. Hệ thức đệ qui Ví dụ. 2xxnn 3 1 0; . x0 1. Phương trình đặc trưng: 2 - 3 = 0 cĩ nghiệm là 0 = 3/2. n Nên hệ thức cĩ nghiệm tổng quát là: 3 xCn 2 Từ điều kiện x0 = 1, ta cĩ C=1. Vậy nghiệm của hệ thức là: n 3 xn 2
  42. Phép đếm IV. Hệ thức đệ qui a0xn + a1xn-1 + + akxn-k = 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: a) Nếu (*) cĩ hai nghiệm thực phân biệt 1 và 2 thì (2) cĩ nghiệm tổng quát là: nn xn C1 1 C 2 2 b) Nếu (*) cĩ nghiệm kép thực 0 thì (2) cĩ nghiệm tổng quát là: n xn () C1 nC 2 0
  43. Phép đếm IV. Hệ thức đệ qui Ví dụ. Giải các hệ thức đệ qui n a) 2 xn 3 x n 12 x n 0 1 xn C12 C 2 n 1 4xn 11 12 x n 9 x n 0; 3 b) xnn 3 xx01 2; 4. 2
  44. Phép đếm IV. Hệ thức đệ qui a) 2 xn 3 x n 12 x n 0 1 Phương trình đặc trưng của (1) 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 (1) là: n 1 xn C12 C 2
  45. Phép đếm IV. Hệ thức đệ qui 4xn 11 12 x n 9 x n 0 2 xx01 2; 4. Phương trình đặc trưng của (2) là: 42 - 12 + 9 = 0 cĩ nghiệm thực kép là 0 = 3/2. Do đĩ nghiệm tổng quát của (2) là: n 3 xn C12 nC 2
  46. Phép đếm IV. Hệ thức đệ qui 4. Hệ thức đệ qui tuyến tính khơng thuần nhất Xét hệ thức đệ qui tuyến tính khơng thuần nhất a0xn + a1xn-1 + + akxn-k = fn (1) Hệ thức đệ qui 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 Nghiệm tổng quát của (2) Nghiệm tổng quát của (1) = + Một nghiệm riêng của (1)
  47. Phép đếm IV. Hệ thức đệ qui Cách tìm một nghiệm riêng của (1) khi vế phải fn của (1) cĩ dạng đặc biệt như sau: 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 đã xét ở trên
  48. Phép đếm IV. Hệ thức đệ qui n Dạng 1. fn =  Pr(n). Cĩ ba trường hợp nhỏ xảy ra: TH 1.  khơng là nghiệm của phương trình đặc trưng TH 2.  là nghiệm đơn của phương trình đặc trưng TH 3.  là nghiệm kép của phương trình đặc trưng . TH1. 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)
  49. Phép đếm IV. Hệ thức đệ qui 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) r r-1 Chú ý Qr(n) = Arn + Ar-1n + + A0 là đa thức tổng quát 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.
  50. Phép đếm IV. Hệ thức đệ qui r r-1 Qr(n) = Arn + Ar-1n + + A0 Để 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. 50
  51. Phép đếm IV. Hệ thức đệ qui 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 đệ qui: a0xn + a1xn-1 + + akxn-k = fni Khi đó xn = xn1 + xn2+ + xns là một nghiệm riêng của (1)
  52. Phép đếm IV. Hệ thức đệ qui a) 2 xn 3 x n 12 x n 4 n 1. x 6 x 9 x (18 n 12)3n ; b) n 11 n n xx01 2; 0. 4x 12 x 9 x (2 n21 29 n 56)2n ; c) n 11 n n xx01 1; 2. nn 2 d) xn 4 x n 12 3 x n 20(2 n )2 3.4
  53. Phép đếm IV. Hệ thức đệ qui a) 2 xn 3 x n 12 x n 4 n 1 (1) Hệ thức đệ qui tuyến tính thuần nhất là: (2) 2xn 3 x n 12 x n 0 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à: n xn = C1 + C2(1/2)
  54. Phép đếm IV. Hệ thức đệ qui Bây giờ ta tìm một nghiệm riêng của (1). Vế phải của (1) là fn = 4n+1 có dạng Pr(n) là đa thức bậc r = 1 theo n. 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ệ: ab 1; 3ab 5.
  55. IV. Hệ thức đệ qui 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à: n xn = C1 + C2(1/2) + n(2n - 1)
  56. Ví Dụ 2 Phép đếm x 6 x 9 x (18 n 12)3n b) n 11 n n xx01 2; 0.
  57. Phép đếm IV. Hệ thức đệ qui
  58. Phép đếm 58
  59. 4x 12 x 9 x (2 n21 29 n 56)2n c) n 11 n n xx01 1; 2 Xét hệ thức đệ qui: 21n 4xn 11 12 x n 9 x n (2 n 29 n 56)2 1 Hệ thức đệ qui tuyến tính thuần nhất là: 4xn 11 12 x n 9 x n 0 2 Phương trình đặc trưng của (2) là: 42 - 12 + 9 = 0 (*) có một nghiệm thực kép là  = 3/2. Do đó nghiệm tổng quát của (2) là n xn = (C1 + nC2)(3/2) . (3) 59
  60. Phép đếm IV. Hệ thức đệ qui Bây giờ ta tìm một nghiệm riêng của (1). Vế phải của (1) là 21n fn (2 n 29 n 56)2 n có dạng  Pr(n) với  = 2 và Pr(n) là đa thức bậc r = 2 theo n. Vì  = 2 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: 2 n xn = (an + bn + c)2 (4) Thế (4) vào (1) ta được : 4[a(n+1)2 + b(n+1) + c)2n+1 -12[an2 + bn + c] 2n + 9[a(n-1)2 + b(n- 1) + c] 2n-1 = (2n2 + 29n +56)2n-1
  61. IV. Hệ thức đệ qui Cho n lần lượt nhận ba giá trị n = -1; n = 0; n = 1 ta được hệ: 3 1 29 3;abc 2 4 4 25 7 1 abc 28; 2 2 2 40a 8 b c 87. Giải hệ trên ta được a = 2; b = 1; c = -1. Thế vào (4) ta tìm được một nghiệm riêng của (1) là 2 n xn = (2n + n - 1)2 (5)
  62. IV. Hệ thức đệ qui Từ (3) và (5) ta suy ra nghiệm tổng quát của (1) là: n 2 n xn = (C1 + nC2)(3/2) + (2n + n -1) 2 (6) Thay điều kiện x0 = 1; x1 = -2 vào (6) ta được: C 1 1; 1 33 CC 4 2. 2212 Từ đó ta có: C1= 2; C2 = - 6. Thế vào (6) ta có nghiệm riêng cần tìm của (1) là: n 2 n xn = (2 - 6n)(3/2) + (2n + n -1) 2
  63. nn 2 d) xn 4 x n 12 3 x n 20(2 n )2 3.4 1 Hệ thức đệ qui tuyến tính thuần nhất là: xn 4 x n 12 3 x n 0 1 Phương trình đặc trưng của (2) là: 2 - 4 + 3 = 0 (*) có hai nghiệm thực phân biệt là 1 = 1; 2 = 3. Do đó nghiệm tổng quát của (2) là: n xn = C1 + C2. 3 . (3) 63
  64. IV. Hệ thức đệ qui Bây giờ ta tìm một nghiệm riêng của (1). Vế phải của (1) là nn 2 fnn 20 (2 )2 3.4 có dạng ở Trường hợp 4. Xét các hệ thức đệ qui: xn 4 x n 12 3 x n 20 1 n 2 xn 4 x n 12 3 x n (2 n )2 1 n xn 4 x n 12 3 x n 3.4 1 64
  65. Lý luận tượng tự như trên ta tìm được: Một nghiệm riêng của (1’) là xn1 = -10n n Một nghiệm riêng của (1’’) là xn2 = n2 n+2 Một nghiệm riêng của (1’’’) là xn3 = 4 Suy ra một nghiệm riêng của (1) là: n n+2 xn1 = -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 65
  66. Bài tập n xn 4 x n 12 5 x n 12 n 8; 2x 5 x 2 x (35 n 51)3 ; n 21 n n xx 0, 5. 01 xx01 3, 0. 2 xn 21 2 x n x n 2; 2x 5 x 2 x n 2 n 3; n n 12 n xx 1, 0. 01 xx01 1, 3. n n 1 x 16 x 64 x 128.8 ; xn 21 8 x n 15 x n 2.5 ; n 21 n n xx 1, 2. xx01 2, 32. 01