Chương 2: Tổ hợp

Nội dung

2.1. Hoán vị

2.2. Tổ hợp (Combination)

2.3. Nguyên lý bù trừ

Chương 2

2.4. Công thức đệ qui và hàm sinh

2.5. Số Stirling

TỔ HỢP (Combinatorics)

Chap02-2

Chap02-1

2.6. Nguyên lý các lồng chim bồ câu

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Chương 2. Lý thuyết tổ hợp

2.1 Hoán vị

2.1. Hoán 2.1. Hoán vị n vị

ổ 2.2. Tổ hợp (C 2.2. Tổ hợp (Combination)

2.3. Nguyên lý bù trừ • 2.1.1. Chỉnh hợp lặp chập m (m-permutation with repetition) • 2.1.2. Chỉnh hợp không lặp chập m (m-permutation) • 2.1.3. Hoán vị (permutation) • 2.1.4. Liệt kê hoán vị 2.4. Công thức đệ qui và hàm sinh

2.5. Số Stirling

Chap02-3

Chap02-4

2.6. Nguyên lý các lồng chim bồ câu

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

2.1.1. Hoán vị lặp (Chỉnh hợp lặp)

Chỉnh hợp lặp

• Dễ thấy tập tất cả các chỉnh hợp lặp chập m từ n phần tử của X chính là

Xm. Vì vậy, theo nguyên lý nhân ta có

m = nm.

• Định lý. An • Ví dụ 1. Tính số ánh xạ từ tập m phần tử U = {u1, u2, ..., um} vào tập n

• Giả sử X là tập n phần tử. • Đị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.

phần tử V.

• Giải: Mỗi ánh xạ f cần đếm được xác định bởi bộ ảnh (f(u1), f(u2), ..., f(um)), trong đó f(ui) ˛ V, i=1, 2, ..., m. Từ đó nhận được số cần tìm là nm.

• Chú ý: Trong tài liệu tiếng Anh, thuật ngữ "m-permutation with repetition" được dùng để chỉ chỉnh hợp lặp chập m. Vì thế có tài liệu dịch là hoán vị lặp.

• Ví dụ 2. Tính số dãy nhị phân độ dài n. • Giải: Mỗi dãy nhị phân độ dài n là một bộ gồm n thành phần, trong đó mỗi thành phần chỉ nhận một trong hai giá trị (1 hoặc 0). Từ đó suy ra số các dãy nhị phân độ dài n là 2n.

• Do mỗi tập con của tập n phần tử tương ứng với một vectơ đặc trưng là

• Ký hiệu số lượng chỉnh hợp lặp chập m từ n phần tử là An • Theo định nghĩa, một chỉnh hợp lặp chập m từ n phần tử của X có thể biểu diễn bởi

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.

Chap02-5

Chap02-6

(a1, a2, ..., am), ai ˛ X, i = 1, 2, ..., m.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Chỉnh hợp lặp

2.1.2. Chỉnh hợp không 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

• Định nghĩa. Ta gọi chỉnh hợp không lặp chập m (m-permutation) 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

(a1, a2, ..., am), ai ˛ X, i = 1, 2, ..., m, ai „aj, i „j.

• Việc đếm số lượng chỉnh hợp không lặp chập m từ n phần tử có

thể thực hiện theo nguyên lý nhân. Ta có

• Định lý.

• Giải: 4100 hay 1004 ? • Mỗi cách phân bố cần tìm có thể biểu diễn bởi bộ có thứ tự gồm 100 thành phần (b1, ..., b100) trong đó bi ˛ {A, F, E, L} là nhóm thực tập của sinh viên thứ i. Từ đó suy ra số cách phân bố cần đếm là 4100.

( ,

(

1)...(

) P n m n n

n m

- + =

(

! n n m -

Chap02-8

Chap02-7

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

• VÝ dô 1. TÝnh sè đơn ¸nh tõ tËp m phÇn tö U = {u1, u2, ..., um}

vµo tËp n phÇn tö V.

• Gi¶i: Mçi đơn ¸nh f cÇn ®Õm ®îc x¸c ®Þnh bëi bé ¶nh (f(u1),

lý nhân:

f(u2), ..., f(um)), trong ®ã f(ui) ˛ V, i=1, 2, ..., m, f(ui)„f(uj), i„j. Tõ ®ã nhËn ®îc sè cÇn tìm lµ n(n-1)...(n-m+1).

(cid:911)Học sinh thứ nhất có 10 cách xếp (cid:911)Tiếp đến học sinh thứ hai có thể xếp vào 1 trong 9 chỗ còn

lại, ...

• Ta lần lượt xếp các học sinh vào chỗ ngồi.

• Ví dụ 2. Có bao nhiêu cách xếp 4 học sinh vào ngồi sau một cái bàn có 10 chỗ ngồi với điều kiện không được phép ngồi lòng. • Giải. Đánh số các học sinh từ 1 đến 4, các chỗ ngồi từ 1 đến 10. Mỗi cách xếp học sinh cần đếm có thể biểu diễn bởi bộ có thứ tự (g1, g2, g3, g4), trong đó gi ˛ {1, 2, ..., 10} là chỗ ngồi của học sinh i. Từ điều kiện đầu bài gi„gj, i„j; do đó mỗi cách xếp cần đếm là một chỉnh hợp không lặp chập 4 từ 10. Vậy số cách xếp cần đếm là P(10,4) = 10.9.8.7 = 5040.

Chap02-9

Chap02-10

• Theo nguyên lý nhân có 10.9.8.7 = 5040 cách xếp

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Hoán vị

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

• Đị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ể

• 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

biểu diễn bởi

trên một máy vi tính. Hỏi có bao nhiêu cách?

(a1, a2, ..., an), ai ˛ X, i = 1, 2, ..., n, ai „aj, i „j.

• Rõ ràng P(n) = P(n,n). Vì vậy, ta có • Định lý.

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

1) ... 2 1

(

( ) P n

( , ) P n n

= · - · · · =

Chap02-11

Chap02-12

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Hoán vị

2.1.4. Liệt kê hoán vị

• Ví dụ 3. Có bao nhiêu song ánh từ tập n phần tử X

vào chính nó?

(cid:911)Cây liệt kê (cid:911)Thuật toán sinh hoán vị

• Xét hai phương pháp liệt kê:

• Cây liệt kê. Ví dụ, liệt kê các hoán vị của {a, b, c}

-

• Giải. Mỗi song ánh f cần đếm được xác định bởi bộ ảnh (f(u1), f(u2), ..., f(un)), trong đó f(ui) ˛ X, i=1, 2, ..., n, f(ui)„f(uj), i„j.

Từ đó nhận được số cần tìm là n!

b

a

c

Thành phần thứ 1

a

c

a

b

c

Thành phần thứ 2

• • Ví dụ 4. Có bao nhiêu cách bố trí n thợ thực hiện n việc sao cho mỗi thợ thực hiện một việc và mỗi việc do đúng một thợ thực hiện

Thành phần thứ 3

c

a

b

c

b

• Giải: n!

(a,b,c) (a,c,b)

(b,a,c)

(b,c,a)

(c,a,b)

(c,b,a)

Chap02-13

Chap02-14

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ

• C¸c ho¸n vÞ tõ 3 phÇn tö cña X ={1, 2, 3} ®îc liÖt kª theo

• Bµi to¸n ®Æt ra lµ: Cho X = {1, 2, ... , n}. H·y liÖt kª c¸c

Thuậuậuật t ttt toáoááoáán sinh h h hoáááoáoáán n n n vị

ho¸n vÞ tõ n phÇn tö cña X.

• Mçi ho¸n vÞ tõ n phÇn tö cña X cã thÓ biÓu diÔn bëi bé cã thø tù gåm n thµnh phÇn a = (a1, a2, ... , an) tho¶ m·n

ai ˛ X , i = 1, 2,..., n , ap „aq, p „q.

• Tríc hÕt ta xÐt quan hÖ thø tù tõ ®iÓn trªn tËp c¸c ho¸n vÞ. • Ta nãi ho¸n vÞ a = (a1, a2,..., an) ®i tríc ho¸n vÞ a' = (a'1, a'2, ... , a'n) trong thø tù tõ ®iÓn vµ ký hiÖu lµ a p a', nÕu tìm ®îc chØ sè k (1 £ k £ n) sao cho:

thø tù tõ ®iÓn nh sau: 3 2 3 1 2 1 1 1 2 2 3 3 2 3 1 3 1 2

Chap02-15

Chap02-16

a1 = a'1 , a2 = a'2, ... , ak-1 = a'k-1, ak < a'k . • Ho¸n vÞ ®Çu tiªn trong thø tù tõ ®iÓn lµ (1, 2, ... , n) • Ho¸n vÞ cuèi cïng lµ (n, n-1, ..., 1). • Ta cÇn t(cid:153)m c¸ch tõ mét ho¸n vÞ ®ang cã a = (a1, a2, ... , an) nÕu cha ph¶i lµ ho¸n vÞ cuèi cïng, ®a ra ho¸n vÞ kÕ tiÕp.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ

Thuật toán sinh kế tiếp

• Gi¶ sö ®ang cã ho¸n vÞ (3, 6, 2, 5, 4, 1), cÇn x©y dùng ho¸n

• Gi¶ sö a = (a1, a2, ... , an) lµ ho¸n vÞ cha ph¶i cuèi cïng,

khi ®ã ho¸n vÞ kÕ tiÕp nã cã thÓ x©y dùng nhê thùc hiÖn c¸c biÕn ®æi sau:

vÞ kÕ tiÕp nã trong thø tù tõ ®iÓn. • Ta cã chØ sè j = 3 (a3 =2 < a4 = 5). • Sè nhá nhÊt cßn lín h¬n a3 trong c¸c sè bªn ph¶i cña a3 lµ

• Cuèi cïng, lËt ngîc thø tù ®o¹n a4 a5 a6 ta thu ®îc ho¸n vÞ

a5 = 4. Đæi chç a3 víi a5 ta thu ®îc (3, 6, 4, 5, 2, 1), (cid:911)Tìm tõ ph¶i qua tr¸i ho¸n vÞ ®ang cã chØ sè j ®Çu tiªn tho¶ m·n aj < aj+1 (nãi c¸ch kh¸c: j lµ chØ sè lín nhÊt tho¶ m·n aj < aj+1);

(cid:911)Tìm ak lµ sè nhá nhÊt cßn lín h¬n aj trong c¸c sè ë bªn kÕ tiÕp (3, 6, 4, 1, 2, 5).

(cid:911)Đổi chỗ aj víi ak ; (cid:911)LËt ngîc ®o¹n tõ aj+1 ®Õn an .

Chap02-17

Chap02-18

ph¶i aj ;

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Chương 2. Lý thuyết tổ hợp

2.2. Tổ hợp

2.1. Hoán vị

• 2.2.1. Tổ hợp • 2.2.2. Tổ hợp lặp • 2.2.3. Tính chất của hệ số tổ hợp • 2.2.4. Liệt kê

2.3. Nguyên lý bù trừ

2.2. Tổ hợ 2.2. Tổ hợp (Combination) ợp (

2.5. Số Stirling

2.4. Công thức đệ qui và hàm sinh

Chap02-19

Chap02-20

2.6. Nguyên lý các lồng chim bồ câu

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Tổ hợp

2.2.1. Tổ hợp (m-combination)

(co the ky hieu la C(n,m) hay

• Định lý. m = C n

(cid:255) n (cid:255) m (cid:255)

(cid:255) ÷) (cid:255)

n! m!(n (cid:255)m)!

m (đôi khi ta

• Định nghĩa. Ta gọi tổ hợp chập m từ n phần tử của X là bộ

• C(n,m) được gọi là hệ số tổ hợp. • Chứng minh. Gọi Q là tập hợp tất cả các chỉnh hợp không

không có thứ tự gồm m thành phần, mỗi thành phần đều là phần tử của X, các thành phần khác nhau từng đôi. • Ký hiệu số lượng tổ hợp chập m từ n phần tử là Cn sẽ sử dụng ký hiệu C(n,m))

biểu diễn bởi bộ không có thứ tự

lớp chỉ khác nhau về thứ tự.

• Theo định nghĩa, một tổ hợp chập m từ n phần tử của X có thể lặp chập m của n phần tử. (cid:911)Phân Q thành các lớp sao cho hai chỉnh hợp thuộc cùng một

(cid:911)Rõ ràng các lớp này tạo thành một phân hoạch của tập Q và mỗi lớp như thế là tương ứng với một tổ hợp chập m của n.

X có thể biểu diễn bởi bộ có thứ tự

(cid:911) Số chỉnh hợp trong mỗi lớp là bằng nhau và bằng m! (số

hoán vị).

{a1, a2, ..., am}, ai ˛ X, i = 1, 2, ..., m, ai „aj, i „j. • Với giả thiết X={1, 2,...,n}, một tổ hợp chập m từ n phần tử của

(cid:911)Số các lớp là bằng số tổ hợp chập m của n: C(n,m).

Chap02-21

Chap02-22

(a1, a2, ..., am), ai ˛ X, i = 1, 2, ..., m, 1 £ a1 < a2 < ...

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Tổ hợp

Ví dụ

• VÝ dô 1. Cã n ®éi bãng thi ®Êu vßng trßn. Hái ph¶i tæ chøc

• Theo nguyên lý cộng, ta có

n(n-1)...(n-m+1) = m! C(n,m).

1)(

( n n

n m

bao nhiªu trËn ®Êu? |Q| = m! C(n,m) • Gi¶i: Cø 2 ®éi thì cã mét trËn. Tõ ®ã suy ra sè trËn ®Êu sÏ suy ra b»ng sè c¸ch chän 2 ®éi tõ n ®éi, nghÜa lµ b»ng

- +

m C n

2)...( ! m

! n m n m -

• Từ đó nhận đượ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 ‡ 4) ®Ønh n»m ë trong ®a gi¸c, nÕu biÕt r»ng kh«ng cã ba ®êng chÐo nµo ®ång quy t¹i ®iÓm ë trong ®a gi¸c?

• Gi¶i: Cø 4 ®Ønh cña ®a gi¸c thì 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µ

Chap02-23

Chap02-24

C(n,4) = n(n-1)(n-2)(n-3)/24. • Định lý được chứng minh. • Khi nhËn xÐt r»ng, gi¸ trÞ cña phÐp chia trong công thức của định lý lµ mét sè nguyªn, ta nhËn ®îc mét kÕt qu¶ lý thó trong sè häc: TÝch cña k sè tù nhiªn liªn tiÕp bao giê còng chia hÕt cho k!.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

2.2.2. Tổ hợp lặp. Bài toán chia kẹo

Bài toán chia kẹo

• Cần thả n quả bóng giống nhau vào k phòng:

Xét bài toán: "Giả sử k và n là các số nguyên không âm. Hỏi phương trình sau đây có bao nhiêu nghiệm?

Room1, Room2, …, Roomk. Hỏi có bao nhiêu cách phân bổ khác nhau?

• Nếu gọi tj là số lượng quả bóng thả vào Roomj, j = 1, 2, ..., n; thì vấn đề đặt ra dẫn về bài toán: Hỏi phương trình sau đây

Nội dung thực tế:

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

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?

Chap02-25

Chap02-26

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

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

D1

D2 D3

D4

D5

• Xét dãy n+k-1 hộp. Tô k-1 hộp nào đó bởi màu xám; các hộp xám này sẽ là vách ngăn: D1, D2, D(k-1).

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

D1

D2 D3

D4

D5

• Thả n quả bóng vào n hộp còn lại, mỗi hộp 1 quả.

Room1

Room6

Room2

Room3

Room4

Room5

Chap02-27

Chap02-28

• Thả các quả bóng trước vách ngăn D1 vào Room1, các quả bóng giữa vách ngăn D1 và D2 vào Room2, vân vân, và cuối cùng các quả bóng sau D(k-1) vào Room(k).

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

• Bài toán chia kẹo 2: Có bao nhiêu cách chia n cái kẹo cho k em bé mà trong đó mỗi em được ít nhất một cái? Hay tương đương: Hỏi phương trình sau đây : • Như vậy, rõ ràng tồn tại tương ứng 1-1 giữa một cách phân bổ các quả bóng và một cách chọn k-1 hộp trong số n+k-1 hộp làm vách ngăn.

t1 + t2 + ... + tk = n. • Do có tất cả

n kC -

1 k 1 + -

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

cách chọn k-1 hộp từ n+k-1 hộp, nên đó cũng chính là số cách phân bổ n quả bóng vào k phòng, cũng chính là số cách chia n cái kẹo cho k em bé và cũng chính là số nghiệm nguyên không âm của phương trình: t1 + t2 + . . . + tk = n.

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

nC -

1 k 1 -

Chap02-29

Chap02-30

• Con số nói trên cũng được gọi là số tổ hợp lặp chập k từ n (k- combination with repetition from n elements).

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

2.2.3. Tính chất của hệ số tổ hợp

Tam giác PASCAL

• Tõ b) vµ c), ta cã thÓ tÝnh tÊt c¶ c¸c hÖ sè tæ hîp chØ b»ng phÐ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éng. C¸c hÖ sè nµy ®îc tÝnh vµ viÕt lÇn lît theo tõng dßng (mçi dßng øng víi mét gi¸ trÞ n=0, 1, ...), trªn mçi dßng chóng ®îc tÝnh vµ viÕt lÇn lît theo tõng cét (mçi cét øng víi mét gi¸ trÞ m = 0, 1, ..., n) theo b¶ng tam gi¸c díi ®©y:

C(n,m) = C(n,n-m)

b) ĐiÒu kiÖn ®Çu

