Bài giảng Toán rời rạc - Phần 1: Lý thuyết tổ hợp - Chương 1: Bài toán đếm - Nguyễn Đức Nghĩa

Toán rời rạc 
Phần thứ nhất 
LÝ THUYẾT TỔ HỢP 
Combinatorial Theory 
Fall 2009 
Toán rời rạc 
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 
Chương 1. BÀI TOÁN ĐẾM 
Nguyên lý cộng và nguyên lý nhân 
Các cấu hình tổ hợp cơ bản 
Nguyên lý bù trừ 
Công thức đệ qui 
Hàm sinh 
Toán rời rạc 
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 
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 A 1 , A 2 , ..., A k lµ mét ph©n ho¹ch cña tËp hîp X th× 
N ( X ) = N ( A 1 ) + N ( A 2 ) + ... + N ( A k ) . 
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 ( A c ). 
Toán rời rạc 
 Nguyên lý cộng: Ví dụ 
V í dụ 1. Một đoàn vận động viên gồm 2 môn bắn súng và bơi được cử đi thi đấu ở nước ngoài. Nam có 10 người. Số vận động viên thi bắn súng (kể cả nam và nữ) là 14. Số nữ vận động viên thi bơi bằng số nam vận động viên thi bắn súng. Hỏi toàn đoàn có bao nhiêu người? 
Giải: Chia đoàn thành 2 lớp: nam và nữ. Lớp nữ lại được chia 2: thi bắn súng và thi bơi. Thay số nữ thi bơi bằng số nam thi bắn súng (2 số này bằng nhau theo đầu bài), ta được số nữ bằng tổng số đấu thủ thi bắn súng. Từ đó, theo nguyên lý cộng, toàn đoàn có 10 + 14 = 24 người. 
Toán rời rạc 
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 
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­¬ng 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 
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 
1.2. Nguyên lý nhânThe product rule 
NÕu mçi thµnh phÇn a i cña bé cã thø tù k thµnh phÇn ( a 1 , a 2 , ..., a k ) cã n i 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 n 1 n 2 ... n k . 
Mét hÖ qu¶ trùc tiÕp cña nguyªn lý nh©n: 
 N ( A 1 A 2 ... A k ) = N ( A 1 ) N ( A 2 ) ... N ( A k ) , 
 víi A 1 , A 2 , ..., A k lµ nh÷ng tËp hîp nµo ®ã, nãi riªng: 
 N ( A k ) = [ N ( A )] k . 
Toán rời rạc 
1.2. Nguyên lý nhânThe 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 ( a 1 , a 2 , ..., a k ) theo tõng thµnh phÇn vµ 
a 1 cã thÓ chän bëi n 1 c¸ch; 
Sau khi a 1 ®· chän, a 2 cã thÓ chän bëi n 2 c¸ch; 
... 
Sau khi a 1 , a 2 ,..., a k -1 ®· chän, a k cã thÓ chän bëi n k c¸ch; 
ThÕ th× sè bé ®­îc t¹o ra lµ tÝch sè n 1 n 2 ... n k . 
Toán rời rạc 
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 
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 
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 
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 
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 
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 
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ó 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 
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 
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 
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 
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à P 6 , P 7 , P 8 là số lượng mật khẩu độ dài 6, 7, và 8, tương ứng, thì 
 P = P 6 +P 7 +P 8 
Toán rời rạc 
Số lượng Mật khẩu 
P 6 = 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) = 36 6 – 26 6 
= 1 867 866 560 
Toán rời rạc 
Số lượng Mật khẩu 
Tương tự như vậy, ta có 
P 7 = 36 7 – 26 7 = 70 332 353 920 
P 8 = 36 8 – 26 8 = 2 612 282 842 880 
P 6 + P 7 + P 8 = 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 
Chương 1. BÀI TOÁN ĐẾM 
Nguyên lý cộng và nguyên lý nhân 
Các cấu hình tổ hợp cơ bản 
Nguyên lý bù trừ 
Công thức đệ qui 
Hàm sinh 
Toán rời rạc 
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 
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 . 
Ký hiệu số lượng chỉnh hợp lặp chập m từ n phần tử là A n m 
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 
 ( a 1 , a 2 , ..., a m ), a i 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à X m . Vì vậy, theo nguyên lý nhân ta có 
