Bài giảng Toán rời rạc & Lý thuyết đồ thị - Chương 2: Phương pháp đếm

Chương 2. Phương pháp đếm 
I. TẬP HỢP 
1. KHÁI NIỆM TẬP HỢP 
 Để chỉ một tập hợp ta dùng chữ in hoa, chẳng hạn như A, B, C,., 
X,Y,Z. 
 Để chỉ một phần tử ta dùng chữ thường, chẳng hạn như a, b, c,., 
x,y,z. 
 Để chỉ x là một phần tử của tập hợp A. Ký hiệu x A 
 Để chỉ x không là một phần tử của tập hợp A. Ký hiệu x A 
Tập vũ trụ: Tập A nằm trong tập U thì U gọi là một vũ trụ của A. 
Tập hợp rỗng: Tập hợp không có phần tử nào được gọi là tập hợp rỗng, 
và được ký hiệu là  . 
Tập hợp bằng nhau: 
A = B  x A thì x B và  x B thì x A 
2.CÁCH XÁC ĐỊNH MỘT TẬP HỢP. 
 Cách liệt kê: Ta liệt kê tất cả các phần tử của tập hợp giữa 2 ký hiệu 
ngoặc và  . 
Ví dụ: 
A = a, b, c 
 Cách nêu đặc trưng của phần tử: 
A = x U / p(x) với U là tập vũ trụ của tập A.
hay vắn tắt (khi hiểu ngầm tập vũ trụ U): A = x / p(x) 
Ví dụ: 
A = n N / n là số nguyên tố  
B = n N / có một số tự nhiên m sao cho n = m2  
a 
 b 
 c 
3. QUAN HỆ "bao hàm trong" VÀ TẬP HỢP CON 
 Định nghĩa: A  B (hay B  A)  x A thì x B 
Ví dụ: 
 0, 1, 2  n N : n < 10 
 Các tập hợp số. 
N  Z  Q  R  C, trong đó 
 N là tập hợp các số tự nhiên, 
 Z là tập hợp các số nguyên, 
 Q là tập hợp các số hữu tỉ, 
 R là tập hợp các số thực, 
 C là tập hợp các số phức. 
 Cho X là một tập hợp. Sưu tập tất cả các tập hợp con của X được ký 
hiệu là P(X). Nói một cách khác, P(X) là một tập hợp mà mỗi phần tử của 
nó là một tập hợp con của X. 
Ví dụ: X= 0, 1, 2
Thì P(X)=  0, 1, 2     
Tính chất: 
  A và A  A, với mọi tập hợp A. 
(A  B)  (B  A) (A = B) 
(A  B)  (B  C) (A  C) 
X  Y P(X)  P(Y) 
Nếu tập hợp X có n phần tử (n N) thì tập hợp P(X) có 2n phần tử. 
4.CÁC PHÉP TÓAN TẬP HỢP. 
 Giao. 
A  B = x : (x A)  (x B)  
 Hợp. 
A  B = x : (x A)  (x B)  
 Hiệu. 
A - B = x : (x A)  (x B)  
 Phần bù. 
Ac = U – A 
 Tích Descartes của 2 tập hợp. 
A x B = (a,b) : a A  b B  
Trong trường hợp B = A, ta kỳ hiệu A x A = A2. 
 Các tính chất của các phép toán: 
Tính giao hoán: 
A  B = B  A 
A  B = B  A 
Tính kết hợp: 
A  (B  C) = (A  B)  C 
A  (B  C) = (A  B)  C 
Tính phân bố: 
A  (B  C) = (A  B)  (A  C) 
A  (B  C) = (A  B)  (A  C) 
Luật De Morgan: 
(A  B)c = Ac  Bc 
(A  B)c = Ac  Bc 
Phần tử trung hòa: 
A   = A 
A  U = A 
Phần bù: 
A  Ac = U 
A  Ac =  
Tính thống trị: 
A  U = U 
A   =  
II. ÁNH XẠ 
2.1 Định nghĩa ánh xạ 
Cho X và Y là các tập hợp khác rỗng. Một ánh xạ f từ tập hợp X vào tập 
hợp Y là phép tương ứng sao cho bởi phép tương ứng nầy mỗi phần tử x 
của X sẽ có một phần tử duy nhất y của Y tương ứng mà ta ký hiệu là f(x) 
và gọi là ảnh của x. Ta viết 
f : X Y 
x f(x) 
 Ta thường minh họa ánh xạ f bởi sơ đồ sau đây: 
 Hai ánh xạ f và g từ X vào Y được gọi là bằng nhau khi ta có: 
 x X : f(x) = g(x) 
 Cách xác định một ánh xạ. 
