Bài giảng Lý thuyết tổ hợp - Chương 1: Bài toán đếm

é ®­îc t¹o ra lµ tÝch sè n1n2 ... nk.Toán rời rạcNguyê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ộiHuếSài gònToán rời rạcNguyê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ạcNguyê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àuGiả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=12Toán rời rạcNguyê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=6Toán rời rạcNguyên lý nhân: Ví dụVí dụ 4. Có bao nhiêu xâu gồm 4 chữ số thập phâna) 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ọnKý 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ọnKý tự thứ tư có 7 cách chọnTổ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ọnKý tự cuối cùng có 5 cách chọnTổng cộng có 10*10*10*5 = 5000 xâu cần đếm.Toán rời rạcCác ví dụ phức tạp hơnKhi 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ânBằng cách đó ta có thể giải được nhiều bài toán thú vị và phức tạp hơnToán rời rạcChụp ảnh đám cướiXé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ó 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 ảnhToán rời rạcChụp ảnh đám cướib) 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 ảnhTrướ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ạiTổng cộng có 30 khả năngTiếp theo, xếp chỗ cho 4 nhân vật còn lại trong bức ảnh theo qui tắc nhânCó 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 = 1680Theo qui tắc nhân có 30 * 1680 = 50 400 bức ảnhToán rời rạcChụp ảnh đám cướic) 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âuQui tắc nhân: xếp cô dâu và sau đó xếp các nhân vật còn lạiTrướ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 = 6720Qui tắc nhân cho 6 * 6720 = 40 320 khả nănghoặc chỉ xếp chú rểSố lượng khả năng cũng giống như cô dâu: 40 320Qui tắc cộng cho 40 320 + 40 320 = 80 640 khả năngToán rời rạcChụp ảnh đám cướiMộ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 400Theo 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 640Toán rời rạcSố 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+P8Toán rời rạcSố lượng Mật khẩuP6 = 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 560Toán rời rạcSố lượng Mật khẩuTương tự như vậy, ta cóP7 = 367 – 267= 70 332 353 920P8 = 368 – 268= 2 612 282 842 880P6 + P7 + P8 = 2 684 483 063 360Chú ý: 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ạcChương 1. BÀI TOÁN ĐẾMNguyên lý cộng và nguyên lý nhânCác cấu hình tổ hợp cơ bảnNguyên lý bù trừCông thức đệ quiHàm sinhToán rời rạc2. Các cấu hình tổ hợp cơ bảnCá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ợpPhé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ơnGiả 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ạcChỉ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.Ký hiệu số lượng chỉnh hợp lặp chập m từ n phần tử là AnmTheo đị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óĐịnh lý 1. Anm = nm.Toán rời rạcChỉnh hợp lặpVÝ 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ạcChỉnh hợp lặpVí 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ênGiả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ạcChỉ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ử là Pnm. 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óĐịnh lý 2. Toán rời rạcChỉnh hợp không lặpVÝ 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 không lặp chập 4 từ 10. Vậy số cách xếp cần đếm là P104 = 10.9.8.7 = 5040.Toán rời rạcChỉnh hợp không lặpChú ý: Để 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ếpTiế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ếpToán rời rạcHoá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.Rõ ràng Pn = Pnn. Vì vậy, ta cóĐịnh lý 3. Toán rời rạcHoá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ạcHoá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ệnGiải: n!Toán rời rạcTổ 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.Ký hiệu số lượng tổ hợp chập m từ n phần tử là Cnm (đô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 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ạcTổ hợpTừ 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ạcTổ hợpTam giác Pascal, n=8Toán rời rạcTổ hợpC¸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µ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ạcTổ hợpTrong c«ng thøc Niuton đặt y=1 ta có: (*)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ạcChương 1. BÀI TOÁN ĐẾMNguyên lý cộng và nguyên lý nhânCác cấu hình tổ hợp cơ bảnNguyên lý bù trừCông thức đệ quiHàm sinhToán rời rạc3. 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ụngToán rời rạc3.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 BKhi đó số phần tử của hợp hai tập là 5+3-1 = 7, chứ không phải là 8CM: Toán rời rạcNguyê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ạcNguyê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ạcNguyên lý bù trừ§Þnh lý. Gi¶ sö A1, A2, ... , Am lµ c¸c tËp h÷u h¹n. Khi ®ã trong ®ã (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ạcNguyê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µ ®óngToán rời rạcNguyê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) = N(X ) – N1 + N2 -...+(– 1)mNm 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ạc3. 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ụngToán rời rạcNguyê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ạcNguyê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ạcNguyê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ạcNguyê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ạcNguyê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(X ) – N1 + N2 – ...+(– 1)nNn 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ạcNguyên lý bù trừ: Bài toán bỏ thưChó ý lµ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 ®ã VËy x¸c suÊt cÇn t×m lµ:Toán rời rạcNguyên lý bù trừMét ®iÒu lý thó lµ x¸c suÊt nµy dÇn ®Õn e-1 (nghÜa lµ cßn lín h¬n 1/3) khi n kh¸ lín. Sè trong bµi to¸n trªn ®­îc gäi lµ sè mÊt thø tù vµ ®­îc ký hiÖu lµ Dn. D­íi ®©y lµ mét vµi gi¸ trÞ cña Dn, cho ta thÊy Dn t¨ng nhanh thÕ nµo so víi n:n234567891011Dn12944265 1854 14833 133496 1334961 4890741 Số lượng toàn ánhGiả 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.) Số lượng toàn ánhAfBKhông tồn tại điểm không có mũi tên đi vàoTa muốn tất cả bi đều thuộc miền giá trị của f. Gọi Pi là tính chất "bi không nằm trong miền giá trị của 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.Số lượng toàn ánhTheo nguyên lý bù trừ số lượng toàn ánh cần đếm là: N – N1 + N2 – ... +(–1)n Nn.Ta có:N - số ánh xạ từ m-tập A vào n-tập B: nmDo 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)mDo N(PiPj) - số ánh xạ không có bi và bj trong miền giá trị, nên N(PiPj) = (n-2)m , do đó N2 = C(n,2) (n-2)m.Tổng quát ta có: dó đó Nk = C(n,k) (n - k)m.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.Số lượng toàn ánhTa 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:Toán rời rạcChương 1. BÀI TOÁN ĐẾMNguyên lý cộng và nguyên lý nhânCác cấu hình tổ hợp cơ bảnNguyên lý bù trừCông thức đệ quiHàm sinhToán rời rạc4. Công thức đệ quiCô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 đếmToán rời rạc4. Công thức đệ qui4.1. Xây dựng công thức đệ qui4.2. Giải công thức đệ quiToán rời rạc4.1 Xây dựng công thức đệ quiVí 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 xB – tập các tập con k phần tử không chứa xToán rời rạc4.1 Xây dựng công thức đệ quiRõ 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ạc4.1 Xây dựng công thức đệ quiCô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ạc4.1 Xây dựng công thức đệ quiHà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ấyC*(n,0) =1; C*(n,n) = 1C*(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ạc4.1 Xây dựng công thức đệ quiVÝ 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ạc4.1 Xây dựng công thức đệ quiGi¶ 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ạc4.1 Xây dựng công thức đệ quil1l2l3l4G1G2G3phần 1phần 2phần 3phần 4Toán rời rạc4.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 Sn = 2 + 2 + 3 + ...+(n-1) + n = n(n+1)/2 + 1 = (n2+n+2)/2Toán rời rạc4.1 Xây dựng công thức đệ quiVí 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ạc4.1 Xây dựng công thức đệ quiDo đó, 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-1Do 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-2Vậ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ạc4.1 Xây dựng công thức đệ quiVí 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ạc4.1 Xây dựng công thức đệ quiDo đó, theo nguyên lý cộng: Qn = |A| + |B|.Ta có:|A| = Qn-1|B| = Qn-2Vậy, ta thu được công thức đệ qui Q1 = 1; Q2 = 2; Qn = Qn-1 + Qn-2, n > 2 (6)............ABToán rời rạc4.1 Xây dựng công thức đệ quiVÝ 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ạc4.1 Xây dựng công thức đệ quiGi¶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ạc4.1 Xây dựng công thức đệ quiB­í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µ hn = 2n – 1, n ≥ 1.Toán rời rạc4.1 Xây dựng công thức đệ quiTa 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 hn−2 + 1) + 1 = 22 hn−2 + 2 + 1 = 22(2 hn−3 + 1) + 2 + 1 = 23 hn−3 + 22 + 2 + 1 = 2n−1 h1 + 2n−2 + + 2 + 1 = 2n−1 + 2n−2 + + 2 + 1 (do h1 = 1) = 2n − 1Toán rời rạcTower of Hanoi: n=5Cọc aCọc cCọc bToán rời rạc4. Công thức đệ qui4.1. Xây dựng công thức đệ qui4.2. Giải công thức đệ quiToán rời rạc§4.2. Giải công thức đệ quiTa 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§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ố.Ví dụ:1) an = 4an-1 +2nan-3 2) hn = 2hn-1 + 13) bn = 5bn-2 + 2(bn-3)2 4) qn = 3 qn-6 + qn-8 Fall 2006Toán rời rạcToán rời rạcGiải CTĐQ TTTNHSHTa sẽ tìm nghiệm dưới dạng an = rn, trong đó r là hằng số.Dãy số {an = rn } thoả mãn CTĐQ đã cho nếu r thoả mãn phương trình: rn = c1rn−1 + + ckrn−k, hay  rk − c1rk−1 − − ck = 0Phươ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ố.(chuyển vế và × với rk−n)Toán rời rạcGiải CTĐQ TTTNHSH§Þnh lý 1. Cho c1, c2 lµ c¸c h»ng sè thùc. Gi¶ sö ph­¬ng tr×nh r2 - 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 an = 1(r1)n + 2(r2)n (5) n = 0, 1, ..., trong ®ã 1 , 2 lµ c¸c h»ng sè.Toán rời rạcGiải CTĐQ TTTNHSHChø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 tr­ng, 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 tr­ng nªn r12 = c1 r1 + c2 , r22 = c1 r2 + c2 Toán rời rạcGiải CTĐQ TTTNHSHTõ ®ã suy ra c1 an-1 + c2 an-2 = c1 (1 r1n-1 + 2 r2n-1) + c2 (1 r1n-2 + 2 r2n-2) = 1 r1n-2(c1 r1 + c2) + 2 r2n-2(c1 r2 + c2) = 1 r1n-2 r12 + 2 r2n-2 r22 = 1 r1n + 2 r2n = an .Toán rời rạcGiải CTĐQ TTTNHSHB©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ạcGiải CTĐQ TTTNHSHTa 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ạcVÝ 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 tr­ng: r2 - r - 1 = 0,ta thu ®­îc hai nghiÖm ®Æc tr­ngLeonardo Fibonacci1170-1250Toán rời rạcVÝ dôDo ®ã c«ng thøc hiÖn cã d¹ng: Fn = 1.(r1)n + 2.(r2)n 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ã: vµ tõ ®ã thu ®­îcC«ng thøc MuavreF0= 1+ 2 = 0F1= 1r1+ 2r2 = 1Toán rời rạcGreat Pyramid at GizehToán rời rạcbaToán rời rạcTỷ lệ giữa chiều cao và lưngToán rời rạcĐị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.ABCToán rời rạcToán rời rạcTrườ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 tr×nh r2 - 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 = 0, 1, ..., trong ®ã 1 , 2 lµ c¸c h»ng sè.Toán rời rạcVí 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: an = 1 3n + 2 n 3n.§Ó 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µ: an = 3n + n 3n .Toán rời rạcTrườ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 tr­ng rk - c1 rk-1 - c2 rk-2 - . . . - 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 an = 1 r1n + 2 r2n + . . . + k rkn víi n = 0, 1, 2,..., trong ®ã 1, 2, ..., k lµ c¸c h»ng sè. Toán rời rạcVí 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 tr­ng 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 an = 1 1n + 2 2n + 3 3n.Toán rời rạcVí 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µ an = 1 - 2n + 2. 3n . Toán rời rạcTrường hợp tổng quátXét CTĐQ TTTNHSH bậc k:PTĐT của nó là:Đị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 đó: với n≥0, và αij là các hằng số.Toán rời rạcVí 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 tr­ng: r3 + 4r2 – 3r – 18 = (r – 2)(r + 3)2 = 0 VËy nghiÖm tæng qu¸t cña c«ng thøc: cn = a10 2n + (a20 + a21 n)(– 3)ntrong đó a10, a20, a21 là các h»ng sè Toán rời rạcVí dụ Các hằng số được xác định từ các điều kiện đầu:Rút gọn ta thu được hệGiải hệ ta nhận được:Cuối cùng nghiệm của công thức là:Toán rời rạcCông thức đệ qui tuyến tính không thuần nhất hệ số hằngCô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)CTĐQ TTTNHSH tương ứng với công thức không thuần nhấtPhần không thuần nhấtToán rời rạcGiả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: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 ứngToán rời rạcGiải công thức không thuần nhấtTừ đó ta có cách giải CTKTN sau đây:Tìm nghiệm tổng quát h(n) của công thức thuần nhất tương ứng.Tìm nghiệm riêng p(n) của CTKTN.Nghiệm của công thức không thuần nhất có dạng: an = h(n) + p(n).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 đầuToán rời rạcGiải công thức không thuần nhấtTì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)snToán rời rạcVí dụGiải công thức đệ quian=5an-1 - 6an-2+7n, n2,a0 = 0; a1 = 1PT đặ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 là: h(n) = c13n + c22n.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ạcVí 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 + 7nTừ đó tìm được C = 49/20. Vậy p(n) = (49/20)7n. Toán rời rạcVí dụNghiệm tổng quát có dạng: an = p(n) + h(n) = (49/20)7n + c13n + c22n.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ạcVí 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 CTĐQ thuần nhất tương ứng là: h(n) = c12n.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ạcVí dụ Nghiệm tổng quát của CTĐQ không thuần nhất là an = c12n – 1.Hệ số c1 xác định từ điều kiện đầu: a1 = c12 -1 = 1Do đó c1 = 1.Vậy nghiệm của CTĐQ không thuần nhất là an = 2n -1, n  1.Toán rời rạcVí 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 thuần nhất tương ứng là: h(n) = c11n.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ạcVí 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 = 2Do đó 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ạcNhận xétPhươ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ạcChương 1. BÀI TOÁN ĐẾMNguyên lý cộng và nguyên lý nhânCác cấu hình tổ hợp cơ bảnNguyên lý bù trừCông thức đệ quiHàm sinh5. 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 g(x) = h0 + h1 x + h2 x2 + ... = .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.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ì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 + ... Ví dụ 3Ví 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). Ví dụ 3Ví 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. Ví dụ 3Tấ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 + ...Ví dụ 4Ví 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.Ví dụ 5Ví 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ạngg(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)2Từ đó 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ó .Vậy hn = n + 1.Hàm sinh và công thức đệ quiHà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 g(x) = h0 + h1 x + h2 x2 + ... =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.Phép toán với hàm sinhTrước hết ta đưa ra một số phép toán đối với hàm sinh. Giả sử là hai hàm sinh còn  là số thực, khi đóTích Côsi của hai hàm sinh g(x) và f(x): trong đó ck = a0 bk + a1 bk-1 + ... + ak b0 = .Chuỗi MaclaurinTừ giải tích ta biết rằng nếu chuỗi 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à hk = g(k)(0)/k! , k = 0, 1, ...Khi đó chuỗi 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.Công thức hay dùngTrong việc áp dụng hàm sinh ta thường sử dụng công thức sau: mà trường hợp riêng của nó là 1/(1 - rx) = 1 + rx + r2 x2 + r3 x3 + ....Dãy số FibonaciDã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.Xét hàm sinh . Ta cóDãy số FibonaciTừ đó suy raTa có (1- x - x2) = (1 -  x) (1 -  x), vớiViết lại F(x) dưới dạng Dãy số FibonaciTừ đó tìm được Do đóSuy ra6. Một số dãy số đặc biệtDãy số StirlingDãy số BellDãy số Catalan 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: Số Stirling loại 2Số 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. Trong nhiều tài liệu, số Stirling còn được ký hiệu bởi James Stirling1692 – 1770ScotlandSố Stirling loại 2Ta 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. Công thức đệ quiTậ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. Công thức tính số StirlingTừ 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ó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. Liên hệ giữa số lượng toàn ánh và số StirlingTa 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) Liên hệ giữa số lượng toàn ánh và số StirlingNhư 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ướcBảng giá trị của số Stirling loại 2Số 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 trong đó S2(n,k) là số Stirling loại 2.Eric Temple BellBorn: 1883, ScotlandDied: 1960, USASố BellTậ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: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) Số CatalanTa 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 .Số CatalanDo 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:Sử dụng công thức này có thể chứng minh công thức sau:Số CatalanMộ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 BelgiumTam giác phân đa giácCn 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:C3 = 5 C2 = 2 C4 = 14 C5 = 42 Đường đi trên lưới ô vuôngCn 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.C5 = 42C4 = 14C2 = 2C3 = 5 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 = 2n = 3n = 4n = 1Cn 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á: Cây nhị phân đầy đủ với n lán234Toán rời rạcAsk questions!Toán rời rạcan=5an-1 - 6an-2+7n, n2,Toán rời rạcToán rời rạcToán rời rạcLiNoReCoCo ExampleFind 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 of the form an = α3n. Thus the solutions to the original problem are all of the form an = p(n) + α3n. So, all we need to do is find one p(n) that works.Toán rời rạcTrial SolutionsIf 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ạcFinding a Desired SolutionFrom the previous, we know that all general solutions to our example are of the form: an = −n − 3/2 + α3n. Solve this for α for the given case, a1 = 3: 3 = −1 − 3/2 + α31 α = 11/6The answer is an = −n − 3/2 + (11/6)3n.Toán rời rạcDouble Check Your Answer!Check the base case, a1=3: an = −n − 3/2 + (11/6)3n a1 = −1 − 3/2 + (11/6)31 = −2/2 − 3/2 + 11/2 = −5/2 + 11/2 = 6/2 = 3Check 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ạcAsk questions!Fall 2006Toán rời rạcFall 2006Toán rời rạcFall 2006Toán rời rạcFall 2006Toán rời rạcFall 2006Toán rời rạcAsk questions!Fall 2006Toán rời rạcFall 2006Toán rời rạc