Phần thứ nhất

LÝ THUYẾT TỔ HỢP Combinatorial Theory

1

Toán rời rạc

Fall 2009

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

2

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 1.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

3

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)

4

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 (cid:0)

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, ..., A k 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).

=

( )

( ) N A

( ) N X N A

5

Toán rời rạc

-

Nguyên lý cộng: Ví dụ

ậ ắ

ộ c  c   đi  thi  đ u

ể ả

ơ ằ ữ ậ ộ ố

ử ộ ố ậ ố ữ ậ ắ

ồ ộ  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  ngoài.  Nam  có  10    n ắ ườ i. S  v n đ ng viên thi b n súng (k  c  nam và n )  ng 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  i?ườ ng

ữ ớ i: ả Chia  đoàn  thành  2  l p:  nam  và  n .  L p  n   l

ớ ố ữ ơ

ữ ạ ơ ầ ắ ắ ằ

ượ ố ữ ằ ủ ắ

 Gi 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  ố ấ ổ c s  n  b ng t ng s  đ u th  thi b n súng.  bài), ta đ ừ T   đó,  theo  nguyên  lý  c ng,  toàn  đoàn  có  10  +  14  =  24  i.ườ ng

6

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 k  ph n m m d y h c" và 10 đ   đ  tài v  ch  đ  "thi ộ ệ 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

ể ự ề

ở

ậ ấ ả ự

7

Toán rời rạc

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.ọ

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.

8

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ó

ữ ố ậ ồ

là 9? đúng 3 ký t

 Gi

ể ứ

ự

ở ị ở ị ở ị

•

khác 9  ự ự ự ể ử ụ

ọ

ứ ấ  v  trí th  nh t ứ  v  trí th  hai ứ  v  trí th  ba ứ ư  v  trí th  t ắ ộ ợ ấ ể ữ ố

9

Toán rời rạc

ậ ự i:ả  Xâu có th  ch a: • Ký t ở ị • ho c ký t ặ  khác 9  • ho c ký t ặ  khác 9  • ho c ký t ặ  khác 9  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 ố

1.2. Nguyên lý nhân The 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 1n2 ... n k.

... (cid:0)

A 2 (cid:0)

A k)  =  N(A 1) N(A 2) ... N(A k),

 Mét hÖ qu¶ trùc tiÕp cña nguyªn lý nh©n:     N(A 1 (cid:0) 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 .

10

Toán rời rạc

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 ng uy ª n lý   nh©n tæ ng  q u¸t:

 Gi¶ sö ta x©y dùng bé cã thø tù k thµnh phÇn (a1, a2,

11

Toán rời rạc

..., 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.

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 (cid:0)

Hà nội

Sài gòn

Huế

12

Toán rời rạc

4 = 12 c¸ch.

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 (cid:0)

30 = 6000.

20 (cid:0)

13

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

ỏ ắ

ầ

ấ ừ

ạ

ỏ ạ  ba m u xanh, đ , tr ng sao cho:

v ch l y t

ế

ạ

a) Không có hai v ch liên ti p nào cùng màu

ố

ố

ủ

ừ

ờ ở

trên xu ng.

ạ b) Không có hai v ch nào cùng màu ạ i.ả  Đánh s  các v ch c a lá c  b i 1, 2, 3 t ợ ng h p a) ủ ạ

ọ

ủ

ạ

ọ

ượ

(không đ

ủ

ạ

 Sau khi màu c a hai v ch 1, 2  đã ch n, màu c a v ch 3 có 2 cách

ọ

 Gi ườ Tr  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  ủ ạ ọ ạ i màu c a v ch 1).  c ch n l ọ ủ ủ ạ ượ i màu c a v ch 2).

ch n (không đ

ờ ầ

ườ

ế

ợ

ạ ọ ạ c ch n l ố  Theo  nguyên  lý  nhân  s   lá  c   c n  đ m  trong  tr

ng  h p  a)  là

3.2.2=12

14

Toán rời rạc

Nguyên lý nhân: Ví dụ 3 (tiếp)

ườ

ợ ng h p b):  ủ ạ

ọ

ượ

ủ

ạ

Tr  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  ch n  l i  màu  c a

ủ ạ ọ có  2  cách  ch n  (không  đ ạ v ch 1).

ọ ạ

ượ

ọ

ủ ạ  Sau  khi  màu  c a  hai  v ch  1,  2  đã  ch n,  màu  c a  i màu

ọ c ch n l

ủ ạ v ch 3 có 1 cách ch n (không đ ủ ạ 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

15

Toán rời rạc

Nguyên lý nhân: Ví dụ

ồ

ứ

ọ

ọ ạ

ữ ố

i ch  s  đã ch n

ị ữ ố ữ ố ậ ầ ầ ượ ừ t t ng v  trí

ứ

vào v  trí th  nhât)

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 • Ký t • Ký t

• Ký t • Ký t ổ T ng c ng có 10*9*8*7 = 5040 xâu c n đ m.

ế ầ

ỗ

ọ  có 10 cách ch n

ọ

cu i cùng có  5 cách ch n

ự ố ộ

ế

ầ

ế

ự ứ ấ ọ  th  nh t có 10 cách ch n ự ứ  th  hai có 9 cách (không ch n l ị ọ ự ứ  th  ba có 8 cách ch n ọ ự ứ ư  th  t  có 7 cách ch n ộ ữ ố ẵ ở b) k t thúc b i ch  s  ch n? ự ự ầ Ba ký t  đ u tiên m i ký t Ký t ổ T ng c ng có 10*10*10*5 = 5000 xâu c n đ m.

16

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

ằ

ể ả ượ

ề

i đ

c nhi u bài toán

ứ ạ

ị

 B ng cách đó ta có th  gi ơ thú v  và ph c t p h n

17

Toán rời rạc

Chụp ảnh đám cưới

ụ ả ể

m t đám c ỉ ồ ỷ ệ ườ i  tham  gia  vào  vi c  ch p  nh  k   i, trong đó có cô dâu và chú r . Ta xét  ườ Xét  bài  toán:  Có  10  ng ướ ệ ở ộ ni m  ứ ả 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?

ữ

ế

ỗ VÀ sau đó x p ch  cho nh ng nhân

ứ ả

ạ

ỗ ế Qui t c nhân: X p ch  cho cô dâu  i trong b c  nh.

ắ ậ v t còn l

ướ ế ế

ể ứ ở

ỗ

ị

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  ậ i đ  ch n nhân v t th  hai, 8 ng nhân: Có 9 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

18

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ú

ữ

ế

ể

ế

ậ

ạ

i  trong

r ?ể ắ Qui  t c  nhân:  X p  dâu/r  VÀ  sau  đó x p nh ng nhân  v t  còn  l ứ ả b c  nh

ể

ướ ế ế

c h t x p dâu và r

ị

ị

ể

i

ổ

ộ

T ng c ng có 30 kh  năng

ế

ậ

ạ

ỗ

ứ ả

ắ

i  trong  b c  nh  theo  qui  t c

ườ ể

ứ

ậ

ọ

ườ ể

ậ

ọ

i đ  ch n nhân v t th  ba, 7 ng

ứ i đ  ch n nhân v t th

Tr • 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 ạ ể ế • ả ế Ti p  theo,  x p  ch   cho  4  nhân  v t  còn  l nhân • Có 8 ng , ...ư 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

19

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

ỉ ế

ắ ộ

ắ

ế

ế

ậ

ể ứ ở ộ

ướ ế ế

i ị

c h t x p cô dâu: Cô dâu có th  đ ng

ế

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 đ   ượ

c

ế ọ ọ

ể

m t trong 6 v  trí Tr ắ ế Ti p đ n, x p nh ng nhân v t khác theo qui t c nhân: Có 8 ng ứ ậ ch n nhân v t th  hai, 7 đ  ch n nhân v t th  ba, v.v. (Ta không đ ch n chú r !)

ổ

ộ

ắ

ả

ể

ặ

ố ượ

ư

ố ng kh  năng cũng gi ng nh  cô dâu: 40 320

S  l

ắ ộ

ả

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 • ả Qui t c c ng cho 40 320 + 40 320 = 80 640 kh  năng

20

Toán rời rạc

Chụp ảnh đám cưới

ộ ả ượ ờ c l i gi

 M t cách khác đ  thu đ c) Có bao nhiêu b c  nh mà trong đó có m t ch  m t ng

i câu c) ặ ể ứ ả ỉ ộ ườ 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

21

Toán rời rạc

ộ ổ

Số lượng Mật khẩu

ề

ồ

ỗ ẩ

ự

ự

ừ

6 đ n 8 ký t

ử ụ ế ữ ố

ỗ , m i ký t ẩ ậ

ả ẩ

ộ

M i cá nhân s  d ng m ng máy tính đ u có m t  ậ ạ ữ  là ch  cái  kh u g m t ấ ứ ậ ặ 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  ộ ng m t kh u đ  dài 6, 7, và

ươ ứ

và P6, P7, P8 là s  l ng  ng, thì  8, t

P = P6+P7+P8

22

Toán rời rạc

Số lượng Mật khẩu

ố ượ

ậ

ẩ

ồ

ự ứ

ng m t kh u g m 6 ký t

ch a ít

P6 = s  l ấ

ữ ố

ộ nh t m t ch  s

ự ừ ớ

ẩ

ổ ậ

ố ồ ố ậ = (t ng s  m t kh u g m 6 ký t ) tr  b t (s   ữ ố ứ ự ồ ẩ  không ch a ch  s ) m t kh u g m 6 ký t

= (26+10)(26+10)(26+10)(26+10)(26+10) –

(26)(26)(26)(26)(26)(26) = 366 – 266

= 1 867 866 560

23

Toán rời rạc

Số lượng Mật khẩu

ươ ự ư ậ T ng t nh  v y, ta có

P7 = 367 – 267= 70 332 353 920

P8 = 368 – 268= 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?

24

Toán rời rạc

(2 684 483 063 360/200 000 000)/(60*60) gi ờ

ồ ế ầ ồ G n 4 ti ng đ ng h !

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

25

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

ấ ượ ử ụ ể c s  d ng đ

ả ổ ợ ơ ả ứ ạ h p c  b n đ ơ gi ế i các bài toán đ m ph c t p h n

 Gi

ổ ả ử X là t p ậ n ph n t ả , mà không gi m t ng quát ta

26

Toán rời rạc

ậ ố s   ể có th  coi ầ ử ồ X là t p g m các s  1, 2, ..., n.

Chỉnh hợp lặp

ị ợ ặ ỉ n

Ta g i ọ ch nh h p l p ch p m t ầ ừ  ph n t ỗ ầ ử ậ   ứ ự ồ m  thành  ph n,  m i  thành g m

 Đ nh nghĩa. c a ủ X  là  b   có  th   t ộ ph n đ u là ph n t

