Bài giảng Toán rời rạc - Phần 1: Lý thuyết tổ hợp - Chương 1: Bài toán đếm - Nguyễn Đức Nghĩa
Nội dung
Chương 0. Mở đầu
Chương 1. Bài toán đếm
Chương 2. Bài toán tồn tại
Chương 3. Bài toán liệt kê tổ hợp
Chương 4. Bài toán tối ưu tổ hợp
2
Toán rời rạc
Chương 1. BÀI TOÁN ĐẾM
1. Nguyên lý cộng và nguyên lý nhân
2. Các cấu hình tổ hợp cơ bản
3. Nguyên lý bù trừ
4. Công thức đệ qui
5. Hàm sinh
3
Toán rời rạc
1. Nguyên lý cộng và Nguyên lý nhân
⚫ Đây là hai nguyên lý cơ bản của tổ hợp,
được vận dụng rộng rã i vào việc giải
quyết cá c bài toá n đếm
⚫ Cò n gọi là Qui tắc cộng và Qui tắc nhâ n
(Sum Rule và Product Rule)
4
Toán rời rạc
1.1. Nguyên lý cộng
(The sum rule)
⚫ NÕu A vµ B lµ hai tËp hîp rêi nhau th×
N(A B) = N(A) + N(B).
⚫ Nguyªn lý céng ®îc më réng cho nhiÒu tËp con rêi nhau:
NÕu A1, A2, ..., Ak lµ mét ph©n ho¹ch cña tËp hîp X th×
N(X) = N(A1) + N(A2) + ... + N(Ak).
⚫ Mét trêng hîp riªng hay dïng cña nguyªn lý céng:
NÕu A lµ mét tÝnh chÊt cho trªn tËp X th×
N(A) = N(X) - N(Ac).
N(A) = N(X ) − N(A)
5
Toán rời rạc
Nguyên lý cộng: Ví dụ
⚫ Ví dụ 1. Một đoàn vận động viên gồm 2 môn bắn súng và
bơi được cử đi thi đấu ở nước ngoài. Nam có 10 người. Số
vận động viên thi bắn súng (kể cả nam và nữ) là 14. Số nữ
vận động viên thi bơi bằng số nam vận động viên thi bắn
súng. Hỏi toàn đoàn có bao nhiêu người?
⚫ Giải: Chia đoàn thành 2 lớp: nam và nữ. Lớp nữ lại được
chia 2: thi bắn súng và thi bơi. Thay số nữ thi bơi bằng số
nam thi bắn súng (2 số này bằng nhau theo đầu bài), ta
được số nữ bằng tổng số đấu thủ thi bắn súng. Từ đó, theo
nguyên lý cộng, toàn đoàn có 10 + 14 = 24 người.
6
Toán rời rạc
Nguyên lý cộng: Ví dụ
⚫ Ví dụ 2. Trong một đợt phổ biến đề tài tốt nghiệp, Ban chủ
nhiệm Khoa công bố danh sách các đề tài bao gồm 80 đề
tài về chủ đề "xây dựng hệ thông tin quản lý", 10 đề tài về
chủ đề "thiết kế phần mềm dạy học" và 10 đề tài về chủ đề
"Hệ chuyên gia". Hỏi một sinh viên có bao nhiêu khả năng
lựa chọn đề tài?
⚫ Giải: Sinh viên có thể lựa chọn đề tài theo chủ đề thứ nhất
bởi 80 cách, theo chủ đề thứ hai bởi 10 cách, theo chủ đề
thứ ba bởi 10 cách. Vậy tất cả có 100 cách lựa chọn.
7
Toán rời rạc
Nguyên lý cộng: Ví dụ
⚫ VÝ dô 3. Hái r»ng gi¸ trÞ cña k sÏ lµ bao nhiªu sau khi ®o¹n ch-
¬ng tr×nh PASCAL sau ®îc thùc hiÖn?
n1:=10; n2:=20; n3:=30;
k:=0;
for i1:= 1 to n1 do k:=k+1;
for i2:= 1 to n2 do k:=k+1;
for i3:= 1 to n3 do k:=k+1;
⚫ Gi¶i: §Çu tiªn gi¸ trÞ cña k ®îc g¸n b»ng 0. Cã 3 vßng lÆp for
®éc lËp. Sau mçi lÇn lÆp cña mçi mét trong 3 vßng for, gi¸ trÞ
cña k t¨ng lªn 1. Vßng for thø nhÊt lÆp 10 lÇn, vßng for thø hai
lÆp 20 lÇn, vßng for thø ba lÆp 30 lÇn. VËy, kÕt thóc 3 vßng lÆp
for gi¸ trÞ cña k sÏ lµ 10+20+30= 60.
8
Toán rời rạc
Nguyên lý cộng: Ví dụ
⚫ Ví dụ 4: Có bao nhiêu xâu gồm 4 chữ số thập phân có
đúng 3 ký tự là 9?
⚫ Gi•ải: XKâýutựcókthháểcc9hởứav:ị trí thứ nhất
• hoặc ký tự khác 9 ở vị trí thứ hai
• hoặc ký tự khác 9 ở vị trí thứ ba
• hoặc ký tự khác 9 ở vị trí thứ tư
• Ta có thể sử dụng qui tắc cộng
• Đối với mỗi trường hợp, có 9 khả năng chọn ký
tự khác với 9 (bất kể chữ số khác 9 nào trong 9
chữ số 0, 1, ...,8)
• Vậy, đáp số là 9+9+9+9 = 36
9
Toán rời rạc
1.2. Nguyên lý nhâ n
The product rule
⚫ NÕu mçi thµnh phÇn ai cña bé cã thø tù k thµnh phÇn
(a1, a2, ..., ak) cã ni kh¶ n¨ng chän (i = 1, 2, ..., k), th×
sè bé sÏ ®îc t¹o ra lµ tÝch sè cña c¸c kh¶ n¨ng nµy
n1n2 ... nk.
⚫ Mét hÖ qu¶ trùc tiÕp cña nguyªn lý nh©n:
N(A1 A2 ... Ak) = N(A1) N(A2) ... N(Ak),
víi A1, A2, ..., Ak lµ nh÷ng tËp hîp nµo ®ã, nãi riªng:
N(Ak) = [N(A)]k .
10
Toán rời rạc
1.2. Nguyên lý nhâ n
The product rule
⚫ Trong nhiÒu bµi to¸n ®Õm, chØ sau khi x©y dùng xong
thµnh phÇn thø nhÊt ta míi biÕt c¸ch x©y dùng thµnh phÇn
thø hai, sau khi x©y dùng xong hai thµnh phÇn ®Çu ta míi
biÕt c¸ch x©y dùng thµnh phÇn thø ba,... Trong trêng hîp
®ã cã thÓ sö dông nguyªn lý nh©n tæng qu¸t:
⚫ Gi¶ sö ta x©y dùng bé cã thø tù k thµnh phÇn (a1, a2, ..., ak)
theo tõng thµnh phÇn vµ
• a1 cã thÓ chän bëi n1 c¸ch;
• Sau khi a1 ®· chän, a2 cã thÓ chän bëi n2 c¸ch;
• ...
• Sau khi a1, a2,...,ak-1 ®· chän, ak cã thÓ chän bëi nk c¸ch;
⚫ ThÕ th× sè bé ®îc t¹o ra lµ tÝch sè n1n2 ... nk.
11
Toán rời rạc
Nguyên lý nhân: Ví dụ
⚫ VÝ dô 1. Tõ Hµ néi ®Õn HuÕ cã 3 c¸ch ®i: m¸y bay, « t«,
tµu ho¶. Tõ HuÕ ®Õn Sµi gßn cã 4 c¸ch ®i: m¸y bay, « t«,
tµu ho¶, tµu thuû. Hái tõ Hµ néi ®Õn Sµi gßn (qua HuÕ) cã
bao nhiªu c¸ch ®i?
⚫ Gi¶i: Mçi c¸ch ®i tõ Hµ néi ®Õn Sµi gßn (qua HuÕ) ®îc
xem gåm 2 chÆng: Hµ néi - HuÕ vµ HuÕ - Sµi gßn. Tõ ®ã,
theo nguyªn lý nh©n, sè c¸ch ®i tõ Hµ néi ®Õn Sµi gßn lµ 3
4 = 12 c¸ch.
Hà nội
Sài gò n
Huế
12
Toán rời rạc
Nguyên lý nhân: Ví dụ
⚫ VÝ dô 2. Hái r»ng gi¸ trÞ cña k sÏ lµ bao nhiªu sau khi ®o¹n ch-
¬ng tr×nh PASCAL sau ®îc thùc hiÖn?
n1:=10; n2:=20; n3:=30;
k:=0;
for i1:=1 to n1 do
for i2:=1 to n2 do
for i3:=1 to n3 do k:=k+1;
⚫ Gi¶i: §Çu tiªn gi¸ trÞ cña k ®îc g¸n b»ng 0. Cã 3 vßng lÆp for
lång nhau. Sau mçi lÇn lÆp cña vßng for, gi¸ trÞ cña k t¨ng lªn 1.
Vßng for thø nhÊt lÆp 10 lÇn, vßng for thø hai lÆp 20 lÇn, vßng
for thø ba lÆp 30 lÇn. VËy, theo nguyªn lý nh©n, kÕt thóc 3 vßng
lÆp for lång nhau, gi¸ trÞ cña k sÏ lµ 10 20 30 = 6000.
13
Toán rời rạc
Nguyên lý nhân: Ví dụ
⚫ Ví dụ 3: Hỏi có bao nhiêu lá cờ gồm 3 vạch mầu, mầu của mỗi vạch
lấy từ ba mầu xanh, đỏ, trắng sao cho:
a) Không có hai vạch liên tiếp nào cùng màu
b) Không có hai vạch nào cùng màu
⚫ Giải. Đánh số các vạch của lá cờ bởi 1, 2, 3 từ trên xuống.
Trường hợp a)
⚫ Màu của vạch 1 có 3 cách chọn.
⚫ Sau khi màu của vạch 1 đã chọn, màu của vạch 2 có 2 cách chọn
(không được chọn lại màu của vạch 1).
⚫ Sau khi màu của hai vạch 1, 2 đã chọn, màu của vạch 3 có 2 cách chọn
(không được chọn lại màu của vạch 2).
⚫ Theo nguyên lý nhân số lá cờ cần đếm trong trường hợp a) là 3.2.2=12
14
Toán rời rạc
Nguyên lý nhân: Ví dụ 3 (tiếp)
Trường hợp b):
⚫ Màu của vạch 1 có 3 cách chọn.
⚫ Sau khi màu của vạch 1 đã chọn, màu của vạch 2 có
2 cách chọn (không được chọn lại màu của vạch 1).
⚫ Sau khi màu của hai vạch 1, 2 đã chọn, màu của
vạch 3 có 1 cách chọn (không được chọn lại màu
của vạch 1 và 2).
⚫ Theo nguyên lý nhân số lá cờ cần đếm trong trường
hợp b) là 3.2.1=6
15
Toán rời rạc
Nguyên lý nhân: Ví dụ
Ví dụ 4. Có bao nhiêu xâu gồm 4 chữ số thập phân
a) không chứa một chữ số nào hai lần?
Chúng ta sẽ chọn chữ số vào lần lượt từng vị trí
• Ký tự thứ nhất có 10 cách chọn
• Ký tự thứ hai có 9 cách (không chọn lại chữ số đã chọn vào
vị trí thứ nhât)
• Ký tự thứ ba có 8 cách chọn
• Ký tự thứ tư có 7 cách chọn
Tổng cộng có 10*9*8*7 = 5040 xâu cần đếm.
b) kết thúc bởi chữ số chẵn?
Ba ký tự đầu tiên mỗi ký tự có 10 cách chọn
Ký tự cuối cùng có 5 cách chọn
Tổng cộng có 10*10*10*5 = 5000 xâu cần đếm.
16
Toán rời rạc
Các ví dụ phức tạp hơn
⚫ Khi nào sử dụng qui tắc cộng?
⚫ Khi nào sử dụng qui tắc nhân?
⚫ Ta có thể sử dụng phối hợp cả qui tắc cộng và qui
tắc nhân
⚫ Bằng cách đó ta có thể giải được nhiều bài toán
thú vị và phức tạp hơn
17
Toán rời rạc
Chụp ảnh đám cưới
Xét bài toán: Có 10 người tham gia vào việc chụp ảnh kỷ niệm
ở một đám cưới, trong đó có cô dâu và chú rể. Ta xét bức
ảnh chỉ gồm 6 người trong họ.
a) Có bao nhiêu bức ảnh trong đó có mặt cô dâu?
Qui tắc nhân: Xếp chỗ cho cô dâu VÀ sau đó xếp chỗ cho những nhân vật
còn lại trong bức ảnh.
Trước hết xếp chỗ cho cô dâu: Cô dâu có thể đứng ở 1 trong 6 vị trí
Tiếp đến, xếp 5 nhân vật còn lại của bức ảnh nhờ sử dụng qui tắc nhân:
Có 9 người để chọn nhân vật thứ hai, 8 người để chọn nhân vật thứ
ba, ... Tổng cộng có 9*8*7*6*5 = 15120 cách xếp 5 nhân vật còn lại
của bức ảnh.
Qui tắc nhân cho ta 6 * 15120 = 90 720 bức ảnh
18
Toán rời rạc
Chụp ảnh đám cưới
b) Có thể chụp bao nhiêu bức ảnh mà trong đó có mặt cả cô dâu lẫn chú rể?
Qui tắc nhân: Xếp dâu/rể VÀ sau đó xếp những nhân vật còn lại trong bức
ảnh
Trước hết xếp dâu và rể
• Cô dâu có thể xếp vào 1 trong 6 vị trí
• Chú rể có thể xếp vào 1 trong 5 vị trí còn lại
• Tổng cộng có 30 khả năng
Tiếp theo, xếp chỗ cho 4 nhân vật còn lại trong bức ảnh theo qui tắc nhân
• Có 8 người để chọn nhân vật thứ ba, 7 người để chọn nhân vật thứ tư, ...
• Tổng cộng có 8*7*6*5 = 1680
Theo qui tắc nhân có 30 * 1680 = 50 400 bức ảnh
19
Toán rời rạc
Chụp ảnh đám cưới
c) Có bao nhiêu bức ảnh mà trong đó có mặt chỉ một người trong cặp tân
hôn?
Qui tắc cộng: Chỉ xếp cô dâu
• Qui tắc nhân: xếp cô dâu và sau đó xếp các nhân vật còn lại
• Trước hết xếp cô dâu: Cô dâu có thể đứng ở một trong 6 vị trí
• Tiếp đến, xếp những nhân vật khác theo qui tắc nhân: Có 8 người để
chọn nhân vật thứ hai, 7 để chọn nhân vật thứ ba, v.v. (Ta không được
chọn chú rể!)
Tổng cộng = 8*7*6*5*4 = 6720
• Qui tắc nhân cho 6 * 6720 = 40 320 khả năng
⚫ hoặc chỉ xếp chú rể
• Số lượng khả năng cũng giống như cô dâu: 40 320
Qui tắc cộng cho 40 320 + 40 320 = 80 640 khả năng
20
Toán rời rạc
Tải về để xem bản đầy đủ
178 trang
25200
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Phần 1: Lý thuyết tổ hợp - Chương 1: Bài toán đếm - Nguyễn Đức Nghĩa", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_phan_1_ly_thuyet_to_hop_chuong_1_bai.ppt
