›
›

Giáo trình Toán rời rạc - Phần 1 - Chương 1: Bài toán đếm

ppt 176 trang hapham 1440
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Phần 1 - Chương 1: Bài toán đếm", để 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:

  • pptgiao_trinh_toan_roi_rac_phan_1_chuong_1_bai_toan_dem.ppt

Nội dung text: Giáo trình Toán rời rạc - Phần 1 - Chương 1: Bài toán đếm

  1. Phần thứ nhất LÝ THUYẾT TỔ HỢP Combinatorial Theory Hà Nội 2014 Toán rời rạc 1
  2. Nội dung Chương 0. Mở đầu Chương 1. Bài toán đếm Chương 2. Bài toán tồn tại Chương 3. Bài toán liệt kê tổ hợp Chương 4. Bài toán tối ưu tổ hợp Toán rời rạc 2
  3. Chương 1. BÀI TOÁN ĐẾM 1. Nguyên lý cộng và nguyên lý nhân 2. Các cấu hình tổ hợp cơ bản 3. Nguyên lý bù trừ 4. Công thức đệ qui 5. Hàm sinh Toán rời rạc 3
  4. 1. Nguyên lý cộng và Nguyên lý nhân ⚫ Đây là hai nguyên lý cơ bản của tổ hợp, được vận dụng rộng rãi vào việc giải quyết các bài toán đếm ⚫ Còn gọi là Qui tắc cộng và Qui tắc nhân (Sum Rule và Product Rule) Toán rời rạc 4
  5. 1.1. Nguyên lý cộng (The sum rule) ⚫ NÕu A vµ B lµ hai tËp hîp rêi nhau th× N(A  B) = N(A) + N(B). ⚫ Nguyªn lý céng ®îc më réng cho nhiÒu tËp con rêi nhau: NÕu A1, A2, , Ak lµ mét ph©n ho¹ch cña tËp hîp X th× N(X) = N(A1) + N(A2) + + N(Ak). ⚫ Mét trường hîp riªng hay dïng cña nguyªn lý céng: NÕu A lµ mét tÝnh chÊt cho trªn tËp X th× N(A) = N(X) - N(Ac). Toán rời rạc 5
  6. Nguyên lý cộng: Ví dụ ⚫ Ví dụ 2. Trong một đợt phổ biến đề tài tốt nghiệp, Ban chủ nhiệm Khoa công bố danh sách các đề tài bao gồm 80 đề tài về chủ đề "xây dựng hệ thông tin quản lý", 10 đề tài về chủ đề "thiết kế phần mềm dạy học" và 10 đề tài về chủ đề "Hệ chuyên gia". Hỏi một sinh viên có bao nhiêu khả năng lựa chọn đề tài? ⚫ Giải: Sinh viên có thể lựa chọn đề tài theo chủ đề thứ nhất bởi 80 cách, theo chủ đề thứ hai bởi 10 cách, theo chủ đề thứ ba bởi 10 cách. Vậy tất cả có 100 cách lựa chọn. Toán rời rạc 6
  7. Nguyên lý cộng: Ví dụ ⚫ VÝ dô 3. Hái r»ng gi¸ trÞ cña k sÏ lµ bao nhiªu sau khi ®o¹n chươnng tr×nh PASCAL sau ®ược thùc hiÖn? n1:=10; n2:=20; n3:=30; k:=0; for i1:= 1 to n1 do k:=k+1; for i2:= 1 to n2 do k:=k+1; for i3:= 1 to n3 do k:=k+1; ⚫ Gi¶i: §Çu tiªn gi¸ trÞ cña k ®îc g¸n b»ng 0. Cã 3 vßng lÆp for ®éc lËp. Sau mçi lÇn lÆp cña mçi mét trong 3 vßng for, gi¸ trÞ cña k t¨ng lªn 1. Vßng for thø nhÊt lÆp 10 lÇn, vßng for thø hai lÆp 20 lÇn, vßng for thø ba lÆp 30 lÇn. VËy, kÕt thóc 3 vßng lÆp for gi¸ trÞ cña k sÏ lµ 10+20+30= 60. Toán rời rạc 7
  8. Nguyên lý cộng: Ví dụ ⚫ Ví dụ 4: Có bao nhiêu xâu gồm 4 chữ số thập phân có đúng 3 ký tự là 9? ⚫ Giải: Xâu có thể chứa: • Ký tự khác 9 ở vị trí thứ nhất • hoặc ký tự khác 9 ở vị trí thứ hai • hoặc ký tự khác 9 ở vị trí thứ ba • hoặc ký tự khác 9 ở vị trí thứ tư • Ta có thể sử dụng qui tắc cộng • Đối với mỗi trường hợp, có 9 khả năng chọn ký tự khác với 9 (bất kể chữ số khác 9 nào trong 9 chữ số 0, 1, ,8) • Vậy, đáp số là 9+9+9+9 = 36 Toán rời rạc 8
  9. 1.2. Nguyên lý nhân The product rule ⚫ NÕu mçi thµnh phÇn ai cña bé cã thø tù k thµnh phÇn (a1, a2, , ak) cã ni kh¶ n¨ng chän (i = 1, 2, , k), th× sè bé sÏ ®ược t¹o ra lµ tÝch sè cña c¸c kh¶ n¨ng nµy n1n2 nk. ⚫ Mét hÖ qu¶ trùc tiÕp cña nguyªn lý nh©n: N(A1 A2 Ak) = N(A1) N(A2) N(Ak), víi A1, A2, , Ak lµ nh÷ng tËp hîp nµo ®ã, nãi riªng: N(Ak) = [N(A)]k . Toán rời rạc 9
  10. 1.2. Nguyên lý nhân The product rule ⚫ Trong nhiÒu bµi to¸n ®Õm, chØ sau khi x©y dùng xong thµnh phÇn thø nhÊt ta míi biÕt c¸ch x©y dùng thµnh phÇn thø hai, sau khi x©y dùng xong hai thµnh phÇn ®Çu ta míi biÕt c¸ch x©y dùng thµnh phÇn thø ba, Trong trường hîp ®ã cã thÓ sö dông nguyªn lý nh©n tæng qu¸t: ⚫ Gi¶ sö ta x©y dùng bé cã thø tù k thµnh phÇn (a1, a2, , ak) theo tõng thµnh phÇn vµ • a1 cã thÓ chän bëi n1 c¸ch; • Sau khi a1 ®· chän, a2 cã thÓ chän bëi n2 c¸ch; • • Sau khi a1, a2, ,ak-1 ®· chän, ak cã thÓ chän bëi nk c¸ch; ⚫ ThÕ th× sè bé ®ược t¹o ra lµ tÝch sè n1n2 nk. Toán rời rạc 10
  11. Nguyên lý nhân: Ví dụ ⚫ VÝ dô 1. Tõ Hµ néi ®Õn HuÕ cã 3 c¸ch ®i: m¸y bay, « t«, tµu ho¶. Tõ HuÕ ®Õn Sµi gßn cã 4 c¸ch ®i: m¸y bay, « t«, tµu ho¶, tµu thuû. Hái tõ Hµ néi ®Õn Sµi gßn (qua HuÕ) cã bao nhiªu c¸ch ®i? ⚫ Gi¶i: Mçi c¸ch ®i tõ Hµ néi ®Õn Sµi gßn (qua HuÕ) ®îc xem gåm 2 chÆng: Hµ néi - HuÕ vµ HuÕ - Sµi gßn. Tõ ®ã, theo nguyªn lý nh©n, sè c¸ch ®i tõ Hµ néi ®Õn Sµi gßn lµ 3 4 = 12 c¸ch. Hà nội Huế Sài gòn Toán rời rạc 11
  12. Nguyên lý nhân: Ví dụ ⚫ VÝ dô 2. Hái r»ng gi¸ trÞ cña k sÏ lµ bao nhiªu sau khi ®o¹n chương tr×nh PASCAL sau ®ược thùc hiÖn? n1:=10; n2:=20; n3:=30; k:=0; for i1:=1 to n1 do for i2:=1 to n2 do for i3:=1 to n3 do k:=k+1; ⚫ Gi¶i: §Çu tiªn gi¸ trÞ cña k ®ược g¸n b»ng 0. Cã 3 vßng lÆp for lång nhau. Sau mçi lÇn lÆp cña vßng for, gi¸ trÞ cña k t¨ng lªn 1. Vßng for thø nhÊt lÆp 10 lÇn, vßng for thø hai lÆp 20 lÇn, vßng for thø ba lÆp 30 lÇn. VËy, theo nguyªn lý nh©n, kÕt thóc 3 vßng lÆp for lång nhau, gi¸ trÞ cña k sÏ lµ 10 20 30 = 6000. Toán rời rạc 12
  13. Nguyên lý nhân: Ví dụ ⚫ Ví dụ 3: Hỏi có bao nhiêu lá cờ gồm 3 vạch màu, màu của mỗi vạch lấy từ ba mầu xanh, đỏ, trắng sao cho: a) Không có hai vạch liên tiếp nào cùng màu b) Không có hai vạch nào cùng màu ⚫ Giải. Đánh số các vạch của lá cờ bởi 1, 2, 3 từ trên xuống. Trường hợp a) ⚫ Màu của vạch 1 có 3 cách chọn. ⚫ Sau khi màu của vạch 1 đã chọn, màu của vạch 2 có 2 cách chọn (không được chọn lại màu của vạch 1). ⚫ Sau khi màu của hai vạch 1, 2 đã chọn, màu của vạch 3 có 2 cách chọn (không được chọn lại màu của vạch 2). ⚫ Theo nguyên lý nhân số lá cờ cần đếm trong trường hợp a) là 3.2.2=12 Toán rời rạc 13
  14. Nguyên lý nhân: Ví dụ 3 (tiếp) Trường hợp b): ⚫ Màu của vạch 1 có 3 cách chọn. ⚫ Sau khi màu của vạch 1 đã chọn, màu của vạch 2 có 2 cách chọn (không được chọn lại màu của vạch 1). ⚫ Sau khi màu của hai vạch 1, 2 đã chọn, màu của vạch 3 có 1 cách chọn (không được chọn lại màu của vạch 1 và 2). ⚫ Theo nguyên lý nhân số lá cờ cần đếm trong trường hợp b) là 3.2.1=6 Toán rời rạc 14
  15. Nguyên lý nhân: Ví dụ Ví dụ 4. Có bao nhiêu xâu gồm 4 chữ số thập phân a) không chứa một chữ số nào hai lần? Chúng ta sẽ chọn chữ số vào lần lượt từng vị trí • Ký tự thứ nhất có 10 cách chọn • Ký tự thứ hai có 9 cách (không chọn lại chữ số đã chọn vào vị trí thứ nhât) • Ký tự thứ ba có 8 cách chọn • Ký tự thứ tư có 7 cách chọn Tổng cộng có 10*9*8*7 = 5040 xâu cần đếm. b) kết thúc bởi chữ số chẵn? Ba ký tự đầu tiên mỗi ký tự có 10 cách chọn Ký tự cuối cùng có 5 cách chọn Tổng cộng có 10*10*10*5 = 5000 xâu cần đếm. Toán rời rạc 15
  16. Các ví dụ phức tạp hơn ⚫ Khi nào sử dụng qui tắc cộng? ⚫ Khi nào sử dụng qui tắc nhân? ⚫ Ta có thể sử dụng phối hợp cả qui tắc cộng và qui tắc nhân ⚫ Bằng cách đó ta có thể giải được nhiều bài toán thú vị và phức tạp hơn Toán rời rạc 16
  17. Chụp ảnh đám cưới Xét bài toán: Có 10 người tham gia vào việc chụp ảnh kỷ niệm ở một đám cưới, trong đó có cô dâu và chú rể. Ta xét bức ảnh chỉ gồm 6 người trong họ. a) Có thể chụp bao nhiêu bức ảnh trong đó có mặt cô dâu? Qui tắc nhân: Xếp chỗ cho cô dâu VÀ sau đó xếp chỗ cho những nhân vật còn lại trong bức ảnh. Trước hết xếp chỗ cho cô dâu: Cô dâu có thể đứng ở 1 trong 6 vị trí Tiếp đến, xếp 5 nhân vật còn lại của bức ảnh nhờ sử dụng qui tắc nhân: Có 9 người để chọn nhân vật thứ hai, 8 người để chọn nhân vật thứ ba, Tổng cộng có 9*8*7*6*5 = 15120 cách xếp 5 nhân vật còn lại của bức ảnh. Qui tắc nhân cho ta 6 * 15120 = 90 720 bức ảnh Toán rời rạc 17
  18. Chụp ảnh đám cưới b) Có thể chụp bao nhiêu bức ảnh mà trong đó có mặt cả cô dâu lẫn chú rể? Qui tắc nhân: Xếp dâu/rể VÀ sau đó xếp những nhân vật còn lại trong bức ảnh Trước hết xếp dâu và rể • Cô dâu có thể xếp vào 1 trong 6 vị trí • Chú rể có thể xếp vào 1 trong 5 vị trí còn lại • Tổng cộng có 30 khả năng Tiếp theo, xếp chỗ cho 4 nhân vật còn lại trong bức ảnh theo qui tắc nhân • Có 8 người để chọn nhân vật thứ ba, 7 người để chọn nhân vật thứ tư, • Tổng cộng có 8*7*6*5 = 1680 Theo qui tắc nhân có 30 * 1680 = 50 400 bức ảnh Toán rời rạc 18
  19. Chụp ảnh đám cưới c) Có bao nhiêu bức ảnh mà trong đó có mặt chỉ một người trong cặp tân hôn? Qui tắc cộng: Chỉ xếp cô dâu • Qui tắc nhân: xếp cô dâu và sau đó xếp các nhân vật còn lại • Trước hết xếp cô dâu: Cô dâu có thể đứng ở một trong 6 vị trí • Tiếp đến, xếp những nhân vật khác theo qui tắc nhân: Có 8 người để chọn nhân vật thứ hai, 7 để chọn nhân vật thứ ba, v.v. (Ta không được chọn chú rể!) Tổng cộng = 8*7*6*5*4 = 6720 • Qui tắc nhân cho 6 * 6720 = 40 320 khả năng ⚫ hoặc chỉ xếp chú rể • Số lượng khả năng cũng giống như cô dâu: 40 320 Qui tắc cộng cho 40 320 + 40 320 = 80 640 khả năng Toán rời rạc 19
  20. Chụp ảnh đám cưới ⚫ Một cách khác để thu được lời giải câu c) c) Có bao nhiêu bức ảnh mà trong đó có mặt chỉ một người trong cặp tân hôn? • Tổng số bức ảnh trong đó có cô dâu (có hoặc không có chú rể): 90 720 • Theo kết quả phần (a) • Tổng số bức ảnh có mặt cả dâu lẫn rể: 50 400 • Theo kết quả phần (b) • Số bức ảnh chỉ có mặt cô dâu: 90 720 – 50 400 = 40 320 • Đó cũng là số bức ảnh chỉ có mặt chú rể • Tổng cộng = 40 320 + 40 320 = 80 640 Toán rời rạc 20
  21. Số lượng Mật khẩu Mỗi cá nhân sử dụng mạng máy tính đều có mật khẩu gồm từ 6 đến 8 ký tự, mỗi ký tự là chữ cái in hoa hoặc chữ số. Mật khẩu phải chứa ít nhất một chữ số. Có bao nhiêu mật khẩu khác nhau? ⚫ Theo qui tắc cộng, nếu P là số lượng mật khẩu và P6, P7, P8 là số lượng mật khẩu độ dài 6, 7, và 8, tương ứng, thì P = P6+P7+P8 Toán rời rạc 21
  22. Số lượng Mật khẩu P6 = số lượng mật khẩu gồm 6 ký tự chứa ít nhất một chữ số = (tổng số mật khẩu gồm 6 ký tự) trừ bớt (số mật khẩu gồm 6 ký tự không chứa chữ số) = (26+10)(26+10)(26+10)(26+10)(26+10) – (26)(26)(26)(26)(26)(26) = 366 – 266 = 1 867 866 560 Toán rời rạc 22
  23. Số lượng Mật khẩu Tương tự như vậy, ta có 7 7 P7 = 36 – 26 = 70 332 353 920 8 8 P8 = 36 – 26 = 2 612 282 842 880 P6 + P7 + P8 = 2 684 483 063 360 Chú ý: Nếu máy tính 2 GHz có thể thử 200 triệu mật khẩu trong một giây, thì trong thời gian bao nhiêu lâu có thể xác định được mật khẩu để thâm nhập hệ thống máy tính này? (2 684 483 063 360/200 000 000)/(60*60) giờ Gần 4 tiếng đồng hồ! Toán rời rạc 23
  24. Chương 1. BÀI TOÁN ĐẾM 1. Nguyên lý cộng và nguyên lý nhân 2. Các cấu hình tổ hợp cơ bản 3. Nguyên lý bù trừ 4. Công thức đệ qui 5. Hàm sinh Toán rời rạc 24
  25. 2. Các cấu hình tổ hợp cơ bản ⚫ Các cấu hình tổ hợp cơ bản là: • Chỉnh hợp lặp, • Chỉnh hợp không lặp, • Hoán vị, • Tổ hợp ⚫ Phép đếm các cấu hình tổ hợp cơ bản được sử dụng để giải các bài toán đếm phức tạp hơn ⚫ Giả sử X là tập n phần tử, mà không giảm tổng quát ta có thể coi X là tập gồm các số 1, 2, , n. Toán rời rạc 25
  26. Chỉnh hợp lặp ⚫ Định nghĩa. Ta gọi chỉnh hợp lặp chập m từ n phần tử của X là bộ có thứ tự gồm m thành phần, mỗi thành phần đều là phần tử của X. m ⚫ Ký hiệu số lượng chỉnh hợp lặp chập m từ n phần tử là An ⚫ Theo định nghĩa, một chỉnh hợp lặp chập m từ n phần tử của X có thể biểu diễn bởi (a1, a2, , am), ai X, i = 1, 2, , m. ⚫ Dễ thấy tập tất cả các chỉnh hợp lặp chập m từ n phần tử của X chính là Xm. Vì vậy, theo nguyên lý nhân ta có m m ⚫ Định lý 1. An = n . Toán rời rạc 26
  27. Chỉnh hợp lặp ⚫ VÝ dô 1. TÝnh sè ¸nh x¹ tõ tËp m phÇn tö U = {u1, u2, , um} vµo tËp n phÇn tö V. ⚫ Gi¶i: Mçi ¸nh x¹ f cÇn ®Õm ®ược x¸c ®Þnh bëi bé ¶nh (f(u1), f(u2), , f(um)), trong ®ã f(ui) V, i=1, 2, , m. Tõ ®ã nhËn ®îc sè cÇn t×m lµ nm. ⚫ VÝ dô 2. TÝnh sè d·y nhÞ ph©n ®é dµi n. ⚫ Gi¶i: Mçi d·y nhÞ ph©n ®é dµi n lµ mét bé gåm n thµnh phÇn, trong ®ã mçi thµnh phÇn chØ nhËn mét trong hai gi¸ trÞ (1 hoÆc 0). Tõ ®ã suy ra sè c¸c d·y nhÞ ph©n ®é dµi n lµ 2n. ⚫ Do mçi tËp con cña tËp n phÇn tö tương øng víi mét vect¬ ®Æc trưng lµ mét x©u nhÞ ph©n ®é dµi n, nªn ta cã ⚫ HÖ qu¶: Sè lîng tËp con cña tËp n phÇn tö lµ 2n. Toán rời rạc 27
  28. Chỉnh hợp lặp ⚫ Ví dụ 3. Cần phải phân bố 100 sinh viên vào 4 nhóm thực tập ACCESS, FOXPRO, EXCEL, LOTUS. Mỗi sinh viên phải tham gia vào đúng một nhóm và mỗi nhóm có thể nhận một số lượng không hạn chế sinh viên ⚫ Giải: 4100 hay 1004 ? ⚫ Mỗi cách phân bố cần tìm có thể biểu diễn bởi bộ có thứ tự gồm 100 thành phần (b1, , b100) trong đó bi {A, F, E, L} là nhóm thực tập của sinh viên thứ i. Từ đó suy ra số cách phân bố cần đếm là 4100. Toán rời rạc 28
  29. Chỉnh hợp không lặp ⚫ Định nghĩa. Ta gọi chỉnh hợp không lặp chập m từ n phần tử của X là bộ có thứ tự gồm m thành phần, mỗi thành phần đều là phần tử của X, các thành phần khác nhau từng đôi. ⚫ Ký hiệu số lượng chỉnh hợp không lặp chập m từ n phần tử m là Pn . Rõ ràng, để tồn tại chỉnh hợp không lặp, thì m n. ⚫ Theo định nghĩa, một chỉnh hợp không lặp chập m từ n phần tử của X có thể biểu diễn bởi (a1, a2, , am), ai X, i = 1, 2, , m, ai aj, i j. ⚫ Việc đếm số lượng chỉnh hợp không lặp chập m từ n phần tử có thể thực hiện theo nguyên lý nhân. Ta có m n! ⚫ Định lý 2. P= n( n − 1) ( n − m + 1) = n (nm− )! Toán rời rạc 29
  30. Chỉnh hợp không lặp ⚫ VÝ dô 1. TÝnh sè đơn ¸nh tõ tËp m phÇn tö U = {u1, u2, , um} vµo tËp n phÇn tö V. ⚫ Gi¶i: Mçi đơn ¸nh f cÇn ®Õm ®îc x¸c ®Þnh bëi bé ¶nh (f(u1), f(u2), , f(um)), trong ®ã f(ui) V, i=1, 2, , m, f(ui) f(uj), i j. Tõ ®ã nhËn ®ược sè cÇn t×m lµ n(n-1) (n-m+1). ⚫ Ví dụ 2. Có bao nhiêu cách xếp 4 học sinh vào ngồi sau một cái bàn có 10 chỗ ngồi với điều kiện không được phép ngồi lòng. ⚫ Giải. Đánh số các học sinh từ 1 đến 4, các chỗ ngồi từ 1 đến 10. Mỗi cách xếp học sinh cần đếm có thể biểu diễn bởi bộ có thứ tự (g1, g2, g3, g4), trong đó gi {1, 2, , 10} là chỗ ngồi của học sinh i. Từ điều kiện đầu bài gi gj, i j; do đó mỗi cách xếp cần đếm là một chỉnh hợp 4 không lặp chập 4 từ 10. Vậy số cách xếp cần đếm là P10 = 10.9.8.7 = 5040. Toán rời rạc 30
  31. Chỉnh hợp không lặp ⚫ Chú ý: Để giải ví dụ 2 có thể lập luận trực tiếp theo nguyên lý nhân: ⚫ Ta lần lượt xếp các học sinh vào chỗ ngồi. • Học sinh thứ nhất có 10 cách xếp • Tiếp đến học sinh thứ hai có thể xếp vào 1 trong 9 chỗ còn lại, ⚫ Theo nguyên lý nhân có 10.9.8.7 cách xếp Toán rời rạc 31
  32. Hoán vị ⚫ Định nghĩa. Ta gọi hoán vị từ n phần tử của X là bộ có thứ tự gồm n thành phần, mỗi thành phần đều là phần tử của X, các thành phần khác nhau từng đôi. ⚫ Ký hiệu số lượng hoán vị từ n phần tử là Pn. ⚫ Theo định nghĩa, một hoán vị từ n phần tử của X có thể biểu diễn bởi (a1, a2, , an), ai X, i = 1, 2, , n, ai aj, i j. n ⚫ Rõ ràng Pn = Pn . Vì vậy, ta có n ⚫ Định lý 3. Pnn= P = n ( n − 1) 2 1 = n ! Toán rời rạc 32
  33. Hoán vị ⚫ VÝ dô 1. 6 người ®øng xÕp thµnh mét hµng ngang ®Ó chôp ¶nh. Hái cã thÓ bè trÝ bao nhiªu kiÓu? ⚫ Gi¶i: Mçi kiÓu ¶nh lµ mét ho¸n vÞ cña 6 ngêi. Tõ ®ã nhËn ®îc sè kiÓu ¶nh cã thÓ bè trÝ lµ 6! = 720. ⚫ VÝ dô 2. CÇn bè trÝ viÖc thùc hiÖn n chương tr×nh trªn mét m¸y vi tÝnh. Hái cã bao nhiªu c¸ch? ⚫ Gi¶i: §¸nh sè c¸c chương tr×nh bëi 1, 2, , n. Mçi c¸ch bè trÝ viÖc thùc hiÖn c¸c chương tr×nh trªn m¸y cã thÓ biÓu diÔn bëi mét ho¸n vÞ cña 1, 2, , n. Tõ ®ã suy ra sè c¸ch bè trÝ cÇn t×m lµ n! Toán rời rạc 33
  34. Hoán vị ⚫ Ví dụ 3. Có bao nhiêu song ánh từ tập n phần tử X vào chính nó? (Mỗi song ánh như vậy được gọi là một phép thế). ⚫ Giải. Mçi song ¸nh f cÇn ®Õm ®îc x¸c ®Þnh bëi bé ¶nh (f(u1), f(u2), , f(un)), trong ®ã f(ui) V, i=1, 2, , n, f(ui) f(uj), i j. Tõ ®ã nhËn ®îc sè cÇn t×m lµ n! ⚫ Ví dụ 4. Có bao nhiêu cách bố trí n thợ thực hiện n việc sao cho mỗi thợ thực hiện một việc và mỗi việc do đúng một thợ thực hiện ⚫ Giải: n! Toán rời rạc 34
  35. Tổ hợp ⚫ Định nghĩa. Ta gọi tổ hợp chập m từ n phần tử của X là bộ không có thứ tự gồm m thành phần, mỗi thành phần đều là phần tử của X, các thành phần khác nhau từng đôi. m ⚫ Ký hiệu số lượng tổ hợp chập m từ n phần tử là Cn (đôi khi ta sẽ sử dụng ký hiệu C(n,m)) ⚫ Theo định nghĩa, một tổ hợp chập m từ n phần tử của X có thể biểu diễn bởi bộ không có thứ tự {a1, a2, , am}, ai X, i = 1, 2, , m, ai aj, i j. ⚫ Với giả thiết X={1, 2, ,n}, một tổ hợp chập m từ n phần tử của X có thể biểu diễn bởi bộ có thứ tự (a1, a2, , am), ai X, i = 1, 2, , m, 1 a1 < a2 < <am n. Toán rời rạc 35
  36. Tổ hợp ⚫ ViÖc ®Õm c¸c tæ hîp cã khã kh¨n h¬n so víi việc đếm c¸c cÊu h×nh ®· tr×nh bµy, tuy nhiªn c¸ch ®Õm dưới ®©y cho biÕt c¸ch vËn dông c¸c nguyªn lý cïng víi c¸c kÕt qu¶ ®Õm ®· biÕt trong viÖc ®Õm mét cÊu h×nh míi. ⚫ XÐt tËp hîp tÊt c¶ c¸c chØnh hîp kh«ng lÆp chËp m cña n phÇn tö. Chia chóng thµnh nh÷ng líp sao cho hai chØnh hîp thuéc cïng mét líp chØ kh¸c nhau vÒ thø tù. Râ rµng c¸c líp nµy lµ mét ph©n ho¹ch trªn tËp ®ang xÐt vµ mçi líp như thÕ lµ t¬ng øng víi mét tæ hîp chËp m cña n. Sè chØnh hîp trong mçi líp lµ b»ng nhau vµ b»ng m! (sè ho¸n vÞ). Sè c¸c líp lµ b»ng sè tæ hîp chËp m cña n. Theo nguyªn lý céng, tÝch cña m! víi sè nµy lµ b»ng sè c¸c chØnh hîp kh«ng lÆp chËp m cña n, nghÜa lµ b»ng n(n- 1) (n-m+1). Tõ ®ã nhËn ®îc sè tæ hîp chËp m cña n lµ n( n− 1)( n − 2) ( n − m + 1) n ! hay m! m !( n− m )! Toán rời rạc 36
  37. Tổ hợp ⚫ Định lý 4. m n! n Cn = (cßn ký hiÖu lµ C ( n , m ) hay ) m!( n− m )! m ⚫ C(n,m) được gọi là hệ số tổ hợp. ⚫ Khi nhËn xÐt r»ng, gi¸ trÞ cña phÐp chia trong công thức của định lý 4 lµ mét sè nguyªn, ta nhËn ®îc mét kÕt qu¶ lý thó trong sè häc: TÝch cña k sè tù nhiªn liªn tiÕp bao giê còng chia hÕt cho k!. Toán rời rạc 37
  38. Tổ hợp ⚫ VÝ dô 1. Cã n ®éi bãng thi ®Êu vßng trßn. Hái ph¶i tæ chøc bao nhiªu trËn ®Êu? ⚫ Gi¶i: Cø 2 ®éi th× cã mét trËn. Tõ ®ã suy ra sè trËn ®Êu sÏ b»ng sè c¸ch chän 2 ®éi tõ n ®éi, nghÜa lµ b»ng C(n,2) = n(n-1)/2. ⚫ VÝ dô 2. Hái cã bao nhiªu giao ®iÓm cña c¸c ®ường chÐo cña mét ®a gi¸c låi n (n 4) ®Ønh n»m ë trong ®a gi¸c, nÕu biÕt r»ng kh«ng cã ba ®ường chÐo nµo ®ång quy t¹i ®iÓm ë trong ®a gi¸c? ⚫ Gi¶i: Cø 4 ®Ønh cña ®a gi¸c th× cã mét giao ®iÓm cña hai ®êng chÐo n»m trong ®a gi¸c. Tõ ®ã suy ra sè giao ®iÓm cÇn ®Õm lµ C(n,4) = n(n-1)(n-2)(n-3)/24. Toán rời rạc 38
  39. Bài toán chia kẹo Giả sử k và n là các số nguyên không âm. Hỏi phương trình sau đây có bao nhiêu nghiệm? t1+ t 2 + t 3 + + tk = n; t12,,, t tk Z+ Nội dung thực tế: Cần chia n cái kẹo cho k em bé B1, B2, ,Bk. Hỏi có bao nhiêu cách chia khác nhau? Toán rời rạc 39
  40. Bài toán chia kẹo • Cần thả n quả bóng giống nhau vào k phòng: Room1, Room2, , Roomk. Hỏi có bao nhiêu cách phân bổ khác nhau? • Nếu gọi tj là số lượng quả bóng thả vào Roomj, j = 1, 2, , n; thì vấn đề đặt ra dẫn về bài toán: Hỏi phương trình sau đây t1+ t 2 + t 3 + + tk = n có bao nhiêu nghiệm nguyên không âm? Toán rời rạc 40
  41. Giải bài toán chia kẹo • Xét dãy n+k-1 hộp. Tô k-1 hộp nào đó bởi màu xám; các hộp xám này sẽ là vách ngăn: D1, D2, D(k-1). • Ví dụ: với n=16, k=6 D1 D2 D3 D4 D5 • Thả n quả bóng vào n hộp còn lại, mỗi hộp 1 quả. Toán rời rạc 41
  42. Giải bài toán chia kẹo • Ví dụ, với n=16, k=6 D1 D2 D3 D4 D5 • Thả các quả bóng trước vách ngăn D1 vào Room1, các quả bóng giữa vách ngăn D1 và D2 vào Room2, vân vân, và cuối cùng các quả bóng sau D(k-1) vào Room(k). Room1 Room2 Room3 Room4 Room5 Room6 Toán rời rạc 42
  43. Giải bài toán chia kẹo • Như vậy, rõ ràng tồn tại tương ứng 1-1 giữa một cách phân bổ các quả bóng và một cách chọn k-1 hộp trong số n+k-1 hộp làm vách ngăn. • Do có tất cả k−1 Cnk+−1 cách chọn k-1 hộp từ n+k-1 hộp, nên đó cũng chính là số cách phân bổ n quả bóng vào k phòng, cũng chính là số cách chia n cái kẹo cho k em bé và cũng chính là số nghiệm nguyên không âm của phương trình: t1 +t2 +t3 ++tk = n Toán rời rạc 43
  44. Giải bài toán chia kẹo • Bài toán chia kẹo 2. Có bao nhiêu cách chia n cái kẹo cho k em bé mà trong đó mỗi em được ít nhất một cái? Hay tương đương: Hỏi phương trình sau đây : t1 + t2 + + tk = n. có bao nhiêu nghiệm nguyên dương? • Trước hết chia cho mỗi em 1 cái kẹo, n-k cái kẹo còn lại sẽ được chia cho k em bé. Bài toán dẫn về: Hỏi có bao nhiêu cách chia n-k cái kẹo cho k em bé. Sử dụng kết quả bài trước, ta có đáp số cần tìm là: k−1 Cn−1 Toán rời rạc 44
  45. Hệ số tổ hợp ⚫ Díi ®©y lµ mét vµi tÝnh chÊt cña c¸c hÖ sè tæ hîp: a) §èi xøng C(n,m) = C(n,n-m) b) §iÒu kiÖn ®Çu C(n,0) = 1; C(n,n) = 1, n 0 c) C«ng thøc ®Ö qui C(n,m) = C(n-1,m) + C(n-1, m-1), n > m > 0 ⚫ Điều kiện đầu suy trực tiếp từ định nghĩa của hệ số tổ hợp. C¸c tính chất còn lại có thể chứng minh nhờ sử dụng công thức trong định lý 4. Toán rời rạc 45
  46. Tổ hợp ⚫ Từ b) và c), ta có thể tính tất cả các hệ số tổ hợp chỉ bằng phép cộng. Các hệ số này được tính và viết lần lượt theo từng dòng (mỗi dòng ứng với một giá trị n=0, 1, ), trên mỗi dòng chúng được tính và viết lần lượt theo từng cột (mỗi cột ứng với một giá trị m = 0, 1, , n) theo bảng tam giác dưới đây: ⚫ B¶ng nµy ®îc gäi lµ tam gi¸c Pascal. Toán rời rạc 46
  47. Tổ hợp ⚫ Tam giác Pascal, n=8 Toán rời rạc 47
  48. Tổ hợp ⚫ C¸c hÖ sè tæ hîp cã liªn quan chÆt chÏ víi viÖc khai triÓn luü thõa cña mét nhÞ thøc. ThËt vËy, trong tÝch (x+y)n = (x+y) (x+y) . . . (x+y) hÖ sè cña xm yn-m sÏ lµ sè c¸ch chän m nh©n tö (x + y) mµ tõ ®ã ta lÊy ra x vµ ®ång thêi trong n-m nh©n tö cßn l¹i ta lÊy ra y, nghÜa lµ n0 nm m n− m n n ()x+ y=Cn y + + C n x y + + C n x n i i n− i = Cn x y i=0 C«ng thøc trên ®îc gäi lµ khai triÓn nhÞ thøc Newton vµ c¸c hÖ sè tæ hîp cßn ®îc gäi lµ c¸c hÖ sè nhÞ thøc. Toán rời rạc 48
  49. Tổ hợp ⚫ Trong c«ng thøc Niuton đặt y=1 ta có: n 0 1n−− 1 n 1 n n (1+ x ) =Cn + C nxx + + C n x + C n (*) ⚫ RÊt nhiÒu ®¼ng thøc vÒ hÖ sè tæ hîp ®îc suy tõ (*). Ch¼ng h¹n, trong (*) chän x =1 ta ®îc: C(n,0) + C(n,1) + + C(n,n) = 2n, tøc lµ nhËn ®îc kÕt qu¶ ®· biÕt: sè c¸c tËp con cña mét n-tËp b»ng 2n, cßn nÕu chän x = -1 ta ®îc: C(n,0) – C(n,1) + C(n,2) - +(-1)nC(n,n) = 0, tøc lµ sè c¸c tËp con ch½n (cã sè phÇn tö lµ sè ch½n) b»ng c¸c sè tËp con lÎ vµ b»ng 2n-1. ⚫ NhiÒu tÝnh chÊt cña hÖ sè tæ hîp cã thÓ thu ®îc tõ (*) b»ng c¸ch lÊy ®¹o hµm hoÆc tÝch ph©n theo x hai vÕ cña ®¼ng thøc nµy mét sè h÷u h¹n lÇn, sau ®ã g¸n cho x nh÷ng gi¸ trÞ cô thÓ. Toán rời rạc 49
  50. Chương 1. BÀI TOÁN ĐẾM 1. Nguyên lý cộng và nguyên lý nhân 2. Các cấu hình tổ hợp cơ bản 3. Nguyên lý bù trừ 4. Công thức đệ qui 5. Hàm sinh Toán rời rạc 50
  51. 3. Nguyên lý bù trừ (The inclusion-exclusion principle) 3.1. Phát biểu nguyên lý 3.2. Các ví dụ áp dụng Toán rời rạc 51
  52. 3.1. Phát biểu nguyên lý ⚫ Nguyên lý bù trừ trong trường hợp hai tập: |A  B| = |A| + |B| - |A  B| (1) • Giả sử A có 5 phần tử, B có 3 phần tử và có 1 phần tử thuộc vào cả A lẫn B • Khi đó số phần tử của hợp hai tập là 5+3-1 = 7, chứ không phải là 8 ⚫ CM: Toán rời rạc 52
  53. Nguyên lý bù trừ ⚫ Mở rộng cho trường hợp 3 tập: Giả sử A, B, C là ba tập bất kỳ. Khi đó: |AB C| = |(A B)C)| = |AB | + |C| − |(AB)C| = |A| +|B | + |C| − |AB| − |(AC)(BC)| = |A| +|B| + |C| − |AB| − |AC|− |BC)|+ |ABC)| Vậy |ABC| = |A|+|B|+ |C| − |AB| − |AC|− |BC)|+ |ABC)| (2) Có thể chứng minh bằng lập luận trực tiếp! Toán rời rạc 53
  54. Nguyên lý bù trừ |ABC| = |A|+|B|+ |C| − |AB| − |AC|− |BC)|+ |ABC)| (2) Có thể chứng minh bằng lập luận trực tiếp: ⚫ Trong tổng của ba số hạng đầu tiên các phần tử chung của A và B được tính hai lần, vì vậy phải trừ bớt đi một lần. Tương tự như vậy đối với các phần tử chung của A và C và các phần tử chung của B và C. ⚫ Thế nhưng, trừ như vậy là hơi quá, bởi vì những phần tử chung của cả ba tập A, B và C chưa được tính đến trong tổng của 6 số hạng đầu tiên. Vì vậy phải cộng bù lại. Toán rời rạc 54
  55. Nguyên lý bù trừ ⚫ §Þnh lý. Gi¶ sö A1, A2, , Am lµ c¸c tËp h÷u h¹n. Khi ®ã m−1 N(A1 A2  Am) = N1 − N2 + + (−1) Nm trong ®ã N= N( A  A   A ), k = 1,2, , m k i12 i ik 1 i12 i ik m (Nk lµ tæng sè phÇn tö cña tÊt c¶ c¸c tËp lµ giao cña k tËp lÊy tõ m tËp ®· cho, nãi riªng N1 = N(A1) + + N(Am), Nm = N(A1  A2   Am) ). Toán rời rạc 55
  56. Nguyên lý bù trừ ⚫ Chøng minh. ⚫ Chó ý r»ng, sè c¸c giao cña k tËp lÊy tõ m tËp b»ng C(m,k), k = 1,2, ,m. ⚫ §Ó chøng minh c«ng thøc cña nguyªn lý bï trõ, ta sÏ tÝnh xem mçi phÇn tö cña tËp A1  A2  . . .  Am ®îc ®Õm bao nhiªu lÇn trong vÕ ph¶i: ⚫ XÐt mét phÇn tö tuú ý a A1  A2  . . .  Am. Gi¶ sö a lµ phÇn tö cña k tËp trong sè m tËp ®· cho. Khi ®ã a ®îc ®Õm ë vÕ ph¶i cña c«ng thøc C(k,1) – C(k,2)+ + (-1)k-1C(k,k) lÇn. Do C(k,1) – C(k,2)+ + (-1)k-1C(k,k) = 1 – [C(k,0) – (C(k,1) – C(k,2)+ + (-1)k-1C(k,k))] = 1 – (1 – 1)k = 1 Tõ ®ã suy ra ®¼ng thøc cÇn chøng minh lµ ®óng Toán rời rạc 56
  57. Nguyên lý bù trừ ⚫ B©y giê ta ®ång nhÊt tËp Ak víi tÝnh chÊt Ak cho trªn mét tËp X nµo ®ã vµ ®Õm xem cã bao nhiªu phÇn tö cña X kh«ng tho¶ m·n bÊt cø mét tÝnh chÊt Ak nµo c¶. ⚫ GäiN lµ sè cÇn ®Õm. Do A1  A2  . . .  Am lµ tËp tÊt c¶ c¸c phÇn tö cña X tho¶ m·n Ýt nhÊt mét trong sè m tÝnh chÊt ®· cho, nªn ta cã: N = N(X )– N(A1  A2  . . .  Am) m = N(X ) – N1 + N2 - +(– 1) Nm trong ®ã Nk lµ tæng c¸c phÇn tö cña X tho¶ m·n k tÝnh chÊt lÊy tõ m tÝnh chÊt ®· cho. ⚫ C«ng thøc thu ®îc cho phÐp tÝnhN qua c¸c Nk trong trêng hîp c¸c sè nµy dÔ tÝnh to¸n h¬n. Toán rời rạc 57
  58. 3. Nguyên lý bù trừ (The inclusion-exclusion principle) 3.1. Phát biểu nguyên lý 3.2. Các ví dụ áp dụng Toán rời rạc 58
  59. Nguyên lý bù trừ ⚫ VÝ dô 1. Hái trong tËp X = {1, 2, , 10000} cã bao nhiªu sè kh«ng chia hÕt cho bÊt cø sè nµo trong c¸c sè 3, 4, 7? ⚫ Gi¶i. Gäi Ai ={ x X : x chia hÕt cho i} , i = 3, 4, 7. ⚫ Khi ®ã A3  A4  A7 lµ tËp c¸c sè trong X chia hÕt cho Ýt nhÊt mét trong 3 sè 3, 4, 7, suy ra sè lîng c¸c sè cÇn ®Õm sÏ lµ N(X) - N(A3  A4  A7) = 10000 – (N1 - N2 + N3). ⚫ Ta cã N1 = N(A3) + N(A4) + N(A7) = [10000/3] + [10000/4] + [10000/7] = 3333 + 2500 + 1428 =7261, Toán rời rạc 59
  60. Nguyên lý bù trừ N2 = N(A3  A4) + N(A3  A7) + N(A4  A7) = [10000/(3 4)] + [10000/(3 7)] + [10000/(4 7)] = 833 + 476 + 357 = 1666, N3 = N(A3  A4  A7) = [10000/(3 4 7) ] = 119, ë ®©y ký hiÖu [ r ] ®Ó chØ sè nguyªn lín nhÊt kh«ng vît qu¸ r. ⚫ Tõ ®ã sè lîng c¸c sè cÇn ®Õm lµ 10000 - 7261 + 1666 - 119 = 4286. Toán rời rạc 60
  61. Nguyên lý bù trừ ⚫ VÝ dô 2. Cã bao nhiªu x©u nhÞ ph©n ®é dµi 10 hoÆc lµ b¾t ®Çu bëi 00 hoÆc lµ kÕt thóc bëi 11? ⚫ Gi¶i. DÔ thÊy lµ sè x©u nhÞ ph©n ®é dµi 10 b¾t ®Çu bëi 00 lµ 28 = 256 vµ sè x©u nhÞ ph©n ®é dµi 10 kÕt thóc bëi 11 lµ 28 = 256. Ngoµi ra, sè x©u nhÞ ph©n ®é dµi 10 b¾t ®Çu bëi 00 vµ kÕt thóc bëi 11 lµ 26 = 64. Theo nguyªn lý bï trõ suy ra sè x©u nhÞ ph©n hoÆc b¾t ®Çu bëi 00 hoÆc kÕt thóc bëi 11 lµ 256 + 256 - 64 = 448. Toán rời rạc 61
  62. Nguyên lý bù trừ: Bài toán bỏ thư ⚫ Bµi to¸n bá thư. Cã n l¸ thư vµ n phong b× ghi s½n ®Þa chØ. Bá ngÉu nhiªn c¸c l¸ thư vµo c¸c phong b×. Hái x¸c suÊt ®Ó x¶y ra kh«ng mét l¸ thư nµo bá ®óng ®Þa chØ lµ bao nhiªu? ⚫ Gi¶i: §¸nh sè c¸c l¸ thư tõ 1 ®Õn n, c¸c phong b× tư¬ng øng víi chóng còng ®ưîc ®¸nh sè tõ 1 ®Õn n. Mçi c¸ch bá thư vµo phong b× cã thÓ biÓu diÔn bëi bé cã thø tù (p1, p2, , pn), trong ®ã pi lµ phong b× bá l¸ thø thø i. Tõ ®ã suy ra tån t¹i tư¬ng øng 1-1 gi÷a mét c¸ch bá thư vµo phong b× víi mét ho¸n vÞ cña n sè. VËy cã tÊt c¶ n! c¸ch bá thư. Toán rời rạc 62
  63. Nguyên lý bù trừ: Bài toán bỏ thư ⚫ VÊn ®Ò cßn l¹i lµ ®Õm sè c¸ch bá thư sao cho kh«ng cã l¸ thư nµo ®óng ®Þa chØ. ⚫ Gäi X lµ tËp hîp tÊt c¶ c¸c c¸ch bá thư vµ Ak lµ tÝnh chÊt l¸ th thø k bá ®óng ®Þa chØ. Khi ®ã, theo nguyªn lý bï trõ ta cã: n N = N(X ) – N1 + N2 – +(– 1) Nn trong ®ã N lµ sè cÇn t×m, N(X) = n!, cßn Nk lµ sè tÊt c¶ c¸c c¸ch bá thư sao cho cã k l¸ thư ®óng ®Þa chØ. Toán rời rạc 63
  64. Nguyên lý bù trừ: Bài toán bỏ thư ⚫ Chó ý lµ N= N( A  A   A ), k = 1,2, , n k i12 i ik 1 i12 i ik n ⚫ nghÜa lµ, Nk lµ tæng theo mäi c¸ch lÊy k l¸ thư tõ n l¸, víi mçi c¸ch lÊy k l¸ thư, cã (n-k)! c¸ch bá trong ®ã k l¸ nµy ®óng ®Þa chØ, ta nhËn ®ưîc: Nk = C(n, k).(n-k)! = n! / k! ⚫ Do ®ã 1 1 (−1)n N = n! (1 − + − + ) 1! 2! n! ⚫ VËy x¸c suÊt cÇn t×m lµ: 1 1 (−1)n 1 − + − + 1! 2! n! Toán rời rạc 64
  65. Số lượng toàn ánh Giả sử A={a1, a2, , am } và B={b1, b2, , bn }. Trong các phần trước ta đã chứng minh: • Số lượng ánh xạ từ A vào B là nm • Số lượng đơn ánh từ A vào B là n(n-1) (n-m+1) (n m). • Số lượng song ánh từ A vào B là n! (n=m). Bây giờ giả sử m n, ta cần đếm số lượng toàn ánh từ A vào B. Nhắc lại: Ánh xạ f từ A vào B là toàn ánh nếu với mỗi phần tử b thuộc B đều tìm được a thuộc A sao cho f(a)=b. (Do mỗi phần tử của A qua ánh xạ f được đặt tương ứng với đúng một phần tử của B, nên muốn có toàn ánh từ A vào B thì rõ ràng ta phải có m n.) 65
  66. Số lượng toàn ánh Ta muốn tất cả bi đều thuộc miền giá trị của f. Gọi P là tính chất "b không nằm trong miền i i A giá trị của f ". B f Khi đó ta cần đếm số ánh xạ không có bất cứ tính chất nào trong số các tính chất P1, , Pn. Ký hiệu: Pi = tập các ánh xạ từ A vào B có tính chất Pi , i = 1, 2, , n. Không tồn tại điểm không có mũi tên đi vào 66
  67. N= N( A  A   A ), k = 1,2, , n k i12 i ik 1 i12 i ik n Số lượng toàn ánh ⚫ Theo nguyên lý bù trừ số lượng toàn ánh cần đếm là: n N – N1 + N2 – +(–1) Nn. ⚫ Ta có: • N - số ánh xạ từ m-tập A vào n-tập B: nm m • Do N(Pi) - số ánh xạ không có bi trong miền giá trị, nên N(Pi) = (n-1) , m do đó N1 = C(n,1) (n-1) • Do N(PiPj) - số ánh xạ không có bi và bj trong miền giá trị, nên m m N(PiPj) = (n-2) , do đó N2 = C(n,2) (n-2) . • Tổng quát ta có: N( P P   P ) = ( n − k )m i12 i ik m dó đó Nk = C(n,k) (n - k) . ⚫ Từ đó ta có số lượng toàn ánh là: nm – C(n,1)(n-1)m + C(n,2)(n-2)m – + (-1)n-1C(n,n-1)1m. 67
  68. Số lượng toàn ánh ⚫ Ta viết gọn công thức nm – C(n,1)(n-1)m + C(n,2)(n-2)m – + (-1)n-1C(n,n-1)1m. dưới dạng sau đây: m12 m m n−−11 n m n− Cn( n − 1) + C n ( n − 2) − + ( − 1) C n 1 0mm 1 2m n− 1 n− 1 m n n m =Cn(n − 0) − C n ( n − 1) + C n ( n − 2) − + ( − 1) C n 1 + (− 1) C n 0 n k k m =( − 1)Cn ( n − k) k=0 68
  69. Chương 1. BÀI TOÁN ĐẾM 1. Nguyên lý cộng và nguyên lý nhân 2. Các cấu hình tổ hợp cơ bản 3. Nguyên lý bù trừ 4. Công thức đệ qui 5. Hàm sinh Toán rời rạc 69
  70. 4. Công thức đệ qui ⚫ Công thức đệ qui là công thức cho phép tính giá trị của các đại lượng theo từng bước, dựa vào các giá trị tính ở các bước trước và một số giá trị đầu. ⚫ Là một kỹ thuật quan trọng cho phép giải nhiều bài toán đếm Toán rời rạc 70
  71. 4. Công thức đệ qui ⚫ 4.1. Xây dựng công thức đệ qui ⚫ 4.2. Giải công thức đệ qui Toán rời rạc 71
  72. 4.1 Xây dựng công thức đệ qui ⚫ Ví dụ 1. Xây dựng công thức đệ qui cho C(n,k) - số lượng tập con k phần tử của tập n phần tử X. ⚫ Giải: ⚫ Theo định nghĩa C(n,0) = 1 và C(n,n) = 1 (1) ⚫ Giả sử n > k > 0, ta xây dựng công thức đệ qui để tính C(n,k). Cố định một phần tử x X. Phân tập các tập con k phần tử của X ra thành 2 tập: • A – tập các tập con k phần tử có chứa x • B – tập các tập con k phần tử không chứa x Toán rời rạc 72
  73. 4.1 Xây dựng công thức đệ qui ⚫ Rõ ràng A và B tạo thành phân hoạch của tập tất cả các tập con k phần tử của X. Do đó, theo nguyên lý cộng: C(n,k) = |A| + |B|. ⚫ Ta có: • Do mỗi tập con trong A có chứa x, nên k-1 phần tử còn lại của nó là một tập con k-1 phần tử của tập X \{x}, suy ra |A| = C(n-1,k-1) • Tương tự như vậy, |B| = C(n-1, k) ⚫ Vậy, C(n,k) = C(n-1, k-1) + C(n-1,k), n > k > 0 (2) Toán rời rạc 73
  74. 4.1 Xây dựng công thức đệ qui ⚫ Công thức đệ qui (2) cùng với điều kiện đầu (1) cho phép tính giá trị của C(n,k) với mọi giá trị của n và k. ⚫ Công thức đệ qui (2) cho phép viết hàm đệ qui sau đây để tính giá trị của C(n,k): function C(n,k: integer): longint; begin if (k=0) or (k=n) then C:=1 else C:= C(n-1,k-1) + C(n-1,k); end; Toán rời rạc 74
  75. 4.1 Xây dựng công thức đệ qui ⚫ Hàm vừa xây dựng không cho một cách tính hiệu quả. Thực vậy, nếu gọi C*(n,k) là số phép toán “gán giá trị” phải thực hiện bởi lệnh gọi hàm C(n,k), dễ thấy C*(n,0) =1; C*(n,n) = 1 C*(n,k) = C*(n-1, k-1) + C*(n-1,k)+1, n > k > 0 tức là C*(n,k) thoả mãn công thức đệ qui tương tự như hệ số tổ hợp C(n, k), do đó: C*(n,k)  n!/[k!(n-k)!] và giá trị này là rất lớn khi n lớn và k = n/2. ⚫ Dễ dàng xây dựng một hàm lặp để tính giá trị của C(n,k) một cách hiệu quả hơn. Toán rời rạc 75
  76. 4.1 Xây dựng công thức đệ qui ⚫ VÝ dô 2. Trªn mÆt ph¼ng, kÎ n ®êng th¼ng sao cho kh«ng cã 2 ®- êng nµo song song vµ 3 ®êng nµo ®ång quy. Hái mÆt ph¼ng ®îc chia thµnh mÊy phÇn ? ⚫ Gi¶i: Gäi sè phÇn mÆt ph¼ng ®îc chia bëi n ®êng th¼ng lµ Sn. Râ ràng S1 = 2, (3) ⚫ XÐt n > 1, ta t×m c«ng thøc ®Ö qui cho Sn. Toán rời rạc 76
  77. 4.1 Xây dựng công thức đệ qui ⚫ Gi¶ sö ®· kÎ n-1 ®êng th¼ng, khi ®ã mÆt ph¼ng ®îc chia ra lµm Sn-1 phÇn. B©y giê kÎ thªm ®êng th¼ng thø n. §êng th¼ng nµy c¾t n-1 ®êng th¼ng ®· vÏ t¹i n-1 giao ®iÓm. C¸c giao ®iÓm nµy chia ®êng th¼ng thø n ra lµm n phÇn, mçi phÇn nh vËy sÏ chia mét phÇn nµo ®ã sinh bëi n-1 ®êng th¼ng vÏ tríc ®ã ra lµm hai phÇn. Tõ ®ã suy ra, sau khi vÏ ®êng th¼ng thø n sè phÇn t¨ng thªm lµ n. Tõ ®ã nhËn ®îc c«ng thøc ®Ö qui Sn = Sn-1 + n, n 2 (4) Toán rời rạc 77
  78. 4.1 Xây dựng công thức đệ qui G3 phần 4 l1 G2 phần 3 G1 phần 2 phần 1 l4 l3 l2 Toán rời rạc 78
  79. 4.1 Xây dựng công thức đệ qui ⚫ §Ó t×m c«ng thøc trùc tiÕp, ta céng c¸c hÖ thøc Sk = Sk-1 + k víi k = 2, , n. S1 = 2 S2 = S1 + 2 S3 = S2 + 3 Sn-1= Sn-2 + (n-1) Sn = Sn-1 + n 2 Sn = 2 + 2 + 3 + +(n-1) + n = n(n+1)/2 + 1 = (n +n+2)/2 Toán rời rạc 79
  80. 4.1 Xây dựng công thức đệ qui ⚫ Ví dụ 3. Xây dựng công thức đệ qui cho fn là số chỉnh hợp lặp chập n từ hai phần tử 0, 1 (cũng chính là xâu nhị phân độ dài n) không chứa hai số 0 liền nhau. ⚫ Giải. Ta có f1 = 2; f2 = 3 Giả sử n > 2. Phân tập các chỉnh hợp cần đếm ra thành 2 tập: • A – tập các chỉnh hợp cần đếm chứa 1 ở vị trí đầu tiên; • B – tập các chỉnh hợp cần đếm chứa 0 ở vị trí đầu tiên; ⚫ Rõ ràng A và B tạo thành phân hoạch của tập tất cả các chỉnh hợp cần đếm. Toán rời rạc 80
  81. 4.1 Xây dựng công thức đệ qui ⚫ Do đó, theo nguyên lý cộng: fn = |A| + |B|. ⚫ Ta có: • Do mỗi chỉnh hợp trong A chứa 1 ở vị trí đầu tiên, nên n-1 phần tử còn lại sẽ tạo thành một chỉnh hợp cần đếm độ dài n-1, suy ra: |A| = fn-1 • Do mỗi chỉnh hợp trong B chứa 0 ở vị trí đầu tiên, nên vị trí thứ hai của nó phải là 1 còn n-2 phần tử còn lại sẽ tạo thành một chỉnh hợp cần đếm độ dài n-2, suy ra: |B| = fn-2 ⚫ Vậy, ta thu được công thức đệ qui f1 = 2; f2 = 3; fn = fn-1 + fn-2, n > 2 (5) Toán rời rạc 81
  82. 4.1 Xây dựng công thức đệ qui ⚫ Ví dụ 4. Xây dựng công thức đệ qui cho Qn là số lượng cách phủ lưới ô vuông kích thước 2 n bằng các quân bài domino. ⚫ Giải. Ta có Q1 = 1; Q2 = 2 (xem hình vẽ) ⚫ Giả sử n > 2. Phân tập các cách phủ cần đếm ra thành 2 tập: • A – tập các cách phủ trong đó ô ở góc trên trái được phủ bởi quân bài nằm đứng; • B – tập các cách phủ trong đó ô ở góc trên trái được phủ bởi quân bài nằm ngang. ⚫ Rõ ràng A và B tạo thành phân hoạch của tập tất cả các cách phủ cần đếm. Toán rời rạc 82
  83. 4.1 Xây dựng công thức đệ qui ⚫ Do đó, theo nguyên lý cộng: Qn = |A| + |B|. A ⚫ Ta có: |A| = Q • n-1 |B| = Q B • n-2 ⚫ Vậy, ta thu được công thức đệ qui Q1 = 1; Q2 = 2; Qn = Qn-1 + Qn-2, n > 2 (6) Toán rời rạc 83
  84. 4.1 Xây dựng công thức đệ qui ⚫ VÝ dô 5. (Bµi to¸n th¸p Hµ néi). Trß ch¬i th¸p Hµ néi ®îc tr×nh bµy nh sau: “Cã 3 cäc a, b, c. Trªn cäc a cã mét chång gåm n c¸i ®Üa ®êng kÝnh gi¶m dÇn tõ díi lªn trªn. CÇn ph¶i chuyÓn chång ®Üa tõ cäc a sang cäc c tu©n thñ qui t¾c: mçi lÇn chØ chuyÓn 1 ®Üa vµ chØ ®îc xÕp ®Üa cã ®êng kÝnh nhá h¬n lªn trªn ®Üa cã ®êng kÝnh lín h¬n. Trong qu¸ tr×nh chuyÓn ®îc phÐp dïng cäc b lµm cäc trung gian”. Bµi to¸n ®Æt ra lµ: Tìm công thức đệ qui cho hn là sè lÇn di chuyÓn ®Üa Ýt nhÊt cÇn thùc hiÖn ®Ó hoàn thành nhiÖm vô ®Æt ra trong trß ch¬i th¸p Hµ néi. Toán rời rạc 84
  85. 4.1 Xây dựng công thức đệ qui ⚫ Gi¶i: Râ rµng: h1 = 1. ⚫ Gi¶ sö n ≥ 2. ViÖc di chuyÓn ®Üa gåm c¸c bíc: (i) ChuyÓn n-1 ®Üa tõ cäc a ®Õn cäc b sö dông cäc c lµm trung gian. Bíc nµy ®îc thùc hiÖn nhê gi¶ thiÕt quy n¹p. (ii) ChuyÓn 1 ®Üa (®Üa víi ®êng kÝnh lín nhÊt) tõ cäc a ®Õn cäc c. (iii) ChuyÓn n-1 ®Üa tõ cäc b ®Õn cäc c (sö dông cäc a lµm trung gian). Bíc nµy ®îc thùc hiÖn nhê gi¶ thiÕt quy n¹p. Toán rời rạc 85
  86. 4.1 Xây dựng công thức đệ qui ⚫ Bíc (i) vµ (iii) ®ßi hái gi¶i bµi to¸n th¸p Hµ néi víi n-1 ®Üa, v× vËy sè lÇn di chuyÓn ®Üa Ýt nhÊt cÇn thùc hiÖn trong hai bíc nµy lµ 2hn-1. Do ®ã ta cã c«ng thøc ®Ö qui sau: hn = 2hn-1 + 1, n ≥ 2. ⚫ Sö dông c«ng thøc ®Ö qui vµ ®iÒu kiÖn ®Çu võa t×m ®îc ®èi víi hn ta cã thÓ dÔ dµng chøng minh b»ng qui n¹p lµ n hn = 2 – 1, n ≥ 1. Toán rời rạc 86
  87. 4.1 Xây dựng công thức đệ qui ⚫ Ta có thể tìm được công thức trực tiếp cho hn bằng phương pháp thế: hn = 2 hn−1 + 1 2 = 2 (2 hn−2 + 1) + 1 = 2 hn−2 + 2 + 1 2 3 2 = 2 (2 hn−3 + 1) + 2 + 1 = 2 hn−3 + 2 + 2 + 1 n−1 n−2 = 2 h1 + 2 + + 2 + 1 n−1 n−2 = 2 + 2 + + 2 + 1 (do h1 = 1) = 2n − 1 Toán rời rạc 87
  88. Tower of Hanoi: n=5 Cọc a Cọc c Cọc b Toán rời rạc 88
  89. 4. Công thức đệ qui ⚫ 4.1. Xây dựng công thức đệ qui ⚫ 4.2. Giải công thức đệ qui Toán rời rạc 89
  90. §4.2. Giải công thức đệ qui ⚫ Ta hiểu việc giải công thức đệ qui là việc tìm công thức dưới dạng hiện cho số hạng tổng quát của dãy số thoả mãn công thức đệ qui đã cho. ⚫ Chưa có phương pháp giải mọi công thức đệ qui. ⚫ Sẽ xét phương pháp giải công thức đệ qui tuyến tính thuần nhất hệ số hằng (sẽ viết tắt là CTĐQ TTTNHSH) Toán rời rạc 90
  91. §4.2. Giải công thức đệ qui ⚫ Định nghiã. Công thức đệ qui tuyến tính thuần nhất hệ số hằng bậc k là công thức đệ qui sau an = c1an−1 + + ckan−k, trong đó ci là các hằng số, và ck ≠ 0. ⚫ Dãy số thoả mãn công thức đã cho là xác định duy nhất nếu đòi hỏi nó thoả mãn k điều kiện đầu a0 = C0, a1 = C1, , ak-1 = Ck-1, trong đó C0, C1, , Ck-1 là các hằng số. Toán rời rạc 91
  92. ⚫ Ví dụ: 1) an = 4an-1 +2nan-3 2) hn = 2hn-1 + 1 2 3) bn = 5bn-2 + 2(bn-3) 4) qn = 3 qn-6 + qn-8 Fall 2006 Toán rời rạc 92
  93. Giải CTĐQ TTTNHSH n ⚫ Ta sẽ tìm nghiệm dưới dạng an = r , trong đó r là hằng số. n ⚫ Dãy số {an = r } thoả mãn CTĐQ đã cho nếu r thoả mãn phương trình: n n−1 n−k r = c1r + + ckr , hay (chuyển vế k k−1 k−n r − c1r − − ck = 0 và × với r ) ⚫ Phương trình cuối cùng được gọi là phương trình đặc trưng, còn nghiệm của nó sẽ được gọi là nghiệm đặc trưng của CTĐQ TTTNHSH. ⚫ Ta có thể sử dụng nghiệm đặc trưng để thu được công thức cho dãy số. Toán rời rạc 93
  94. Giải CTĐQ TTTNHSH ⚫ §Þnh lý 1. Cho c1, c2 lµ c¸c h»ng sè thùc. Gi¶ sö ph¬ng 2 tr×nh r - c1 r - c2 = 0 cã hai nghiÖm ph©n biÖt r1 vµ r2. Khi ®ã d·y sè {an} lµ nghiÖm cña c«ng thøc ®Ö qui an = c1 an-1 + c2 an-2 khi vµ chØ khi n n an = 1(r1) + 2(r2) (5) n = 0, 1, , trong ®ã 1 , 2 lµ c¸c h»ng sè. Toán rời rạc 94
  95. Giải CTĐQ TTTNHSH ⚫ Chøng minh. Tríc hÕt ta chøng minh r»ng nÕu r1 vµ r2 lµ hai nghiÖm ph©n biÖt cña ph¬ng tr×nh ®Æc trng, vµ 1 , 2 lµ c¸c h»ng sè, th× d·y sè {an} x¸c ®Þnh bëi c«ng thøc (5) lµ nghiÖm cña c«ng thøc ®Ö qui ®· cho. ⚫ Thùc vËy, do r1 vµ r2 lµ nghiÖm ®Æc trng nªn 2 r1 = c1 r1 + c2 , 2 r2 = c1 r2 + c2 Toán rời rạc 95
  96. Giải CTĐQ TTTNHSH ⚫ Tõ ®ã suy ra c1 an-1 + c2 an-2 n-1 n-1 n-2 n-2 = c1 ( 1 r1 + 2 r2 ) + c2 ( 1 r1 + 2 r2 ) n-2 n-2 = 1 r1 (c1 r1 + c2) + 2 r2 (c1 r2 + c2) n-2 2 n-2 2 = 1 r1 r1 + 2 r2 r2 n n = 1 r1 + 2 r2 = an . Toán rời rạc 96
  97. Giải CTĐQ TTTNHSH ⚫ B©y giê ta sÏ chØ ra r»ng nghiÖm {an} cña c«ng thøc ®Ö qui an = c1 an-1 + c2 an-2 lu«n cã d¹ng (5) víi 1, 2 nµo ®ã. ⚫ Thùc vËy, gi¶ sö {an} lµ nghiÖm cña c«ng thøc ®· cho víi ®iÒu kiÖn ®Çu a0 = C0 , a1 = C1, (6) ⚫ Ta chØ ra r»ng cã thÓ t×m ®îc c¸c sè 1 , 2 ®Ó cho (5) lµ nghiÖm cña hÖ thøc víi ®iÒu kiÖn ®Çu nµy. Toán rời rạc 97
  98. Giải CTĐQ TTTNHSH ⚫ Ta cã a0 = C0 = 1 + 2 , a1 = C1 = 1r1 + 2r2. ⚫ HÖ ph¬ng tr×nh tuyÕn tÝnh phô thuéc hai Èn 1, 2 nµy cã ®Þnh thøc lµ r2 – r1 0 (do r1 r2) cã nghiÖm duy nhÊt 1 = (C1 - C0r2 )/(r1 - r2), 2 = (C0 r1 - C1 )/(r1 - r2). ⚫ Víi nh÷ng gi¸ trÞ cña 1 , 2 võa t×m ®îc, d·y {an} x¸c ®Þnh theo (5) lµ nghiÖm cña hÖ thøc ®· cho víi ®iÒu kiÖn ®Çu (6). Do hÖ thøc ®· cho cïng víi ®iÒu kiÖn ®Çu (6) x¸c ®Þnh duy nhÊt mét d·y sè, nªn nghiÖm cña hÖ thøc ®îc cho bëi c«ng thøc (5). ⚫ §Þnh lý ®îc chøng minh. Toán rời rạc 98
  99. VÝ dô ⚫ D·y Fibonaci trong to¸n häc ®îc ®Þnh nghÜa b»ng hÖ thøc truy håi: Fn = Fn-1 + Fn-2, n 2, F0 = 0, F1 = 1. T×m c«ng thøc hiÖn cho Fn. ⚫ Gi¶i: Gi¶i ph¬ng tr×nh ®Æc trng: 2 Leonardo Fibonacci r - r - 1 = 0, 1170-1250 ta thu ®îc hai nghiÖm ®Æc trng 1+− 5 1 5 rr==; 1222 Toán rời rạc 99
  100. VÝ dô ⚫ Do ®ã c«ng thøc hiÖn cã d¹ng: F0= 1+ 2 = 0 n n F = r + r = 1 Fn = 1.(r1) + 2.(r2) 1 1 1 2 2 trong ®ã 1, 2 lµ c¸c h»ng sè cÇn x¸c ®Þnh tõ c¸c gi¸ trÞ ban ®Çu F0, F1. Gi¶i hÖ PTTT nµy, ta cã: 11 =; = − 1255 C«ng thøc Muavre vµ tõ ®ã thu ®îc nn 1 1+− 5 1 5 Fn= −, 0. n 5 ( 22) ( ) Toán rời rạc 100
  101. Great Pyramid at Gizeh Toán rời rạc 101
  102. a = 1.618 b a b Toán rời rạc 102
  103. Tỷ lệ giữa chiều cao và lưng Toán rời rạc 103
  104. Định nghĩa tỷ lệ vàng  (Euclid) ⚫ Tỷ lệ thu được khi chia đoạn thẳng ra 2 phần không bằng nhau sao cho tỷ lệ giữa đoạn thẳng đã cho và đoạn con lớn hơn là bằng tỷ lệ giữa đoạn lớn hơn và đoạn nhỏ hơn. C AC AB A B  = = AB BC AC  2 = 51+ BC  = AC AB BC 2  2 −  = − = = 1 BC BC BC 2 = 2 cos  −  −1 = 0 5 Toán rời rạc 104
  105. Toán rời rạc 105
  106. Trường hợp nghiệm kép ⚫ §Þnh lý 2. Cho c1, c2 lµ c¸c h»ng sè thùc, c2 0. Gi¶ sö ph¬ng 2 tr×nh r - c1 r - c2 = 0 cã nghiÖm kÐp r0. Khi ®ã d·y sè {an } lµ nghiÖm cña c«ng thøc ®Ö qui an = c1 an-1 + c2 an-2 khi vµ chØ khi n n an = 1r0 + 2nr0 n = 0, 1, , trong ®ã 1 , 2 lµ c¸c h»ng sè. Toán rời rạc 106
  107. Ví dụ ⚫ T×m nghiÖm cho c«ng thøc ®Ö qui an = 6 an-1 - 9 an-2 víi ®iÒu kiÖn ®Çu a0 = 1 vµ a1 = 6. ⚫ Gi¶i: PT§T r2 - 6 r + 9 = 0 cã nghiÖm kÐp r = 3. Do ®ã nghiÖm cña hÖ thøc cã d¹ng: n n an = 1 3 + 2 n 3 . ⚫ §Ó t×m 1, 2 , sö dông ®iÒu kiÖn ®Çu ta cã a0 = 1 = 1 , a1 = 6 = 1 . 3 + 2 . 3. ⚫ Gi¶i hÖ nµy ta t×m ®îc 1 = 1 vµ 2 = 1. Tõ ®ã nghiÖm cña hÖ thøc ®· cho lµ: n n an = 3 + n 3 . Toán rời rạc 107
  108. Trường hợp tổng quát ⚫ §Þnh lý 3. Cho c1, c2, , cn lµ c¸c sè thùc. Gi¶ sö ph¬ng tr×nh ®Æc trng k k-1 k-2 r - c1 r - c2 r - . . . - ck = 0 cã k nghiÖm ph©n biÖt r1, r2, , rk . Khi ®ã d·y sè {an} lµ nghiÖm cña c«ng thøc an = c1 an-1 + c2 an-2 + + ck an-k, khi vµ chØ khi n n n an = 1 r1 + 2 r2 + . . . + k rk víi n = 0, 1, 2, , trong ®ã 1, 2, , k lµ c¸c h»ng sè. Toán rời rạc 108
  109. Ví dụ ⚫ T×m nghiÖm cña công thức đệ qui an = 6 an-1 - 11 an-2 + 6 an-3 víi ®iÒu kiÖn ®Çu a0 = 2, a1 = 5, a2 = 15. ⚫ Gi¶i: Ph¬ng tr×nh ®Æc trng r3 - 6 r2 + 11 r - 6 = 0 cã 3 nghiÖm r1 = 1, r2 = 2, r3 = 3. V× vËy, nghiÖm cã d¹ng n n n an = 1 1 + 2 2 + 3 3 . Toán rời rạc 109
  110. Ví dụ ⚫ Sö dông c¸c ®iÒu kiÖn ®Çu ta cã hÖ ph¬ng tr×nh sau ®©y ®Ó x¸c ®Þnh c¸c h»ng sè 1, 2, 3: a0 = 2 = 1 + 2 + 3 a1 = 5 = 1 + 2.2 + 3.3 a2 = 15 = 1 + 2.4 + 3.9. ⚫ Gi¶i hÖ ph¬ng tr×nh trªn ta thu ®îc 1 = 1, 2 = -1 vµ 3 = 2. ⚫ VËy nghiÖm cña c«ng thøc ®· cho lµ n n an = 1 - 2 + 2. 3 . Toán rời rạc 110
  111. Trường hợp tổng quát k ⚫ Xét CTĐQ TTTNHSH bậc k: an = cian−i i=1 ⚫ PTĐT của nó là: k k k −i r − cir = 0 i=1 ⚫ Định lý 4: Nếu PTĐT có t nghiệm r1, ,rt với bội tương ứng là m1, ,mt (m1+ +mt=k). Khi đó: t mi −1 a = n j r n n   i, j i i=1 j=0 với n≥0, và αij là các hằng số. Toán rời rạc 111
  112. Ví dụ Giải công thức đệ qui: cn = – 4cn-1 + 3cn-2 + 18cn-3 , n 3, c0 = 1; c1 = 2; c2 = 13. Ph¬ng trình ®Æc trng: r3 + 4r2 – 3r – 18 = (r – 2)(r + 3)2 = 0 VËy nghiÖm tæng qu¸t cña c«ng thøc: n n cn = a10 2 + (a20 + a21 n)(– 3) trong đó a10, a20, a21 là các h»ng sè Toán rời rạc 112
  113. Ví dụ Các hằng số được xác định từ các điều kiện đầu: 0 0 0 = c0 = a10 2 + (a20 + a21 0)(−3) = a10 + a20 1 1 2 = c1 = a10 2 + (a20 + a21 1)(−3) = 2a10 − 3a20 − 3a21 2 2 13 = c2 = a10 2 + (a20 + a21 2)(−3) = 4a10 + 9a20 +18a21 Rút gọn ta thu được hệ 0 = a10 + a20 2 = 2a10 −3a20 −3a21 13 = 4a10 + 9a20 +18a21 Giải hệ ta nhận được: a10 =1,a20 = −1,a21 =1 Cuối cùng nghiệm của công thức là: nn cnn =2 + ( − 1 + )( − 3) Toán rời rạc 113
  114. Công thức đệ qui tuyến tính không thuần nhất hệ số hằng ⚫ Công thức đệ qui tuyến tính không thuần nhất hệ số hằng (Linear nonhomogeneous Recurrence Relation with constant coefficients) có chứa số hạng không thuần nhất F(n) phụ thuộc vào n (và không phụ thuộc vào bất cứ ai nào) : an = c1an−1 + + ckan−k + F(n) Phần không CTĐQ TTTNHSH tương ứng với thuần nhất công thức không thuần nhất Toán rời rạc 114
  115. Giải công thức không thuần nhất (CTKTN) ⚫ Kết quả sau đây là cơ sở để giải công thức không thuần nhất: • Nếu an = p(n) là một nghiệm riêng của CTKTN: k an = cian−i + F(n) i=1 • Khi đó mọi nghiệm của CTKTN đều có dạng: an = p(n) + h(n), trong đó an = h(n) là nghiệm tổng quát của CTĐQ TTTNHSH tương ứng k an=  c i a n− i i=1 Toán rời rạc 115
  116. Giải công thức không thuần nhất ⚫ Từ đó ta có cách giải CTKTN sau đây: (a) Tìm nghiệm tổng quát h(n) của công thức thuần nhất tương ứng. (b) Tìm nghiệm riêng p(n) của CTKTN. (c) Nghiệm của công thức không thuần nhất có dạng: an = h(n) + p(n). (d) Xác định các hằng số từ hệ phương trình thu được bởi đòi hỏi an thoả mãn các điều kiện đầu Toán rời rạc 116
  117. Giải công thức không thuần nhất ⚫ Tìm nghiệm riêng bằng cách nào? ⚫ Để tìm nghiệm riêng có thể căn cứ vào dạng của phần không thuần nhất F(n): • Nếu F(n) = P(n) sn, trong đó P(n) là đa thức của n còn s là hằng số và không là nghiệm đặc trưng, thì hãy tìm nghiệm riêng có dạng giống như F(n). • Nếu F(n) = P(n) sn, trong đó P(n) là đa thức của n còn s là nghiệm đặc trưng với bội là m, thì hãy tìm nghiệm riêng dưới dạng nm Q(n) sn Toán rời rạc 117
  118. Ví dụ ⚫ Giải công thức đệ qui n an=5an-1 - 6an-2+7 , n 2, a0 = 0; a1 = 1 ⚫ PT đặc trưng r2 – 5r +6 = 0 có nghiệm r1 = 3, r2 = 2. ⚫ Do đó nghiệm tổng quát của CTĐQ thuần nhất tương ứng n n là: h(n) = c13 + c22 . ⚫ Do F(n) = 7n và 7 không là nghiệm đặc trưng nên nghiệm riêng tìm dưới dạng p(n) = C.7n. Toán rời rạc 118
  119. Ví dụ ⚫ Nghiệm riêng tìm dưới dạng p(n) = C.7n. ⚫ Thay vào công thức ta có C7n = 5C7n-1 – 6C7n-2 + 7n ⚫ Từ đó tìm được C = 49/20. ⚫ Vậy p(n) = (49/20)7n. Toán rời rạc 119
  120. Ví dụ ⚫ Nghiệm tổng quát có dạng: n n n an = p(n) + h(n) = (49/20)7 + c13 + c22 . ⚫ Các hằng số c1, c2 xác định từ hệ phương trình: a0 = c1 + c2 + 49/20 = 0 a1 = 3c1 + 2c2 +(49/20).7 = 1 ⚫ Toán rời rạc 120
  121. Ví dụ ⚫ Giải công thức đệ qui an = 2an-1 + 1, n 1; a1 = 1. ⚫ PTĐT r - 2 = 0 có nghiệm r=2. Nghiệm tổng quát của n CTĐQ thuần nhất tương ứng là: h(n) = c12 . ⚫ Do F(n) = 1, nên nghiệm riêng tìm dưới dạng p(n) = C. ⚫ Thay vào công thức đã cho ta được: C = 2C+1. Từ đó tìm được C = -1. Vậy nghiệm riêng là p(n) = -1. Toán rời rạc 121
  122. Ví dụ ⚫ Nghiệm tổng quát của CTĐQ không thuần nhất là n an = c12 – 1. ⚫ Hệ số c1 xác định từ điều kiện đầu: a1 = c12 -1 = 1 ⚫ Do đó c1 = 1. ⚫ Vậy nghiệm của CTĐQ không thuần nhất là n an = 2 -1, n 1. Toán rời rạc 122
  123. Ví dụ ⚫ Giải công thức đệ qui an = an-1 + n, n 1; a1 = 2. ⚫ PTĐT r - 1 = 0 có nghiệm r=1. Nghiệm tổng quát của CTĐQ n thuần nhất tương ứng là: h(n) = c11 . ⚫ Do F(n) = n 1n, và 1 là nghiệm đặc trưng bội 1, nên nghiệm riêng tìm dưới dạng p(n) = (C2 + C3n).n. ⚫ Thay vào công thức đã cho ta được: (C2 + C3n).n = [C2 + C3(n-1)].(n-1) + n. ⚫ Từ đó tìm được C2 = ½ và C3 = ½ . Vậy nghiệm riêng là p(n) = (n+1)n/2. Toán rời rạc 123
  124. Ví dụ ⚫ Nghiệm tổng quát của CTĐQ không thuần nhất là an = c1+ (n+1)n/2 . ⚫ Hệ số c1 xác định từ điều kiện đầu: a1 = c1 + 1 = 2 ⚫ Do đó c1 = 1. ⚫ Vậy nghiệm của CTĐQ không thuần nhất là an = 1+ (n+1)n/2, n 1. Toán rời rạc 124
  125. Nhận xét ⚫ Phương pháp giải công thức đệ qui TTTNHSH trình bày ở trên cho phép qui dẫn việc tìm nghệm của nó về việc tìm tất cả các nghiệm của đa thức bậc k. ⚫ Việc tìm tất cả các nghiệm của một đa thức bậc tuỳ ý là vấn đề không đơn giản: • Ta có công thức để tìm nghiệm của đa thức bậc k 4. • Nhưng không có công thức để tìm tất cả các nghiệm của đa thức bậc k 5 (Định lý Aben). Toán rời rạc 125
  126. Chương 1. BÀI TOÁN ĐẾM 1. Nguyên lý cộng và nguyên lý nhân 2. Các cấu hình tổ hợp cơ bản 3. Nguyên lý bù trừ 4. Công thức đệ qui 5. Hàm sinh Toán rời rạc 126
  127. 5. Hàm sinh (Generating Function) ⚫ Giả sử {hn | n = 0, 1, 2, } là một dãy số. Ta viết dãy này như là dãy vô hạn phần tử, tuy nhiên ta coi rằng nó bao gồm cả trường hợp dãy hữu hạn. Nếu h0, h1, , hm là dãy hữu hạn, thì ta sẽ biến nó thành dãy vô hạn bằng cách đặt hi = 0, i > m . ⚫ Định nghĩa. Hàm sinh g(x) của dãy số {hn | n = 0, 1, 2, } là chuỗi vô hạn 2 hxi g(x) = h0 + h1 x + h2 x + =  i . i=0 ⚫ Như vậy hàm g(x) sinh ra dãy số đã cho như là dãy các hệ số của nó. ⚫ Nếu dãy là hữu hạn thì sẽ tìm được m sao cho hi = 0, i > m. Trong trường hợp này g(x) là một đa thức bậc m. 127
  128. Ví dụ ⚫ Ví dụ 1. Một trong những nguồn gốc dẫn đến định nghĩa hàm sinh chính là định lý về khai triển nhị thức: Hàm g(x) = (1 + x)m sinh ra dãy các hệ số tổ hợp {hk = C(m, k), k=0, 1, , m}. Bởi vì m (1+ x)m = C(m,k)xk k =0 ⚫ Ví dụ 2. Hàm g(x) = 1/(1-x) sinh ra dãy 1, 1, 1, ⚫ Dễ dàng chứng minh điều đó bằng cách thực hiện phép chia: 1/(1- x) = 1 + x + x2 + 128
  129. Ví dụ 3 ⚫ Ví dụ 3. Với k > 0, hàm g(x) = 1/(1-x)k sinh ra dãy {C(n+k-1, n): n = 0, 1, 2, }. ⚫ Như vậy hệ số thứ n sẽ là số khả năng chọn n vật từ k loại đồ vật. ⚫ Chứng minh. Thực vậy, ta có 1/(1-x)k =[ 1/(1-x)]k = (1 + x + x2 + )k. ⚫ Nếu ta khai triển biểu thức này bằng cách thực hiện nhân phá ngoặc, thì số lần xuất hiện số hạng xn sẽ bằng số nghiệm nguyên không âm của phương trình t1 + t2 + + tk = n, mà như đã biết là bằng C(n+k-1, n). 129
  130. Ví dụ 3 ⚫ Ví dụ này có thể gợi ý cho ta cách giải nhiều bài toán đếm. Chẳng hạn xét hàm sinh g(x) = (1 + x + x2 + x3) (1 + x + x2) (1 + x + x2 + x3 + x4). ⚫ Giả sử xa, xb, xc tương ứng là các số hạng lấy từ các thừa số thứ nhất, hai, ba của vế phải, điều đó có nghĩa là 0 a 3, 0 b 2, 0 c 4. Khi khai triển vế phải, các thừa số này sẽ cho ta số hạng xn, với n = a + b + c. ⚫ Như vậy hệ số của xn trong g(x) sẽ là số nghiệm nguyên không âm của phương trình n=a + b + c thoả mãn 0 a 3, 0 b 2, 0 c 4. ⚫ Suy ra hệ số này cũng cho ta số cách chọn n bông hoa từ 3 bông cúc, 2 bông layơn và 4 bông hồng. 130
  131. Ví dụ 3 ⚫ Tất nhiên việc sử dụng hàm sinh để giải bài toán đếm sẽ đòi hỏi nhiều tính toán khi thực hiện phép nhân các đa thức, và không thích hợp cho việc tính tay. Tuy nhiên, việc đó lại có thể thực hiện nhanh chóng trên máy tính, và vì thế hàm sinh sẽ là một công cụ hữu hiệu để giải nhiều bài toán đếm trên máy tính. ⚫ Ta dẫn ra một số khai triển đại số rất hay sử dụng trong việc sử dụng hàm sinh: • xk/(1-x) = xk (1 + x + x2 + ) = xk + xk+1 + xk+2 + • (1-xk+1)/(1-x) = 1 + x + x2 + + xk. • 1/(1-x2) = 1 + x2 + x4 + x6 + • x/(1-x2) = x(1 + x2 + x4 + x6 + ) = x + x3 + x5 + x7 + 131
  132. Ví dụ 4 ⚫ Ví dụ 4. Có bao nhiêu cách chọn ra n quả từ 4 loại quả: táo, chuối, cam và đào (mỗi loại đều có số lượng ít ra là n) mà trong đó có một số chẵn quả táo, số lẻ quả chuối, không quá 4 quả cam và ít ra 2 quả đào? ⚫ Giải. Hàm sinh để giải bài toán này là g(x) = (1+ x2+x4+x6+ ) (x+x3+x5+x7+ ) (1+x+x2+x3+x4) (x2+x3+x4+ ). ⚫ Trong công thức trên có 4 thừa số để đếm số quả táo (các số mũ chẵn), chuối (số mũ lẻ), cam (chỉ có đến số mũ 4) và đào (số mũ bắt đầu từ 2). Từ đó g(x) = [1/(1-x2)] [x/(1-x2)] [(1-x5)/(1-x)] [x2/(1-x)] = [x3(1-x5)]/[(1-x2)2(1-x)2]. ⚫ Câu trả lời là: Số cách cần đếm là hệ số thứ n trong khai triển g(x) dưới dạng chuỗi luỹ thừa. Tuy là chúng ta không có câu trả lời bằng số, nhưng sử dụng hàm xây dựng được ta có thể lập trình trên máy tính để đưa ra bảng đáp số cho các giá trị của n mong muốn. 132
  133. Ví dụ 5 ⚫ Ví dụ 5. Tìm hàm sinh cho hn là số cách chọn ra n quả từ 4 loại quả: táo, chuối, cam và đào (mỗi loại đều có số lượng ít ra là n) mà trong đó có một số chẵn quả táo, số lượng chuối chia hết cho 5, không quá 4 quả cam và không quá 1 quả đào? ⚫ Giải. Hàm sinh có dạng g(x)=(1+x2+x4+x6+ )(1+x5+x10+x15+ )(1+x+x2+x3+x4)(1+x) = [1/(1-x2)] [1/(1-x5)] [(1-x5)/(1-x)] (1+x) = [1/((1-x)(1 +x)] [1/(1-x)] (1+x) = 1/(1-x)2 ⚫ Từ đó ta có thể tìm công thức hiện cho lời giải, bởi vì, theo ví dụ 3, ta có 1 =Cn x n. = C n x n =( n + 1) x n 2 nn+2 − 1  + 1  (1− x ) n=0 n = 0 n = 0 ⚫ Vậy hn = n + 1. 133
  134. Hàm sinh và công thức đệ qui ⚫ Hàm sinh có thể sử dụng để tìm công thức dưới dạng hiện cho số hạng tổng quát của dãy số {hn , n=0,1,2, } xác định bởi công thức đệ qui. Nội dung của phương pháp có thể trình bày như sau: i) Xây dựng hàm sinh g(x) của dãy số này theo công thức 2 hxi g(x) = h0 + h1 x + h2 x + =  i i=0 ii) Tìm công thức giải tích cho hàm sinh g(x). (Sử dụng các tính chất của dãy số suy từ công thức đệ qui xác định nó). iii) Theo công thức tìm được, tìm khai triển hàm g(x) dưới dạng chuỗi luỹ thừa (chuỗi Maclaurin). iv) So sánh hệ số ở các số hạng với cùng số mũ của x ta tìm được công thức cho hn. 134
  135. Phép toán với hàm sinh ⚫ Trước hết ta đưa ra một số phép toán đối với hàm sinh. Giả sử ii f(),() x== aii x g x b x ii==00 là hai hàm sinh còn là số thực, khi đó ii fxgx()()(),()+ = abxi + i fx = ax i ii==00 ⚫ Tích Côsi của hai hàm sinh g(x) và f(x): i f()() x g x=  ci x i=0 trong đó k ck = a0 bk + a1 bk-1 + + ak b0 = abi k− i . i=0 135
  136. Chuỗi Maclaurin ⚫ Từ giải tích ta biết rằng nếu chuỗi i g() x=  hi x i=0 hội tụ ở lân cận điểm 0 thì tổng g(x) luôn là hàm giải tích trong lân cận này và (k) hk = g (0)/k! , k = 0, 1, ⚫ Khi đó chuỗi i  hxi i=0 chính là khai triển Maclaurin của hàm g(x). Như vậy có một tương ứng 1-1 giữa một hàm giải tích và một chuỗi hội tụ trong lân cận 0. 136
  137. Công thức hay dùng ⚫ Trong việc áp dụng hàm sinh ta thường sử dụng công thức sau: 1 Ck r k x k n =  nk+−1 (1− rx ) k=0 mà trường hợp riêng của nó là 1/(1 - rx) = 1 + rx + r2 x2 + r3 x3 + 137
  138. Dãy số Fibonaci ⚫ Dãy số Fibonaci. Dãy số Fibonaci là dãy số được xác định bởi công thức đệ qui fn = fn-1 + fn-2, n 2, f0 = 0, f1 = 1. ⚫ Ta sẽ tìm công thức cho số hạng tổng quát của dãy số nhờ phương pháp hàm sinh. ⚫ n Xét hàm sinh F () x =  f n x . Ta có n=0 n n n Fx()()= fxffxn =0 + 1 + fxffx n = 0 + 1 + f n−− 1 + fx n 2 n=0 n = 2 n = 2 nn++12 =f01 + f x + fnn x + f x nn==00 =x + xF ( x ) + x2 F ( x ). 138
  139. Dãy số Fibonaci ⚫ Từ đó suy ra x Fx().= 1−−xx2 ⚫ Ta có (1- x - x2) = (1 - x) (1 -  x), với 1+− 5 1 5 ==,. 22 ⚫ Viết lại F(x) dưới dạng AB Fx(),=+ 11−− xx 139
  140. Dãy số Fibonaci ⚫ Từ đó tìm được 11 AB=,. = − 55 ⚫ Do đó 1 1 1 Fx()=− 5 11−− xx 1 =− ( n n )x n . n=0 5 ⚫ Suy ra nn 1 1 1+− 5 1 5 fn=( nn − ) = − , 0. n 55 22 140
  141. 6. Một số dãy số đặc biệt ⚫ Dãy số Stirling ⚫ Dãy số Bell ⚫ Dãy số Catalan 141
  142. Nhắc lại: Số lượng ánh xạ Cho các tập hữu hạn A = {a1, , am} và B = {b1, , bn}. Hỏi có bao nhiêu ánh xạ f: A → B ? Như ta đã chứng minh: ⚫ Tổng số ánh xạ có thể: |B||A| = nm. ⚫ Số lượng đơn ánh: P(n,m) = n∙(n–1)∙∙∙(n–m+1) = n!/(n–m)!. ⚫ Số lượng song ánh là P(n,n) = n! nếu |A| = |B| = n. ⚫ Số lượng toàn ánh: với m ≥ n: n k n− k m  (−− 1)Cn ( n k ) k=0 142
  143. Số Stirling loại 2 ⚫ Số lượng toàn ánh từ tập A = {a1, ,am} vào tập B = {b1, ,bn} liên quan đến một con số tổ hợp nổi tiếng đó là số Stirling loại 2 (Stirling Numbers of the 2nd Kind). ⚫ Định nghĩa. Số Stirling loại 2, ký hiệu bởi S2(m,n), là số cách phân hoạch tập m phần tử thành n tập con (m n). ⚫ Ví dụ: Ta đếm số cách phân hoạch tập {1,2,3,4} ra thành 2 tập con. Ta có thể kể ra tất cả các cách phân hoạch như vậy: {{1,2,3},{4}}, {{1,2,4},{3}}, {{1,3,4},{2}}, {{2,3,4},{1}}, {{1,2},{3,4}}, {{1,3},{2,4}},{{1,4},{2,3}}. ⚫ Vậy S2(4,2)=7. 143
  144. ⚫ Trong nhiều tài liệu, số Stirling còn được ký hiệu bởi ()n m Sm hoÆc  n James Stirling 1692 – 1770 Scotland 144
  145. Số Stirling loại 2 ⚫ Ta sẽ xây dựng công thức đệ qui để đếm số S2(m,n). ⚫ Ta có: • S2(0,0)=1. • Nếu m > 0, thì S2(m,0) = 0, S2(m,1)=1, và S2(m,m)=1. Định lý. Với m, n > 1, S2(m,n) = S2(m–1,n–1) + n∙S2(m–1,n). Chứng minh. Ta cần đếm số cách phân hoạch tập m phần tử X = {x1, x2, , xm} ra thành n tập con. 145
  146. Công thức đệ qui ⚫ Tập các cách phân hoạch như vậy có thể phân hoạch thành 2 tập: A = Tập các cách phân hoạch X ra thành n tập con trong đó có một tập con là {xm}; B = Tập các cách phân hoạch X ra thành n tập con trong đó không có tập con nào là {xm} (tức là xm không đứng riêng một mình!). ⚫ Ta có: |A| = S2(m–1,n–1) . |B| = n∙S2(m–1,n), bởi vì có S2(m–1,n) cách phân hoạch X \{xm} ra thành n tập con và có n cách xếp xm vào một trong số các tập con này. ⚫ Từ đó S2(m,n)= |A| + |B| = S2(m–1,n–1) + n∙S2(m–1,n). Định lý được chứng minh. 146
  147. Công thức tính số Stirling ⚫ Từ công thức đệ qui có thể chứng minh bằng qui nạp toán học công thức sau đây: n 1 n− k k m S2 ( m , n )=− ( 1) Cn k n! k =0 ⚫ Nói chung để tính S2(m,n) người ta thường dùng công thức đệ qui, chứ không sử dụng công thức này. Điều này được giải thích tương tự như để tính hệ số tổ hợp người ta thường dùng tam giác Pascal. 147
  148. Liên hệ giữa số lượng toàn ánh và số Stirling ⚫ Ta xét mối liên hệ giữa số Stirling loại 2 với số lượng toàn ánh từ tập m phần tử A vào tập n phần tử B (ký hiệu là S'(m,n)). ⚫ Giả sử cho f là toàn ánh từ A vào B. Đặt Ai = {a A| f(a) = bi}, i = 1, 2, , n, Rõ ràng các tập A1, A2, , An tạo thành một phân hoạch của tập A. ⚫ Ngược lại, cho một phân hoạch của tập A ra thành n tập con A1, A2, , An và (1), (2), , (n) là hoán vị của 1, 2, , n, thì ta có thể xây dựng được toàn ánh f từ A vào B theo qui tắc f(a) = b (i) , a A (i) , i = 1,2, , n, ⚫ Như vậy mỗi phân hoạch cho ta n! toàn ánh. Vì thế, số lượng toàn ánh từ tập m phần tử vào tập n phần tử là bằng n! nhân với số cách phân hoạch tập m phần tử ra thành n tập con, nghĩa là bằng n!S2(m,n) 148
  149. Liên hệ giữa số lượng toàn ánh và số Stirling ⚫ Như vậy ta có đẳng thức cho mối liên hệ giữa số toàn ánh từ tập m phần tử vào tập n phần tử S'(m,n) và số Stirling loại 2 sau đây: S'(m,n) = n! S2(m,n) . ⚫ Do đó từ công thức đã chứng minh ở mục trước n k k m S '( m , n )= ( − 1) Cn ( n − k ) k=0 Suy ra n 1 k k m S2 ( m , n )= ( − 1) Cn ( n − k ) n! k=0 149
  150. Bảng giá trị của số Stirling loại 2 S2(n,k) 0 1 2 3 4 5 6 7 8 9 10 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 n 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 150
  151. Số Bell ⚫ Định nghĩa. Số Bell (Bell numbers) là số cách phân hoạch tập n phần tử ra thành các tập con khác rỗng. ⚫ Các phần tử đầu tiên của dãy số này là 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, ⚫ Ví dụ: Tập {1, 2, 3} có các cách phân hoạch sau đây: {{1}, {2}, {3}} , {{1, 2}, {3}}, {{1, 3}, {2}} , {{1}, {2, 3}}, {{1, 2, 3}}. ⚫ Số Bell thứ n được tính bởi công thức n  S2 (,) n k k=1 Eric Temple Bell Born: 1883, Scotland trong đó S2(n,k) là số Stirling loại 2. Died: 1960, USA 151
  152. Số Bell ⚫ Tập {1, 2, 3} có 5 cách phân hoạch: ⚫ Tập {1, 2, 3, 4, 5} có 52 cách phân hoạch: 152
  153. Số Catalan ⚫ Định nghĩa. Số Catalan thứ n, ký hiệu là Cn , là số cách đặt dấu ngoặc để tổ chức thực hiện việc tính tích của n+1 thừa số: P0 n = x0 x1 x2 xn. ⚫ Ví dụ: ⚫ Có 2 cách để tính P0 2 : x0*x1*x2 = (x0*(x1*x2)) = ((x0*x1)*x2) ⚫ Có 5 cách để tính P0 3: 1*2*3*4 = (1*(2*(3*4))) = (1*((2*3)*4)) = ((1*2)*(3*4)) = ((1*(2*3))* 4) = (((1*2)*3)*4) ⚫ Có 14 cách để tính P0 4 : 1*2*3*4*5 = (1 (2 (3 (4 5)))) = (1 (2 ((3 4) 5))) = (1 ((2 3) (4 5))) = (1 ((2 (3 4)) 5)) = (1 (((2 3) 4) 5)) = ((1 2) (3 (4 5))) = ((1 2) ((3 4) 5)) = ((1 (2 3)) (4 5)) = ((1 (2 (3 4))) 5) = ((1 ((2 3) 4)) 5) = (((1 2) 3) (4 5)) = (((1 2) (3 4)) 5) = (((1 (2 3)) 4) 5) = ((((1 2) 3) 4) 5) 153
  154. Số Catalan ⚫ Ta xây dựng công thức đệ qui để tính Cn. ⚫ Rõ ràng C0 = 1 và C1 = 1. ⚫ Giả sử n > 1. Sau khi đặt dấu ngoặc phân tách đầu tiên, tích x0 x1 x2 xn được chia làm hai tích con. ⚫ Ví dụ: P0 4 = P0 2 P3 4 = (x0 x1 x2) (x3 x4) ⚫ Giả sử dấu ngoặc phân tách đầu tiên được đặt sau thừa số xk: P0 n = P0 k Pk+1 n = (x0 x1 x2 xk) (xk+1 xk+2 xn) ⚫ Khi đó ta có Ck cách tính P0 k , Cn-k-1 cách tính Pk+1 n , và do đó việc tính P0 n có thể thực hiện bởi Ck Cn-k-1 cách . 154
  155. Số Catalan ⚫ Do dấu ngoặc phân tách đầu tiên có thể đặt vào sau bất cứ thừa số nào trong các thừa số x0, x1, , xn-1, suy ra tổng số cách tính P0 n là: Cn = C0 Cn-1 + C1Cn-2+ +Cn-1C0 . ⚫ Như vậy ta thu được công thức đệ qui: n−1 Cn=  C k C n−− k 1 , n 1, k=0 CC01==1, 1 ⚫ Sử dụng công thức này có thể chứng minh công thức sau: n−1 1 2n (2n )! Cn= C k C n−− k 1 = =, n 0. k=0 n++1 n n !( n 1)! 155
  156. Số Catalan ⚫ Một số phần tử đầu tiên của dãy số Catalan: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ⚫ Số Catalan là lời giải của rất nhiều bài toán tổ hợp. ⚫ Ta sẽ kể ra dưới đây một số bài toán như vậy. E. C. Catalan 1814 -1894 Belgium 156
  157. Tam giác phân đa giác ⚫ Cn là số cách chia đa giác n+2 đỉnh ra thành các tam giác nhờ vẽ các đường chéo không cắt nhau ở trong đa giác: C2 = 2 C3 = 5 C4 = 14 C5 = 42 157
  158. Đường đi trên lưới ô vuông ⚫ Cn là số lượng đường đi đơn điệu (tức là đường đi xuất phát từ vị trí góc dưới-phải kết thúc ở góc trên-trái và chỉ đi sang trái hoặc lên trên) độ dài 2n trên lưới ô vuông kích thước n n không vượt lên trên đường chéo. C2 = 2 C3 = 5 C = 42 C4 = 14 5 158
  159. Cây nhị phân đầy đủ Cn là số lượng cây nhị phân đầy đủ không đẳng cấu có n đỉnh trong. Cây nhị phân có gốc được gọi là đầy đủ nếu mỗi đỉnh của nó hoặc là không có con hoặc có đúng hai con. Đỉnh trong (internal vertice) là đỉnh có con. n = 1 n = 2 n = 3 n = 4 159
  160. Cây nhị phân đầy đủ với n lá ⚫ Cn là số cây nhị phân đầy đủ với n + 1 lá. ⚫ Có C3 = 5 cây nhị phân đầy đủ với 4 lá: n 2 3 4 160
  161. Ask questions! Toán rời rạc 161
  162. n an=5an-1 - 6an-2+7 , n 2, Toán rời rạc 162
  163. Toán rời rạc 163
  164. Toán rời rạc 164
  165. LiNoReCoCo Example ⚫ Find all solutions to an = 3an−1+2n. Which solution has a1 = 3? • Notice this is a 1-LiNoReCoCo. Its associated 1- LiHoReCoCo is an = 3an−1, whose solutions are all n of the form an = α3 . Thus the solutions to the original problem are all of the form n an = p(n) + α3 . So, all we need to do is find one p(n) that works. Toán rời rạc 165
  166. Trial Solutions ⚫ If the extra terms F(n) are a degree-t polynomial in n, you should try a general degree-t polynomial as the particular solution p(n). ⚫ This case: F(n) is linear so try an = cn + d. cn+d = 3(c(n−1)+d) + 2n (for all n) (2c+2)n + (2d−3c) = 0 (collect terms) So c = −1 and d = −3/2. So an = −n − 3/2 is a solution. ⚫ Check: an≥1 = {−5/2, −7/2, −9/2, } Toán rời rạc 166
  167. Finding a Desired Solution ⚫ From the previous, we know that all general solutions to our example are of the form: n an = −n − 3/2 + α3 . Solve this for α for the given case, a1 = 3: 3 = −1 − 3/2 + α31 α = 11/6 n ⚫ The answer is an = −n − 3/2 + (11/6)3 . Toán rời rạc 167
  168. Double Check Your Answer! ⚫ Check the base case, a1=3: n an = −n − 3/2 + (11/6)3 1 a1 = −1 − 3/2 + (11/6)3 = −2/2 − 3/2 + 11/2 = −5/2 + 11/2 = 6/2 = 3 ⚫ Check the recurrence, an = 3an−1+2n: −n − 3/2 + (11/6)3n = 3[−(n−1) − 3/2 + (11/6)3n−1]+2n = 3[−n − 1/2 + (11/6)3n−1] + 2n = −3n − 3/2 + (11/6)3n + 2n = −n − 3/2 + (11/6)3n ■ Toán rời rạc 168
  169. Ask questions! Toán rời rạc 169
  170. Fall 2006 Toán rời rạc 170
  171. Fall 2006 Toán rời rạc 171
  172. Fall 2006 Toán rời rạc 172
  173. Fall 2006 Toán rời rạc 173
  174. Ask questions! Fall 2006 Toán rời rạc 174
  175. Fall 2006 Toán rời rạc 175
  176. Fall 2006 Toán rời rạc 176