ề ầ ầ ử ủ X. c a

 Ký hi u s  l

m

ệ ố ượ ợ ặ ỉ ầ ử 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

X, i = 1, 2, ..., m.

ợ ặ t c  các ch nh h p l p ch p ậ m t ừ n ph n ầ

(a1, a2, ..., am), ai (cid:0) ễ ấ ậ ấ ả ỉ  D  th y t p t ậ ử ủ X chính là Xm. Vì v y, theo nguyên lý nhân ta có  c a t

m = nm.

 Đ nh lý 1.

27

Toán rời rạc

ị An

Chỉnh hợp lặp

 VÝ dô  1. TÝnh sè ¸nh x¹ tõ tËp m phÇn tö U = {u1, u 2, ...,

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  V, i=1, 2, ..., m. Tõ ®ã

(f(u 1), f(u2), ..., f(u m)), trong ®ã f(ui) (cid:0) 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µ 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µ 2n.

28

Toán rời rạc

Chỉnh hợp lặp

ả ầ

ậ ự

ộ

ộ ố ượ ể ế ậ

 Gi

ố  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

i:ả    4100  hay  1004 ?

ố ầ ở ộ ể ể ễ

1, ..., b100) trong đó bi (cid:0) ừ

ầ

ứ

100.

29

Toán rời rạc

g m 100 thành ph n (b ự ậ ủ ế ố ầ ố ỗ  M i  cách  phân  b   c n  tìm  có  th   bi u  di n  b i  b   có  ứ ự ồ th  t  {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

Chỉnh hợp không lặp

ặ

ộ

ậ m t ợ  Ta g i ọ ch nh h p không l p ch p  ầ   g m  ầ ừ n ph n ầ ỉ ứ ự ồ m  thành  ph n,  m i  thành  ỗ ầ ử ủ X,  các  thành  ph n  khác  nhau    c a

ệ ố ượ ỉ

ng ch nh h p không l p ch p  ỉ ậ m t ặ ặ ợ ừ n ph n ầ m (cid:0) ợ ể ồ ạ m. Rõ ràng, đ  t n t i ch nh h p không l p, thì

ị  Đ nh nghĩa. ử ủ X  là  b   có  th   t   c a  t ề ầ ph n  đ u  là  ph n  t ừ t ng đôi .  Ký hi u s  l  là ử Pn t n.

 Theo  đ nh  nghĩa,  m t  ch nh  h p  không  l p  ch p

ị ỉ ợ ặ ậ m  t ừ n

ễ ở c a ph n t ầ ử ủ X có th  bi u di n b i

)!

! n ặ ( n m

30

Toán rời rạc

- ậ m  t ừ n -

ộ ể ể          (a1, a2, ..., am), ai (cid:0)  X, i = 1, 2, ..., m, ai (cid:0)  aj, i (cid:0)  j. = - + = m 1) 1)...( ( n m n n P ợ ố ượ ỉ ế ệ  Vi c  đ m  s   l ng  ch nh  h p  không  l p  ch p  n ệ ể ự ầ ử  có th  th c hi n theo nguyên lý nhân. Ta có ph n t ị  Đ nh lý 2.

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),  V, i=1, 2, ..., m, f(ui)(cid:0)  f(uj), i(cid:0)  j. Tõ

f(u 2), ..., f(u m)), trong ®ã f(ui) (cid:0) ®ã 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

ớ

ỗ

ệ

ề

ượ

ồ ồ

ọ

ọ ồ v i đi u ki n không đ có 10 ch  ng i  ế ố

1 đ n 4, các ch  ng i t

i.ả  Đánh s  các h c sinh t  Gi ọ ỗ

ể ể

ừ ế

ế

ế

ầ

ỗ ậ ố

ừ

ế

ế

ầ

c phép ng i lòng. ồ ừ ỗ ế  1 đ n 10.  ở ộ ứ ự ễ   ồ ủ ọ ỗ  {1, 2, ..., 10} là ch  ng i c a h c sinh i.   gj, i(cid:0)  j; do đó m i cách x p c n đ m là  ậ  10. V y s  cách x p c n đ m

ầ ế 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 (cid:0) (cid:0) ừ ề ầ ệ T  đi u ki n đ u bài g i ặ ợ ỉ ộ m t ch nh h p không l p ch p 4 t 4 = 10.9.8.7 = 5040. là P10

31

Toán rời rạc

Chỉnh hợp không lặp

ể ả

ự ế

ể ậ

ậ

i ví d  2 có th  l p lu n tr c ti p

 Chú ý: Đ  gi

ụ 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ế

32

Toán rời rạc

Hoán vị

 Đ nh  nghĩa.  g m

c a  ề ầ ộ ầ ử ủ X  là b   có  ầ ử

ừ ị ị ừ n  ph n  t  Ta  g i ọ hoán  v   t ầ ỗ ứ ự ồ n thành ph n, m i thành ph n đ u là ph n t th  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 ầ ử Pn.   là

 Theo đ nh nghĩa, m t hoán v  t

ộ ị ừ n ph n t ầ ử ủ X có th  ể c a

ể ở

 Rõ ràng Pn = Pn =

ị ễ bi u di n b i           (a1, a2, ..., an), ai (cid:0)

= 1) ... 2 1

!

( n

n

P n

 Đ nh lý 3.

33

Toán rời rạc

- (cid:0) (cid:0) (cid:0) X, i = 1, 2, ..., n, ai (cid:0)  aj, i (cid:0)  j. ậ n. Vì v y, ta có = (cid:0) n n P n ị

Hoán vị

 VÝ  dô   1. 6 ng­êi ®øng xÕp thµnh mét hµng ngang

 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

®Ó chôp ¶nh. Hái cã thÓ bè trÝ bao nhiªu kiÓu?

 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!

34

Toán rời rạc

trªn mét m¸y vi tÝnh. Hái cã bao nhiªu c¸ch?

Hoán vị

 Ví d  3.ụ  Có bao nhiêu song ánh t ư ậ

ừ ậ n ph n t

ỗ t p  ượ ọ ầ ử X vào    ộ c g i là m t phép

 Gi

chính nó? (M i song ánh nh  v y đ th ).ế

i.ả Mçi song ¸nh f cÇn ®Õm ®­îc x¸c ®Þnh bëi bé  V, i=1, 2, ...,

¶nh (f(u1), f(u2), ..., f(un)), trong ®ã f(u i) (cid:0) n, f(ui)(cid:0)  f(uj), i(cid:0)  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

ệ ệ ỗ

 Gi

ộ ệ 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

35

Toán rời rạc

i:ả  n!

Tổ hợp

 Đ nh nghĩa.

ị ổ ợ ừ n ph n t h p ch p

ậ m t ầ ề ỗ ầ ử ủ X là b  ộ  Ta g i ọ t  c a  ầ ứ ự ồ m  thành  ph n,  m i  thành  ph n  đ u  là g m

không  có  th   t ph n t

m (đôi khi

ầ ử ủ X, các thành ph n khác nhau t ng đôi .  là   h p ch p ầ ậ m t ừ n ph n t ng t ừ ầ ử Cn

ừ n  ph n  t ầ ử ủ X  có    c a

ẽ ử ụ ị ể ể ễ h p  ch p  ở b  không có th  t

c a  ệ ố ượ ổ ợ  Ký hi u s  l ệ  C(n,m)) ta s  s  d ng ký hi u ộ ổ ợ  Theo  đ nh  nghĩa,  m t  t ộ th  bi u di n b i           {a1, a2, ..., am}, ai (cid:0) ả ớ  V i gi  thi ừ n ph n t ầ ử

ộ ễ ế  X={1, 2,...,n}, m t t t ể ể c a ủ X có th  bi u di n b i ậ m  t ứ ự  X, i = 1, 2, ..., m, ai (cid:0)  aj, i (cid:0)  j. ậ m t ộ ổ ợ ở b  có th  t

36

Toán rời rạc

(cid:0) X, i = 1, 2, ..., m, 1 (cid:0) n. h p ch p  ứ ự  a1 < a2 < ...

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.

1)

!

 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µ 1)( n

- + n m

( n n

hay

- -

!(

)!

2)...( ! m

n m n m

37

Toán rời rạc

-

Tổ hợp

ị

!

=

(c�n k� hi�u l� ( ,

) hay

C n m

m C n

!(

)!

 Đ nh lý 4.  n m n m

n � � ) � � 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  lµ mét sè nguyªn, ta nhËn ®­îc mét th c c a đ nh lý 4 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!.

38

Toán rời rạc

ứ ủ ị

Tổ hợp

 VÝ dô  1. Cã n ®éi bãng thi ®Êu vßng trßn. Hái ph¶i

 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

tæ chøc bao nhiªu trËn ®Êu?

 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µ

39

Toán rời rạc

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  (cid:0)  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?

C(n,4) = n(n-1)(n-2)(n-3)/24.

Bài toán chia kẹo

ố

ỏ

s

ả ử k  và  n  là  các  s   nguyên  không  âm.  H i  ươ

ệ

Gi ph

ng trình sau đây có bao nhiêu nghi m?

+ + +

L

; n

t

+ = t k

2 L ,

,

t 3 t

Z+

t 1 , t t 1 2

k

ộ

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?

40

Toán rời rạc

(cid:0)

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 Room ẫ

ố ượ ấ

ề

ả j,  ề ặ j = 1, 2, ..., n; thì v n đ  đ t ra d n v  bài toán:  ỏ H i ph

t

+ =L t

n

ươ ng trình sau đây + + + t t 1 3

2

k

ệ     có bao nhiêu nghi m nguyên không âm?

41

Toán rời rạc

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

D5

D4

D2 D3

ộ

ạ

ỗ ộ

• Th  ả n qu  bóng vào  ả

n h p còn l

ả i, m i h p 1 qu .

42

Toán rời rạc

Giải bài toán chia kẹo

ụ ớ • Ví d , v i n=16, k=6

D4

D2 D3

D5

D1

ả ướ ả • Th  các qu  bóng tr

ố

Room1

Room6

Room2

Room3

Room4

Room5

43

Toán rời rạc

ả ữ ả 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).

Giải bài toán chia kẹo

ư ậ ộ i t

ồ ạ ươ ộ ng  ng 1­1 gi a m t cách phân  ố n+k­1 ữ ứ ộ ọ k­1  h p  trong  s

• Nh  v y, rõ ràng t n t ả ổ b   các  qu   bóng  và  m t  cách  ch n  ộ h p làm vách ngăn.

1

1 k n kC + -

ấ ả • Do có t t c -

ộ cách  ch n ọ k­1  h p  t

ố

ẹ ố

ệ

n

k

2

44

Toán rời rạc

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) ng trình: 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  k  em  bé  và  cũng  chính  là  s   nghi m  chia  n  cái  k o  cho  ủ nguyên không âm c a ph t t t 1 ươ L3

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  ỗ ươ ượ ấ ộ c ít nh t m t cái? Hay t k  ng