Định lý 1. A n m = n m . 
Toán rời rạc 
Chỉnh hợp lặp 
VÝ dô 1 . TÝnh sè ¸nh x¹ tõ tËp m phÇn tö U = { u 1 , u 2 , ..., u m } 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 ( u 1 ), f ( u 2 ), ..., f ( u m )), trong ®ã f ( u i ) V , i =1, 2, ..., m . Tõ ®ã nhËn ®­îc sè cÇn t×m lµ n m . 
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µ 2 n . 
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µ 2 n . 
Toán rời rạc 
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: 4 100 hay 100 4 ? 
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 (b 1 , ..., b 100 ) trong đó b i {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à 4 100 . 
Toán rời rạc 
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ử là P n m . 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 
 ( a 1 , a 2 , ..., a m ), a i X , i = 1, 2, ..., m, a i a j , 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ạc 
Chỉnh hợp không lặp 
VÝ dô 1 . TÝnh sè đơn ¸nh tõ tËp m phÇn tö U = { u 1 , u 2 , ..., u m } 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 ( u 1 ), f ( u 2 ), ..., f ( u m )), trong ®ã f ( u i ) V , i =1, 2, ..., m , f ( u i ) f ( u j ) , 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ự (g 1 , g 2 , g 3 , g 4 ), trong đó g i {1, 2, ..., 10} là chỗ ngồi của học sinh i. Từ điều kiện đầu bài g i g j , 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à P 10 4 = 10.9.8.7 = 5040. 
Toán rời rạc 
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 
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à P n . 
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 
 ( a 1 , a 2 , ..., a n ), a i X , i = 1, 2, ..., n, a i a j , i j. 
Rõ ràng P n = P n n . Vì vậy, ta có 
Định lý 3. 
Toán rời rạc 
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ª ...  thức đệ qui 
Hàm sinh 
5. Hàm sinh (Generating Function) 
Giả sử { h n | 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 h 0 , h 1 , ..., h m 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 h i = 0 , i > m . 
Định nghĩa. Hàm sinh g ( x ) của dãy số { h n | n = 0, 1, 2, ....} là chuỗi vô hạn 
 g ( x ) = h 0 + h 1 x + h 2 x 2 + ... = . 
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 h i = 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 
 { h k = 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 + x 2 + ... 
 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 + x 2 + ... ) 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 x n sẽ bằng số nghiệm nguyên không âm của phương trình 
 t 1 + t 2 + ... + t k = n, 
 mà như đã biết là bằng C ( n+k- 1 , n ). 
 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 + x 2 + x 3 ) (1 + x + x 2 ) (1 + x + x 2 + x 3 + x 4 ) . 