Ta có thể xác định ánh xạ f từ X vào Y bằng nhiều cách, chẳng hạn như 
cách liệt kê tất cả các ảnh của từng phần tử của X, cách cho một công 
thức để xác định ảnh f(x) của mỗi phần tử x, hoặc ta có thể đưa ra một 
thủ tục xác định để tính ra (hay tìm ra) được phần tử f(x) ứng với mỗi 
phần tử x X. 
Ví dụ: 
f : N N xác định bởi f(n) = 2(n+1). 
Thì 
f(1)=4 
f(2)=6 
.
2.2 Ảnh và ảnh ngược 
 Ảnh của tập hợp. 
Cho f là một ánh xạ từ X vào Y. Giả sử A là một tập hợp con của X. Ảnh 
của tập A qua ánh xạ f, ký hiểu bởi f(A), là tập hợp con của Y gồm tất cả 
những phần tử y sao cho y là ảnh của ít nhất một phần tử x thuộc A. 
f(A) = f(a) : a A  
Ảnh ngược (hay tạo ảnh) của một tập hợp. 
Cho f là một ánh xạ từ X vào Y. Giả sử B là một tập hợp con của Y. Aûnh 
ngược của tập B bởi ánh xạ f, ký hiểu là f-1(B), là tập hợp con của X gồm 
tất cả những phần tử x sao cho f(x) thuộc B. 
f-1(B) = x X : f(x) B  
Trong trường hợp tập B chỉ có một phần tử y thì ảnh ngược của B sẽ 
được viết vắn tắt là f-1(y). 
Ví dụ: 
Cho ánh xạ f : Z N xác định bởi f(n) = n2+1. Đặt A = -2, -1, 0, 1, 2, 3 
và B = 0, 1, 2, 3, 4, 5 . Ta có : 
f(A) = 1, 2, 5, 10 
f-1(B) = -2,-1, 0, 1,2 
2.3 Các ánh xạ đặc biệt 
Đơn ánh: 
Ánh xạ f : X Y được gọi là một đơn ánh khi các ảnh của 2 phần tử 
khác nhau tùy ý thì khác nhau, nghĩa là với mọi x và x' thuộc X ta có: 
x x' f(x) f(x') 
hay f(x) = f(x') x = x' 
Toàn ánh: 
Ánh xạ f : X Y được gọi là một toàn ánh khi mọi phần tử của Y đều là 
ảnh của ít nhất một phần tử x thuộc X, nghĩa là 
f(X) = Y. 
Song ánh: 
Aùnh xạ f : X Y được gọi là một song ánh khi nó vừa là đơn ánh vừa là 
toàn ánh. Khi ấy với mỗi y Y, có duy nhất phần tử x X sao cho f(x) = 
y. Như thế phép tương ứng liên kết y với x sẽ cho ta một ánh xạ từ Y vào 
X. Ta gọi ánh xạ nầy là ánh xạ ngược của f và ký hiệu là f-1. Vậy ta có 
f-1 : Y X, xác định bởi f-1(y) = x, với f(x) = y. 
Ví dụ: 
Ánh xạ f : Z N xác định bởi f(n) = n2+1 không phải là một đơn ánh vì 
f(-1) = f(1) = 2 mà -1 1. 
Ánh xạ f : N N xác định bởi f(n) = n2+1 là một đơn ánh vì ta có thể 
thấy rằng với mọi n và n' thuộc N ta có: nếu f(n) = f(n') thì n = n'. 
Cho a và b là 2 số thực tùy ý và a 0. 
Ánh xạ f : R R xác định bởi 
 f(x) = a.x+b 
 là một song ánh vì với mọi số thực y thì phương trình 
 ax + b = y 
có nghiệm thực x duy nhất là x = (y-b) / a. Từ đó ta cũng có ánh xạ ngược 
được xác định bởi 
f-1(y) = (y-b) / a. 
III. CÁC NGUYÊN LÝ ĐẾM. 
3.1 Phép Đếm 
 Định nghĩa: 
Cho A là một tập hợp khác rỗng. Nếu tồn tại một số nguyên dương n và 
một song ánh f từ A vào 1, 2, . . ., n thì ta nói A là một tập hợp hữu hạn 
và A có n phần tử. 
Khi đó song ánh f : A 1, 2, . . ., n được xem là một phép đếm tập 
hợp A. 
 Tập hợp rỗng có số phần tử là 0, và cũng được xem là tập hữu hạn. Số 