c) C«ng thøc ®Ö qui

C(n,0) = 1; C(n,n) = 1, n ‡ 0

B¶ng nµy ®îc gäi lµ tam gi¸c Pascal.

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

Chap02-31

Chap02-32

• Điều kiện đầu suy trực tiếp từ định nghĩa của hệ số tổ hợp. C¸c tính chất còn lại có thể chứng minh nhờ sử dụng công thức trong định lý 4.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Tam giác PASCAL

• Tam giác Pascal, n=8

• Mỗi số trong ô lục giác bằng tổng của hai số của hai ô

Chap02-33

Chap02-34

chung cạnh ở phía trên nó

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Khai triển nhị thức

Tổng quát hóa

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

• Định lý khai triển nhị thức có thể tổng quát cho trường hợp phải khai triển lũy thừa của tổng nhiều hơn hai số hạng. Khi khai triển (x+y+z)n, ta có n!/(i!·j!·k!) cách tạo ra số hạng chứa i thừa số là x, j thừa số là y và k thừa số là z. Vì thế số này chính là hệ số của số hạng xi yj zk trong khai triển đang xét.

n m -

... + +

(

)

0 n

n n

m m C x n

hÖ sè cña xm yn-m sÏ lµ sè c¸ch chän m nh©n tö (x + y) mµ tõ ®ã ta lÊy ra x vµ ®ång thêi trong n-m nh©n tö cßn l¹i ta lÊy ra y, nghÜa lµ

C n

• Ví dụ: Xét khai triển (x+y+z)7. Hệ số của xy2z4 là số cách

n i -

i C x y n

tạo ra số hạng dạng xyyzzzz. Số đó là bằng

(cid:229)

7! / (1!(cid:153)2!(cid:153)4!) = 105.

Chap02-35

Chap02-36

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

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Multinomials

Xét cách xây dựng dãy gồm n đối tượng từ k loại đối tượng sao cho trong đó có n1 đối tượng loại 1, n2 đối tượng loại 2,..., nk đối tượng loại k (n1+…+nk = n). Ký hiệu C(n; n1,...,nk) là số cách tạo dãy như vậy. Số này được gọi là hệ số bội thức (multinomial).

Định lý.

,...,

)