Giả sử x a , x b , x c 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 x n , với n = a + b + c. 
Như vậy hệ số của x n 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ụ 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: 
x k /(1- x ) = x k (1 + x + x 2 + ...) = x k + x k+ 1 + x k+ 2 + ... 
(1- x k+ 1 )/(1 -x ) = 1 + x + x 2 + ... + x k . 
1/(1- x 2 ) = 1 + x 2 + x 4 + x 6 + ... 
x/ (1 -x 2 ) = x (1 + x 2 + x 4 + x 6 + ...) = x + x 3 + x 5 + x 7 + ... 
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+ x 2 +x 4 +x 6 +... ) ( x+x 3 +x 5 +x 7 +... ) (1 +x+x 2 +x 3 +x 4 ) ( x 2 +x 3 +x 4 +... ). 
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- x 2 )] [ x /(1- x 2 )] [(1- x 5 )/(1- x )] [ x 2 /(1- x )] 
 = [ x 3 (1 -x 5 )]/[(1- x 2 ) 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ụ 5 
V í dụ 5 . Tìm hàm sinh cho h n 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 +x 2 +x 4 +x 6 +.. .)(1 +x 5 +x 10 +x 15 +... )(1 +x+x 2 +x 3 +x 4 )(1 +x ) 
 = [1/(1- x 2 )] [1 / (1- x 5 )] [(1 -x 5 )/(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ó 
 . 
Vậy h n = n + 1 . 
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ố { h n , 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 ) = h 0 + h 1 x + h 2 x 2 + ... = 
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 k hai 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 h n . 
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ử 
 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 đó 
 c k = a 0 b k + a 1 b k- 1 + ... + a k b 0 = . 
Chuỗi Maclaurin 
Từ 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à 
 h k = g ( k ) (0) /k ! , k = 0, 1, ... 
Khi đó chuỗi 
 c hính là khai triển Macl aurin 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ùng 
Trong 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 + r 2 x 2 + r 3 x 3 + .... 
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 
	 f n = f n- 1 + f n- 2 , n 2 , 
	 f 0 = 0 , f 1 = 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ố Fibonaci 
Từ đó suy ra 
Ta có (1- x - x 2 ) = (1 - x ) (1 -  x ), với 
Viết lại F ( x ) dưới dạng 
Dãy số Fibonaci 
Từ đó tìm được 
Do đó 
Suy ra 
6. Một số dãy số đặc biệt 
Dãy số Stirling 
Dãy số Bell 
Dãy số Catalan 
Nhắc lại: Số lượng ánh xạ 
Cho các tập hữu hạn A = { a 1 ,, a m } và B = { b 1 ,, b n }. 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 | = n m . 
 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 2 
Số lượng toàn ánh từ tập A = { a 1 ,, a m } vào tập B = { b 1 ,, b n } 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 2 nd Kind). 
Định nghĩa. Số Stirling loại 2 , ký hiệu bởi S 2 ( 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 S 2 (4,2)=7. 
Trong nhiều tài liệu, số Stirling còn được ký hiệu bởi 
James Stirling 
1692 – 1770 
Scotland 
Số Stirling loại 2 
Ta sẽ xây dựng công thức đệ qui để đếm số S 2 ( m,n ). 
Ta có: 
S 2 (0,0)=1. 
Nếu m > 0, thì 
 S 2 ( m ,0) = 0, 
 S 2 ( m ,1)=1, 
 và S 2 ( m,m )=1. 
Định lý. Với m, n > 1, 
 S 2 ( m , n ) = S 2 ( m –1, n –1) + n ∙ S 2 ( m –1, n ). 
Chứng minh. 
	Ta cần đếm số cách phân hoạch tập m phần tử X = { x 1 , x 2 ,  , x m } ra thành n tập con. 
 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à { x m }; 
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à { x m } (tức là x m không đứng riêng một mình!). 
Ta có: 
| A | = S 2 ( m –1, n –1) . 
| B | = n ∙ S 2 ( m –1, n ), bởi vì có S 2 ( m –1, n ) cách phân hoạch X \ { x m } ra thành n tập con và có n cách xếp x m vào một trong số các tập con này. 
Từ đó 
 S 2 ( m,n )= | A | + | B | = S 2 ( m –1, n –1) + n ∙ S 2 ( m –1, n ). 
Định lý được chứng minh. 
 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ói chung để tính S 2 ( 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ố 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 
 A i = { a A| f ( a ) = b i }, i = 1, 2, ..., n, 
 Rõ ràng các tập A 1 , A 2 , ..., A n 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 A 1 , A 2 , ..., A n 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 ! S 2 ( m,n ) 
 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 ! S 2 ( m,n ) . 
Do đó từ công thức đã chứng minh ở mục trước 
Bảng giá trị của số Stirling loại 2 
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 
 trong đó S 2 ( n,k ) là số Stirling loại 2. 
Eric Temple Bell 
Born: 1883, ScotlandDied: 1960, USA 
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: 
Số Catalan 
Định nghĩa. Số Catalan thứ n , ký hiệu là C n , 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ố: 
 P 0.. n = x 0 x 1 x 2 ... x n . 
Ví dụ: 
Có 2 cách để tính P 0..2 : x 0 * x 1 * x 2 = ( x 0 *( x 1 * x 2 )) = (( x 0 * x 1 )* x 2 ) 
Có 5 cách để tính P 0..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 P 0..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ố Catalan 
Ta xây dựng công thức đệ qui để tính C n . 
Rõ ràng 
 C 0 = 1 và C 1 = 1. 
Giả sử n > 1. Sau khi đặt dấu ngoặc phân tách đầu tiên, tích x 0 x 1 x 2 ... x n được chia làm hai tích con. 
Ví dụ: P 0..4 = P 0..2 P 3..4 = ( x 0 x 1 x 2 ) ( x 3 x 4 ) 
Giả sử dấu ngoặc phân tách đầu tiên được đặt sau thừa số x k : 
 P 0.. n = P 0.. k P k +1.. n = ( x 0 x 1 x 2 ... x k ) ( x k +1 x k +2 ... x n ) 
Khi đó ta có C k cách tính P 0.. k , C n-k- 1 cách tính P k +1.. n , và do đó việc tính P 0 ..n có thể thực hiện bởi C k C n-k -1 cách . 
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ố x 0 , x 1 , ..., x n -1 , suy ra tổng số cách tính P 0.. n là: 
 C n = C 0 C n -1 + C 1 C n -2 + ... + C n -1 C 0 . 
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ố 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 
Tam giác phân đa giác 
C n 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: 
C 3 = 5 
C 2 = 2 
C 4 = 14 
C 5 = 42 
 Đường đi trên lưới ô vuông 
C n 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 2 n trên lưới ô vuông kích thước n n không vượt lên trên đường chéo. 
C 5 = 42 
C 4 = 14 
C 2 = 2 
C 3 = 5 
 Cây nhị phân đầy đủ 
C n 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 = 2 
n = 3 
n = 4 
n = 1 
C n là số cây nhị phân đầy đủ với n  + 1 lá. 
Có C 3 = 5 cây nhị phân đầy đủ với 4 lá: 
Cây nhị phân đầy đủ với n lá 
n 
2 
3 
4 
Toán rời rạc 
Ask questions! 
Toán rời rạc 
a n =5 a n -1 - 6 a n -2 +7 n , n 2, 
Toán rời rạc 
Toán rời rạc 
Toán rời rạc 
LiNoReCoCo Example 
Find all solutions to a n = 3 a n −1 +2 n . Which solution has a 1 = 3 ? 
Notice this is a 1-Li No ReCoCo. Its associated 1-Li Ho ReCoCo is a n = 3 a n −1 , whose solutions are all of the form a n = α 3 n . Thus the solutions to the original problem are all of the form  a n = p ( n ) + α 3 n . So, all we need to do is find one p ( n ) that works. 
Toán rời rạc 
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 a n = cn + d . 
	 cn+d = 3( c ( n −1)+ d ) + 2 n 	 (for all n )	 (2 c +2) n + (2 d −3 c ) = 0 	 (collect terms)		So c = −1 and d = −3/2 . 
	So a n = − n − 3/2 is a solution. 
Check: a n ≥1 = {−5/2, −7/2, −9/2,  } 
Toán rời rạc 
Finding a Desired Solution 
From the previous, we know that all general solutions to our example are of the form: 
	 a n = − n − 3/2 + α 3 n . 
	 Solve this for α for the given case, a 1 = 3 : 
	 3 = −1 − 3/2 + α 3 1 
	 α = 11/6 
The answer is a n = − n − 3/2 + (11/6)3 n . 
Toán rời rạc 
Double Check Your Answer! 
Check the base case, a 1 =3: 
	a n = − n − 3/2 + (11/6)3 n 
	 a 1 = −1 − 3/2 + (11/6)3 1  = −2/2 − 3/2 + 11/2 = −5/2 + 11/2 = 6/2 = 3 
Check the recurrence, a n = 3 a n −1 +2 n : 
− n − 3/2 + (11/6)3 n = 3[−( n −1) − 3/2 + (11/6)3 n −1 ]+2 n= 3[− n − 1/2 + (11/6)3 n −1 ] + 2 n = −3 n − 3/2 + (11/6)3 n + 2 n = − n − 3/2 + (11/6)3 n ■ 
Toán rời rạc 
Ask questions! 
Fall 2006 
Toán rời rạc 
Fall 2006 
Toán rời rạc 
Fall 2006 
Toán rời rạc 
Fall 2006 
Toán rời rạc 
Fall 2006 
Toán rời rạc 
Ask questions! 
Fall 2006 
Toán rời rạc 
Fall 2006 
Toán rời rạc