phần tử của một tập hợp hữu hạn A được ký hiệu là |A| (còn gọi là lực 
lượng của tập hợp A). 
 Nếu tập hợp A không hữu hạn, ta nói A là vô hạn và viết |A| = 
3.2 Nguyên lý cộng 
 Mệnh đề: Cho A và B là 2 tập hợp hữu hạn rời nhau, nghĩa là A  B = 
 . Khi ấy ta có: | A  B | = | A | + | B | 
 Một cách tổng quát: Nếu A1, A2, ..., An là các tập hợp hữu hạn rời nhau 
thì: | A1  A2  . . .  An | = | A1 | + | A2 | + . . . + | An | 
 Nguyên lý bù trừ: Trong trường hợp đối với hai tập hợp hữu hạn A và 
B tùy ý thì ta có: 
| A  B | = | A | + | B | - | A  B | 
 Nguyên lý cộng : để thực hiện một công việc ta có thể chọn một trong hai 
phương án khác nhau, cách thực hiện phương án thứ nhất luôn luôn khác 
cách thực hiện phương án thứ hai. Phương án thứ nhất có m cách thực 
hiện, và phương án thứ hai có n cách thực hiện. Thì tất cả sẽ có (m+n) cách 
thực hiện công việc. 
3.3 Nguyên lý nhân 
 Mệnh đề: Cho A và B là 2 tập hợp hữu hạn rời nhau. Khi ấy ta có: 
| A x B | = | A | . | B | 
 Một cách tổng quát: Nếu A1, A2, ..., An là các tập hợp hữu hạn thì số 
phần tử của tích Descartes của các tập hợp trên bằng tích của các số 
lượng phần tử của các tập hợp trên: 
| A1 x A2 x . . . x An | = | A1 | . | A2 | . . . . . | An | 
 Nguyên lý nhân : Để thực hiện một công việc phải qua hai giai đọan kế 
tiếp nhau. Giai đọan thứ nhất ta có m cách làm, và ứng với mỗi cách làm 
giai đọan thứ nhất có n cách làm giai đọan thứ hai. Thì sẽ có (m*n) cách 
thực hiện công việc. 
 Ví dụ: Các ghế ngồi trong một hội trường sẽ được ghi nhãn gồm một 
mẫu tự và một số nguyên dương không lớn hơn 100. Hỏi số ghế tối đa có 
thể được ghi nhãn khác nhau là bao nhiêu? 
Lời giải. Thủ tục ghi nhãn cho một ghế gồm 2 giai đọan : ghi một trong 26 
mẫu tự và kế tiếp là ghi một trong 100 số nguyên dương. Qui tắc nhân 
cho thấy có 26 x 100 = 2600 cách khác nhau để ghi nhãn cho một ghế 
ngồi. Do đó số ghế lớn nhất có thể được ghi nhãn khác nhau là 2600. 
Ví dụ: Một mật khẩu bao gồm 6 ký tự, trong đó gồm 3 mẫu tự rồi đến 3 
ký số thập phân. Hỏi có bao nhiêu mật khẩu khác nhau? 
Lời giải. Có 26 cách chọn cho mỗi mẫu tự và có 10 cách chọn cho mỗi ký 
số thập phân. Do đó, theo qui tắc nhân, có tất cả 26.26.26.10.10.10 = 17 
576 000 mã khác nhau. 
Ví dụ: Mỗi người sử dụng trên một hệ thống máy tính có một mật 
khẩu, dài từ 6 đến 8 ký tự, trong đó mỗi ký tự là một chữ in hoa hoặc là 
một ký số thập phân. Mỗi mật khẩu phải có chứa ít nhất một ký số. Hỏi 
có bao nhiêu mật khẩu khác nhau? 
Lời giải. Đặt P là số lượng tất cả các mật khẩu, và P6, P7, P8 lần lượt là số 
các mật khẩu có độ dài 6, 7, 8. Do qui tắc cộng ta có P = P6 + P7 + P8. 
Chúng ta sẽ tính P6, P7, và P8. 
Tính trực tiếp P6 tương đối khó. Để tính P6 cho dễ, ta tính số chuỗi có độ 
dài 6 gồm các chữ in hoa hay ký số thập phân (kể cả các chuỗi không có 
ký số thập phân), và trừ cho số chuỗi (với độ dài 6) không có ký số thập 
phân nào. Theo qui tắc nhân, số chuỗi gồm 6 ký tự là 366 và số chuỗi 
không có ký số nào là 266. Suy ra 
P6 = 36
6 - 266 = 2 176 782 336 - 308 915 776 
 = 1 867 866 560. 