ươ em bé mà trong đó m i em đ ươ đ ỏ ng: H i ph ng trình sau đây :

t1 + t2 + ... + tk = n.

ươ có bao nhiêu nghi mệ nguyên d ng?

ẹ

ỗ ế c h t chia cho m i em 1 cái k o,  c  chia  cho

ề ử ụ ế ả

ẹ ố ầ ướ • Tr ướ ượ đ cách  chia  n­k  cái  k o  cho  tr c, ta có đáp s  c n tìm là - ẹ n­k cái k o còn l ạ ẽ i s   ỏ ẫ k  em  bé.  Bài  toán  d n  v :  H i  có  bao  nhiêu  k  em  bé.  S   d ng  k t  qu   bài  :

1 1

k nC

45

Toán rời rạc

-

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 )

0 b) §iÒu kiÖn ®Çu C(n,0) = 1; C(n,n) = 1, n (cid:0)

c) C«ng thøc ®Ö qui

C(n,m ) = C(n-1,m ) + C(n-1, m -1), n > m > 0

ệ ề ự đ nh nghĩa c a h  s  t

ấ ứ ủ ệ ố ổ ế ừ ị   ờ ử ể ạ i  có  th     ch ng  minh  nh   s

46

ị

ầ  Đi u ki n đ u suy tr c ti p t h p. ợ C¸c tính  ch t  còn  l ứ ụ d ng công th c trong đ nh lý 4. Toán rời rạc

Tổ hợp

ể

t  c   các  h   s   t

ệ ố ổ ợ ế ầ ượ t  l n  l

ấ ả c  tính  và  vi

ỗ

ỗ ộ ứ

ừ

ộ

ớ

ỉ ằ   h p  ch   b ng  phép  ừ t  theo  t ng  dòng  ị n=0,  1,  ...),  trên  m i  dòng  chúng  t theo t ng c t (m i c t  ng v i m t giá

c tính và vi

ộ ướ

ừ  T   b)  và  c),  ta  có  th   tính  t ượ ệ ố ộ c ng.  Các  h   s   này    đ ộ ứ ớ ỗ (m i  dòng  ng  v i  m t  giá  tr   ế ầ ượ ượ t l n l đ ả 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 Pas cal.

47

Toán rời rạc

Tổ hợp

 Tam giác Pascal, n=8

48

Toán rời rạc

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µ

n

n m

n

m

=

+

+

+

...

+ + ...

x

(

n )

x

y

y

y

0 n

n n

m C x n

C

C n

-

i

n i

-

=

i C x y n

=

0

i

(cid:0)

49

Toán rời rạc

C«ng thøc trên ®­îc gäi lµ khai triÓn nhÞ thø c Ne wton vµ c¸c hÖ sè tæ hîp cßn ®­îc gäi lµ c¸c hÖ s è  nhÞ thø c.

Tổ hợp

n

1

n

+

...

x

x

+ (1 )n x

1 n

n n

=

+ + (*)

 Trong c«ng thøc Niuton đ t ặ y=1 ta có: + 0 1 n C C C x n n

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Ó.

50

Toán rời rạc

- -

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

51

Toán rời rạc

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

52

Toán rời rạc

3.1. Phát biểu nguyên lý

ậ ợ ừ ng h p hai t p:

(cid:0) (cid:0) B|         (1) ườ  B| = |A| + |B| ­ |A(cid:0)

 Nguyên lý bù tr  trong tr            |A(cid:0) • Gi ử t

ầ ử ầ , B có 3 ph n t và có 1 ph n

ầ ử ủ ợ ậ ứ  c a h p hai t p là 5+3­1 = 7, ch

 CM:

53

Toán rời rạc

ả ử ầ ử  s  A có 5 ph n t ộ ẫ ả  thu c vào c  A l n B • Khi đó s  ph n t ố ả không ph i là 8

Nguyên lý bù trừ

(cid:0)  |(A(cid:0) B)(cid:0) C|

(B(cid:0) C)|

ấ ợ ậ ậ ườ ả ử s  A, B, C là ba t p b t ng h p 3 t p: Gi

(2)

ở ộ  M  r ng cho tr ỳ k . Khi đó: |A(cid:0) B (cid:0) C|  = |(A (cid:0) B)(cid:0) C)|  = |A(cid:0) B | + |C| (cid:0) = |A| +|B | + |C| (cid:0)  |A(cid:0) B| (cid:0)  |(A(cid:0) C)(cid:0) = |A| +|B| + |C| (cid:0)  |A(cid:0) B| (cid:0)  |A(cid:0) C|(cid:0)  |B(cid:0) C)|+ |A(cid:0) B(cid:0) C)| V yậ |A(cid:0) B(cid:0) C| = |A|+|B|+ |C| (cid:0)  |A(cid:0) B| (cid:0)  |A(cid:0) C|(cid:0)  |B(cid:0) C)|+ |A(cid:0) B(cid:0) C)|

54

Toán rời rạc

ự ế ể ứ ậ ậ ằ Có th  ch ng minh b ng l p lu n tr c ti p!

Nguyên lý bù trừ

|A(cid:0) B(cid:0) C| = |A|+|B|+ |C| (cid:0)  |A(cid:0) B| (cid:0)  |A(cid:0) C|(cid:0)  |B(cid:0) C)|+ |A(cid:0) B(cid:0) 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 ầ c tính hai l n, vì v y ph i

ả tr  b t

ổ ượ ư ậ

ủ

ầ ử  chung c a A  ộ ầ ừ ớ  đi m t l n. T ng  ầ  chung c a A và C và các ph n

và B đ ự t ử t

ậ ầ ử ố ớ  nh  v y đ i v i 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   ổ ư ượ ậ c tính đ n trong t ng  chung c a c  ba t p A, B và C ch a đ ả ộ ủ bù l c a 6 s  h ng đ u tiên. Vì v y ph i c ng

iạ .

55

Toán rời rạc

Nguyên lý bù trừ

 §Þnh lý.  Gi¶ s ö A1, A 2, ... , A m lµ c¸c tËp h÷u h¹n. Khi ®ã

m

1

(

1 )

...

)

...

m

m

1

2

N A ( 1

A 2

A

N

N

N

=

=

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

...

),

1,2,...,

k

m

k

( N A i 1

��� A i 2

A i k

1

< < < (cid:0) ... i i i m 1 2 k

(cid:0) trong ®ã  N (cid:0)

(Nk  lµ tæ ng s è  phÇn tö cña tÊt c¶ c¸c tËp lµ giao cña k

56

Toán rời rạc

(cid:0) ... (cid:0) A2 tËp lÊy tõ m  tËp ®∙ cho, nãi riªng N1 = N(A1) + ... + N(Am),                       Nm = N(A1 (cid:0) Am) ).

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 .

A2 (cid:0)

 §Ó chøng minh c«ng thøc cña nguyªn lý bï trõ, ta sÏ tÝnh xem mçi . . . (cid:0) Am ®­îc ®Õm bao nhiªu lÇn

phÇn tö cña tËp A1 (cid:0) trong vÕ ph¶i:

. . . (cid:0)

 XÐt mét phÇn tö tuú ý a (cid:0)

A1 (cid:0)

A2 (cid:0) 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

57

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 Toán rời rạc

= 1

Tõ ®ã suy ra ®¼ng thøc cÇn chøng minh lµ ®óng

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¶.

. . . (cid:0)

A2 (cid:0)

 Gäi(cid:0) N lµ sè cÇn ®Õm.  Do A1 (cid:0)

. . . (cid:0)

A2 (cid:0)

Am)

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ã:          (cid:0) N = N(X )– N(A1 (cid:0) = 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(cid:0) N qua c¸c Nk trong tr­êng

hîp c¸c sè nµy dÔ tÝnh to¸n h¬n.

58

Toán rời rạc

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

59

Toán rời rạc

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 (cid:0)  Khi ®ã A3 (cid:0)

X : x chia hÕt cho i} , i = 3, 4, 7. A4 (cid:0)

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µ

A4 (cid:0)

A7) = 10000 – (N1 ­ N2 + N3).

N(X) - N(A3 (cid:0)  Ta cã

N1 = N(A3) + N(A4) + N(A7)

= [10000/3] + [10000/4] + [10000/7] = 3333 + 2500 + 1428 =7261,

60

Toán rời rạc

Nguyên lý bù trừ

A4) + N(A3 (cid:0) A7) + N(A4 (cid:0) A7)