( ; C n n 1

n k

n ,...,

, n n 1 2

n k

! n n 1 2

! n !.... n k

(cid:230) (cid:231) Ł

(cid:246) (cid:247) ł

CM. Ta lần lượt chọn các đồ vật. Đồ vật loại 1 có C(n,n1) cách chọn. Sau khi đồ vật 1 đã chọn, đồ vật loại 2 có C(n-n1,n2) cách chọn, ..., cuối cùng đồ vật loại k có C(nk,nk) cách chọn. Theo nguyên lý nhân

Khi k=2 ta có hệ số nhị thức C(n,n1). Có thể chứng minh bằng cách khác: Nếu các đối tượng là không phân biệt thì có n! cách. Chúng ta đã tính lặp lại n1!·…·nk! lần, từ đó suy ra định lý. Ví dụ: Có bao nhiêu từ gồm 11chữ cái lấy từ 11 chữ cái của từ “MISSISSIPPI”? Giải: Trong từ “MISSISSIPPI” có tất cả có 1 chữ cái “M”, 4 chữ “I”, 4 chữ “S”, và 2 chữ “P”. Ta xét cách xếp vị trí cho các chữ cái này trong từ cần xây dựng. Có C(11,1) vị trí để xếp "M", tiếp đến có C(10,4) để xếp vị trí cho 4 chữ "I", 4 chữ "S" được xếp vào 6 vị trí còn lại bởi C(6,4) cách và cuối cùng có C(2,2) cách xếp 2 chữ "P". Theo nguyên lý nhân có:

C(n; n1,...,nk) = C(n,n1)·C(n-n1,n2)· ...·C(nk,nk),

C(11,1)(cid:153)C(10,4)(cid:153)C(6,4)(cid:153)C(2,2) = 11!/(1! 4! 4! 2!) = 34650.

từ đó suy ra kết quả cần chứng minh.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Tổ hợp

2.2.4. Liệt kê m-tập con

• Bµi to¸n ®Æt ra lµ: Cho X = {1, 2, ... , n}. H·y liÖt kª c¸c tËp

...

(*)

1 n

0 n

n n

• Trong c«ng thøc Niuton đặt y=1 ta có: + C C

1 n - C x n

+ • RÊt nhiÒu ®¼ng thøc vÒ hÖ sè tæ hîp ®îc suy tõ (*). Ch¼ng h¹n,

con m phÇn tö cña X.

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:

• Mçi tËp con m phÇn tö cña X cã thÓ biÓu diÔn bëi bé cã thø

C(n,0) – C(n,1) + C(n,2) - ...+(-1)nC(n,n) = 0,

tù gåm m thµnh phÇn a = (a1, a2, ... , am) tho¶ m·n ai ˛ X , i = 1, 2,..., m ; a1 < a2 < ... < am • Xét hai phương pháp liệt kê tất cả m-tập con của X:

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

Chap02-39

Chap02-40

(cid:911)Cây liệt kê (cid:911)Thuật toán sinh m-tập con

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

2.2.4. Cây liệt kê m-tập con

• Mçi tËp con m phÇn tö cña X cã thÓ biÓu diÔn bëi bé cã thø

Thuậuậậuậuậật t t toáoáoán sinh mmm-mmm-tập con

• Cây liệt kê. Ví dụ, liệt kê các tập con 3 phần tử của {1,...,5}

tù gåm m thµnh phÇn a = (a1, a2, ... , am) tho¶ m·n ai ˛ X , i = 1, 2,..., m ; a1 < a2 < ... < am

• Tríc hÕt ta ®a vµo quan hÖ thø tù tõ ®iÓn trên tập tất cả m-

-

Thành phần thứ 1

tập con của X :

1

2

3

Thành phần thứ 2

• Ta nãi tËp con a = (a1, a2,..., an) ®i tríc tËp con a' = (a'1, a'2, ... , a'n) trong thø tù tõ ®iÓn vµ ký hiÖu lµ a p a', nÕu tìm ®îc chØ sè k (1 £ k £ m) sao cho:

3

2

4

a1 = a'1 , a2 = a'2, ... , ak-1 = a'k-1, ak < a'k .

Thành phần thứ 3

4

5

3

5

4

5

4

5

135

235

345

123 124 125

134

145 234

245

Chap02-41

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ

Thuật toán sinh kế tiếp

• C¸c tËp con 3 phÇn tö cña X = {1, 2, 3, 4, 5} ®îc liÖt kª theo

• TËp con ®Çu tiªn trong thø tù tõ ®iÓn lµ (1, 2, ... , m) • TËp con cuèi cïng lµ (n-m+1, n-m+2, ..., n). • Gi¶ sö a=(a1, a2, ... , am) lµ tËp con ®ang cã cha ph¶i cuèi cïng, khi ®ã tËp con kÕ tiÕp trong thø tù tõ ®iÓn cã thÓ x©y dùng b»ng c¸ch thùc hiÖn c¸c quy t¾c biÕn ®æi sau ®èi víi tËp ®ang cã:

Chap02-43

Chap02-44

(cid:911)Tìm từ bên phải dãy a1, a2,..., am phÇn tö ai „n-m+i, (cid:911)Thay ai bëi ai + 1; (cid:911)Thay aj bëi ai + j - i, víi j = i+1, i+2,..., m. thø tù tõ ®iÓn nh sau 3 4 5 4 5 5 4 5 5 5 2 2 2 3 3 4 3 3 4 4 1 1 1 1 1 1 2 2 2 3

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ

Chương 2. Lý thuyết tổ hợp

• Ví dụ: n = 6, m = 4. Giả sử đang có tập con (1, 2, 5, 6), cần

2.1. Hoán vị

xây dựng tập con kế tiếp nó trong thứ tự từ điển. . Tổ hợ 2.2. Tổ hợp (C 2.2. Tổ hợp (Combination) • 1 2 5 6

2.3. Nguyên lý bù trừ

3 4 5 6 (tập con cuối cùng)

tiếp (1, 3, 4, 5).

2.5. Số Stirling

2.4. Công thứ 2.4. Công thức đệ qui và hàm sinh • Ta có i=2, thay a2 = 3, và a3 = 4, a4 = 5, ta được tập con kế

Chap02-45

Chap02-46

2.6. Nguyên lý các lồng chim bồ câu

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

2.3. Nguyên lý bù trừ

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

• Nguyên lý bù trừ trong trường hợp hai tập:

2.3.1. Phát biểu nguyên lý 2.3.2. Các ví dụ áp dụng

(The inclusiononononnonon-nnnnnn-exclusion principle)

|A ¨ B| = |A| + |B| - |A ˙ B| (1) Ví dụ: Giả sử A có 5 phần tử, B có 4 phần tử và có 2 phần tử thuộc vào cả A lẫn B. Khi đó số phần tử của hợp hai tập là 5+4-2 = 7, chứ không phải là 5+4 = 9.

• CM:

A˙B

2 lần

Chap02-47

Chap02-48

1 lần

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Nguyên lý bù trừ

|A¨B ¨C| = |A| +|B| + |C| - |A˙B| - |A˙C|- |B˙C)|+ |A˙B˙C)| (2)

kỳ. Khi đó:

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

• Mở rộng cho trường hợp 3 tập: Giả sử A, B, C là ba tập bất

|A¨B ¨C|

= |(A ¨B)¨C)|

= |A¨B| + |C| - |(A¨B)˙C|

• Trong tổng của ba số hạng đầu tiên các phần tử chung của A và B được tính hai lần, vì vậy phải trừ bớt đi một lần. Tương tự như vậy đối với các phần tử chung của A và C và các phần tử chung của B và C.

= |A| +|B| + |C| - |A˙B| - |A˙C|- |B˙C)|+ |A˙B˙C)|

= |A| +|B| + |C| - |A˙B| - |(A˙C)¨(B˙C)|

Vậy

• Thế nhưng, trừ như vậy là hơi quá, bởi vì những phần tử chung của cả ba tập A, B và C chưa được tính đến trong tổng của 6 số hạng đầu tiên. Vì vậy phải cộng bù lại.

|A¨B¨C| =

|A| +|B| + |C| - |A˙B| - |A˙C|- |B˙C)|+ |A˙B˙C)| (2)

Chap02-49

Chap02-50

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ minh họa

Nguyên lý bù trừ

dt = 2-1=1

...

)

dt = 4-3=1 U

¨ ¨ ¨

( 1)m

+ -

- N N 1

N-

˙B C

˙A C