Tương tự, ta có thể tính ra được : 
P7 = 36
7 - 267 = 78 364 164 096 - 8 031 810 176 
 = 70 332 353 920. 
và 
P8 = 36
8 - 268 = 2 821 109 907 456 - 208 827 064 576 
 = 2 612 282 842 880. 
Từ đó ta tính được : 
P = P6 + P7 + P8 = 2 684 483 063 360. 
IV. GIẢI TÍCH TỔ HỢP. 
LỌAI KÝ HIỆU CÔNG THỨC 
Chỉnh 
Hợp 
Không 
Lặp 
k
nAhayknA ),( )!(
!
)1(*...*)1(*
kn
n
knnnAkn
Có 
Lặp 
k
nPhayknP ),( 
kk
n nP 
Hóan 
vị 
Không 
Lặp 
n
nAhaynnA ),( !nA
n
n 
Có 
Lặp 
!*.....*!*!
!
21 knnn
n
Tổ 
Hợp 
Không 
Lặp 
k
nChayknC ),( )!(!
!
knk
n
C kn
Có 
Lặp 
)!1(!
)!1(
1
nk
kn
C k kn 
Với mọi số thự nhiên n ta có: 
C(n, 0) = 1 
C(n, n) = 1 
Cho n và r là 2 số nguyên không âm và k n. Ta có: 
C(n,k) = C(n,n-k) 
Cho n và k là 2 số nguyên sao cho 0 < k < n. Khi đó ta có: 
 C(n, k) = C(n-1, k) + C(n-1, k-1). 
 Ðịnh lý. Cho x và y là 2 biến thực, n là một số nguyên không ấm tùy ý. 
Ta có: 
 Hệ quả 1. Cho n là một số nguyên không âm tùy ý. Ta có: 
 Hệ quả 2. Cho n là một số nguyên không âm. Ta có: 
BÀI TẬP 
Bài 1: Có bao nhiêu chuỗi nhị phân dài tối đa 6 bit? 
Bài 2: Có bao nhiêu chuỗi nhị phân dài 10 bit, sao cho bit đầu bằng 0 hay 
bit cuối bằng 1. 
Bài 3: Một mật khẩu phải có độ dài 6 ký tự (không phân biệt ký tự hoa, thường), 
mỗi ký tự được lấy từ bảng 26 chữ cái và 10 chữ số. Tính số mật khẩu có thể tạo 
ra trong mỗi trường hợp sau: 
a) Không có điều kiện gì thêm. 
b) Trong mật khẩu phải có ít nhất một ký tự số. 
c) Trong mật khẩu phải có ít nhất một ký tự số và không có ký tự A. 
Bài 4: Có bao nhiêu dãy nhị phân dài 12 bit, chứa ít nhất 3 bit 0 và 3 bit 
1. 
Bài 5: Cần bầu một ủy ban gồm 6 đại biểu, chọn từ 8 Bà và 8 Ông ứng 
viên. Có bao nhiêu cách chọn trong mỗi trường hợp sau: 
a) Chọn tùy ý? 
b) Chọn số Bà bằng số Ông? 
c) Chọn số Bà ít hơn số Ông? 
Bài 6: Có bao nhiêu tam giác được tạo ra từ 9 điểm phân biệt 
trên mặt phẳng sao cho không có 3 điểm nào thẳng hàng. 
Bài 7: 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 nhất, nhì, ba, tư. Hỏi 
a) Có bao nhiêu cách trao giải? 
b) Có bao nhiêu cách trao giải, nếu người có vé 50 trúng giải nhất? 
c) Có bao nhiêu cách trao giải, nếu người có vé 50 không trúng giải 
nào? 
d) Có bao nhiêu cách trao giải, nếu 3 người có vé 10,15, 20 trúng giải? 
e) Có bao nhiêu cách trao giải, nếu 2 người có vé 20,30 trúng giải, 
nhưng người có vé 15 không trúng giải? 
Bài 8: Có 6 người vào tiệm ăn phở, trong tiệm có 4 lọai phở. Hỏi có bao 
nhiêu cách gọi cho mỗi người 1 tô phở? 
Bài 9: Cô dâu, chú rể, cùng chụp hình với 6 người bạn, có bao nhiêu cách 
xếp thành 1 hàng ngang để chụp, trong mỗi trường hợp sau: 
a) Xếp tùy í? 
b) Xếp sao cho cô dâu, chú rể luôn bên nhau? 
c) Xếp sao cho cô dâu luôn bên trái chú rể? 
d) Xếp sao cho cô dâu, chú rể đứng đúng giữa hàng?