Bài giảng Toán rời rạc - Phép đếm

1Trường đại học Cần Thơ
Khoa Công nghệ thông tin và truyền thông
Bộ môn Khoa học máy tính
PHÉP ĐẾM
2Nội dung
Các nguyên lý đếm
Đại số tổ hợp
3Các nguyên lý đếm
 Nguyên lý cộng: Giả sử các sự kiện Ai
(i=1,m) đôi một loại trừ nhau; và các sự kiện
Ai có tương ứng ni cách xãy ra. Khi đó sự kiện
(hoặc A1, hoặc A2, , hoặc Am)có:
n1 + n2 +  + nm cách xãy ra
4Các nguyên lý đếm
 Ví dụ 1: An có 3 áo tay dài, 5 áo tay ngắn. Để
chọn 1 cái áo thì An có mấy cách?
3+5=8
5Các nguyên lý đếm
 Ví dụ 2: Một sinh viên có thể chọn đề tài niên
luận từ 3 danh sách đề tài tương ứng có 23
của giảng viên 1, 15 của giảng viên 2 và 19 đề
tài của giảng viên 3. Hỏi có bao nhiêu cách để
một sinh viên chọn đề tài.
23+15+19=57
6Các nguyên lí đếm
 Nguyên lý nhân: Giả sử các sự kiện Ai
(i=1,m) đôi một loại trừ nhau; và các sự kiện
Ai có tương ứng ni cách xãy ra. Khi đó sự kiện
(A1 và A2 và  và Am) có:
n1 x n2 x  x nm cách xãy ra
7 Ví dụ 1: Giả sử có 2 cái mặt nạ, 3 cái mũ, Hỏi có
mấy cách hóa trang?
Các nguyên lí đếm
2 x 3 = 6
8Các nguyên lý đếm
 Ví dụ 2: Có bao nhiêu xâu bit nhị phân có độ
dài là 7?
2 x 2 x 2 x 2 x 2 x 2 x 2 = 128
9Các nguyên lý đếm
 Ví dụ 3: Có bao nhiêu bảng số xe khác nhau
nếu mỗi bảng số bắt đầu là 3 chữ cái (có 26
chữ cái) và theo sau là 3 chữ số (có 10 chữ
số)?
26 x 26 x 26 x 10 x 10 x 10 = 17576000
10
Các nguyên lý đếm
 Ví dụ 4: Cho tập X ={0, 1, 2, 3, 4, 5}. Hỏi có bao nhiêu số tự nhiên
có 3 chữ số khác nhau mà chia hết cho 2
 Gọi số có 3 chữ số là abc
 TH1: c=0. Khi đó
 c có 1 cách chọn
 a có 5 cách chọn (a  X\{0})
 b có 4 cách chọn (b  X\{a, 0})
 TH2: c≠0. Khi đó
 c có 2 cách chọn
 a có 4 cách chọn ( a  X\{c, 0} )
 b có 4 cách chọn ( b  X\{a, c} )
Vậy có 20 + 32 = 52
TH1 có 1*5*4 =20
TH2 có 2*4*4 =32
11
Các nguyên lý đếm
 Ví dụ 5: Mỗi mật khẩu có độ dài từ 6-8 ký tự, mỗi
ký tự là 1 chữ cái hoa hoặc là 1 chữ số, mỗi mật
khẩu phải chứa ít nhất 1 chữ số. Hỏi có bao
nhiêu mật khẩu có thể?
P = P6 + P7 + P8
P6= 36
6 – 266
P7= 36
7 – 267
P8= 36
8 – 268
(366 – 266) + (367 – 267) + (368 – 268)
12
Các nguyên lý đếm
 Nguyên lý bù trừ: Cho A1 và A2 là 2 sự kiện
bất kỳ, có thể xãy ra theo n1, n2 cách tương
ứng. Khi đó sự kiện (A1 hoặc A2) xãy ra:
(n1 + n2) – số lần (A1 và A2)
A1 ∩ A2A1
A2
13
Các nguyên lý đếm
 Ví dụ 1: Trong một lớp ngoại ngữ Anh Pháp. Có 24
HS học tiếng Pháp, 26 HS học tiếng Anh, trong số
đó có 15 HS học cả tiếng Anh và tiếng Pháp. Hỏi lớp
có bao nhiêu người?
 A1 là HS học Tiếng Pháp
 A2 là HS học Tiếng Anh
 Số học sinh của lớp là: 24 + 26 – 15 = 35
14
Các nguyên lý đếm
 Ví dụ 2: Có bao nhiêu xâu bit nhị phân có độ dài
bằng 8 được bắt đầu bằng bit 1 hoặc kết thúc bằng
hai bit 00?
Xâu bit có độ dài bằng tám và có bit 1 đầu tiên?
Xâu bit có độ dài bằng tám và kết thúc bằng hai bit 00?
Xâu bit có độ dài bằng 8 bắt đầu bằng bit 1 và kết thúc
bằng hai bit 00?
27 + 26 – 25 = 128 + 64 – 32 =160
15
Nguyên lý Dirichlet
 Nguyên lý Dirichlet: Nếu có N vật được đặt
vào trong k hộp thì sẽ tồn tại một hộp chứa ít
nhất N/k vật.
 Áp dụng để trả lời câu hỏi dạng: có tồn tại
phần tử thỏa tính chất cho trước
16
Các nguyên lý đếm
 Ví dụ 1: Trong 100 người có ít nhất 9 người sinh
cùng một tháng vì nếu chọn:
 Số vật là 100 (người)
 Số hộp là 12 (tháng)
sẽ có một cái hộp chứa không ít hơn = 8,333..
người, tức là chứa ít nhất là 9 người.
17
Các nguyên lý đếm
 Ví dụ 2: Có 3 họ Nguyễn, Trần, Lê và 3 tên Mai,
Lan, Trúc. Chứng minh rằng nếu ghép họ và tên để
đặt cho 10 Cô thì sẽ có ít nhất 2 Cô cùng họ và tên.
 10 (Cô)
 Tổng số họ-tên: 3x3 = 9 (họ và tên)
sẽ có một cái hộp (họ và tên) chứa không ít hơn 2
người.
18
Các nguyên lý đếm
 Ví dụ 3: CM rằng trong 5 số chọn từ tập
X = {1, 2, 3, 4, 5, 6, 7, 8} phải có 1 cặp có tổng
bằng 9.
Ta lập 4 hộp như sau: {1, 8}, {2, 7}, {3, 6}, {4, 5}.
Có 5 số nguyên được chọn từ X thì tồn tại ít nhất 2 số
thuộc cùng 1 cặp (trong 1 hộp).
19
Các nguyên lý đếm
 Ví dụ 4: CM rằng trong n+1 số nguyên dương
không lớn hơn 2n thì tồn tại 1 số nguyên chia
hết cho số nguyên kia.
Số nguyên ai = 2
kiqi (i=1, n+1), trong đó ki số nguyên
và qi là số nguyên dương lẻ và không vượt quá 2n
=> có n giá trị nguyên dương lẻ và không vượt quá
2n
Với (n+1) số lẻ qi thì tồn tại 2 số bằng nhau => tồn
tại 2 số mà số này chia hết số kia.
20
Nội dung
Các nguyên lý đếm
Đại số tổ hợp
21
Hoán vị
 Định nghĩa. Hoán vị của n phần tử x1, x2, , xn là
một sắp xếp có thứ tự n phần tử này.
 Định lý. Có n! hoán vị của n phần tử.
 Kí hiệu: Pn = n! = n*(n-1)*(n-2)**1
 Quy ước 0! =1
 Ví dụ: Cho A ={a,b,c}. Khi đó A có các hoán vị sau:
 abc,acb,
 bac,bca,
 cab,cba
22
Hoán vị
 Ví dụ 1: Một thương nhân định đi bán hàng tại
8 thành phố. Anh ta bắt đầu cuộc hành trình
của mình từ một thành phố nào đó, đi đến 7
thành phố còn lại theo bất kì thứ tự nào mà
anh ta muốn. Hỏi anh ta có thể đi qua 7 thành
phố còn lại theo bao nhiêu cách khác nhau?
7! = 7*6*5*4*3*2*1 = 5040
23
Hoán vị
 Ví dụ 2: Có bao nhiêu cách sắp xếp các chữ
cái {A, B, C, D, E, F, G, H} có chứa xâu ABC?
Hãy xem xâu ABC như 1 ký tự đơn => có tất cả 6
ký tự {ABC, D, E, F, G, H} => có số cách sắp chữ
là:
7201*2*3*4*5*6!66 P
24
Hoán vị
 Ví dụ 2: Có bao nhiêu cách sắp xếp các chữ
cái {A, B, C, D, E, F, G, H} có chứa xâu ABC
theo thứ tự bất kỳ?
Có 3! hoán vị của xâu độ dài 3 ký tự A, B, C
Hãy xem hoán vị của xâu 3 ký tự A, B, C như 1 ký
tự đơn => có tất cả 6 ký tự => có số cách sắp chữ
là:
!6!*3
25
Chỉnh hợp
 Định nghĩa: Một sắp xếp có thứ tự của k phần tử
trong tập hợp n phần tử được gọi là chỉnh hợp chập
k của tập n phần tử.
 Công thức:
)(
)!(
!
nk
kn
n
Akn 


26
Chỉnh hợp
 Ví dụ 1: Cho X ={a,b,c}. Khi đó X có các chỉnh hợp chập
2 của 3 là: ab, ba, ac, ca, bc, cb.
 Ví dụ 2: Có bao nhiêu số tự nhiên gồm 3 chữ số
được tạo thành từ 1, 2, 3, 4, 5, 6.
1204*5*6
!3
!3*4*5*6
!3
!63
6 A
27
Tổ hợp
 Định nghĩa: Tổ hợp chập k của một tập hợp có n
phần tử là một cách chọn không có thứ tự k phần tử
của n phần tử.
 Công thức:
k
n
kn
n CC 

k
n
k
n
k
n CCC 1
1

 
)(
)!(!
!
nk
knk
n
C kn 


10  nnn CC
28
Tổ hợp
 Ví dụ 1: Cho X = {1,2,3,4}. Tổ hợp chập 3 của
4 phần tử của X là {1,2,3}, {1,2,4}, {1,3,4},
{2,3,4}
 Ví dụ 2: Một lớp có 30 học sinh. Hỏi có bao
nhiêu cách chọn 10 bạn?
Số cách chọn là tổ hợp chập 10 của 30.
)!1030(!10
!3010
30

C
29
Tổ hợp
 Ví dụ 3: Một nhóm 30 người được đào tạo để
trở thành nhà du hành vũ trụ thực hiện chuyến
bay đầu tiên tới sao Hỏa. Hỏi có bao nhiêu
cách lựa chọn một phi đội gồm 6 người cho
nhiệm vụ đó?
593775
!24*1*2*3*4*5*6
!24*25*26*27*28*29*30
!24!*6
!306
30 C
30
Tổ hợp
 Ví dụ 4: Xác định số xâu bit có độ dài n và
chứa đúng r bit 1.
Các vị trí của r bit 1 trong xâu bit độ dài n là
không quan trọng. Do đó, số các xâu này
đúng bằng tổ hợp chập r của n phần tử, tức là
r
nC
31
Tổ hợp
 Ví dụ 5: Xác đinh số cách lựa chọn một hội đồng để
triển khai môn toán rời rạc tại một trường đại học,
nếu hội đồng gồm 3 thành viên của khoa toán, 4
thành viên của khoa CNTT. Biết rằng khoa toán có 9
thành viên và khoa CNTT có 11 thành viên.
27720
!7!*4
!11
*
!6!*3
!9
* 411
3
9 CC
32
Hoán vị lặp
 Định nghĩa. Cho n đối tượng trong đó có ni đối
tượng loại i (i =1,,k; n1+ + nk= n). Một sắp xếp
có thứ tự n đối tượng là một hoán vị lặp của n.
 Số hoán vị lặp của n đối tượng
!!....!
!
),...,,(
21
21
k
kn
nnn
n
nnnP 
33
Hoán vị lặp
 Ví dụ 1: Có thể nhận bao nhiêu xâu khác nhau bằng
cách sắp xếp lại các chữ cái của từ SUCCESS?
 Xâu độ dài là 7 trong đó có 3 ký tự S, 2 ký tự C, 1 ký tự E,
1 ký tự U
420
!1!*1!*2!*3
!7

34
Chỉnh hợp lặp
 Định nghĩa: Có n phần tử khác nhau, mỗi cách lấy k
phần tử từ n phần tử có lặp, có thứ tự được gọi là
chỉnh hợp lặp chập k của n.
kk
n nB 
35
Chỉnh hợp lặp
 Ví dụ 1: Từ bảng 26 chữ cái tiếng Anh có thể
tạo ra được bao nhiêu xâu có độ dài n?
Theo qui tắc nhân, vì có 26 chữ cái và vì mỗi
chữ có thể dùng lại nên chúng ta có 26n xâu
với độ dài n.
36
Tổ hợp lặp
 Định nghĩa. Mỗi cách chọn ra k phần tử
(không quan tâm đến thứ tự) từ tập gồm t
phần tử khác nhau (mỗi phần tử có thể được
chọn lặp lại) được gọi là tổ hợp lặp chập k
của t
)!1(!
)!1(
1
1
1


 


tk
kt
CC k kt
t
kt
37
Tổ hợp lặp
 Ví dụ 1: Giả sử trong một đĩa trái cây có táo, cam, lê,
mỗi loại có ít nhất 4 quả. Tính số cách lấy 4 quả từ
đĩa này nếu giả sử rằng thứ tự các quả được chọn
không quan trọng.
4 táo 4 cam 4 lê
3 táo, 1 cam 3 táo, 1 lê 3 cam, 1 táo
3 cam, 1 lê 3 lê, 1 táo 3 lê, 1 cam
2 táo, 2 cam 2 táo, 2 lê 2 cam, 2 lê
2 táo, 1 cam, 1 lê 2 cam, 1 táo, 1 lê 2 lê, 1 táo, 1 cam
38
Tổ hợp lặp
 Ví dụ 2: Có bao nhiêu cách chọn 5 tờ giấy bạc từ một
két đựng tiền gồm 7 tờ có mệnh giá là 1$, 2$, 5$,
10$, 20$, 50$ và 100$? Giả sử thứ tự các tờ tiền
chọn ra là không quan trọng, các tờ tiền cùng loại là
không phân biệt và mỗi loại có ít nhất 5 tờ.
462
!6!*5
!115
11 C