Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 2: Phép đếm (Tiếp theo) - Võ Tấn Dũng

LOGO
Chương 2 (tt). Phép đếm
Chương 2
1
GV: Võ Tấn Dũng
TOÁN RỜI RẠC
Mệnh đề 
Cho A và B là hai tập hữu hạn rời nhau. Khi đó 
|A  B|= |A|+|B|
NGUYÊN LÝ CỘNG
BA
2
NGUYÊN LÝ CỘNG
Nguyên lý cộng:
Giả sử để thực hiện một công việc ta có 2 phương án
- Phương án 1 có n cách làm
- Phương án 2 có m cách làm
Khi đó số cách làm công việc A là n+m
Ví dụ. 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
Bài tập:
 Thầy giáo có 3 danh sách bài tập:
- Danh sách thứ nhất có 23 bài.
- Danh sách thứ hai có 15 bài.
- Danh sách thứ ba có 19 bài.
Một sinh viên phải chọn một bài tập để làm. Hỏi sinh 
viên đó có bao nhiêu cách chọn bài tập?
4
Giải:
5
Ta có:
- 23 cách chọn bài tập từ danh sách thứ nhất.
- 15 cách chọn bài tập từ danh sách thứ hai.
- 19 cách chọn bài tập từ danh sách thứ ba.
Vì vậy:
- Theo nguyên lý cộng, sinh viên đó có 23+15+19=57 
cách chọn bài tập.
NGUYÊN LÝ NHÂN
Nguyên lý nhân:
Giả sử để làm một công việc, ta cần thực hiện 2 bước
- Bước 1 có n cách làm
- Bước 2 có m cách làm
Khi đó số cách làm công việc A là n.m
Ví dụ: 
A B C
Có 3.2 =6 con đường đi từ A đến C
Phép đếm
6
Bài tập:
Cho tập X ={1,2,3,4,5,0}
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 ý: Gọi số có 3 chữ số là
Thì c phải bằng 2 hoặc 4 hoặc 0 
abc
7
Giải
Cho tập X ={1,2,3,4,5,0}
Hỏi có bao nhiêu số tự nhiên có 3 chữ số khác nhau mà chia 
hết cho 2
Giải. 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} )
TH1 có 1.4.5 =20
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} )
TH2 có 2.4.4 =32
Vậy có 20+32 =52
8
Bài tập
Một dãy số XXXYYY có độ dài 6. Mỗi X có thể gán 
bởi một chữ cái. Mỗi Y có thể gán một chữ số. Hỏi 
có bao nhiêu dãy số được thành lập theo cách trên?
9
Giải
Một dãy số XXXYYY có độ dài 6. Mỗi X có thể gán 
bởi một chữ cái. Mỗi Y có thể gán một chữ số. Hỏi 
có bao nhiêu dãy số được thành lập theo cách trên?
10
Có 26 chữ cái và 10 chữ số.
Vậy dãy số được thành lập theo cách trên là:
26^3*10^3 =17.576.000
Bài tập
Có bao nhiêu xâu nhị phân có độ dài 10 bit sao cho 
bit đầu tiên và bit cuối cùng là 1?
11
Bài tập
Có bao nhiêu xâu nhị phân có độ dài 10 bit sao cho 
bit đầu tiên và bit cuối cùng là 1?
12
Xâu nhị phân có dạng 1a1a2a3a4a5a6a7a81 thuộc về tập {0,1}
Có 28 xâu nhị phân như vậy.
Nguyên lý bù trừ. 
Cho A và B là hai tập hữu hạn. Khi đó 
|A  B|= |A|+|B| - |A  B|
NGUYÊN LÝ BÙ TRỪ
A  B BA
13
Bài tập
A  B
A  C BC 
A  B  C
A B
C
|A  B  C|=?
14
Bài tập
Bài tập: Trong một lớp ngoại ngữ Anh Pháp. Có 24 HS 
học Tiếng Pháp, 26 học sinh học Tiếng Anh. 15 học sinh 
học Tiếng Anh và Tiếng Pháp. Hỏi lớp có bao nhiêu 
người
15
Bài tập
Bài tập: Trong một lớp ngoại ngữ Anh Pháp. Có 24 HS 
học Tiếng Pháp, 26 học sinh học Tiếng Anh. 15 học sinh 
học Tiếng Anh và Tiếng Pháp. Hỏi lớp có bao nhiêu 
người
Giải. 
Gọi A là những học sinh học Tiếng Pháp
B là những học sinh học Tiếng Anh
Khi đó. Số học sinh của lớp là |A  B |. Theo nguyên lý 
bù trừ ta có |A  B|= |A|+|B| - |A  B|=24+26-15=35
16
Bài tập
Bài tập: Trong một lớp học có 45 sinh viên học tiếng Anh, 
30 sinh viên học tiếng Pháp và 10 sinh viên học cả Anh 
và Pháp.
1) Nếu trong lớp đó, không ai không biết một 
trong hai thứ tiếng trên, hãy tính số sinh viên của lớp.
2) Nếu sĩ số của lớp là 70. Hỏi có bao nhiêu sinh 
viên không biết ngoại ngữ Anh, Pháp?
17
Bài tập
Giải: Đặt A là số sinh viên học tiếng Anh thì |A| = 45
Đặt B là số sinh viên học tiếng Pháp thì |B| = 30
A  B là số SV học tiếng Anh và Pháp |A  B| = 10
1) Theo nguyên lý bù trừ ta có:
|A  B|= |A|+|B| - |A  B|=45+30-10=65
Vậy số sinh viên của lớp là 65
2) |A  B| = 65 là số SV học tiếng Anh hoặc tiếng Pháp 
hoặc học cả hai. Vậy, nếu sỉ số lớp là 70 thì ta có
70-65=5 SV không học tiếng Anh hoặc Pháp.
18
HOÁN VỊ
Hoán vị
Định nghĩa. Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt 
có thứ tự n phần tử của A được gọi là một hoán vị của n
phần tử. Số các hoán vị của n phần tử ký hiệu là Pn 
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
19
Bài tập. 
Cho X ={1,2,3,4,5}. Hỏi có bao nhiêu số tự nhiên gồm 
5 chữ số khác nhau được tạo từ tập X? 
20
Giải: 5!
Bài tập. 
Giả sử một vận động viên đi xe đạp dự định đi qua 8 
thành phố. Vận động viên này bắt đầu cuộc hành trình từ 
một thành phố nào đó và có thể đến thành phố tiếp theo 
theo bất kỳ một thứ tự nào mà anh ta muốn. Hỏi vận động 
viên có thể đi qua 8 thành phố này theo bao nhiêu lộ trình 
khác nhau?
21
Giải. 
Số lộ trình khác nhau có thể có của vận động viên này 
bằng số hoán vị của 7 thành phố còn lại vì thành phố đầu 
tiên đã được xác định rồi. Bảy thành phố còn lại có thứ tự 
tùy chọn. Do đó số lộ trình khác nhau là 7! = 5040.
22
Giải: 5!
CHỈNH HỢP
Chỉnh hợp.
Định nghĩa. Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k
phần tử (1 k n) sắp thứ tự của tập hợp A được gọi là một 
chỉnh hợp chập k của n phần tử.
Số các chỉnh hợp chập k của n ký hiệu là
- Công thức 
!
!
k
n
n
A
n k
k
nA
Ví dụ. Cho X ={abc}. Khi đó X có các chỉnh hợp chập 2 của 
3 là: ab, ba, ac, ca, bc, cb. 
23
Bài tập
Bài tập: 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. 
Kết quả: 3
6A
24
Bài tập. 
Có bao nhiêu cách chọn có thứ tự 4 cầu thủ khác 
nhau trong 10 cầu thủ của đội bóng quần vợt để chơi bốn 
trận đấu đơn, các trận đấu là có thứ tự?
25
Giải: 
Có bao nhiêu cách chọn có thứ tự 4 cầu thủ khác 
nhau trong 10 cầu thủ của đội bóng quần vợt để chơi bốn 
trận đấu đơn, các trận đấu là có thứ tự?
Một cách chọn có thứ tự bốn cầu thủ của đội bóng là một 
chỉnh hợp chập 4 của 10 phần tử. Theo công thức của chỉnh 
hợp, ta có:
26
TỔ HỢP
Tổ hợp.
Định nghĩa. Cho tập hợp A gồm n phần tử. Mỗi tập con gồm k 
phần tử của A được gọi là một tổ hợp chập k của n phần tử.
Số tổ hợp chập k của n phần tử được kí hiệu là hay
k
nC 
k
n
!
! !
k
n
n
C
k n k
27
Bài tập
Bài tập. 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} 
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. 
10
30C
28
Bài tập. 
Có 100 vé số được đánh số từ 1 đến 100 được bán 
cho 100 người khác nhau. Người ta sẽ trao 4 giải thưởng kể 
cả giải độc đắc. Hỏi:
1) Có bao nhiêu cách trao thưởng?
2) Có bao nhiêu cách trao giải thưởng nếu người giữ vé 47 
trúng giải độc đắc?
29
Giải: 
Có 100 vé số được đánh số từ 1 đến 100 được bán 
cho 100 người khác nhau. Người ta sẽ trao 4 giải thưởng kể 
cả giải độc đắc. Hỏi:
1) Có bao nhiêu cách trao thưởng?
2) Có bao nhiêu cách trao giải thưởng nếu người giữ vé 47 
trúng giải độc đắc?
1) Số cách trao thưởng là: 
2) Số cách trao thưởng là:
30
HOÁN VỊ LẶP
Hoán vị lặp
Định nghĩa. Cho n đối tượng trong đó có ni đối tượng loại i 
giống hệt nhau (i =1,2,,k ; n1+ n2,+ nk= n).
Mỗi cách sắp xếp có thứ tự n đối tượng đã cho gọi là một 
hoán vị lặp của n.
Số hoán vị của n đối tượng, trong đó có 
n1 đối tượng giống nhau thuộc loại 1, 
n2 đối tượng giống nhau thuộc loại 2,, 
nk đối tượng giống nhau thuộc loại k, là 
1 2
!
! !... !k
n
n n n
31
BÀI TẬP
Bài tập. Có bao nhiêu chuỗi kí tự khác nhau bằng cách sắp 
xếp các chữ cái của từ SUCCESS?
Giải. Trong từ SUCCESS có 3 chữ S, 1 chữ U, 2 chữ C và 
1 chữ E. Do đó số chuỗi có được là 
.
7!
420
3!1!2!1!
32
Bài tập
Hãy tính xem có bao nhiêu cách sắp 
xếp khác nhau của 6 mẫu tự trong từ 
PEPPER
33
TỔ HỢP LẶP
Tổ hợp lặp
Định nghĩa. Mỗi cách chọn ra k vật từ n loại vật khác nhau 
(trong đó mỗi loại vật có thể được chọn lại nhiều lần) 
được gọi là tổ hợp lặp chập k của n
Số các tổ hợp lặp chập k của n được ký hiệu là k
nK
1
k k
n n kK C 
34
Bài tập. Có 3 loại nón A, B, C. An mua 2 cái nón. Hỏi An có 
bao nhiêu cách chọn.
Ta có mỗi cách chọn là mỗi tổ hợp lặp chập 2 của 3. Cụ thể 
AA, AB, AC, BB, BC, CC
2 2 2
3 3 2 1 4 6K C C 
Bài tập
35
Bài tập
Bài tập: Một người vào một cửa hàng ăn uống muốn 
chọn mua 7 phần ăn, mỗi phần ăn sẽ được chọn một trong 
4 loại khác nhau: A, B, C, D. Hỏi có bao nhiêu cách chọn 7 
phần ăn.
36
Giải
37