( N A trong ®ã

A B C ˙ ˙

...

1, 2,...,

˙ ˙ ˙

dt = 1

N k

( N A i 1

A i 2

A i k

(cid:229)

• §Þnh lý. Gi¶ sö A1, A2, ... , Am lµ c¸c tËp h÷u h¹n. Khi ®ã =

˙A B

...

1 £ < < < £

i 2

i 1

i m k

• Giả sử mỗi hình tròn có diện tích là 4. Giao của hai hình tròn có diện

N1 = N(A1) + ... + N(Am), Nm = N(A1 ˙ A2 ˙ ... ˙ Am) ).

tích 2, Giao của cả ba hình tròn có diện tích 1. Hỏi tổng diện tích bị phủ bởi ba hình tròn là bao nhiêu? A B C A ¨ ¨ = | | |

- ˙ - ˙ - ˙ + ˙ ˙ |

A B C

C A

B C

A B

• A=4+4+4 – 2 -2 -2 + 1 = 12 – 6 + 1 = 7.

Chap02-51

Chap02-52

(Nk lµ tæng sè phÇn tö cña tÊt c¶ c¸c tËp lµ giao cña k tËp lÊy tõ m tËp ®· cho, nãi riªng

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Nguyên lý bù trừ

• B©y giê ta ®ång nhÊt tËp Ak víi tÝnh chÊt Ak cho trªn mét tËp X nµo ®ã vµ ®Õm xem cã bao nhiªu phÇn tö cña X kh«ng tho¶ m·n bÊt cø mét tÝnh chÊt Ak nµo c¶.

• Gäi‘N lµ sè cÇn ®Õm. Do A1 ¨ A2 ¨ . . . ¨ Am lµ tËp tÊt c¶ c¸c phÇn tö cña X tho¶ m·n Ýt nhÊt mét trong sè m tÝnh chÊt ®· cho, nªn ta cã:

• Chøng minh. • Chó ý r»ng, sè c¸c giao cña k tËp lÊy tõ m tËp b»ng C(m,k), k=1,2,..., m. • §Ó chøng minh c«ng thøc cña nguyªn lý bï trõ, ta sÏ tÝnh xem mçi phÇn tö cña tËp A1 ¨ A2 ¨ . . . ¨ Am ®îc ®Õm bao nhiªu lÇn trong vÕ ph¶i: • XÐt mét phÇn tö tuú ý a ˛ A1 ¨ A2 ¨ . . . ¨ Am. Gi¶ sö a lµ phÇn tö cña k tËp trong sè m tËp ®· cho. Khi ®ã a ®îc ®Õm ë vÕ ph¶i cña c«ng thøc

C(k,1) – C(k,2)+ ... + (-1)k-1C(k,k)

‘N = N(X )(cid:127) N(A1 ¨ A2 ¨ . . . ¨ Am) = N(X ) (cid:127) N1 + N2 -...+((cid:127) 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.

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 –

• C«ng thøc thu ®îc cho phÐp tÝnh‘N qua c¸c Nk trong trêng hîp

1)k = 1

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

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

Chap02-53

Chap02-54

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Các ví dụ áp dụng

Ví dụ

• VÝ dô 1. Hái trong tËp X = {1, 2, ..., 10000} cã bao nhiªu sè

N2 = N(A3 ˙ A4) + N(A3 ˙ A7) + N(A4 ˙ A7)

kh«ng chia hÕt cho bÊt cø sè nµo trong c¸c sè 3, 4, 7?

= [10000/(3·4)] + [10000/(3·7)] + [10000/(4·7)]

• Gi¶i. Gäi

= 833 + 476 + 357 = 1666,

Ai ={ x ˛ X : x chia hÕt cho i} , i = 3, 4, 7.

N3 = N(A3 ˙ A4 ˙ A7) = [10000/(3·4·7) ] = 119,

• Khi ®ã A3 ¨ A4 ¨ A7 lµ tËp c¸c sè trong X chia hÕt cho Ýt nhÊt mét

ë ®©y ký hiÖu [ r ] ®Ó chØ sè nguyªn lín nhÊt kh«ng vît qu¸ r.

trong 3 sè 3, 4, 7, suy ra sè lîng c¸c sè cÇn ®Õm sÏ lµ N(X) – N(A3 ¨ A4 ¨ A7) = 10000 – (N1

– N2 + N3).

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

• Ta cã

10000 - 7261 + 1666 - 119 = 4286.

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

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

Chap02-55

Chap02-56

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ 3

Ví dụ

• Ví dụ 3. Đếm số nghiệm nguyên không âm của phương trình x1 + x2 + x3 = 11, thỏa mãn x1 £ 3, x2 £ 4, x3 £ 6.

• VÝ dô 2. Cã bao nhiªu x©u nhÞ ph©n ®é dµi 10 hoÆc lµ b¾t

• Gi¶i. Ta cã

P1: x1 > 3 ; P2: x2 > 4; P3: x3 > 6.

®Çu bëi 00 hoÆc lµ kÕt thóc bëi 11? • Giải. Xét các tính chất

(cid:911)Sè x©u nhÞ ph©n ®é dµi 10 b¾t ®Çu bëi 00 lµ 28 = 256

• Theo nguyªn lý bï trõ suy ra sè x©u nhÞ ph©n hoÆc b¾t ®Çu

(cid:911)Sè x©u nhÞ ph©n ®é dµi 10 kÕt thóc bëi 11 lµ 28 = 256. • Lời giải cần đếm là lời giải không thỏa mãn bất cứ tính chất nào trong P1, P2, P3. Theo nguyên lý bù trừ số lượng lời giải cần đếm là bằng (cid:911)Sè x©u nhÞ ph©n ®é dµi 10 b¾t ®Çu bëi 00 vµ kÕt thóc bëi N – N1 + N2 – N3. 11 lµ 26 = 64.

• Ta cần tính các số N, N1 , N2 , N3. • Tổng số nghiệm nguyên không âm của phương trình là bëi 00 hoÆc kÕt thóc bëi 11 lµ bằng N = C(3+11–1, 11) = 78.

Chap02-57

Chap02-58

256 + 256 - 64 = 448.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ 3

Bài toán bỏ thư

• Để đếm số lời giải thỏa mãn tính chất x1 > 3 ta lập luận như sau: Đổi

biến y1 = x1 - 4, số nghiệm nguyên không âm của phương trình x1 + x2 + x3 = 11 thỏa mãn tính chất x1 > 3 chính là bằng số nghiệm nguyên không âm của phương trình y1 + x2 + x3 = 11 – 4 = 7. Vậy

N(P1) = C(3+7–1,7) = 36.

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

• Tương tự như vậy ta có • Số lời giải thỏa mãn tính chất x2>4: N(P2) = C(3+6-1,6) = 28. • Số lời giải thỏa mãn tính chất x3>6: N(P3) = C(3+4-1,4) = 15. • Số lời giải thỏa mãn tính chất x1>3 và x2>4: N(P1˙P2)=C(3+2-1,2)=6. • Số lời giải thỏa mãn tính chất x1>3 và x3>6: N(P1˙P3)=C(3+0-1,0)=1. • Số lời giải thỏa mãn tính chất x2>4 và x3>6: N(P2˙P3)=0. • Số lời giải thỏa mãn tính chất x1>3, x2>4 và x3>6: N(P1˙P2˙P3)=0. • Ta thu được số lượng lời giải thỏa mãn điều kiện đầu bài là

(p1, p2, ..., pn),

78 – 36 – 28 –15 + 6 + 1 + 0 – 0 = 6.

Chap02-59

Chap02-60

trong ®ã pi lµ phong b× bá l¸ thø thø i. Tõ ®ã suy ra tån t¹i t- ¬ng øng 1-1 gi÷a mét c¸ch bá th vµo phong b× víi mét ho¸n vÞ cña n sè. VËy cã tÊt c¶ n! c¸ch bá th.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

• Chó ý lµ

...

1, 2,...,

˙ ˙ ˙

N k

( N A i 1

A i 2

A i k

(cid:229)

...

1 £ < < < £

i 2

i 1

i k

• VÊn ®Ò cßn l¹i lµ ®Õm sè c¸ch bá th sao cho kh«ng cã l¸ th

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:

nµo ®óng ®Þa chØ.

Nk = C(n, k).(n-k)! = n! / k!

(cid:127) ...+((cid:127) 1)nNn

‘N = N(X ) (cid:127) N1 + N2

• Do ®ã

(

... - +

! ( n 1

)

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

1 2 !

1 ) - n !

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

(

...

) 1 - n !

1 ! 1

1 ! 2

Chap02-61

Chap02-62

trong ®ã‘N lµ sè cÇn t×m, N(X) = n!, cßn Nk lµ sè tÊt c¶ c¸c c¸ch bá th sao cho cã k l¸ th ®óng ®Þa chØ.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Số lượng toàn ánh

Nguyên lý bù trừ

Toàn ánh: Ánh xạ f từ A vào B là toàn ánh nếu với mỗi phần tử b thuộc B đều tìm được a thuộc A sao cho f(a)=b.

Giả sử A={a1, a2, ..., am } và B={b1, b2, ..., bn }, m ‡n. Hỏi có bao nhiêu toàn ánh từ A vào B?

• Díi ®©y lµ mét vµi gi¸ trÞ cña Dn, cho ta thÊy Dn t¨ng nhanh

Ta muốn tất cả bi đều thuộc miền giá trị của f. Gọi P i là tính chất "bi không nằm trong miền giá trị của f ".

A • 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è thu ®îc trong bµi to¸n trªn ®îc gäi lµ sè mÊt thø tù (number of derangements) vµ ®îc ký hiÖu lµ Dn.

nh thÕ nµo khi n t¨ng:

2

3

4

5

6

7

8

9

10

11

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 P

1,..., P n.

1

2 9 44 265 1854 14833 133496 1334961 4890741

n Dn

Ký hiệu:

Pi = tập các ánh xạ từ A vào B có tính chất P

i , i=1, 2, ...,n.

Không tồn tại điểm không có mũi tên đi vào

Chap02-64

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Chap02-63

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Số lượng toàn ánh

• Theo nguyên lý bù trừ số lượng toàn ánh cần đếm là:

• Ta viết gọn công thức

...

1, 2,...,

˙ ˙ ˙

N – N1 + N2 – ... +(–1)n Nn. =

N k

( N P i 1

P i 2

P i k

(cid:229)

...

£ < < < £

i 2

i 1

i k

nm – C(n,1)(n-1)m + C(n,2)(n-2)m – ...+ (-1)n-1C(n,n-1)1m.

• Ta có:

- 1

- + -

( 1)

...

- 1 m 1

- 1

(cid:911) N - số ánh xạ từ m-tập A vào n-tập B: nm (cid:911) Do N(Pi) - số ánh xạ không có bi trong miền giá trị,

1 C n ( n n

(

...

( 1)

m - 1 1

- ( 1)

n C n - + -

0 C n

2 C n ( n 1 C n ( n

2 C n ( n

n C n

n m 0 n

nên N(Pi) = (n-1)m, do đó N1 = C(n,1) (n-1)m

- ( 1)

C n k (

)

k n

(cid:911) Do N(Pi˙Pj) - số ánh xạ không có bi và bj trong miền giá trị,

(cid:229)

nên N(Pi˙Pj) = (n-2)m , do đó N2 = C(n,2) (n-2)m.

...

)

(

)

˙ ˙ ˙

n k -

(cid:911) Tổng quát ta có P i 2

( N P i 1

P i k

dó đó Nk = C(n,k) (n - k)m.

• Từ đó ta có số lượng toàn ánh là:

dưới dạng sau đây:

Chap02-65

Chap02-66

nm – C(n,1)(n-1)m + C(n,2)(n-2)m – ...+ (-1)n-1C(n,n-1)1m.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Chương 2. Lý thuyết tổ hợp

2.4 Công thức đệ qui và hàm sinh

2.1. Hoán vị

2.4.1. Xây dựng công thức đệ qui 2.4.2. Giải công thức đệ qui 2.4.3. Hàm sinh và công thức đệ qui

2.3. Nguyên lý bù trừ

2.2. Tổ hợp (Combination)

2.5. Số Stirling

2.4. Công 2.4. Công thức đệ qui và hàm sinh thứ

Chap02-67

Chap02-68

2.6. Nguyên lý các lồng chim bồ câu

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

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

• Ví dụ 1. Công thức đệ qui cho C(n,k) - số lượng tập con k

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

phần tử của tập n phần tử X.

C(n,0) = 1 và C(n,n) = 1 (1)

trị tính ở các bước trước và một số giá trị đầu.

• Theo định nghĩa

• Là một kỹ thuật quan trọng cho phép giải nhiều bài

• Giả sử n > k > 0, ta xây dựng công thức đệ qui để tính

toán đếm

C(n,k). Cố định một phần tử x ˛ X. Phân tập các tập con k phần tử của X ra thành 2 tập:

(cid:911)A – tập các tập con k phần tử có chứa x;

(cid:911)B – tập các tập con k phần tử không chứa x.

• Rõ ràng A và B tạo thành phân hoạch của tập tất cả các tập

Chap02-69

Chap02-70

con k phần tử của X.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

• Công thức đệ qui (2) cho phép viết hàm đệ qui sau đây để

• Công thức đệ qui (2) cùng với điều kiện đầu (1) cho phép • Rõ ràng A và B tạo thành phân hoạch của tập tất cả các tập con tính giá trị của C(n, k) với mọi giá trị của n và k. k phần tử của X. Do đó, theo nguyên lý cộng:

C(n,k) = |A| + |B|. tính giá trị của C(n,k): • Ta có:

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);

(cid:911)Do mỗi tập con trong A có chứa x, nên k-1 phần tử còn lại của nó là một tập con k-1 phần tử của tập X \ {x}, suy ra |A| = C(n-1,k-1) (cid:911)Tương tự như vậy,

end;

|B| = C(n-1, k)

C(n,k) = C(n-1, k-1) + C(n-1,k), n > k > 0 (2)

Chap02-71

Chap02-72

• Vậy,

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

• VÝ dô 2. Trªn mÆt ph¼ng, kÎ n ®êng th¼ng sao cho kh«ng cã 2 ®êng nµo song song vµ 3 ®êng nµo ®ång quy. Hái mÆt ph¼ng ®îc chia thµnh mÊy phÇn ?

• Gi¶i: Gäi sè phÇn mÆt ph¼ng ®îc chia bëi n ®êng th¼ng lµ Sn. Râ ràng

S1 = 2, (3)

C*(n,0) =1; C*(n,n) = 1 C*(n,k) = C*(n-1, k-1) + C*(n-1,k)+1, n > k > 0 tức là C*(n,k) thoả mãn công thức đệ qui như hệ số tổ hợp C(n, k), do đó:

• Hàm vừa xây dựng không cho một cách tính hiệu quả. Thực vậy, nếu gọi C*(n,k) là số phép toán “gán giá trị” phải thực hiện bởi lệnh gọi hàm C(n,k), dễ thấy

• XÐt n > 1, ta tìm c«ng thøc ®Ö qui cho Sn. • Gi¶ sö ®· kÎ n-1 ®êng th¼ng, khi ®ã mÆt ph¼ng ®îc chia ra lµm Sn-1 phÇn. B©y giê kÎ thªm ®êng th¼ng thø n. Đêng th¼ng nµy c¾t n-1 ®êng th¼ng ®· vÏ t¹i n- 1 giao ®iÓm. C¸c giao ®iÓm nµy chia ®êng th¼ng thø n ra lµm n phÇn, mçi phÇn nh vËy sÏ chia mét phÇn nµo ®ã sinh bëi n-1 ®êng th¼ng vÏ tríc ®ã ra lµm hai phÇn. Tõ ®ã suy ra, sau khi vÏ ®êng th¼ng thø n sè phÇn tăng thªm lµ n. Tõ ®ã nhËn ®îc c«ng thøc ®Ö qui

C*(n,k) ~ n!/[k!(n-k)!] và giá trị này là rất lớn khi n lớn và k = n/2.

Sn = Sn-1 + n, n ‡ 2 (4)

Chap02-73

Chap02-74

• Dễ dàng xây dựng một hàm lặp để tính giá trị của C(n, k) một cách hiệu quả hơn.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

G42

G41

• Để tìm công thức trực tiếp, ta cộng các hệ thức Sk = Sk-1 + k víi

G32

phần 4

G22

phần 3

G31

G12

G21

phần 2

G11

Phương pháp thế: Sn = Sn-1+n

k = 2, ..., n. S1 = 2 S2 = S1 + 2 S3 = S2 + 3 ... Sn-1= Sn-2 + (n-1) Sn = Sn-1 + n

phần 1

Sn = 2 + 2 + 3 + ...+(n-1) + n = n(n+1)/2 + 1 = (n2+n+2)/2

Chap02-75

Chap02-76

= Sn-2+(n-1)+n = Sn-3 +(n-2)+(n-1) +n = .... = S1+2+3+....+(n-1)+n = 2+2+3+....+(n-1)+n

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

fn = |A| + |B|.

• Do đó, theo nguyên lý cộng:

(cid:911) Do mỗi chỉnh hợp trong A chứa 1 ở vị trí đầu tiên, nên n-1 phần tử còn lại

• Ta có: • Ví dụ 3. Xây dựng công thức đệ qui cho fn là số chỉnh hợp lặp chập n từ hai phần tử 0, 1 (cũng chính là xâu nhị phân độ dài n) không chứa hai số 0 liền nhau.

sẽ tạo thành một chỉnh hợp cần đếm độ dài n-1, suy ra

|A| = fn-1

• Giải. Ta có

f1 = 2; f2 = 3

(cid:911) Do mỗi chỉnh hợp trong B chứa 0 ở vị trí đầu tiên, nên vị trí thứ hai của nó phải là 1 còn n-2 phần tử còn lại sẽ tạo thành một chỉnh hợp cần đếm độ dài n-2, suy ra

(cid:911)A – tập các chỉnh hợp cần đếm chứa 1 ở vị trí đầu tiên;

|B| = fn-2

Giả sử n > 2. Phân tập các chỉnh hợp cần đếm ra thành 2 tập:

(cid:911)B – tập các chỉnh hợp cần đếm chứa 0 ở vị trí đầu tiên; • Vậy, ta thu được công thức đệ qui • Rõ ràng A và B tạo thành phân hoạch của tập tất cả các chỉnh

f1 = 2; f2 = 3; fn = fn-1 + fn-2, n > 2 (5)

Chap02-77

Chap02-78

hợp cần đếm.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

• Do đó, theo nguyên lý cộng:

... ...

(cid:911)|A| = Qn-1 (cid:911)|B| = Qn-2

• Ví dụ 4. Xây dựng công thức đệ qui cho Qn là số lượng cách phủ lưới ô vuông kích thước 2·n bằng các quân bài domino. Qn = |A| + |B|. • Giải. Ta có • Ta có: A Q1 = 1; Q2 = 2 (xem hình vẽ)

... ...

• Vậy, ta thu được công thức đệ qui

• Giả sử n > 2. Phân tập các cách phủ cần đếm ra thành 2 tập: B (cid:911)A – tập các cách phủ trong đó ô ở góc trên trái được phủ bởi quân bài nằm đứng;

(cid:911)B – tập các cách phủ trong đó ô ở góc trên trái được phủ bởi Q1 = 1; Q2 = 2; Qn = Qn-1 + Qn-2, n > 2 (6) quân bài nằm ngang.

Chap02-79

Chap02-80

• Rõ ràng A và B tạo thành phân hoạch của tập tất cả các cách phủ cần đếm.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

•

Gi¶i: Râ rµng:

(i) ChuyÓn n-1 ®Üa tõ cäc a ®Õn cäc b sö dông cäc c lµm

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

cäc c.

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

• Bài toán đặt ra là: Tìm công thức đệ qui cho hn là số lần di

• Ví dụ 5. (Bài toán tháp Hà nội). Trò chơi tháp Hà nội được trình bày như sau: “Có 3 cọc a, b, c. Trên cọc a có một chồng gồm n cái đĩa đường kính giảm dần từ dưới lên trên. Cần phải chuyển chồng đĩa từ cọc a sang cọc c tuân thủ qui tắc: mỗi lần chỉ chuyển 1 đĩa và chỉ được xếp đĩa có đường kính nhỏ hơn lên trên đĩa có đường kính lớn hơn. Trong quá trình chuyển được phép dùng cọc b làm cọc trung gian”.

Chap02-81

Chap02-82

(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. chuyển đĩa ít nhất cần thực hiện để hoàn thành nhiệm vụ đặt ra trong trò chơi tháp Hà nội.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

• • Ta có thể tìm được công thức trực tiếp cho hn bằng phương pháp thế:

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

= 22 hn−2 + 2 + 1 hn = 2hn-1 + 1, n ≥ 2.

•

= 2 (2 hn−2 + 1) + 1 = 22(2 hn−3 + 1) + 2 + 1 = 23 hn−3 + 22 + 2 + 1 … Sö dông c«ng thøc ®Ö qui vµ ®iÒu kiÖn ®Çu võa tìm ®îc ®èi víi hn ta cã thÓ dÔ dµng chøng minh b»ng qui n¹p lµ

hn = 2n – 1, n ≥ 1.

= 2n − 1

Chap02-83

Chap02-84

= 2n−1 h1 + 2n−2 + … + 2 + 1 = 2n−1 + 2n−2 + … + 2 + 1 (do h1 = 1)

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

2.4.2.222222. Hàm sinh (Generating Function)

Tháp Hà nội với n=5

Chuyển vào cọc này

• Giả sử {hn | n = 0, 1, 2, ....} là một dãy số. Ta viết dãy này như là dãy vô hạn phần tử, tuy nhiên ta coi rằng nó bao gồm cả trường hợp dãy hữu hạn. Nếu h0, h1, ..., hm là dãy hữu hạn, thì ta sẽ biến nó thành dãy vô hạn bằng cách đặt hi = 0, i > m .

h x i

(cid:229)

• Định nghĩa. Hàm sinh g(x) của dãy số {hn | n = 0, 1, 2, ....} là chuỗi vô hạn

g(x) = h0 + h1 x + h2 x2 + ... = . • Như vậy hàm g(x) sinh ra dãy số đã cho như là dãy các hệ số của nó.

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

Chap02-85

Chap02-86

Cọc c Cọc b

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ

Ví dụ 3

• Ví dụ 3. Với k > 0, hàm

g(x) = 1/(1-x)k

• 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

sinh ra dãy

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

{C(n+k-1, n): n = 0, 1, 2, ...}.

Bởi vì

)

(

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

m (cid:229) ), xkmC k 0 =

• Ví dụ 2. Hàm

1/(1-x)k =[ 1/(1-x)]k = (1 + x + x2 + ...)k.

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

• Nếu ta khai triển biểu thức này bằng cách thực hiện nhân phá ngoặc, thì số lần xuất hiện số hạng xn sẽ bằng số nghiệm nguyên không âm của phương trình t1 + t2 + ... + tk = n, mà như đã biết là bằng C(n+k-1, n).

Chap02-87

Chap02-88

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ 3

• Ví dụ này có thể gợi ý cho ta cách giải nhiều bài toán đếm.

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

việc sử dụng hàm sinh:

• Ta dẫn ra một số khai triển đại số rất hay sử dụng trong Chẳng hạn xét hàm sinh g(x) = (1 + x + x2 + x3) (1 + x + x2) (1 + x + x2 + x3 + x4). • Giả sử xa, xb, xc tương ứng là các số hạng lấy từ các thừa số thứ nhất, hai, ba của vế phải, điều đó có nghĩa là 0 £ a £ 3, 0 £ b £ 2, 0 £ c £ 4. Khi khai triển vế phải, các thừa số này sẽ cho ta số hạng xn, với n = a + b + c.

• Như vậy hệ số của xn trong g(x) sẽ là số nghiệm nguyên

(1-xk+1)/(1-x) = 1 + x + x2 + ... + xk.

Chap02-89

Chap02-90

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. • xk/(1-x) = xk (1 + x + x2 + ...) = xk + xk+1 + xk+2 + ... • • 1/(1-x2) = 1 + x2 + x4 + x6 + ... • x/(1-x2) = x(1 + x2 + x4 + x6 + ...) = x + x3 + x5 + x7 + ...

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ 4

Ví dụ 5

• Ví dụ 5. Tìm hàm sinh cho hn là số cách chọn ra n quả từ 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à

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?

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

(1+ x2+x4+x6+ ...) (x+x3+x5+x7+ ...) (1+x+x2+x3+x4) (x2+x3+x4+ ...) • Trong công thức trên có 4 thừa số để đếm số quả táo (các số mũ chẵn), chuối (số mũ lẻ), cam (chỉ có đến số mũ 4) và đào (số mũ bắt đầu từ 2). Hàm sinh sẽ là

g(x) = [1/(1-x2)] [x/(1-x2)] [(1-x5)/(1-x)] [x2/(1-x)]

= [1/(1-x2)] [1/(1-x5)] [(1-x5)/(1-x)] (1+x) = [1/((1-x)(1 +x)] [1/(1-x)] (1+x) = 1/(1-x)2

= [x3(1-x5)]/[(1-x2)2(1-x)2].

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

• Câu trả lời là: Số cách cần đếm là hệ số thứ n trong khai triển g(x)

(

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

n C 2 1 n + -

n C x 1 n +

(cid:229)

)

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.

1 x - • Vậy hn = n + 1.

Chap02-91

Chap02-92

. =

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

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ử

( ) f x

i , ( ) a x g x i

b x i

(cid:229)

• Hàm sinh có thể sử dụng để tìm công thức dưới dạng hiện cho số hạng tổng quát của dãy số {hn , n=0,1,2,...} xác định bởi công thức đệ qui. Nội dung của phương pháp có thể trình bày như sau: (cid:911)Xây dựng hàm sinh g(x) của dãy số này theo công thức

là hai hàm sinh còn a là số thực, khi đó ¥

(

( ) f x

( ) g x

( ) f x

a i

) b x i

a x i

h x i

(cid:229)

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

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

(cid:911)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ó).

( ) ( ) f x g x

c x i

= (cid:229)

(cid:911)Theo công thức tìm được, tìm khai triển hàm g(x) dưới dạng

chuỗi luỹ thừa (chuỗi Maclaurin).

(cid:911)So sánh hệ số ở các số hạng với cùng số mũ của x ta tìm được

k i

a b -

(cid:229)

công thức cho hn.

Chap02-93

Chap02-94

. trong đó ck = a0 bk + a1 bk-1 + ... + ak b0 =

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Chuỗi Maclaurin

Dãy số Fibonaci

• Dãy số Fibonaci. Dãy số Fibonaci là dãy số được xác định bởi công

h x i

• Từ giải tích ta biết rằng nếu chuỗi g(x) =

hội tụ ở lân cận

(cid:229)

thức đệ qui

điểm 0 thì tổng g(x) luôn là hàm giải tích trong lân cận này và

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

fn = fn-1 + fn-2, n ‡ 2, f0 = 0, f1 = 1.

• Ta sẽ tìm công thức cho số hạng tổng quát của dãy số nhờ phương pháp

h x i

• Khi đó chuỗi

chính là khai triển Maclaurin của hàm g(x).

(cid:229)

hàm sinh.

( ) F x

• Xét hàm sinh . Ta có

f x n

= (cid:229)

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.

( ) F x

f x 1

f x n

(cid:229)

• Trong việc áp dụng hàm sinh ta thường sử dụng công thức sau:

(

)

f x 1

1 -

(cid:229)

k r x

k 1 n k + -

(cid:229)

)

1 rx -

1 +

f x 1

f x n

(cid:229)

mà trường hợp riêng của nó là

Leonardo Pisano Fibonacci 1170 - 1250

( ).

( ) xF x

x F x

x = +

n = +

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

Chap02-95

Chap02-96

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Chương 2. Lý thuyết tổ hợp

• Từ đó suy ra

2.1. Hoán vị

( ) F x

x x - -

+ 2

- 2

2.3. Nguyên lý bù trừ

• Ta có (1- x - x2) = (1 - ax) (1 - bx), với • Viết lại F(x) dưới dạng ( ) F x +

A x a -

B x b -

2.2. Tổ hợp (Combination)

1 • Từ đó tìm được

= -

2.4. Công thứ 2.4. Công thức đệ qui và hàm sinh g

2.5. Số Stirling

• Do đó

)

( ) F x

n n ( - a b

(cid:229)

1 x - a

1 x - b

Ø Œ º

ø œ ß

• Suy ra

)

‡

n n ( - a b

+ 2

- 2

(cid:230) (cid:231) (cid:231) Ł

(cid:246) (cid:247) (cid:247) ł

(cid:230) (cid:231) (cid:231) Ł

(cid:246) (cid:247) (cid:247) ł

Ø Œ Œ º

ø œ œ ß

Chap02-97

Chap02-98

2.6. Nguyên l 2.6. Nguyên lý các lồng chim bồ câu

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

2.5 Số Stirling

Có bao nhiêu ánh xạ?

• 2.5.1. Số Stirling • 2.5.2. Số Bell • 2.5.3. Số Catalan

Cho các tập hữu hạn A = {a1,…, am} và B = {b1,…, bn}. Hỏi có bao nhiêu ánh xạ f: A ﬁ B ?

• Tổng số ánh xạ có thể: |B||A| = nm.

Như ta đã chứng minh:

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

(

)

( 1) -

n k -

n k - C n

(cid:229)

Chap02-99

Chap02-100

• Số lượng toàn ánh: với m ≥ n:

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

2.5.1. Số Stirling loại 2

hoac

(n) Sm

• Trong nhiều tài liệu, số Stirling còn được ký hiệu bởi (cid:255) (cid:255) (cid:255)

(cid:255) (cid:255) n (cid:255)

• Số lượng toàn ánh từ tập A = {a1,…,am} vào tập B = {b1,…,bn} liên quan đến một con số tổ hợp nổi tiếng đó là số Stirling loại 2 (Stirling Numbers of the 2nd Kind).

• Ví dụ: Ta đếm số cách phân hoạch tập {1,2,3,4} ra thành 2 tập

• Định nghĩa. Số Stirling loại 2, ký hiệu bởi S2(m,n), là số cách phân hoạch tập m phần tử thành n tập con (m ‡ n).

James Stirling 1692 – 1770 Scotland 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}}.

Chap02-101

Chap02-102

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

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

2.5.1. Số Stirling loại 2

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ó

• Ta sẽ xây dựng công thức đệ qui để đếm số S2(m,n). • Ta có:

một tập con là {xm};

B = Tập các cách phân hoạch X ra thành n tập con trong đó không có tập con nào là {xm} (tức là xm không đứng riêng một mình!).

• Ta có:

(cid:911)S2(0,0)=1. (cid:911)Nếu m > 0, thì

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

S2(m,0) = 0, S2(m,1)=1, và S2(m,m)=1. Định lý. Với m, n > 1,

• Từ đó

S2(m,n)= |A| + |B| = S2(m–1,n–1) + n∙S2(m–1,n).

S2(m,n) = S2(m–1,n–1) + n∙S2(m–1,n). Chứng minh. Ta cần đếm số cách phân hoạch tập m phần tử

Định lý được chứng minh.

Chap02-103

Chap02-104

X = {x1, x2, … , xm} ra thành n tập con.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

Công thức tính 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ừ công thức đệ qui có thể chứng minh bằng qui nạp toán

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

- n k

Ai = {a˛A| f(a) = bi}, i = 1, 2, ..., n,

S m n , ) (

k m C k n

-(cid:229) ( 1)

1 n !

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

• Ngược lại, cho một phân hoạch của tập A ra thành n tập con A1, A2, ..., An và p(1), p(2), ...,p(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) = bp(i) , a˛Ap(i) , i = 1,2, ..., n,

• Nói chung để tính S2(m,n) người ta thường dùng công thức đệ qui, chứ không sử dụng công thức này. Điều này được giải thích tương tự như để tính hệ số tổ hợp người ta thường dùng tam giác Pascal.

• Như vậy mỗi phân hoạch cho ta n! toàn ánh. Vì thế, số lượng toàn ánh từ tập m phần tử vào tập n phần tử là bằng n! nhân với số cách phân hoạch tập m phần tử ra thành n tập con, nghĩa là bằng n!S2(m,n)

Chap02-105

Chap02-106

học công thức sau đây:

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

Bảng giá trị của số Stirling loại 2

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

S2(n,k) 0 1

8 9 10

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

S m n '( , )

- ( 1)

C n k (

m - (cid:222) )

S m n , ) (

- ( 1)

C n k (

)

k n

(cid:229)

1 n !

1 10 65 350

• Do đó từ công thức đã chứng minh ở mục trước

1 21 266

1 28

- n k

0 1 1 0 1 1 2 0 1 1 3 3 0 1 6 4 0 1 7 1 25 5 0 1 15 15 6 0 1 31 90 140 7 0 1 63 301 8 0 1 127 966 1701 1050 9 0 1 255 3025 7770 6951 2646 462 36 1

(cid:222)

S m n ( , )

- ( 1)

S m n '( , )

- ( 1)

k m C k n

(cid:229)

10 0 1 511 9330 34105 42525 22827 5880 750 45 1

1 n !

Chap02-107

Chap02-108

• Ngược lại, nếu coi công thức của S2(m,n) đã biết thì

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

2.5.2. Số Bell

Số Bell

• Định nghĩa. Số Bell (Bell numbers) là số cách phân hoạch

• Tập {1, 2, 3} có 5 cách phân hoạch:

tập n phần tử ra thành các tập con khác rỗng.

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, ...

• Các phần tử đầu tiên của dãy số này là

• Ví dụ: Tập {1, 2, 3} có các cách phân hoạch sau đây: • Tập {1, 2, 3, 4, 5} có 52 cách phân hoạch:

( , ) S n k 2

{{1}, {2}, {3}} , {{1, 2}, {3}}, {{1, 3}, {2}} , {{1}, {2, 3}}, {{1, 2, 3}}.

1 =

• Số Bell thứ n được tính bởi công thức n (cid:229)

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

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

Chap02-109

Chap02-110

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

2.5.2. Số Catalan

• Ta xây dựng công thức đệ qui để tính Cn. • Rõ ràng

• Định nghĩa. Số Catalan thứ n, ký hiệu là Cn , là số cách đặt dấu ngoặc để tổ chức thực hiện việc tính tích của n+1 thừa số: P0..n = x0 x1 x2 ... xn.

• Giả sử n > 1. Sau khi đặt dấu ngoặc phân tách đầu tiên, tích

• Ví dụ: • Có 2 cách để tính P0..2 : x0*x1*x2 = (x0*(x1*x2)) = ((x0*x1)*x2) • Có 5 cách để tính P0..3: 1*2*3*4 =

(1*(2*(3*4))) = (1*((2*3)*4)) = ((1*2)*(3*4)) = ((1*(2*3))* 4) = (((1*2)*3)*4)

• Có 14 cách để tính P0..4 : 1*2*3*4*5 =

C0 = 1 và C1 = 1.

x0 x1 x2 ... xn được chia làm hai tích con. • Ví dụ: P0..4 = P0..2 P3..4 = (x0 x1 x2) (x3 x4) • Giả sử dấu ngoặc phân tách đầu tiên được đặt sau thừa số xk: P0..n = P0..k Pk+1..n = (x0 x1 x2 ... xk) (xk+1 xk+2 ... xn) • Khi đó ta có Ck cách tính P0..k , Cn-k-1 cách tính Pk+1..n , và do

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

Chap02-111

Chap02-112

đó việc tính P0..n có thể thực hiện bởi Ck Cn-k-1 cách .

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

2.5.2. Số Catalan

• Một số phần tử đầu tiên của dãy số Catalan:

• Do dấu ngoặc phân tách đầu tiên có thể đặt vào sau bất cứ thừa số nào trong các thừa số x0, x1, ..., xn-1, suy ra tổng số cách tính P0..n là:

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

1 -

C C k

C n

n k

1 - -

Cn = C0 Cn-1 + C1Cn-2+ ... +Cn-1C0 .

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

k = 1,

C 0

C 1

1 • Sử dụng công thức này có thể chứng minh công thức sau:

- 1

‡

C C k

n k

- - 1

(cid:229)

n 2 n

1 +

n (2 )! + n n !(

1)!

(cid:230) (cid:231) Ł

(cid:246) (cid:247) ł

• Như vậy ta thu được công thức đệ qui: n (cid:229)

E. C. Catalan 1814 -1894 Belgium

Chap02-113

Chap02-114

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

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

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

• Cn là số lượng đường đi đơn điệu (tức là đường đi xuất phát từ vị trí góc dưới-phải kết thúc ở góc trên-trái và chỉ đi sang trái hoặc lên trên) độ dài 2n trên lưới ô vuông kích thước n·n không vượt lên trên đường chéo.

C2 = 2

C3 = 5

C4 = 14

C5 = 42

C4 = 14

C5 = 42

Chap02-115

Chap02-116

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

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

• Cn là số cây nhị phân đầy đủ với n + 1 lá. • Có C3 = 5 cây nhị phân đầy đủ với 4 lá:

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.

Cn là số lượng cây nhị phân đầy đủ không đẳng cấu có n đỉnh trong.

n = 2 n = 1 n

2 n = 3

n = 4

Chap02-117

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Chap02-118

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

2.6 Nguyên lý các lồng chim bồ câu

Chương 2. Lý thuyết tổ hợp

(Pigeonhole Principle)

2.6.1. Phát biểu nguyên lý 2.6.2. Các ví dụ ứng dụng

2.1. Hoán vị

2.2. Tổ hợp (Combination)

2.3. Nguyên lý bù trừ

2.4. Công thức đệ qui và hàm sinh

2.5. Số Stirling 2.5. Số Sti 2 5. Số Stirlin

Chap02-119

Chap02-120

2.6. Nguy 2.6. Nguyên lý các lồng chim bồ câu yên l

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

Pigeonhole Principle

Nếu xếp nhiều hơn n đối tượng vào n cái hộp thì bao giờ cũng tìm được ít nhất một cái hộp chứa ít ra là hai đối tượng.

Chøng minh.

Chap02-121

Chap02-122

Việc chứng minh nguyên lý trên chỉ là một lập luận phản chứng đơn giản. Giả sử ngược lại là không tìm được cái hộp nào chứa không ít hơn 2 đối tượng. Điều đó có nghĩa là mỗi cái hộp chứa không quá một đối tượng. Từ đó suy ra tổng số đối tượng xếp trong n cái hộp là không vượt quá n, trái với giả thiết là có nhiều hơn n đối tượng được xếp trong chúng.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

• Lập luận trên đã được nhà toán học người Đức là Dirichlet vận dụng thành công vào việc giải quyết rất nhiều bài toán tồn tại tổ hợp. • Trong lập luận của Dirichlet, các đối tượng được xét là các quả táo còn các cái hộp được thay bởi các cái giỏ: “Nếu đem bỏ nhiều hơn n quả táo vào n cái giỏ thì bao giờ cũng tìm được ít nhất một cái giỏ chứa ít ra là 2 quả táo”. Trong tài liệu tiếng Anh lập luận đó lại được trình bày trong ngôn ngữ của các con chim bồ câu: “Nếu đem nhốt nhiều hơn n con chim bồ câu vào n cái lồng thì bao giờ cũng tìm được ít nhất 1 cái lồng chứa ít ra là 2 con chim bồ câu”. Vì thế nguyên lý còn có tên gọi là “Nguyên lý về các lồng chim bồ câu”.

Johann Peter Gustav Lejeune Dirichlet Born: 13 Feb 1805 Died: 5 May 1859

Chap02-123

Chap02-124

Trong ngôn ngữ của lý thuyết tập hợp, nguyên lý có thể phát biểu như sau: “Nếu tập X gồm nhiều hơn n phần tử được phân hoạch thành n tập con, thì bao giờ cũng tìm được một tập con trong phân hoạch đó có lực lượng ít ra là 2”

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ

• Ví dụ 1. Trong số 367 người bao giờ cũng tìm được hai

• Ví dụ 3. Trong số những người có mặt trên trái đất luôn tìm

được hai người có hàm răng giống nhau.

người có ngày sinh nhật giống nhau bởi vì chỉ có tất cả 366 ngày sinh nhật khác nhau. • Giải: Tất cả chỉ có

232 = 4 294 967 296

hàm răng khác nhau mà số người trên hành tinh chúng ta hiện nay đã vượt quá 5 tỷ.

• Giải. Theo nguyên lý Dirichlet, số học sinh cần tìm là 102,

• Ví dụ 2. Trong kỳ thi học sinh giỏi điểm bài thi được đánh giá bởi một số nguyên trong khoảng từ 0 đến 100. Hỏi rằng ít nhất phải có bao nhiêu học sinh dự thi để cho chắc chắn tìm được hai học sinh có kết quả thi như nhau?

Chap02-125

Chap02-126

vì ta có 101 kết quả điểm thi khác nhau.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

g

Nguyên lý Dirichlet tổng quát ê ên lý ý ý Diriric c Nguyêêu ý ý Dir á chleleet ổ hlet tổng quátát Generalized Pigeonhole Principle

• Khi số lượng quả táo bỏ vào k cái giỏ vượt quá số lượng cái giỏ nhiều lần thì rõ ràng khẳng định trong nguyên lý về sự tồn tại cái giỏ chứa ít ra là 2 quả táo là quá ít. Trong trường hợp như vậy ta sử dụng nguyên lý Dirichlet tổng quát sau đây:

• Chứng minh nguyên lý tổng quát: • Giả sử khẳng định của nguyên lý là không đúng. Khi đó mỗi cái giỏ chứa không quá Øn/kø - 1 quả táo. Từ đó suy ra tổng số quả táo bỏ trong k cái giỏ không vượt quá

k(Øn/kø - 1) < k((n/k+1) - 1)) = n.

• “Nếu đem bỏ n quả táo vào k cái giỏ thì bao giờ cũng tìm

Mâu thuẫn thu được đã chứng minh nguyên lý.

được ít nhất một cái giỏ chứa ít ra là Øn/kø quả táo”.

Chap02-127

Chap02-128

• Ở đây ký hiệu Øaø gọi là phần nguyên già của số thực a, theo định nghĩa, là số nguyên nhỏ nhất còn lớn hơn hoặc bằng a.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ

• Ví dụ 4. Trong 100 người có ít nhất 9 người sinh cùng một

• Ví dụ 6. Hỏi ít nhất phải có bao nhiêu người có mặt trên

tháng.

• Giải: Tất cả chỉ có

• Giải: Xếp những người cùng sinh một tháng vào một nhóm. Có 12 tháng tất cả. Vậy theo nguyên lý Dirichlet, tồn tại ít nhất một nhóm có không ít hơn Ø100/12ø = 9 người.

trái đất để luôn tìm được ba người có hàm răng giống nhau?

• Ví dụ 5. Có năm loại học bổng khác nhau. Hỏi rằng phải có ít

hàm răng khác nhau. Ta cần tìm số n nhỏ nhất để

nhất bao nhiêu sinh viên để chắc chắn rằng có ít ra là sáu người cùng nhận học bổng như nhau?

232 = 4 294 967 296

• Từ đó số người cần tìm là

Øn/232ø = 3.

• Giải: Số sinh viên ít nhất cần có để đảm bảo chắc chắn có 6 sinh viên cùng nhận học bổng như nhau là số nguyên nhỏ nhất n sao cho Øn/5ø = 6. Số nguyên nhỏ nhất đó là n = 5·5+1 = 26. Vậy 26 là số lượng sinh viên nhỏ nhất đảm bảo chắc chắn là có sáu sinh viên cùng hưởng một loại học bổng.

Chap02-129

Chap02-130

2·232 + 1 = 8 589 934 593.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

2.6.2. Các ví dụ ứng dụng

Ví dụ 1

• Trong các ví dụ ứng dụng phức tạp hơn của nguyên lý

• Ví dụ 1. Trong một phòng họp bao giờ cũng tìm được hai người có số người quen trong số những người dự họp là bằng nhau.

khéo hơn rất nhiều.

Dirichlet, cái giỏ và quả táo cần phải được lựa chọn khôn

• Gi¶i: Gäi sè ngêi dù häp lµ n, khi ®ã sè ngêi quen cña mét ngêi nµo ®ã trong phßng häp chØ cã thÓ nhËn c¸c gi¸ trÞ tõ 0 ®Õn n-1. Râ rµng trong phßng kh«ng thÓ ®ång thêi cã ngêi cã sè ngêi quen lµ 0 (tøc lµ kh«ng quen ai c¶) vµ cã ngêi cã sè ngêi quen lµ n-1 (tøc lµ quen tÊt c¶). V× vËy, theo sè lîng ngêi quen ta chØ cã thÓ ph©n n ngêi ra thµnh n-1 nhãm. Theo nguyªn lý Dirichlet suy ra cã Ýt nhÊt mét nhãm ph¶i cã kh«ng Ýt h¬n hai ngêi, tøc lµ lu«n t×m ®îc Ýt ra lµ hai ngêi cã sè ngêi quen lµ b»ng nhau.

Chap02-131

Chap02-132

• Trong phần này ta sẽ xét một số ví dụ như vậy.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ 2

• Tất cả có 60 số nguyên dương

• Ví dụ 2. Trong một tháng gồm 30 ngày một đội bóng chuyền thi đấu mỗi ngày ít nhất một trận, nhưng không chơi quá 45 trận. Chứng minh rằng phải tìm được một giai đoạn gồm một số ngày liên tục nào đó trong tháng sao cho trong giai đoạn đó đội chơi đúng 14 trận.

a1, a2, ..., a30, a1+14, a2+14, ..., a30+14, trong đó tất cả đều nhỏ hơn hoặc bằng 59.

j cña ®éi. Khi ®ã

• Gi¶i: Gi¶ sö aj lµ tæng sè trËn thi ®Êu cho ®Õn hÕt ngµy thø

• Vì vậy theo nguyên lý Dirichlet, hai trong số các số nguyên này phải là bằng nhau. Vì các số a1, ..., a30 là đôi một khác nhau và các số a1+14, ..., a30+14 cũng là đôi một khác nhau, nên suy ra phải tìm được chỉ số i và j sao cho a1, a2, ..., a30 j

lµ d·y t¨ng c¸c sè nguyªn d¬ng vµ ®ång thêi 1 £ aj £ 45. Suy ra d·y • Điều đó có nghĩa là có đúng 14 trận đấu trong giai đoạn từ

ngày j+1 đến hết ngày i. a1+14, a2+14, ..., a30+14

Chap02-133

Chap02-134

còng lµ d·y t¨ng c¸c sè nguyªn d¬ng vµ 15 £ aj +14 £ 59.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ 3

Ví dụ 3

• Các số q1, q2, ..., qn+1 là các số nguyên lẻ, mỗi số

không lớn hơn 2n.

• Ví dụ 3. Chứng minh rằng, trong số n+1 số nguyên dương, mỗi số không lớn hơn 2n, bao giờ cũng tìm được hai số sao cho số này chia hết cho số kia.

• Gi¶i: Gäi c¸c sè ®· cho lµ

• Do trong đoạn từ 1 đến 2n chỉ có n số lẻ, nên từ nguyên lý Dirichlet suy ra là hai trong số các số q1, q2, ..., qn+1 là bằng nhau, tức là tìm được hai chỉ số i và j sao cho qi = qj = q.

a1, a2, . . . , an+1 .

• Khi đó

• ViÕt mçi mét sè aj trong n+1 sè trªn díi d¹ng:

ai = 2k(i)q, aj = 2k(j)q.

aj = 2k(j)qj , j = 1, 2, ..., n+1

trong ®ã k(j) lµ nguyªn kh«ng ©m, qj lµ sè lÎ.

• Suy ra nếu k(i) < k(j) thì aj chia hết cho ai, còn

nếu k(i) ‡ k(j) thì ai chia hết cho aj.

Chap02-135

Chap02-136

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ 4

Ví dụ 4

• Từ đó theo nguyên lý Dirichlet phải tìm được một nhóm chứa ít ra là 2 điểm, chẳng hạn đó là Mi, Mj. Khi đó điểm giữa Gij của đoạn thẳng nối Mi và Mi có toạ độ

Gij = ((xi+xj)/2, (yi+yj)/2).

• Ví dụ 4. Trên mặt phẳng cho 5 điểm có toạ độ nguyên Mi(xi, yi), i=1, 2, ..., 5. Chứng minh rằng luôn tìm được 2 điểm sao cho đoạn thẳng nối chúng, ngoài hai đầu mút, còn đi qua một điểm có toạ độ nguyên khác nữa.

• Do xi và xj cũng như yi và yj có cùng tính chẵn lẻ nên các toạ độ của Gij là các số nguyên. Khẳng định của ví dụ được chứng minh.

• Giải. Ta sẽ chứng minh: Luôn tìm được 2 điểm sao cho điểm giữa của đoạn thẳng nối chúng có toạ độ nguyên. Theo tính chẵn lẻ của hai toạ độ, 5 điểm đã cho có thể phân vào nhiều nhất là 4 nhóm:

• Khẳng định của ví dụ có thể tổng quát cho không gian n- chiều: “Trong không gian n-chiều cho 2n + 1 điểm có toạ độ nguyên. Khi đó luôn tìm được 2 điểm sao cho đoạn thẳng nối chúng, ngoài hai đầu mút, còn đi qua một điểm có toạ độ nguyên khác nữa”.

Chap02-137

Chap02-138

(Chẵn, Chẵn), (Chẵn, Lẻ), (Lẻ, Chẵn), (Lẻ, Lẻ).

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ 5

Ví dụ 5

Trước hết ta cần một số khái niệm.

• Cho a1, a2, … an là dãy số thực. • n được gọi là độ dài của dãy số đã cho.

• Định lý: Mỗi dãy gồm n2+1 số phân biệt (nghĩa là các phần tử là khác nhau từng đôi) luôn chứa hoặc dãy con tăng ngặt độ dài n+1 hoặc dãy con giảm ngặt độ dài n+1.

• Ta gọi dãy con của dãy đã cho là dãy có dạng ai1, ai2, …, aim, trong đó

1 £ i1 < i2 < . . . < im £ n

• Ví dụ: Dãy

• Dãy số được gọi là tăng ngặt nếu mỗi số hạng đứng sau luôn lớn hơn số hạng đứng trước. Dãy số được gọi là giảm ngặt nếu mỗi số hạng đứng sau luôn nhỏ hơn số hạng đứng trước..

gồm 10 = 32+1 số hạng phải chứa hoặc dãy con tăng ngặt độ dài 4 phần tử hoặc dãy con giảm ngặt độ dài 4 phần tử.

(cid:911) Ví dụ: Cho dãy số

1, 5, 6, 2, 3, 9.

• 5, 6, 9 là dãy con tăng ngặt của dãy đã cho

8, 11, 9, 1, 4, 6, 12, 10, 5, 7

• 6, 3 là dãy con giảm ngặt của dãy đã cho

Chap02-139

Chap02-140

1, 4, 6, 12 1, 4, 6, 7 11, 9, 6, 5

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ 5

Ví dụ 5

• Do 1 £ ik, dk £ n, nên theo qui tắc nhân có tất cả n2 cặp có

• Chứng minh: Giả sử a1, a2, …, an2+1 là dãy gồm n2+1 số phân biệt. Gán cho mỗi số hạng ak của dãy số cặp có thứ tự (ik,dk), trong đó ik là độ dài của dãy con tăng dài nhất bắt đầu từ ak còn dk là độ dài của dãy con giảm dài nhất bắt đầu từ ak.

thứ tự dạng (ik,dk) khác nhau.

• Do ta có tất cả n2 + 1 cặp (ik,dk), nên theo nguyên lý Dirichlet, hai trong số chúng là trùng nhau. Tức là tồn tại hai số hạng as và at trong dãy đã cho với s < t sao cho is = it và ds = dt.

hoặc là as < at hoặc là as > at.

• Ta sẽ chỉ ra điều này là không thể xảy ra. • Ví dụ: 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 a2 = 11, (i2,d2) = (2,4) a4 = 1 , (i4,d4) =(4,1) • Do các số hạng của dãy là phân biệt, nên

Chap02-141

Chap02-142

• Bây giờ giả sử không tồn tại dãy tăng cũng như dãy giảm có độ dài n+1. Khi đó ik và dk là các số nguyên dương £ n, với k = 1, 2, ..., n2+1.

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Ví dụ 5

• Nếu as < at, khi đó do is = it , ta có thể xây dựng dãy con tăng độ dài it+1 bắt đầu từ as, bằng cách nối đuôi nó bởi dãy con tăng độ dài it, bắt đầu từ at.

... , as , ..., at , ....

• Suy ra dãy con tăng dài nhất bắt đầu từ as có độ dài ít ra là

it + 1, nghĩa là is > it. Mâu thuẫn với giả thiết is= it.

s

• Tương tự như vậy, nếu as > at, ta có thể chỉ ra ds phải lớn

hơn dt, và cũng đi đến mâu thuẫn.

Hết chương 2

• Định lý được chứng minh.

Chap02-143

Chap02-144

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

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

• Định nghĩa. Công thức đệ qui (recurence relation) cho dãy số {an} là công thức cho phép tính an thông qua một hoặc một vài số hạng đi trước nó trong dãy số (đó là các số hạng a0, a1,..., an-1) với mọi n ‡ n0, trong đó n0 là số nguyên không âm. Một dãy số được gọi là nghiệm của công thức đệ qui nếu như các số hạng của nó thỏa mãn của công thức này.

• Ví dụ: Xét công thức đệ qui an= 2an– 1 – an– 2 với n = 2,3,4,...

(cid:911)Dãy số {an} với an = 3n là nghiệm của công thức này, vì ta có

an= 2an– 1 – an– 2 = 2[3(n–1)] – 3(n–2) = 3n, với n ‡ 2.

(cid:911)Dãy số {an = 5} cũng là nghiệm, vì an= 2an – 1 – an – 2 =2*5–

5=5, với mọi n ‡ 2.

(cid:911)Dãy số {an = 2n} không là nghiệm, vì ta có a0= 1, a1=2, a2 =

4, nhưng a2 = 4 „ 2a1 – a0 = 2*2 – 1 = 3.

Chap02-145

Chap02-146

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Cây nhị phân

•

• A binary tree is often defined recursively as either (a) being empty, or (b) consisting of a root node together with left and right subtrees, both of which are binary trees. It is this definition that is most useful from the point of view of data structures in computer science. From the mathematical point of view these objects are not trees. Changing (a) from "empty" to "a single vertex" gives a definition equivalent to that of ordered trees in which every node is either a leaf (no children) or has two children. These are sometimes called extended binary trees. In either case, they are usually parameterized by n, the number of applications of rule (b) that are used. In the extended binary tree illustrated above there are 5 internal nodes (the brown circles, which correspond to applications of rule (b)) and 6 leaves (the blue squares, which correspond to applications of rule (a)). By removing the blue edges and the leaves you obtain the corresponding binary tree.

Chap02-147

Chap02-148

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội

• Ordered Trees • An ordered tree is a rooted tree in which the relative order of subtrees matters. An ordered forest is an ordered collection of ordered trees. There is a one-to-one correspondence between ordered forests with n nodes and binary trees with n nodes. This correspondence is best explained using the well-formed parentheses strings with n left and n right parentheses. If the n left parentheses and n right parentheses are labelled 1 through n from left to right in the string, then there are n pairs of matching left/right pairs of parentheses. These pairs correspond to the nodes of the corresponding ordered forest. Listing the pairs in increasing order of the left parentheses corresponds to a preorder listing of the nodes of the forest and listing the pairs in increasing order of the right parentheses corresponds to a postorder listing of the nodes of the forest.

Chap02-149

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội