Bài giảng Toán rời rạc - Chương 2: Tổ hợp (Combinatorics)

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)

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

Chap02-2

Chap02-1

Toán rời rạc – NGUYỄN ĐỨC NGGHĨĨAA – Bộ môn KKHMT – Đ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 vị

• 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.2. Tổ hợp (Combination)

2.3. Nguyên lý bù trừ

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

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

2.5. Số Stirling

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

Chap02-3

Chap02-4

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à

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

Định lý. A_n^m= n^m.

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

•

Ví dụ 1. Tính số ánh xạ từ tập m phần tử U = {u₁, u₂, ..., u_m} vào tập n

phần tử V.

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

•

Giải: Mỗi ánh xạ f cần đếm được xác định bởi bộ ảnh (f(u₁), f(u₂), ...,

f(u_m)), trong đó f(u_i) Î V, i=1, 2, ..., m. Từ đó nhận được số cần tìm là

n^m.

•

Ví dụ 2. Tính số dãy nhị phân độ dài n.

m

• Ký hiệu số lượng chỉnh hợp lặp chập m từ n phần tử là A_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ⁿ.

• 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

•

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

một xâu nhị phân độ dài n, nên ta có

Hệ quả: Số lượng tập con của tập n phần tử là 2ⁿ.

(a₁, a₂, ..., a_m), a_iÎ X, i = 1, 2, ..., m.

Chap02-5

Chap02-6

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

• Giải: 4¹⁰⁰hay 100⁴?

• Mỗi cách phân bố cần tìm có thể biểu diễn bởi bộ có

thứ tự gồm 100 thành phần (b₁, ..., b₁₀₀) trong đó b_iÎ

{A, F, E, L} là nhóm thực tập của sinh viên thứ i. Từ

đó suy ra số cách phân bố cần đếm là 4¹⁰⁰.

(a₁, a₂, ..., a_m), a_iÎ X, i = 1, 2, ..., m, a_i¹ a_j, i ¹ j.

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

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

• Định lý.

n!

P(n,m) = n(n -1)...(n -m +1) =

(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

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

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

• Chú ý: Để giải ví dụ 2 có thể lập luận trực tiếp theo nguyên

lý nhân:

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

f(u₂), ..., f(u_m)), trong ®ã f(u_i) Î V, i=1, 2, ..., m, f(u_i)¹ f(u_j), i¹ j.

Tõ ®ã nhËn ®îc sè cÇn tìm lµ n(n-1)...(n-m+1).

• 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

• Ví dụ 2. Có bao nhiêu cách xếp 4 học sinh vào ngồi sau một cái

lại, ...

bàn có 10 chỗ ngồi với điều kiện không được phép ngồi lòng.

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

• Giải. Đánh số các học sinh từ 1 đến 4, các chỗ ngồi từ 1 đến 10.

Mỗi cách xếp học sinh cần đếm có thể biểu diễn bởi bộ có thứ tự

(g₁, g₂, g₃, g₄), trong đó g_iÎ {1, 2, ..., 10} là chỗ ngồi của học

sinh i. Từ điều kiện đầu bài g_i¹ g_j, i¹ j; do đó mỗi cách xếp cần

đếm là một chỉnh hợp không lặp chập 4 từ 10. Vậy số cách xếp

cần đếm là P(10,4) = 10.9.8.7 = 5040.

Chap02-9

Chap02-10

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.

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

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

• Ví dụ 2. Cần bố trí việc thực hiện n chương trình

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

biểu diễn bởi

(a₁, a₂, ..., a_n), a_iÎ X, i = 1, 2, ..., n, a_i¹ a_j, i ¹ j.

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

• Định lý.

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

P(n) = P(n,n) = n´(n-1)´...´2´1= 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ị

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

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

ΏCây liệt kê

ΏThuật toán sinh hoán vị

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

vào chính nó?

• Giải. Mỗi song ánh f cần đếm được xác định bởi

bộ ảnh (f(u₁), f(u₂), ..., f(u_n)), trong đó f(u_i) Î X,

i=1, 2, ..., n, f(u_i)¹ f(u_j), i¹ j.

-

•

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

b

a

c

Thành phần thứ 1

• 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

a

c

a

b

a

b

c

Thành phần thứ 2

Thành phần thứ 3

a

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ụ

Thuậ

t

toá

n sinh

hoá

n

vị

• 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

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

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

1

2

3

2

3

1

3

1

2

3

2

3

1

2

1

• 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 = (a₁, a₂, ... , a_n) tho¶ m·n

a_iÎ X , i = 1, 2,..., n , a_p¹ a_q, 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 = (a₁, a₂,..., a_n) ®i tríc ho¸n vÞ a' = (a'₁,

a'₂, ... , 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:

• 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 tm c¸ch tõ mét ho¸n vÞ ®ang cã a = (a₁, a₂, ... , a_n)

nÕu cha ph¶i lµ ho¸n vÞ cuèi cïng, ®a ra ho¸n vÞ kÕ tiÕp.

a₁= a'₁, a₂= a'₂, ... , a_k-1= a'_k-1, a_k< a'_k.

Chap02-15

Chap02-16

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ö a = (a₁, a₂, ... , a_n) 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:

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

vÞ kÕ tiÕp nã trong thø tù tõ ®iÓn.

• Ta cã chØ sè j = 3 (a₃=2 < a₄= 5).

ΏTìm tõ ph¶i qua tr¸i ho¸n vÞ ®ang cã chØ sè j ®Çu tiªn

tho¶ m·n a_j< a_j+1(nãi c¸ch kh¸c: j lµ chØ sè lín nhÊt

tho¶ m·n a_j< a_j+1);

• Sè nhá nhÊt cßn lín h¬n a₃trong c¸c sè bªn ph¶i cña a₃lµ

a₅= 4. Đæi chç a₃víi a₅ta thu ®îc (3, 6, 4, 5, 2, 1),

• Cuèi cïng, lËt ngîc thø tù ®o¹n a₄a₅a₆ta thu ®îc ho¸n vÞ

ΏTìm a_klµ sè nhá nhÊt cßn lín h¬n a_jtrong c¸c sè ë bªn

ph¶i a_j;

kÕ tiÕp (3, 6, 4, 1, 2, 5).

ΏĐổi chỗ a_jvíi a_k;

ΏLËt ngîc ®o¹n tõ a_j+1®Õn a_n.

Chap02-17

Chap02-18

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.2.1. Tổ hợp

2.1. Hoán vị

• 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.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.6. Nguyên lý các lồng chim bồ câu

Chap02-19

Chap02-20

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)

• Định lý.

C_n^m=

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

không có thứ tự gồm m thành phần, mỗi thành phần đều là phần

tử của X, các thành phần khác nhau từng đôi.

• Ký hiệu số lượng tổ hợp chập m từ n phần tử là C_n^m(đôi khi ta

n

n!

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

)

÷

m!(n m)!

m

• 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

lặp chập m của n phần tử.

sẽ sử dụng ký hiệu C(n,m))

• Theo định nghĩa, một tổ hợp chập m từ n phần tử của X có thể

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

ΏPhân Q thành các lớp sao cho hai chỉnh hợp thuộc cùng một

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

{a₁, a₂, ..., a_m}, a_iÎ X, i = 1, 2, ..., m, a_i¹ a_j, i ¹ j.

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

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

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

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

(a₁, a₂, ..., a_m), a_iÎ X, i = 1, 2, ..., m, 1 £ a₁< a₂< ...<a_m£ n.

hoán vị).

Ώ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

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

bao nhiªu trËn ®Êu?

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

|Q| = m! C(n,m)

• Gi¶i: Cø 2 ®éi thì 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

suy ra

n(n-1)...(n-m+1) = m! C(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?

n(n -1)(n -2)...(n -m +1)

m!

n!

C_n^m=

=

m!(n -m)!

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

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

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

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

Chap02-23

Chap02-24

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

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?

• 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 t_jlà 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ần chia n cái kẹo cho k em bé B₁, B₂, …,B_k. Hỏi có

bao nhiêu cách chia khác nhau?

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

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

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

D1

D2 D3

D4

D5

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

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

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

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.

t₁+ t₂+ ... + t_k= n.

Do có tất cả

k-1

n+k-1

C

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

Trước hết chia cho mỗi em 1 cái kẹo, n-k cái kẹo còn lại sẽ

được chia cho k em bé. Bài toán dẫn về: Hỏi có bao nhiêu

cách chia n-k cái kẹo cho k em bé. Sử dụng kết quả bài

trước, ta có đáp số cần tìm là

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: t₁+ t₂+ . . . + t_k= n.

k-1

n-1

•

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

C

Chap02-29

Chap02-30

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

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:

• Díi ®©y lµ mét vµi tÝnh chÊt cña c¸c hÖ sè tæ hîp:

a) Đèi xøng

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

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

m

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

c) C«ng thøc ®Ö qui

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

• Điều kiện đầu suy trực tiếp từ định nghĩa của hệ số tổ hợp.

C¸c tính chất còn lại có thể chứng minh nhờ sử dụng công

thức trong định lý 4.

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

Chap02-31

Chap02-32

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 ô

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

Chap02-33

Chap02-34

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

• Đị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)ⁿ, 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 xⁱy^jz^ktrong khai triển đang

xét.

• 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)ⁿ= (x+y) (x+y) . . . (x+y)

hÖ sè cña x^my^n-msÏ 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µ

(x + y)ⁿ

⁰y

^my

m

C_nx

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

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

=

ⁿ+ ... +

^n-m+...+ ⁿxⁿ

C_n

n

=

Cⁱxⁱy^n-i

å

n

i=0

7! / (1!2!4!) = 105.

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.

Chap02-35

Chap02-36

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

Multinomials

Khi k=2 ta có hệ số nhị thức C(n,n₁).

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ó

n₁đối tượng loại 1, n₂đối tượng loại 2,..., n_kđối tượng loại k (n₁+…+n_k= n).

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 n₁!´…´n_k! lần, từ đó suy ra

định lý.

Ký hiệu C(n; n₁,...,n_k) 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).

Ví dụ: Có bao nhiêu từ gồm 11chữ cái lấy từ 11 chữ cái của từ

“MISSISSIPPI”?

n

æ

ç

è

ö

÷

ø

n!

Định lý.

C(n;n ,...,n ) =

=

1

k

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

n₁,n₂,...,n_k

n₁!n₂!....n_k!

CM. Ta lần lượt chọn các đồ vật. Đồ vật loại 1 có C(n,n₁) cách chọn. Sau khi

đồ vật 1 đã chọn, đồ vật loại 2 có C(n-n₁,n₂) cách chọn, ..., cuối cùng đồ vật loại

k có C(n_k,n_k) cách chọn. Theo nguyên lý nhân

Theo nguyên lý nhân có:

C(n; n₁,...,n_k) = C(n,n₁)´C(n-n₁,n₂)´ ...´C(n_k,n_k),

C(11,1)C(10,4)C(6,4)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

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

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

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

(1+ x)ⁿ

0

C_nC_n

1

=

+

x + ... +

+

ⁿxⁿ

C_n^n-1x^n-1C_n

(*)

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

trong (*) chän x =1 ta ®îc:

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

tù gåm m thµnh phÇn a = (a₁, a₂, ... , a_m) tho¶ m·n

C(n,0) + C(n,1) + ...+ C(n,n) = 2ⁿ,

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 2ⁿ, cßn nÕu chän x = -1 ta ®îc:

a_iÎ X , i = 1, 2,..., m ; a₁< a₂< ... < a_m

• Xét hai phương pháp liệt kê tất cả m-tập con của X:

ΏCây liệt kê

C(n,0) – C(n,1) + C(n,2) - ...+(-1)ⁿC(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 2^n-1.

ΏThuật toán sinh m-tập con

• 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

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

Thuậ

t

toá

n sinh 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ø

tù gåm m thµnh phÇn a = (a₁, a₂, ... , a_m) tho¶ m·n

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

a_iÎ X , i = 1, 2,..., m ; a₁< a₂< ... < a_m

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

tập con của X :

-

Thành phần thứ 1

1

4

2

• Ta nãi tËp con a = (a₁, a₂,..., a_n) ®i tríc tËp con a' = (a'₁,

a'₂, ... , 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

4

Thành phần thứ 2

2

4

3

4

5

3

4

a₁= a'₁, a₂= a'₂, ... , a_k-1= a'_k-1, a_k< a'_k.

Thành phần thứ 3

3

5

4

5

135

235

345

123 124 125 134

145 234

245

Chap02-41

42

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

thø tù tõ ®iÓn nh sau

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

1

2

3

2

3

4

3

4

3

4

5

4

5

4

5

• Gi¶ sö a=(a₁, a₂, ... , a_m) 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ã:

ΏTìm từ bên phải dãy a₁, a₂,..., a_mphÇn tö a_i¹ n-m+i,

ΏThay a_ibëi a_i+ 1;

ΏThay a_jbëi a_i+ j - i, víi j = i+1, i+2,..., m.

Chap02-43

Chap02-44

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.

2.2. Tổ hợp (Combination)

2.3. Nguyên lý bù trừ

•

1 2 5

6

3 4 5

6

(tập con cuối cùng)

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

2.5. Số Stirling

• Ta có i=2, thay a₂= 3, và a₃= 4, a₄= 5, ta được tập con kế

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

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

Chap02-45

Chap02-46

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ý

(The inclusion-exclusion principle)

• 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

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

2 lần

• CM:

U

AÇB

A

B

1 lần

Chap02-47

Chap02-48

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

Nguyên lý bù trừ

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

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

|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| + |C| - |(AÈB)ÇC|

= |A| +|B| + |C| - |AÇB| - |(AÇC)È(BÇC)|

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

Vậy

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

• §Þnh lý. Gi¶ sö A₁, A₂, ... , A_mlµ c¸c tËp h÷u h¹n. Khi ®ã

dt = 4-3=1

U

C

^m-1N_m

dt = 2-1=1

N(

È

A₁A₂

È ... È ) =

A_m

-

+ ... +

(-1)

N₁N₂

B Ç C

AÇ C

trong ®ã

AÇ B ÇC

N_k=

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

dt = 1

å

i₁

i₂

i_k

A

AÇ B

1£i₁<i₂<...<i_k£m

(N_klµ 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

•

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

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| +| B| +|C | -| AÇB| -| BÇC | -|C Ç A| +| AÇBÇC |

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

N₁

= N(A₁) + ... + N(A_m),

N_m= N(A₁Ç A₂Ç ... Ç A_m) ).

Chap02-51

Chap02-52

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

Nguyên lý bù trừ

•

Chøng minh.

• B©y giê ta ®ång nhÊt tËp A_kvíi tÝnh chÊt A_kcho 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 A_knµo c¶.

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

• Gäi`N lµ sè cÇn ®Õm. Do A₁È A₂È . . . È A_mlµ 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ã:

tö cña tËp A₁È A₂È . . . È A_m®îc ®Õm bao nhiªu lÇn trong vÕ ph¶i:

•

XÐt mét phÇn tö tuú ý a Î A₁È A₂È . . . È A_m. 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

`N = N(X ) N(A₁È A₂È . . . È A_m)

= N(X ) N₁+ N₂-...+( 1)^mN_m

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

lÇn. Do

trong ®ã N_klµ 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(k,1) – C(k,2)+ ... + (-1)^k-1C(k,k)

= 1 – [C(k,0) – (C(k,1) – C(k,2)+ ... + (-1)^k-1C(k,k))] = 1 – (1 –

1)^k= 1

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

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è

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

N₂= N(A₃Ç A₄) + N(A₃Ç A₇) + N(A₄Ç A₇)

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

= 833 + 476 + 357 = 1666,

• Gi¶i. Gäi

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

N₃= N(A₃Ç A₄Ç A₇) = [10000/(3´4´7) ] = 119,

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

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

• Khi ®ã A₃È A₄È A₇lµ tËp c¸c sè trong X chia hÕt cho Ýt nhÊt mét

trong 3 sè 3, 4, 7, suy ra sè lîng c¸c sè cÇn ®Õm sÏ lµ

N(X) – N(A₃È A₄È A₇) = 10000 – (N₁– N₂+ N₃).

• Ta cã

10000 - 7261 + 1666 - 119 = 4286.

N₁= N(A₃) + N(A₄) + N(A₇)

= [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 x₁+ x₂+ x₃= 11, thỏa mãn x₁£ 3, x₂£ 4, x₃£ 6.

• Giải. Xét các tính chất

• 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. Ta cã

P₁: x₁> 3 ; P₂: x₂> 4; P₃: x₃> 6.

ΏSè x©u nhÞ ph©n ®é dµi 10 b¾t ®Çu bëi 00 lµ 2⁸= 256

ΏSè x©u nhÞ ph©n ®é dµi 10 kÕt thóc bëi 11 lµ 2⁸= 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 P₁, P₂, P₃. Theo nguyên lý bù trừ số lượng lời giải

cần đếm là bằng

ΏSè x©u nhÞ ph©n ®é dµi 10 b¾t ®Çu bëi 00 vµ kÕt thóc bëi

N – N₁+ N₂– N₃.

11 lµ 2⁶= 64.

• Ta cần tính các số N, N₁, N₂, N₃.

• Tổng số nghiệm nguyên không âm của phương trình là

bằng N = C(3+11–1, 11) = 78.

bëi 00 hoÆc kÕt thóc bëi 11 lµ

256 + 256 - 64 = 448.

Chap02-57

Chap02-58

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 x₁> 3 ta lập luận như sau: Đổi

biến y₁= x₁- 4, số nghiệm nguyên không âm của phương trình x₁+ x₂+

x₃= 11 thỏa mãn tính chất x₁> 3 chính là bằng số nghiệm nguyên

không âm của phương trình y₁+ x₂+ x₃= 11 – 4 = 7. Vậy

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

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

• 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 x₂>4: N(P₂) = C(3+6-1,6) = 28.

Số lời giải thỏa mãn tính chất x₃>6: N(P₃) = C(3+4-1,4) = 15.

Số lời giải thỏa mãn tính chất x₁>3 và x₂>4: N(P₁ÇP₂)=C(3+2-1,2)=6.

Số lời giải thỏa mãn tính chất x₁>3 và x₃>6: N(P₁ÇP₃)=C(3+0-1,0)=1.

Số lời giải thỏa mãn tính chất x₂>4 và x₃>6: N(P₂ÇP₃)=0.

Số lời giải thỏa mãn tính chất x₁>3, x₂>4 và x₃>6: N(P₁ÇP₂ÇP₃)=0.

Ta thu được số lượng lời giải thỏa mãn điều kiện đầu bài là

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

(p₁, p₂, ..., p_n),

trong ®ã p_ilµ 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.

Chap02-59

Chap02-60

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µ

N_k=

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

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

å

i₁

i₂

i_k

1£i₁<i₂<...<i_k£n

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

nghÜa lµ, N_klµ 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:

• Gäi X lµ tËp hîp tÊt c¶ c¸c c¸ch bá th vµ A_klµ tÝnh chÊt l¸ th

thø k bá ®óng ®Þa chØ. Khi ®ã, theo nguyªn lý bï trõ ta cã:

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

`N = N(X ) N₁+ N₂...+( 1)ⁿN_n

• Do ®ã

(-1)ⁿ

n!

trong ®ã`N lµ sè cÇn t×m, N(X) = n!, cßn N_klµ sè tÊt c¶ c¸c

c¸ch bá th sao cho cã k l¸ th ®óng ®Þa chØ.

1

N = n!(1-

+

- ... +

)

1! 2!

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

(-1)ⁿ

n!

1

1-

+

- ... +

1! 2!

Chap02-61

Chap02-62

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.

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

Giả sử A={a₁, a₂, ..., a_m} và B={b₁, b₂, ..., b_n}, m ³ n.

Hỏi có bao nhiêu toàn ánh từ A vào B?

A

B

f

Ta muốn tất cả b_iđều thuộc miền giá trị của f.

Gọi P_ilà tính chất "b_ikhông nằm trong

miền giá trị của f ".

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

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

n

2

1

3

2

4

5

6

7

8

9

10

11

D_n

9 44 265 1854 14833 133496 1334961 4890741

Ký hiệu:

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

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

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

N – N₁+ N₂– ... +(–1)ⁿN_n.

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

N_k=

N(P ÇP Ç...ÇP ), k =1,2,...,n

å

i₁

i₂

i_k

1£ i₁< i₂<...< i_k£n

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

Ta có:

ΏN - số ánh xạ từ m-tập A vào n-tập B: n^m

n^m-C_n¹(n -1)^m+C_n²(n - 2)^m-...+ (-1)^n-1C_n^n-11^m

ΏDo N(P_i) - số ánh xạ không có b_itrong miền giá trị,

nên N(P_i) = (n-1)^m, do đó N₁= C(n,1) (n-1)^m

= C_n⁰(n -0)^m-C_n¹(n -1)^m+C_n²(n - 2)^m-...+ (-1)^n-1C_n^n-11^m+(-1)ⁿC_nⁿ0^m

n

=

(-1)^kC^k(n - k)^m

ΏDo N(P_iÇP_j) - số ánh xạ không có b_ivà b_jtrong miền giá trị,

å

n

nên N(P_iÇP_j) = (n-2)^m, do đó N₂= C(n,2) (n-2)^m.

k=0

ΏTổng quát ta có

N(P ÇP Ç...ÇP ) = (n-k)^m

i₁

i₂

i_k

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

•

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

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

Chap02-65

Chap02-66

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.4.1. Xây dựng công thức đệ qui

2.4.2. Giải công thức đệ qui

2.1. Hoán vị

2.2. Tổ hợp (Combination)

2.3. Nguyên lý bù trừ

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

2.4

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

2.5. Số Stirling

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

Chap02-67

Chap02-68

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

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

• Công thức đệ qui là công thức cho phép tính giá trị

của các đại lượng theo từng bước, dựa vào các giá

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

• Theo định nghĩa

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

(1)

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

C(n,k). Cố định một phần tử x Î X. Phân tập các tập con k

phần tử của X ra thành 2 tập:

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

toán đếm

ΏA – tập các tập con k phần tử có chứa x;

ΏB – tập các tập con k phần tử không chứa x.

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

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

Chap02-69

Chap02-70

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

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

k phần tử của X. Do đó, theo nguyên lý cộng:

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

tính giá trị của C(n,k):

C(n,k) = |A| + |B|.

• Ta có:

ΏDo mỗi tập con trong A có chứa x, nên k-1 phần tử còn lại

của nó là một tập con k-1 phần tử của tập X \ {x}, suy ra

function C(n,k: integer): longint;

begin

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

ΏTương tự như vậy,

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

if (k=0) or (k=n) then C:=1

else C:= C(n-1,k-1) + C(n-1,k);

end;

• Vậy,

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

(2)

Chap02-71

Chap02-72

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

• Hàm vừa xây dựng không cho một cách tính hiệu quả. Thực

vậy, nếu gọi C^*(n,k) là số phép toán “gán giá trị” phải thực

hiện bởi lệnh gọi hàm C(n,k), dễ thấy

C^*(n,0) =1; C^*(n,n) = 1

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

tức là C^*(n,k) thoả mãn công thức đệ qui như hệ số tổ hợp

C(n, k), do đó:

C^*(n,k) ~ n!/[k!(n-k)!]

và giá trị này là rất lớn khi n lớn và k = n/2.

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µ S_n. Râ ràng

S₁= 2,

(3)

•

XÐt n > 1, ta tìm c«ng thøc ®Ö qui cho S_n.

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

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

S_n= S_n-1+ n, n ³ 2

(4)

Chap02-73

Chap02-74

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

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

G₄₂

G₄₁

Phương pháp thế:

S₁= 2

S_n= S_n-1+n

G₃₂

phần 4

S₂= S₁+ 2

S₃= S₂+ 3

...

= S_n-2+(n-1)+n

= S_n-3+(n-2)+(n-1) +n

= ....

l₁

G₂₂

G₃₁

phần 3

G₁₂

G₂₁

= S₁+2+3+....+(n-1)+n

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

S_n-1= S_n-2+ (n-1)

S_n= S_n-1+ n

phần 2

G₁₁

phần 1

S_n= 2 + 2 + 3 + ...+(n-1) + n = n(n+1)/2 + 1 = (n²+n+2)/2

l₄

l₃

l₂

Chap02-75

Chap02-76

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:

f_n= |A| + |B|.

• Ví dụ 3. Xây dựng công thức đệ qui cho f_nlà 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.

• Ta có:

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

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

• Giải. Ta có

|A| = f_n-1

f₁= 2; f₂= 3

Ώ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

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

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

ΏB – tập các chỉnh hợp cần đếm chứa 0 ở vị trí đầu tiên;

|B| = f_n-2

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

f₁= 2; f₂= 3;

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

hợp cần đếm.

f_n= f_n-1+ f_n-2, n > 2

(5)

Chap02-77

Chap02-78

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ụ 4. Xây dựng công thức đệ qui cho Q_nlà số lượng cách phủ

lưới ô vuông kích thước 2´n bằng các quân bài domino.

• Giải. Ta có

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

Q_n= |A| + |B|.

...

• Ta có:

A

Q₁= 1; Q₂= 2 (xem hình vẽ)

Ώ|A| = Q_n-1

Ώ|B| = Q_n-2

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

...

B

ΏA – tập các cách phủ trong đó ô ở góc trên trái được phủ bởi

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

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

Q₁= 1; Q₂= 2;

ΏB – tập các cách phủ trong đó ô ở góc trên trái được phủ bởi

Q_n= Q_n-1+ Q_n-2, n > 2

(6)

quân bài nằm ngang.

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

cần đếm.

Chap02-79

Chap02-80

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

Bài giảng Toán rời rạc - Chương 2: Tổ hợp (Combinatorics) - Nguyễn Đức Nghĩa