N2 = N(A3 (cid:0) = [10000/(3(cid:0) 4)] + [10000/(3(cid:0) 7)] + [10000/ (4(cid:0) 7)]

= 833 + 476 + 357 = 1666,            N3 = N(A3 (cid:0) A4 (cid:0) A7) = [10000/(3(cid:0) 4(cid:0) 7) ] = 119,

ë ®©y ký hiÖu [ r ] ®Ó chØ sè nguyªn lín nhÊt

 Tõ ®ã sè l­îng c¸c sè cÇn ®Õm lµ

kh«ng v­ît qu¸ r.

61

Toán rời rạc

10000 - 7261 + 1666 - 119 = 4286.

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µ

62

Toán rời rạc

256 + 256 - 64 = 448.

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ù

63

Toán rời rạc

(p1, p 2, ..., 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­.

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

 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ã:

cã l¸ th­ nµo ®óng ®Þa chØ.

64

Toán rời rạc

(cid:0) (cid:0) N = N(X ) – N1 + N2 – ...+(– 1)nNn trong ®ã (cid:0) 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Ø.

Nguyên lý bù trừ: Bài toán bỏ thư

=

=

...

),

1,2,...,

 Chó ý lµ N

k

n

k

( N A i 1

��� A i 2

A i k

(cid:0)

1

n

< < < (cid:0) ... i i i 1 2 k

 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 ®ã

n

(cid:0)

(

(cid:0)

N

n 1 ! (

...

)

1 1 !

1 2 !

1 ) n !

n

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

(

(cid:0)

...

1

 VËy x¸c suÊt cÇn t×m lµ: ) 1 1 n ! ! 1

1 ! 2

65

Toán rời rạc

(cid:0) (cid:0) (cid:0) (cid:0)

Nguyê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:

2

3

4

5

6

7

8

9

10

11

1

2

9 44 265  1854  14833  133496  1334961  4890741

n Dn

66

Toán rời rạc

Số lượng toàn ánh

Gi s ả ử A={a1, a2, ..., am } và B={b1, b2, ..., bn }.

ứ c ta đã ch ng minh:

m).

ố ượ ố ượ ố ượ Trong các ph n tr •  S  l •  S  l •  S  l ướ ầ ạ ừ A vào B là nm ng ánh x  t ơ ng đ n ánh t ng song ánh t ừ A vào B là n(n­1)...(n­m+1) (n (cid:0)   ừ A vào B là n!  (n=m).

ừ A vào B là toàn ánh n u v i m i ph n t

ề ượ

ứ

ớ

c a  ố

ầ ế ố ượ gi s ờ ả ử m(cid:0) n,  ta  c n  đ m  s   l ng  toàn  ánh  t ừ A

ắ ạ  Ánh x  ạ f  t c  ặ ươ ng  ng v i đúng m t ph n t

ế ỗ  c a

ầ ử b thu cộ  B  ớ ầ ử ủ A qua ánh x  ạ f  ừ

ầ ử ủ B, nên mu n có toàn ánh t

ả

m (cid:0)

67

Bây  gi vào B. ỗ i:  Nh c l ượ a thu c ộ A sao cho f(a)=b. (Do m i ph n t đ u tìm đ ộ c đ t t đ  n.)  A vào B thì rõ ràng ta ph i có

Số lượng toàn ánh

ị ủ

t c

ộ ố ấ ả bi đ u thu c mi n giá tr  c a

ề ằ

A

B

ề

ề Ta mu n t f. G i ọ Pi là tính ch t "ấ bi không n m trong  mi n giá tr  c a

ị ủ f ".

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:ệ

ậ

ạ ừ A vào B có tính

Pi = t p các ánh x  t           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

68

=

=

...

),

1,2,...,

N

k

n

k

( N A i 1

��� A i 2

A i k

1

n

i 2

i 1

< < < (cid:0) ... i k

(cid:0) (cid:0)

Số lượng toàn ánh

ừ ố ượ

ế

ầ

ng toàn ánh c n đ m là:

 Theo nguyên lý bù tr  s  l                     N – N1 + N2 – ... +(–1)n Nn.  Ta có:

ạ

ề

ị

bi trong mi n giá tr ,  nên

N(Pi) = (n­1)m,

ố

ị

(cid:0) Pj) ­ s  ánh x  không có

ề bi và bj trong mi n giá tr ,  nên

=

� � �

...

)

m )

• N ­ s  ánh x  t ạ ừ m­t p ậ A vào n­t p ậ B: nm ố • Do N(Pi) ­ s  ánh x  không có  ố do đó N1 = C(n,1) (n­1)m ạ (cid:0) Pj) = (n­2)m , do đó  N2 = C(n,2) (n­2)m. ( n k

( N P i 1

P i 2

P i k

• Do N(Pi N(Pi ổ

• 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.

69

-

Số lượng toàn ánh

 Ta vi       nm – C(n,1)(n­1)m + C(n,2)(n­2)m – ...+ (­1)n­1C(n,n­1)1m. ướ ạ d

ế ọ ứ t g n công th c

i d ng sau đây:

m

n

1

C

+ m 1)

- + - m 2)

...

m 1 1

1 C n ( n

n n

- - - - -

m

m

n

n

+ 1

n =

C

n

C

C

(

0)

2 C n ( n + 1)

( 1) - + - m 2)

...

( 1)

m 1 1

( 1)

0 n

1 C n ( n

2 C n ( n

n n

n m 0 n

n

k

m

=

- - - - - - -

( 1)

C n k (

)

k n

=

k

0

70

- - (cid:0)

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

71

Toán rời rạc

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 và  c tr  các b ộ ố 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

72

Toán rời rạc

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

73

Toán rời rạc

4.1 Xây dựng công thức đệ qui

 Ví  d   1.ụ  Xây  d ng  công  th c  đ   qui  cho  ầ ử X.

ệ ự C(n,k)  ­  s  ố

ứ ầ ử ủ ậ  n ph n t c a t p k ph n t

ậ ng t p con  i:ả

ượ l  Gi ị  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   X. Phân t p các t p con

74

Toán rời rạc

ự ầ ử x (cid:0) ộ ầ ử ủ X ra thành 2 t p:ậ ầ ử ậ k ph n t ầ ử ậ k ph n t ứ x  có ch a  ứ x  không ch a ố ị C(n,k). C  đ nh m t ph n t k ph n t  c a  • A – t p các t p con  ậ • B  – t p các t p con  ậ

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 ầ ử ủ X. Do đó, theo nguyên lý c ng:ộ

ạ ủ ậ ấ ả ậ t c   các t p

con k ph n t ạ  c a

C(n,k) = |A| + |B|.  Ta có:

ỗ ậ ầ ử ạ còn l i

• Do m i t p con trong  ủ c a nó là m t t p con

ộ ậ A có ch a ứ x, nên k­1 ph n t k­1 ph n t ầ ử ủ ậ X \{x}, suy ra c a t p

ươ ng t

 V y,ậ           C(n,k) = C(n­1, k­1) + C(n­1,k),  n > k > 0      (2)

75

Toán rời rạc

|A| = C(n­1,k­1) • T ự ư ậ  nh  v y,              |B| = C(n­1, k)

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

ứ ệ ị ủ C(n,k): giá tr  c a

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;

76

Toán rời rạc

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  ọ C*(n,k)  là  s   phép  toán  “gán  giá  tr ”  ph i  th c

ả ả ự ự ố ị

ừ ế ậ v y,  n u  g i  ở ệ ệ 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 C*(n,k) tho  mãn công th c đ  qui t ng t ự ư ệ ố ổ    nh  h  s  t

ả ứ    t c là  h p ợ C(n, k), do đó:

(cid:0) n!/[k!(n­k)!]

ớ k = n/2. n l n và  ể ặ ễ ộ C*(n,k) (cid:0) ị    và giá tr  này là r t l n khi   D  dàng xây d ng m t hàm l p đ  tính giá tr  c a ị ủ C(n,k) m t ộ

77

Toán rời rạc

ấ ớ ự ả ơ ệ cách hi u qu  h n.

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

 Gi¶i: Gäi sè phÇn mÆt ph¼ng ®­îc chia bëi n ®­êng

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 ?

th¼ng lµ S n. Râ ràng

S 1 = 2,

 XÐt n > 1, ta t×m c«ng thøc ®Ö qui cho S n.

78

Toán rời rạc

(3)

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 S n-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

2 S n = S n­1 + n, n (cid:0)

79

Toán rời rạc

(4)

4.1 Xây dựng công thức đệ qui

G3

phần 4

l1

phần 3

G2

G1

phần 2

phần 1

l4

l3

l2

80

Toán rời rạc

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 S k = S k-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)/2

81

Toán rời rạc

4.1 Xây dựng công thức đệ qui

ứ ệ

ợ ặ ộ ố ỉ ị ừ fn là s  ch nh h p l p   0, 1 (cũng chính là xâu nh  phân đ  dài

 Ví d  3.ụ  Xây d ng công th c đ  qui cho  ự ch p ậ n t ầ ử  hai ph n t ố n) không ch a hai s  0 li n nhau.

 Gi

ứ ề

i.ả  Ta có

f1 = 2; f2 = 3

ỉ ợ ầ ế ậ s Gi

ậ ợ ầ ở ị ứ ế ỉ ầ  v  trí đ u tiên;

ợ ầ ở ị ứ ế ậ ỉ ầ  v  trí đ u tiên;

ủ ậ ấ ả ạ ạ ỉ ả ử 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  • B  – t p các ch nh h p c n đ m ch a 0   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

82

Toán rời rạc

ế ợ ầ h p c n đ m.

4.1 Xây dựng công thức đệ qui

 Do đó, theo nguyên lý c ng:ộ                    fn = |A| + |B|.  Ta có:

ầ

ứ A ch a 1

• Do m i ch nh h p trong  ỉ ợ ạ ẽ ạ

ộ

ỉ

ở ị  v  trí đ u tiên, nên ế ợ

ầ

ộ

ỗ  còn l

i s  t o thành m t ch nh h p c n đ m đ  dài

n­1 ph n ầ n­1, suy

ợ

ị

ử t ra:     |A| = fn­1 ỗ ủ

ả

ở ị ầ ử

ứ  v  trí đ u tiên, nên v  trí th   ộ i  s   t o  thành  m t

ầ ạ ẽ ạ   còn  l

ợ ầ

ế

ộ

ỉ

• Do m i ch nh h p trong  ỉ hai  c a  nó  ph i  là  1  còn  ch nh h p c n đ m đ  dài

ứ B ch a 0  n­2  ph n  t n­2, suy ra:   |B| = fn­2

ậ

ượ

ứ ệ

c công th c đ  qui

 V y, ta thu đ                         f1 = 2; f2 = 3;                         fn = fn­1 + fn­2,  n > 2                            (5)

83

Toán rời rạc

4.1 Xây dựng công thức đệ qui

 Ví d  4.ụ  Xây d ng công th c đ  qui cho

ự ố ượ ủ ng cách ph Qn là s  l

ứ ệ ằ ướ (cid:0) n b ng các quân bài domino. c 2

i ô vuông kích th i.ả  Ta có

ậ ướ l  Gi               Q1 = 1; Q2 = 2 (xem hình v )ẽ  Gi s

ậ ượ ế  góc trên trái đ ậ ủ ở c ph  b i

ủ ằ quân bài n m đ ng;

ủ ở ượ ậ góc trên trái đ c ph  b i ủ ầ ả ử 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 đó ô  ở ứ • B  – t p các cách ph  trong đó ô  ở

ủ ằ 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

84

Toán rời rạc

ế ầ c n đ m.

4.1 Xây dựng công thức đệ qui

A

... ...

 Do đó, theo nguyên lý c ng:ộ                    Qn = |A| + |B|.  Ta có:

B

... ...

ứ ệ

ượ

c công th c đ  qui

• |A| = Qn­1 • |B| = Qn­2 ậ  V y, ta thu đ                         Q1 = 1; Q2 = 2;                         Qn = Qn­1 + Qn­2,  n > 2                   (6)

85

Toán rời rạc

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  s ang  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.

86

Toán rời rạc

ứ ệ

4.1 Xây dựng công thức đệ qui

 Gi¶i: Râ rµng:

 Gi¶ sö n ≥ 2. ViÖc di chuyÓn ®Üa gåm c¸c b­íc:

h1 = 1.

(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.

87

Toán rời rạ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.

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µ

88

Toán rời rạc

hn = 2n – 1, n ≥ 1.

4.1 Xây dựng công thức đệ qui

ượ ự ế ứ ươ c công th c tr c ti p cho ng ằ hn b ng ph

ể Ta có th  tìm đ pháp th :ế    hn = 2 hn−1 + 1

= 22 hn−2 + 2 + 1

= 2 (2 hn−2 + 1) + 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)

89

Toán rời rạc

= 2n − 1

Tower of Hanoi: n=5

90

Toán rời rạc

C c aọ C c cọ C c bọ

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

91

Toán rời rạc

ả

ứ ệ

§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

92

Toán rời rạc

ấ ệ ố ằ thu n nh t h  s  h ng (s  vi ả công  th c  đ   qui  tuy n  tính  ệ ứ i  ẽ ế ắ t là CTĐQ TTTNHSH) t t

ả

ứ ệ

§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  ầ    k đi u ki n đ u ả ế n u đòi h i nó tho  mãn

a0 = C0, a1 = C1, ..., ak­1 = Ck­1,

93

Toán rời rạc

ằ ố     trong đó  C0, C1, ..., Ck­1 là các h ng s .

 Ví d :ụ

1) an = 4an­1 +2nan­3

2) hn = 2hn­1 + 1

3) bn = 5bn­2 + 2(bn­3)2

4) qn = 3 qn­6 + qn­8

94

Fall 2006

Toán rời rạc

Giải CTĐQ TTTNHSH

ệ

ẽ

ướ ạ

ằ

 Ta s  tìm nghi m d

i d ng

ố an = rn, trong đó r là h ng s .

ả

ế r  tho  mãn

ả  Dãy s  {ố an = rn } tho  mãn CTĐQ đã cho n u

ươ

ph

ng trình: rn = c1rn−1 + … + ckrn−k, hay  rk − c1rk−1 − … − ck = 0

ượ

ươ  Ph ư

ủ

ặ ặ

ng  trình  đ c  ệ nghi m  đ c

ọ c  g i  là  ẽ ượ s   đ

ươ ph ọ c  g i  là

ủ

ố ng  trình  cu i  cùng  đ ệ tr ng,  còn  nghi m  c a  nó  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 .

95

Toán rời rạc

ế ể (chuy n v   và × v i ớ rk−n)

Giải CTĐQ TTTNHSH

 §Þnh lý 1. Cho c 1, c2 lµ c¸c h»ng s è  thùc. Gi¶ s ö ph­ ¬ng tr×nh r2 ­ c1 r ­ c 2 = 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 = c 1 an­1 + c 2 an­2

1(r1)n + (cid:0)

2(r2)n

(5) khi vµ chØ khi  an =  (cid:0)

1 , (cid:0)

2  lµ c¸c h»ng s è .

96

Toán rời rạc

n = 0, 1, ..., trong ®ã (cid:0)

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 tr­ng, vµ 1 , (cid:0) (cid:0) 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

2 = c 1 r1 + c 2  ,

r1

2 = c 1 r2 + c 2

97

Toán rời rạc

r2

Giải CTĐQ TTTNHSH

 Tõ ®ã suy ra

c1 a n-1 + c2 a n-2

n-2)

2 r2

2 r2

n-2 + (cid:0) 1 r1 n-2(c1 r2 + c2)

2 r2 n

n-1 + (cid:0) n-1) + c2 ((cid:0) 1 r1 n-2(c1 r1 + c 2) + (cid:0) 2 r2 2  + (cid:0) 2 n­2 r2 n­2 r1 n  + (cid:0) 2 r2

= c 1 ((cid:0) = (cid:0) 1 r1 = (cid:0) 1 r1 = (cid:0) 1 r1 = an .

98

Toán rời rạc

Giải CTĐQ TTTNHSH

 B©y giê ta sÏ chØ ra r»ng nghiÖm {a n} cña c«ng thøc ®Ö qui an = c 1 an-1 + c 2 an-2  lu«n cã d¹ng (5) víi (cid:0) 1,  (cid:0) 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

 Ta chØ ra r»ng cã thÓ t×m ®­îc c¸c sè (cid:0)

1 ,  (cid:0)

2 ®Ó cho (5) lµ nghiÖm cña hÖ thøc víi ®iÒu kiÖn ®Çu nµy.

99

Toán rời rạc

a 0 = C0 , a1 = C1, (6)

Giải CTĐQ TTTNHSH

 Ta cã

a0 = C0 = (cid:0) a1 = C1 = (cid:0)

1 + (cid:0) 2 , 1r1 + (cid:0)

2r2.

 HÖ ph­¬ng tr×nh tuyÕn tÝnh phô thuéc hai Èn (cid:0)

1, (cid:0)

2 nµy

0 (do r1 (cid:0)

r2) cã nghiÖm duy

cã ®Þnh thøc lµ r2 – r1 (cid:0) nhÊt            (cid:0)

2 = (C0 r1 ­ C1 )/(r1 ­ r2).

 Víi nh÷ng gi¸ trÞ cña  (cid:0)

1 = (C1 ­ C0r2 )/(r1 ­ r2),  (cid:0) 1  ,  (cid:0)

100

2  võa t×m ®­îc, d·y {a n} 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). Toán rời rạc

 §Þnh lý ®­îc chøng minh.

VÝ dô

 D·y Fibonaci trong to¸n häc ®­îc ®Þnh nghÜa

2,

Leonardo Fibonacci 1170­1250

+

b»ng hÖ thøc truy håi:            Fn  =  Fn-1  +  Fn­2, n (cid:0)            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­ng 5

5

1

1

=

=

;

r 1

r 2

2

2

101

Toán rời rạc

-

VÝ dô

2 = 0

1+ (cid:0) 1r1+ (cid:0)

F0= (cid:0) F1= (cid:0)

2r2 = 1

1.(r1)n  + (cid:0)

 Do ®ã c«ng thøc hiÖn cã d¹ng:                  Fn  = (cid:0) trong ®ã (cid:0)

2.(r2)n 1, (cid:0)  2  lµ c¸c h»ng sè cÇn x¸c ®Þnh

1

1

=

a

;

tõ c¸c gi¸ trÞ ban ®Çu F0, F1. Gi¶i hÖ PTTT = - a nµy, ta cã:

1

2

5

5

n

n

+

C«ng  thø c   Muavre

1

1

1

5

0.

n

nF

- - (cid:0)

)

)

(

(

vµ tõ ®ã thu ®­îc 5 = 2

2

5

� � � �

� � , � �

102

Toán rời rạc

Great Pyramid at Gizeh

103

Toán rời rạc

(cid:0)

1.618

a b

a

b

104

Toán rời rạc

Tỷ lệ giữa chiều cao và lưng

105

Toán rời rạc

Định nghĩa tỷ lệ vàng (cid:0)

(Euclid)

 T  l

ỷ ệ ầ thu đ

ằ ớ ẳ ẳ

ạ ạ ạ ớ ạ ỏ ơ ạ ằ ơ ượ nhau sao cho t ơ h n là b ng t c khi chia đo n th ng ra 2 ph n không b ng  ỷ ệ ữ  l  gi a đo n th ng đã cho và đo n con l n  ỷ ệ ữ  gi a đo n l n h n và đo n nh  h n.  l

(cid:0)

C A B

AB BC

2

(cid:0)

(cid:0) (cid:0)

f

=

AC AB AC BC

+ 5 1 2

2

(cid:0)

(cid:0)

(cid:0)

1

p

AB BC

BC BC

=

2

2cos

(cid:0)

(cid:0)

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

AC BC 1 0

� � � � 5 � �

106

Toán rời rạc

(cid:0) (cid:0) (cid:0)

107

Toán rời rạc

Trường hợp nghiệm kép

 §Þnh lý 2. Cho c 1, c2 lµ c¸c h»ng s è  thùc, c 2 (cid:0)

0. Gi¶ s ö

ph­¬ng  tr×nh  r2 ­  c 1 r  ­  c 2 = 0 cã  nghiÖm   kÐp  r0.  Khi  ®ã  d∙y s è  {an } lµ nghiÖm  cña c«ng thø c ®Ö qui

an = c 1 an­1 + c 2 an-2

(cid:0)

(cid:0)

khi vµ chØ khi

a

n

n r 1 0

n nr 0

2

(cid:0) (cid:0)

1 , (cid:0)

2  lµ c¸c h»ng s è .

108

Toán rời rạc

n = 0, 1, ..., trong ®ã (cid:0)

Ví dụ

 T×m nghiÖm cho c«ng thøc ®Ö qui an = 6 an­1 ­ 9 a n-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 ®ã

1 3n + (cid:0)

 §Ó t×m (cid:0)

1, (cid:0)

nghiÖm cña hÖ thøc cã d¹ng: an = (cid:0) 2 n 3n. 2 , sö dông ®iÒu kiÖn ®Çu ta cã a0 = 1 = (cid:0) a1 = 6 = (cid:0)

1 ,  1 . 3 + (cid:0)

 Gi¶i hÖ nµy ta t×m ®­îc (cid:0)

2 . 3. 1 = 1  vµ  (cid:0)

2 = 1.  Tõ ®ã

nghiÖm cña hÖ thøc ®· cho lµ:

an = 3 n + n 3 n .

109

Toán rời rạc

Trường hợp tổng quát

 §Þnh lý 3. Cho c 1, c2, ..., c n lµ c¸c s è  thùc. Gi¶ s ö ph­

¬ng tr×nh ®Æ c tr­ng

rk ­ c 1 rk-1 ­ c 2 rk­2  ­ . . . ­ c k = 0

cã  k  nghiÖm   ph©n  biÖt  r1,  r2,  ...,  rk  .  Khi  ®ã  d∙y  s è

{a n} lµ  nghiÖm   cña  c«ng  thø c

a n = c 1 an-1 + c 2 a n-2 +...+ c k an­k,

n + (cid:0)

1 r1

2 r2

khi vµ chØ khi

110

Toán rời rạc

n + . . . + (cid:0)        víi n = 0, 1, 2,..., trong ®ã (cid:0)

k rk 1, (cid:0)

n  2, ..., (cid:0)

k  lµ c¸c h»ng

an = (cid:0)

s è .

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,  a 1 = 5,  a 2 = 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,

1 1n + (cid:0)

2 2n + (cid:0)

3 3n.

nghiÖm cã d¹ng an = (cid:0)

111

Toán rời rạc

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è (cid:0) 1, 2, (cid:0)

3

3.3 3.9.

2 + (cid:0) 2.2 + (cid:0) 2.4 + (cid:0)

3: a0 = 2 = (cid:0) a1 = 5 = (cid:0) a2 = 15 = (cid:0)

1 = 1, (cid:0)

3 = 2.

112

Toán rời rạc

1 + (cid:0) 1 + (cid:0) 1 + (cid:0)  Gi¶i hÖ ph­¬ng tr×nh trªn ta thu ®­îc 2 = -1 vµ  (cid:0)           (cid:0)  VËy nghiÖm cña c«ng thøc ®· cho lµ            an  = 1 - 2n + 2. 3n .

(cid:0)

Trường hợp tổng quát

k

a

n

ac ini

(cid:0) (cid:0) (cid:0)

i

1

ủ

 Xét CTĐQ TTTNHSH b c ậ k:  PTĐT c a nó là:

k

(cid:0)

k

ik

r

0

rc i

(cid:0) (cid:0) (cid:0) (cid:0)

i

1

N u PTĐT có

ớ ộ t nghi m ệ r1,…,rt v i b i

(cid:0)

ị  Đ nh lý 4:  ươ ứ

t

ế m1,…,mt (m1+…+mt=k). Khi đó: ng  ng là

t

m i

n

(cid:0) (cid:0) (cid:0)

1 (cid:0)

a

n

j rn i

ji ,

i

j

1

0

ằ

v i ớ n≥0, và αij là các h ng s . ố

113

Toán rời rạc

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

Ví dụ

ả

ứ ệ

Gi

i công th c đ  qui:

3,

cn = – 4cn­1 + 3cn­2 + 18cn­3 ,    n (cid:0) 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)n trong đó a10, a20, a21 là các h»ng sè

114

Toán rời rạc

Ví dụ

0

0

10

21

20

10

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

10

21

20

10

20

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

a a a

c 0 c 1 c

a a a

Các hằng số được xác định từ các điều kiện đầu: a 0 a 2 a 13

)3)(0 1 )3)(1 2 )3)(2

a ( a ( a (

2 1 2 2 2

2 4

a 20 a 3 a 9

a 3 21 a 18

20

21

10

2

10

20

21

Rút gọn ta thu được hệ

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

a

0

10

20

(cid:0)

a (cid:0) a

a

a

2

2

3

3

10

20

21

(cid:0) (cid:0) (cid:0)

a

a

a

13

4

9

18

10

20

21

Giải hệ ta nhận được:

(cid:0) (cid:0) (cid:0)

a

a

,1

,1

1

a 10

21

n

+ - +

=

(cid:0) (cid:0) (cid:0) (cid:0)

n 2 ( 1 )( 3)

n

20 Cuối cùng nghiệm của công thức là: nc

115

Toán rời rạc

-

Công thức đệ qui tuyến tính không thuần nhất hệ số hằng

ế

ầ

không thu n nh t

ệ  Công th c đ  qui tuy n tính

ộ

ụ

ấ    ứ ệ ố ằ nonhomogeneous Recurrence  h  s  h ng (Linear  ố ứ Relation  with  constant  coefficients)  có  ch a  s   ụ ấ F(n) ph  thu c vào  ạ ầ n (và  h ng không thu n nh t  ộ không ph  thu c vào b t c

ấ ứ ai nào) : an = c1an−1 + … + ckan−k + F(n)

Phần không thuần nhất

ớ ng  ng v i

116

Toán rời rạc

ứ ươ ứ CTĐQ TTTNHSH t ấ ầ công th c không thu n nh t

Giải công thức không thuần nhất (CTKTN)

 K t qu  sau đây là c  s  đ  gi

k

ả ơ ở ể ả ứ ầ i công th c không thu n

n

i

1

ủ (cid:0) (cid:0) ế nh t:ấ • N u ế an = p(n) là m t nghi m riêng c a CTKTN: (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) a ệ nF )( ộ ac ini (cid:0) (cid:0) (cid:0)

• Khi đó m i nghi m c a CTKTN đ u có d ng: ủ

ề ạ

ọ ệ an = p(n) + h(n),

k = (cid:0) ổ

c a - i n i

=

ủ

1

i

117

Toán rời rạc

ươ ứ ệ trong đó an = h(n) là nghi m t ng quát c a CTĐQ  a n TTTNHSH t ng  ng

Giải công thức không thuần nhất

 T  đó ta có cách gi

ừ ả i CTKTN sau đây:

ổ ủ ứ ầ ấ h(n) c a công th c thu n nh t

ươ ứ ệ (a) Tìm nghi m t ng quát  ng  ng. t

(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

ị ượ ở ng trình thu đ c b i

118

Toán rời rạc

ằ ả ố ừ ệ ươ  h  ph ệ ề ầ đòi h i ỏ an tho  mãn các đi u ki n đ u

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

ứ ủ ệ ể ể ầ ạ

ấ F(n):

ầ không thu n nh t  • N u ế F(n) = P(n) (cid:0) ố sn, trong đó P(n) là đa th c c a  ệ ằ

• N u ế F(n) = P(n) (cid:0)

ệ ố ứ ủ n  ặ ư còn s là h ng s  và không là nghi m đ c tr ng, thì  ư F(n). ạ hãy tìm nghi m riêng có d ng gi ng nh

ứ ủ n  m, thì hãy tìm

119

Toán rời rạc

ệ sn, trong đó P(n) là đa th c c a  ặ ớ ộ ư ệ còn s là nghi m đ c tr ng v i b i là  ướ ạ  nm(cid:0) Q(n)(cid:0) i d ng nghi m riêng d sn

Ví dụ

 Gi

ả ứ ệ i công th c đ  qui

an=5an­1 ­ 6an­2+7n, n(cid:0) 2, a0 = 0; a1 = 1 ư r2 – 5r +6 = 0 có nghi m ệ

ủ ầ ệ ấ ươ ặ  PT đ c tr ng                   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

120

Toán rời rạc

p(n) = C.7n.

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

 V yậ

C = 49/20.

121

Toán rời rạc

p(n) = (49/20)7n.

Ví 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 ừ ệ ươ  h  ph ng trình: ố c1, c2 xác đ nh t

a0 = c1 + c2 + 49/20 = 0

 ...

122

Toán rời rạc

a1 = 3c1 + 2c2 +(49/20).7 = 1

Ví dụ

ả ứ ệ

1;

 Gi i công th c đ  qui                  an = 2an­1 + 1, n (cid:0)                  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. ướ ạ i d ng

 Do F(n) = 1, nên nghi m riêng tìm d                 p(n) = C.   Thay vào công th c đã cho ta đ

ừ ượ C = 2C+1. T  đó tìm c:

ệ ậ ứ c ượ C = ­1. V y nghi m riêng là đ

123

Toán rời rạc

p(n) = ­1.

Ví dụ

ủ

ệ

ấ

ầ

ổ

 Nghi m t ng quát c a CTĐQ không thu n nh t

là

an = c12n – 1.

ị

ừ ề

ầ

 H  s

ệ  đi u ki n đ u:

ệ ố c1 xác đ nh t

a1 = c12 ­1 = 1

 Do đó c1 = 1.

ậ

ệ

ầ

ấ

1.

ủ  V y nghi m c a CTĐQ không thu n nh t là             an = 2n ­1, n (cid:0)

124

Toán rời rạc

Ví dụ

ả

ứ ệ

ủ

ổ

 Gi i công th c đ  qui                  an = an­1 + n, n (cid:0)  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

ư

ặ

ộ

ệ h(n) = c11n. ệ

ng  ng là:     Do F(n) = n(cid:0) 1n, và 1 là nghi m đ c tr ng b i 1,

nên nghi m ệ

ướ ạ

riêng tìm d

i d ng

ượ

c:

ượ

ừ

ệ

c C

p(n) = (C2 + C3n).n.  ứ  Thay vào công th c đã cho ta đ       (C2 + C3n).n = [C2 + C3(n­1)].(n­1) + n. ậ 2 = ½ và C3 = ½ . V y nghi m riêng là  T  đó tìm đ

p(n) = (n+1)n/2.

125

Toán rời rạc

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

ị ừ ề ầ ệ  đi u ki n đ u: ệ ố c1 xác đ nh t

 Do đó c1 = 1.

a1 = c1 + 1 = 2

ậ ủ ấ ầ

126

Toán rời rạc

1. ệ  V y nghi m c a CTĐQ không thu n nh t là             an = 1+ (n+1)n/2, n (cid:0)

Nhận xét

ả ng pháp gi

ề ệ ủ

 Ph ở tìm t

ấ ả ủ ệ ứ ệ ươ 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 c  các nghi m c a đa th c b c ứ ậ k.

ứ ủ ậ ộ ỳ t c  các nghi m c a m t đa th c b c tu  ý

ệ  Vi c tìm t ề ấ ả ơ

ứ ể ủ ệ ứ ậ k (cid:0) ệ ấ ả 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

4.

• Nh ng không có công th c đ  tìm t

ư ấ ả ệ t c  các nghi m

127

Toán rời rạc

ứ ể ị ủ c a đa th c b c ứ ậ k (cid:0) 5 (Đ nh lý Aben).

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

128

Toán rời rạc

5. Hàm sinh (Generating Function)

 Gi

ộ ế s  {

ạ

ồ ạ

ằ ố t dãy này  ằ , tuy nhiên ta coi r ng nó bao g m  ữ ế  h0, h1, ..., hm là dãy h u h n,  ặ hi = 0, i >

i

=

0

i

 Đ nh nghĩa.  ạ ỗ chu i vô h n

(cid:0) ả ử hn  | n =  0, 1, 2,  ....} là m t dãy s . Ta vi ầ ử ư nh  là dãy vô h n ph n t ạ ữ ợ ả ườ ng h p dãy h u h n. N u c  tr ạ ẽ ế thì ta s  bi n nó thành dãy vô h n b ng cách đ t  m . ị ủ (cid:0) ố {hn | n = 0, 1, 2, ....} là  Hàm sinh g(x) c a dãy s   h x i

ư ố ệ ố g(x) sinh ra dãy s  đã cho nh  là dãy các h  s

129

g(x) = h0 + h1 x + h2 x2 + ... =             . ư ậ  Nh  v y hàm  ủ c a nó.  ế ẽ

ườ ứ ậ m. ữ ạ ượ  m sao cho hi = 0, i > m.   N u dãy là h u h n thì s  tìm đ ộ ợ ng h p này c g(x) là m t đa th c b c Trong tr

ộ

ẫ

ị

ố ị ứ

ể

ế ữ ồ  Ví d  1. ụ M t trong nh ng ngu n g c d n đ n đ nh nghĩa hàm sinh   g(x) = (1 + x)m sinh ra  chính là đ nh lý v  khai tri n nh  th c: Hàm  dãy các h  s  t

ị ề ệ ố ổ ợ  h p

{hk = C(m, k), k=0, 1,..., m}.

m

B i vìở

m

k

Ví dụ

x

1(

)

(

(cid:0) (cid:0) (cid:0)

k

xkmC ), 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 + ...

130

(cid:0)

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.

ứ

ự ậ

Th c v y, ta có

 Ch ng minh.             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á  ố ầ xn s  b ng s  nghi m nguyên  ngo c, thì s  l n xu t hi n s  h ng  ươ ủ 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).

131

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

ủ ế

ề

2,

ừ ố

ừ ố ứ  các th a s  th    b (cid:0)  3, 0 (cid:0)  a (cid:0) ố ả , các th a s  này s  cho ta s   ẽ

4. Khi khai tri n v  ph i

ấ ừ ươ ứ ả ử xa, xb, xc t ng  ng là các s  h ng l y t ả ấ nh t, hai, ba c a v  ph i, đi u đó có nghĩa là 0  0 (cid:0)  c (cid:0) ể h ng ạ

ế xn, v iớ  n = a + b + c.

ẽ

ệ

 Nh  v y h  s  c a

ư ậ ủ c a ph

ệ ố ủ xn trong g(x) s  là s  nghi m nguyên không âm  ố ng

ươ  trình

(cid:0)

ả

b (cid:0)

n=a + b + c tho  mãn 0

a (cid:0)

3, 0 (cid:0)

2, 0 (cid:0)

c (cid:0)

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.

132

(cid:0)

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  ạ i có th  th c hi n nhanh chóng trên  vi c tính tay. Tuy nhiên, vi c đó l ộ ẽ ế 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 + ...

133

Ví dụ 4

ạ

ả

n qu  t

ố ộ ố

ẵ

ả ừ  4 lo i qu : táo, chu i, cam  n) mà trong đó có m t s  ch n  ả

ọ ố ượ ng ít ra là  ả

ố

 Ví d  4. ụ Có bao nhiêu cách ch n ra  ạ ề ả  qu  chu i, không quá 4 qu  cam và ít ra 2 qu  đào?

ể ả

i bài toán này là

ỗ và đào (m i lo i đ u có s  l ả ố ẻ qu  táo, s  l i.ả  Hàm sinh đ  gi

ả

ố

ứ ẻ

ố

ố

ỉ

 Gi         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),  ắ ầ ừ ế ố ố  2).  chu i (s  mũ l ), cam (ch  có đ n s  mũ 4) và đào (s  mũ b t đ u t T  đóừ

ầ

ệ ố ứ n trong khai tri n ể g(x) d

i là:

ố ỹ ừ

ả ờ ằ

ể ậ

ự

i ướ ư   ố i b ng s , nh ng ư đ  ể đ a ra

ố

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  S  cách c n đ m là h  s  th   ỗ ạ d ng chu i lu  th a. Tuy là chúng ta không có câu tr  l ử ụ  hàm xây d ng đ c  s  d ng ả b ng đáp s  cho các giá tr  c a

ượ ta có th  l p trình trên máy tính  ị ủ n mong mu n.ố

134

Ví dụ 5

ả ừ

ạ

ả

ố

 Ví d  ụ 5. Tìm hàm sinh cho hn là s  cách ch n ra ỗ

ọ ố ượ

ạ ề

n qu  t ng ít ra là

ố ộ ố

ế

ẵ

ả

ố

4 lo i qu : táo,  n) mà trong đó có  ả ng chu i chia h t cho 5, không quá 4 qu

chu i, cam và đào (m i lo i đ u có s  l ố ượ m t s  ch n qu  táo, s  l cam và không quá 1 qu  đào?

ả i. ả Hàm sinh có d ngạ

 Gi

g(x)=(1+x2+x4+x6+...)(1+x5+x10+x15+...)(1+x+x2+x3+x4)(1+x)

ứ

ừ

ờ

n

ụ , theo ví d  3, ta có 1) x

ệ = �

� n C + - n

ở ả i, b i vì i gi + = � n ( n

(cid:0) (cid:0) (cid:0)

=

=

=

= [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 1 = n n                                                        . C x x + 1 2 1 n 2 (1 ) x

0

0

0

n

n

n

 V y ậ hn = n + 1.

135

-

Hàm sinh và công thức đệ qui

ể

ể ử ụ  đ  tìm công th c d

ổ

ủ

ị

ố ệ ứ ướ ạ i d ng hi n cho s   ứ ố  {hn , n=0,1,2,...}  xác đ nh b i công th c  ươ

ủ

ng pháp có th  trình bày nh  sau

:

ộ ự

ủ

ố

 Hàm sinh có th  s  d ng ạ h ng t ng quát c a dãy s ệ đ  qui. N i dung c a ph i) Xây d ng hàm sinh

ở ể ư ứ  g(x) c a dãy s  này theo công th c

i

(cid:0)

h x i

=

0

i

g(x) = h0 + h1 x + h2 x2 + ... =

ứ

ả

i  tích  cho  hàm  sinh

ii)  Tìm  công  th c  gi

ứ ệ

ấ ủ

ướ ạ

ể

ử ụ g(x).  (S   d ng  các  tính  ị  công th c đ  qui xác đ nh nó) . ượ ,  tìm  khai  tri n  hàm  g(x)  d

i  d ng

c

ừ ch t c a dãy s  suy t iii)  Theo  công  th c  tìm  đ

ỗ

ỗ ỹ ừ  (chu i Maclaurin). ớ

ố ạ

ố

các s  h ng v i cùng s  mũ c a

ủ x ta tìm đ

c ượ

ố ứ chu i lu  th a iv) So sánh h  s   ứ công th c cho

ệ ố ở hn.

136

(cid:0)

Phép toán với hàm sinh

 Tr sử

i

=

=

( ) f x

i , ( ) a x g x i

b x i

�

�

=

=

0

0

i

i

ướ ế ố ớ ộ ố ư c h t ta đ a ra m t s  phép toán đ i v i hàm sinh. Gi ả (cid:0) (cid:0)

i

+

a

=

(cid:0) (cid:0)

( ) g x

a x i

=

a � =

0

0

i

i

là hai hàm sinh còn (cid:0) = ( ) f x ố ự  là s  th c, khi đó + � i ( ( ) ) , f x b x a i i

i

(cid:0)

= (cid:0)

c x i

=

0

i

k

g(x) và f(x): ủ  Tích Côsi c a hai hàm sinh  ( ) ( ) f x g x

a b - i k i

=

0

i

trong đó (cid:0)

137

ck = a0 bk + a1 bk­1 + ... + ak b0 =             .

Chuỗi Maclaurin

ừ ả

 T  gi

i tích ta bi

ế t r ng n u chu i

ỗ

i

ế ằ = (cid:0)

( ) g x

h x i

=

0

i

ậ

ổ

ả

ể  lân c n đi m 0 thì t ng

g(x) luôn là hàm gi

i tích trong

ộ ụ ở      h i t ậ

lân c n này và

hk = g(k)(0)/k! , k = 0, 1, ...

 Khi đó chu i  ỗ

(cid:0)

i

(cid:0)

h x i

=

0

i

ộ

chính  là  khai  tri n  Macl

ứ

ộ

ả

ủ aurin  c a  hàm  ộ i tích và m t chu i h i t

ư ậ g(x).  Nh   v y  có  m t  ỗ ộ ụ  trong

138

ể ươ ữ ng  ng 1­1 gi a m t hàm gi t ậ lân c n 0.

(cid: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:

k

=

(cid:0)

C

k r x 1

k + - n k

=

n )

(1

1 rx

0

k

ườ

ủ

ợ

mà tr

ng h p riêng c a nó là

1/(1 ­ rx) =  1 + rx + r2 x2 + r3 x3 + ....

139

(cid:0) -

Dãy số Fibonaci

ố ượ

ố

ở

ị

Dãy s  Fibonaci là dãy s  đ

c xác đ nh b i công

ố  Dãy s  Fibonaci. ứ ệ th c đ  qui

2,

fn = fn­1 + fn­2, n (cid:0) 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

= (cid:0)

f x n

( ) F x  Xét hàm sinh                       . Ta có

=

0

n

(cid:0)

n

n

n

=

=

+

+

=

+

+

+

(cid:0) (cid:0) (cid:0)

( ) F x

f

f

f

) x

f

0

f x 1

0

f x 1

2

1

f x n

f x n

n

n

�

�

� (

=

=

=

0

2

2

n

n

n

- -

+

+

1

2

n

n

=

+

+

+

f

0

f x 1

f x n

f x n

� �

=

0

0

n

= n +

( ).

= + x

( ) xF x

2 x F x

140

(cid:0) (cid:0)

Dãy số Fibonaci

ừ

 T  đó suy ra

=

.

( ) F x

2

1

x x

x

 Ta có (1­ x ­ x2) = (1 ­ (cid:0)  x) (1 ­ (cid:0)  x), v iớ

+

- -

1

1

5

a

=

=

5 b ,

.

2

2

ướ ạ

 Vi

ế ạ F(x) d i

t l

i d ng

B

=

+

,

( ) F x

A a

b

-

1

1

x

x

141

- -

Dãy số Fibonaci

ừ

ượ

 T  đó tìm đ

c  1

1

=

= -

,

.

A

B

5

5

 Do đó

1

1

=

( ) F x

1 a

b

1

x

x

5

� � �

- - -

� � 1 � 1

n

n

n

=

b

(cid:0)

a (

)

.

x

=

0

n

5

 Suy ra

+

- (cid:0)

1

1

5

5

n

n

=

b

a (

= )

0.

nf

2

2

5

5

n � � 1 � � � � � �

n � � � �

� � 1 � � � � � �

� � , n � �

142

- - - (cid:0)

6. Một số dãy số đặc biệt

 Dãy số Stirling

 Dãy số Bell

 Dãy số Catalan

143

Nhắc lại: Số lượng ánh xạ

́

̃

̣ ư

Cho ca c tâp h u han

̣ A = {a1,…, am} va  ̀ B = {b1,…, bn}.

́

́

Hoi co  bao nhiêu a nh xa

̣ f: A (cid:0)

B ?

́

̃

ư

ư

Nh  ta đa  ch ng minh:

́

́

̉

́   Tông sô  a nh xa co  thê: |

̉ B||A| = nm.

́

́

ượ

ơ

  Sô  l

ng đ n a nh:

P(n,m) = n∙(n–1)∙∙∙(n–m+1) = n!/(n–m)!.

́

́

ượ

  Sô  l

̀ ng song a nh la

P(n,n) = n! nê u |

́ A| = |B| = n.

ố ượ

   S  l

ng toàn ánh: v i ́

ơ m ≥ n:

n

̉ ̣

k ( 1)

m )

( n k

n k C n

=

0

k

144

- - - (cid:0)

Số Stirling loại 2

 Sô  l

́ ́ ̀ ượ ư ̀ ng toa n a nh t ̀  tâp ̣ A = {a1,…,am} va o tâp

ế ộ ố ổ ợ ổ ế ̣ B = {b1,  h p n i ti ng đó là sô  ́

nd Kind).

̣ …,bn} liên quan đ n m t con s  t Stirling loai 2 (Stirling Numbers of the 2

 Đ nh nghĩa.

ị ố ệ ố ạ , ký hi u b i S  Stirling lo i 2 ở S2(m,n), là s  cách

ầ ử ậ ạ phân ho ch t p ậ m ph n t thành n t p con ( m (cid:0) 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 {{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}}.

145

 V y ậ S2(4,2)=7.

ố ể ể ạ t c  các cách phân ho ch nh  v y:

ố

ệ

ề

ượ

còn đ

( ) ho�c n S m

 Trong nhi u tài li u, s  Stirling  ở ệ c ký hi u b i m � � � � n �

James Stirling 1692 – 1770 Scotland

146

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.   V i ớ m, n > 1,

ứ

ạ

ầ

ố

ậ m ph n t

ầ ử X = {x1, x2, … , xm}

ậ

Đ nh lý.                 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  ra thành n t p con.

147

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:

ộ ậ

ậ

ậ

ạ ạ X ra thành n t p con trong đó có m t t p

A = T p các cách phân ho ch

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.

148

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 k

=

- -

(cid:0) n

S m n , ) (

( 1)

k m C k n

2

=

1 n !

k

0

ể ườ ườ i  ta  th S2(m,n)  ng

ươ nh  đ  tính h  s  t c gi

 Nói  chung  đ   tính  ệ ượ i ta th

149

ả ườ ng  dùng  công  ề ứ ử ụ ứ th c  đ   qui,  ch   không  s   d ng  công  th c  này.  Đi u  ệ ố ổ ợ ự  h p  này đ ườ ng ứ ư ể ng t i thích t ng dùng tam giác Pascal.

ớ ố ượ

ừ

 Ta xét m i liên h  gi a s  Stirling lo i 2 v i s  l

ng toàn ánh t

ố ệ ữ ố ầ ử A vào t p ậ n ph n t

ạ ầ ử B (ký hi u làệ

t p ậ m ph n t

S'(m,n)).

ả ử

s  cho

ừ A vào B. Đ t ặ

f là toàn ánh t

 Gi                     Ai = {a(cid:0) A| f(a) = bi}, i = 1, 2, ..., n,

ạ

ộ

ủ ậ A.

ạ       Rõ ràng các t p ậ A1, A2, ..., An t o thành m t phân ho ch c a t p

ộ

ạ

ậ

ượ ạ c  l

 Ng

ủ ậ A  ra  thành  n  t p  con

A1,  ..., n, thì ta có th  ể

ượ

i,  cho  m t  phân  ho ch  c a  t p  A2, ..., An và (cid:0) (1), (cid:0) (2), ...,(cid:0) (n) là hoán v  c a 1, 2,  ị ủ  ừ A vào B theo qui t cắ ự f t xây d ng đ

c toàn ánh                       f(a) = b(cid:0) (i) , a(cid:0) A(cid:0) (i) , i = 1,2, ..., n,

ư ậ

ế ố ượ

 Nh  v y m i phân ho ch cho ta

ầ ử

ỗ ừ ậ m ph n t

ạ  vào t p  ầ ử

ớ ố ằ

ậ

ậ m  ph n  t

ậ n ph n t   ra  thành

n! toàn ánh. Vì th , s  l ằ ầ ử  là b ng  n  t p  con,  nghĩa  là  b ng

ng toàn  n! nhân v i s  cách  n! 150

t p  ánh t ạ phân  ho ch  t p  S2(m,n)

Liên hệ giữa số lượng toàn ánh và số Stirling

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   vào t p

ẳ ầ ử ệ ữ ố ầ ử S'(m,n) và s  ố ố ậ n ph n t

ừ ậ m ph n t ánh t  t p  ạ Stirling lo i 2 sau đây:

S'(m,n) =   n! S2(m,n) .

 Do đó t

k

m

=

ừ ứ ở ụ ướ công th c đã ch ng minh m c tr c ứ n

S m n '( , )

( 1)

C n k (

)

k n

=

k

0

Suy ra

n

k

m

=

- - (cid:0)

S m n ( , )

( 1)

C n k (

)

k n

2

=

1 n !

k

0

151

- - (cid:0)

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

n

1 10 65 350 1701 7770

1 15 140 1050 6951

1 21 266 2646

1 28 462

1 36

0 1 2 3 4 5 6 7 8 9 10

1 0 1 1 0 1 1 3 0 1 6 7 0 1 25 15 0 1 90 31 0 1 301 63 0 1 0 1 127 966 1 0 1 255 3025 0 1 511 9330 34105 42525 22827 5880 750 45

1

152

Số Bell

ố

 Đ nh nghĩa. ho ch t p

ầ ử ầ

ậ ỗ ậ n ph n t S  Bell (Bell numbers) là s  cách phân   ra thành các t p con khác r ng.

ố

đ u tiên c a dãy s  này là

ạ

ậ

ố ầ ử ủ

ượ

ố

ở

{{1}, {2, 3}}, {{1, 2, 3}}.  S  Bell th

ứ n đ

ứ c tính b i công th c

n

ị ạ  Các ph n t          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}} ,

( , ) S n k 2

=

1

k ố

ạ

trong đó S2(n,k) là s  Stirling lo i 2.

(cid:0)

Eric Temple Bell Born: 1883, Scotland Died:  1960, USA

153

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:

154

ậ ạ

Số Catalan

 Đ nh nghĩa.

S  Catalan th

ự ệ ệ ặ ố ứ n, ký hi u làệ  Cn , là s  cách đ t  ủ n+1 th a ừ  ch c th c hi n vi c tính tích c a

ể

ố ị ặ ể ổ ứ ấ d u ngo c đ  t s :   ố

ể

 Có 5 cách đ  tính P

0..2 :   x0*x1*x2 = (x0*(x1*x2)) =  ((x0*x1)*x2) 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) =  155 (((1 (2 3)) 4) 5) = ((((1 2) 3) 4) 5)

P0..n = x0 x1 x2 ... xn.  Ví d :ụ  Có 2 cách đ  tính P

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,

ượ c chia làm hai tích con. tích x0 x1 x2 ... xn đ

 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 đ xk:

ả ử ấ ầ ượ ặ ừ ố c đ t sau th a s

156

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ố Catalan

ặ ấ

ể ặ ầ  Do d u ngo c phân tách đ u tiên có th  đ t vào sau b t  ừ ố x0, x1, ..., xn­1, suy ra

ấ ứ ừ ố c  th a s  nào trong các th a s   ố ổ t ng s  cách tính P

0..n là:                           Cn = C0 Cn­1 + C1Cn­2+ ... +Cn­1C0 . ượ  Nh  v y ta thu đ 1 n =

ư ậ -

,

1

C n

n k

=

0

=

=

k 1,

1

C 0

C 1

(cid:0) - - ứ ệ c công th c đ  qui: > 1, n C C k

1

=

=

ứ ử ụ ứ -

(cid:0) n

n

0.

,

C C k

n k

n

1

 S  d ng công th c này có th  ch ng minh công th c  1 +

=

n

n (2 )! + n n !(

1)!

1

k

0

(cid:0) - - sau: C

157

ể ứ n 2 � � = � � n � �

Số Catalan

ầ ử ầ ủ ố đ u tiên c a dãy s  Catalan:

ộ ố  M t s  ph n t       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, …

ố ổ ợ h p.

 S  Catalan là l ẽ ể  Ta s  k  ra d

ờ ướ ề i c a r t nhi u bài toán t ư ậ ả ủ ấ ộ ố i gi i đây m t s  bài toán nh  v y.

E. C. Catalan 1814 ­1894   Belgium

158

Tam giác phân đa giác

 Cn là s  cách chia đa giác

ỉ

C2 = 2

C3 = 5

C4 = 14

C5 = 42

159

ườ ắ ố ờ ẽ nh  v  các đ n+2 đ nh ra thành các tam giác  ở  trong đa giác: ng chéo không c t nhau

Đường đi trên lưới ô vuông

ườ

ừ ị

ấ ng đi xu t phát t

v  trí

ơ ng đi đ n đi u

ở

ườ

ượ

ng đ ả ế i­ph i k t thúc  ướ n trên l

ườ  góc trên­trái và ch  đi sang trái ho c lên trên)  ng

ệ (t c là đ ứ ỉ ướ n(cid:0) n không v

ặ t lên trên đ

i ô vuông kích th

c

ố ượ  Cn là s  l ướ góc d ộ đ  dài 2 chéo.

C2 = 2

C3 = 5

C5 = 42

C4 = 14

160

Cây nhị phân đầy đủ

ẳ

ỉ

ố ượ ị

ủ ế

ặ

ố

ọ

ấ ỗ ỉ c g i là đ y đ  n u m i đ nh c a nó ho c là không

ặ

ỉ

ỉ

ầ ủ ị n đ nh trong. Cn là s  l ng cây nh  phân đ y đ  không đ ng c u có  ủ ầ ượ Cây nh  phân có g c đ có con ho c có đúng hai con. Đ nh trong (internal vertice) là đ nh có con.

n = 2

n = 1

n = 3

n = 4

161

Cây nhị phân đầy đủ với n lá

ố

ầ ủ ớ n + 1 lá. ầ ủ ớ

ị  Cn là s  cây nh  phân đ y đ  v i  ị  Có C3 = 5 cây nh  phân đ y đ  v i 4 lá:

n

2

3

4

162

Ask questions!

163

Toán rời rạc

an=5an­1 ­ 6an­2+7n, n(cid:0) 2,

164

Toán rời rạc

165

Toán rời rạc

166

Toán rời rạc

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  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.

167

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 an = cn + d.

(for all n)   (collect terms)

cn+d = 3(c(n−1)+d) + 2n (2c+2)n + (2d−3c) = 0 So c = −1 and d = −3/2. So an = −n − 3/2   is a solution.

 Check:  an≥1 = {−5/2, −7/2, −9/2, … }

168

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:

an = −n − 3/2 + α3n.

Solve this for α for the given case, a1 = 3:

3 = −1 − 3/2 + α31 α = 11/6

 The answer is an = −n − 3/2 + (11/6)3n.

169

Toán rời rạc

Double 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 = 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

■

170

Toán rời rạc

Ask questions!

171

Toán rời rạc

172

Fall 2006

Toán rời rạc

173

Fall 2006

Toán rời rạc

174

Fall 2006

Toán rời rạc

175

Fall 2006

Toán rời rạc

Ask questions!

176

Fall 2006

Toán rời rạc

177

Fall 2006

Toán rời rạc

178

Fall 2006

Toán rời rạc