Bài giảng Toán rời rạc - Chương 3: Phương pháp đếm - Nguyễn Lê Minh

TOÁN RỜI RẠC
Chương 3: PHƯƠNG PHÁP ĐẾM
GV: NGUYỄN LÊ MINH
Bộ môn Công nghệ thông tin
Nội dung
Tập hợp và hàm số
Các nguyên lý đếm
Lý thuyết tổ hợp
Nguyên lý Dirichlet
Hệ thức truy hồi
2
Tập hợp
Định nghĩa: Là một trong những khái niệm cơ
bản của toán học, làm cơ sở cho các định
nghĩa toán học. Đó là những đối tượng được
nhóm lại theo một tính chất nào đó
Ví dụ: Tập hợp các bài tập toán rời rạc
Tập hợp số sinh viên lớp CNTT K59
Hệ các phương trình tuyến tính
(Tập hợp đồng nghĩa với họ, hệ, lớp .)
3
Tập hợp
Những yếu tố tạo thành một tập hợp gọi là
phần tử (hay điểm) của tập hợp
Kí hiệu:
Nếu a là phần tử của A
a∈A (a thuộc A)
3
Diễn tả tập hợp
Có 2 cách diễn tả tập hợp:
 Nêu tính chất đặc trưng các phần tử tạo
thành tập hợp
 Liệt kê các phần tử của tập hợp
Ví dụ: A = 𝑥 ∈ 𝑁| 𝑥 𝑙à 𝑠ố 𝑛𝑔𝑢𝑦ê𝑛 𝑡ố
A = 1 ; 2 ; 3 ; 4 ; 5
3
Tập hợp
Các tập hợp số:
N =  −> tập hợp số tự nhiên
𝑁∗ =  −> tập hợp số tự nhiên khác 0
Z =  −> tập hợp các số nguyên
Q =  −> tập hợp các số hữu tỉ
R =  −> tập hợp các số thực
C =  −> tập hợp các số phức
3
Tập hợp
- Tập hợp A có n phần tử |A| = n
- Tập hợp A có vô số phần tử |A| = +∞
- Tập hợp không có phần tử nào ( tập hợp
rỗng) |A| = ∅
( Lưu ý: Tập hợp rỗng ≠ tập hợp có phần tử 0)
3
Tập hợp
Nếu mọi phần tử của tập hợp A đều là phần tử
của tập hợp B thì A là tập hợp con của B
Ngoài ra:
Nếu và thì A = B
Nếu 𝐴 ≠ 𝐵 thì hay
3
A B
A A A
A B B A
A B B A
Tập hợp
Mối quan hệ giữa hai tập hợp được biểu diễn
bằng biểu đồ Venn
3
Các phép toán trên tập hợp
• Phép giao: 𝑨 ∩ 𝑩 = 𝒙 ∈ 𝑼|(𝒙 ∈ 𝑨) (𝒙 ∈ 𝑩)
• Phép hợp: 𝑨 ∪ 𝑩 = 𝒙 ∈ 𝑼|(𝒙 ∈ 𝑨)(𝒙 ∈ 𝑩)
• Phần bù:
3
 \ |A U A x U x A 
Tính chất của các phép toán
Với A, B, C là các tập con tùy ý của U
3
Tích Descartes của các tập hợp
Tích Descartes của hai tập hợp A, B (ký hiệu
AxB) là tập các cặp có thứ tự (a,b) trong đó 𝑎 ∈ 𝐴
và 𝑏 ∈ 𝐵
𝐴𝑥𝐵 = 𝑎, 𝑏 |𝑎 ∈ 𝐴 𝑣à 𝑏 ∈ 𝐵
Ví dụ:
Nếu A = {a,b} và B={c,d,e}
A x B = {(a,c),(a,d),(a,e),(b,c),(b,d),(b,e)}
Từ đó suy ra trường hợp tổng quát
Tích Descartes của n tập 𝐴1, 𝐴2, 𝐴3,  , 𝐴𝑛
3
Ánh xạ
Một ánh xạ f từ tập hợp X vào tập hợp Y, ký hiệu
f: X−>Y là phép tương ứng liên kết mỗi phần tử
𝑥 ∈ 𝑋 với một phần tử duy nhất 𝑦 ∈ 𝑌
• X gọi là tập nguồn, Y gọi là tập đích
• Phần tử y = f(x)∈Y gọi là ảnh của X
3
:f X Y
x y
Xác định một ánh xạ
• Liệt kê tất cả các ảnh của từng phần tử của X
• Công thức để xác định ảnh f(x) của mỗi phần
tử x
• Đư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
3
Ả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 } 
3
Ánh xạ hợp
• Cho 2 ánh xạ
f : X Y
g : Y Z
• Ánh xạ hợp h của f và g là ánh xạ từ X vào Z 
xác định bởi:
• Ký hiệu: h = g o f.
3
:
( ) ( )
h X Z
x h x g f x
Đơ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
• 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'
3
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
3
Song ánh
• Á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
• Phép tương ứng liên kết y với x sẽ cho một ánh 
xạ từ Y vào X. Ánh xạ này là ánh xạ ngược của 
f và ký hiệu là 𝑓−1
f-1 : Y X, xác định bởi f-1(y) = x, với f(x) = 
y
3
Phép đếm
Các bài toán đếm xuất hiện phổ biến trong toán
học cũng như trong tin học. Dùng để giải nhiều
dạng bài toán khác nhau, ví dụ: Số phép toán
trong một thuật toán để nghiên cứu độ phức tạp,
số mật khẩu truy nhập vào hệ máy tính 
3
Những nguyên lý đếm cơ bản
Nguyên lý cộng: Giả sử một công việc được
phân thành n trường hợp riêng biệt, trường hợp
1 có 𝑚1 cách, trường hợp 2 có 𝑚2 cách,
trường hợp n có 𝑚𝑛 cách. Khi đó số cách thực
hiện công việc là 𝑚1 +𝑚2 +𝑚3 +⋯+𝑚𝑛
• Giả sử chọn một đại diên (cán bộ hoặc sinh
viên) của một khoa tham dự đại hội trường,
biết khoa có 15 cán bộ, 135 sinh vên. Hỏi có
bao nhiêu cách chọn đại diện này ?
3
Những nguyên lý đếm cơ bản
Nguyên lý nhân: Giả sử một công việc được
thực hiện qua n bước liên tiếp, bước 1 có 𝑚1
cách, bước 2 có 𝑚2 cách,  bước n có 𝑚𝑛 cách.
Khi đó số cách chọn thực hiện công việc là
𝑚1x𝑚2x𝑚3xx𝑚𝑛
• Trong một lớp học có 30 người, có bao nhiêu
cách cử một ban đại diện gồm 1 lớp trưởng, 1
lớp phó và 1 thủ quỹ.
3
Những nguyên lý đếm cơ bản
Nguyên lý bù trừ: Khi 2 công việc được làm
đồng thời, không thể dùng quy tắc cộng để tính
số cách thực hiện nhiệm vụ ( dẫn tới trùng lặp)
sử dụng nguyên lý bù trừ để tính đúng số cách
thực hiện
• Trong tập X={1,2,,1000} có bao nhiêu số
không chia hết cho bất cứ số nào trong các số
3,4,5
3
Bài tập
1. Cho tập X={1,2,3,4,5,0}. Có bao nhiêu số tự
nhiên có 3 chữ số khác nhau mà chia hết cho
2 ?
2. Ghế trong hội trường được đánh dấu bằng 1
chữ cái và 1 số nguyên dương không vượt
quá 100. Hỏi nhiều nhất có bao nhiêu ghế
được đánh dấu khác nhau ?
3. Có bao nhiêu biển đăng ký xe nếu dùng 3
chữ số ở đầu 3 chữ cái phía sau hoặc ngược
lại ?
3
Bài tập
4. Mật khẩu máy tính gồm 1 chữ cái và 3 hoặc 4
chữ số, tính số mật khẩu tối đa có thể? Cùng câu
hỏi với điều kiện các chữ số không được lặp lại
5. Cho 10 chữ số 0,1,2,3,4,5,6,7,8,9. Có bao
nhiêu số lẻ có 6 chữ số khác nhau nhỏ hơn
600000 được xây dựng từ 10 chữ số trên ?
6. Có bao nhiêu cách sắp xếp 5 bạn A, B, C, D,
E vào một chiếc ghế dài sao cho
a) C ngồi chính giữa.
b) A và E ngồi ở 2 đầu ghế.
3
Hoán vị
Định nghĩa: Một hoán vị của n phần tử là một
nhóm có thứ tự gồm đủ mặt n phần tử đã cho
Số hoán vị của n phần tử là 𝑷𝒏 = 𝒏!
Ví dụ: Thầy giáo muốn tặng 5 cuốn sách khác
nhau cho 5 học sinh. Hỏi có bao nhiêu cách
tặng ?
5! = 120
3
Tổ hợp
Định nghĩa: Một tổ hợp chập k từ n phần tử
(0 ≤ 𝑘 ≤ 𝑛) là một bộ gồm k phần tử không
phân biệt thứ tự lấy từ n phần tử đã cho, mỗi
phần tử lấy không được lặp lại.
Ví dụ: Một tổ gồm 8 nam và 6 nữ, có bao nhiêu
cách chọn 1 nhóm 5 người mà trong đó có
đúng 2 nữ.
3
Chỉnh hợp
Định nghĩa: Một chỉnh hợp chập k từ n phần
tử (0 ≤ 𝑘 ≤ 𝑛) là một bộ có thứ tự gồm k
phần tử lấy từ n phần tử đã cho, mỗi phần tử
không được lấy lặp lại.
Ví dụ: Một lớp phải học 10 môn, mỗi ngày học
2 môn. Hỏi có bao nhiêu cách sắp xếp thời
khóa biểu trong 1 ngày
3
Tổ hợp lặp
Định nghĩa: Một tổ hợp lặp chập k từ n phần
tử là một bộ gồm k phần tử không phân biệt
thứ tự, mỗi phần tử có thể được lấy lặp lại từ
n phần tử đã cho
Ví dụ: Có 4 loại bút bi: Xanh, đỏ, vàng, tím,
mỗi loại có ít nhất 6 cây bút. Có bao nhiêu
cách khác nhau để chọn ra 6 cây bút ?
3
Chỉnh hợp lặp
Định nghĩa: Một chỉnh hợp lặp chập k từ n
phần tử là một bộ có thứ tự gồm k phần tử
lấy từ n phần tử đã cho, trong đó mỗi phần tử
có thể được lấy lặp lại
Ví dụ: Để đăng ký một loại ký hiệu máy mới,
người ta dùng 3 chữ số trong 9 chữ số:
1,2,3,,9. Hỏi có thể đánh số được bao
nhiêu máy ?
3
Nguyên lý Dirichlet (nguyên lý
chuồng bồ câu)
Định nghĩa: Nếu xếp nhiều hơn n đối tượng và
n cái hộp thì tồn tại ít nhất một hộp chứa
không ít hơn 2 đối tượng
Giả sử có 1 đàn chim bồ câu bay vào chuồng,
nếu số chim nhiều hơn số ngăn chuồng thì
chắc chắn có ít nhất một ngăn có nhiều hơn 1
con chim
3
Bài tập
1. Số mã vùng cần thiết nhỏ nhất là bao nhiêu
để đảm bảo 25 triệu máy điện thoại khác
nhau. Mỗi điện thoại có 9 chữ số dạng 0XX-
8XXXXX với X nhận giá trị từ 0-9
2. Biển số xe gồm 8 ký tự dạng NN-NNNN-XN,
ví dụ (75-1234-H1). Hai số đầu là mã tỉnh, X
là chữ cái (26 chữ cái), N gồm các số từ
0,1,2,,9. Hỏi số biển tối đa có thể tạo được
? 25,000,000
3. Có bao nhiêu xâu nhị phân có độ dài 10, bắt
đầu bằng 00 kết thúc bằng 11 và ngược lại ?
3
Bài tập
4. Khóa 59 CNTT có 150Sv học Java, 160Sv học
Web, 40 Sv học cả 2 môn trên.
a) Tìm tất cả sv khóa 59 biết sv nào cũng học ít
nhất một môn
b) Giả sử số sv là 285, hỏi có bao nhiêu sv
không học 2 môn trên
5. Mỗi người sử dụng máy tính dùng password
6->8 ký tự, các ký tự là chữ số hoặc chữ cái, mỗi
password phải có ít nhất 1 chữ số. Tìm tổng
password có thể có.
3
Bài tập
6. Cần phải có bao nhiêu sv ghi tên vào lớp Toán
rời rạc để chắc chắn có ít nhất 65sv đạt cùng
điểm thi, giả sử thang điểm thi gồm 10 bậc.
7. Cần lập ra một ủy ban có ít nhất 4 người,
nhiều nhất 10 người, được chọn ra từ 5 nam, 7
nữ, với điều kiện phải có ít nhất 2 nam và số nữ
ít nhất gấp đôi số nam. Vậy có bao nhiêu cách
chọn ủy ban.
8. Có bao nhiêu cách sắp xếp các sách trên một
giá sách, biết trên giá có 10 quyển sách, trong đó
7 quyển có tác giả khác nhau và 3 quyển có
cùng tác giả.
3
Hệ thức truy hồi
Nguyên lý quy nạp toán học: Giả sử cần
chứng minh mệnh đề có dạng ∀n ≥ 𝑛𝑜, p(n)
đúng.
Bước 1: Chứng minh p(𝑛0) đúng
Bước 2: Giả sử p(k), 𝑛0 ≤ k đúng. Ta chứng
minh p(k+1) cũng đúng
Khi đó p(n) đúng với ∀n ≥ 𝑛𝑜
3
Hệ thức truy hồi
Ví dụ: Dùng phương pháp quy nạp chứng minh:
1
2!
+
2
3!
+⋯+
𝑛
𝑛 + 1 !
= 1 −
1
𝑛 + 1 !
∀𝑛 ≥ 1 (1)
Bước 1: Xét n = 1
Bước 2: Giả sử
1
2!
+
2
3!
+ ⋯+
𝑘
𝑘 + 1 !
= 1 −
1
𝑘 + 1 !
(∀𝑘 ≥ 1)
Chứng minh phương trình (1) đúng với n = k+1,
hay
1
2!
+
2
3!
+ ⋯+
𝑘
𝑘 + 1 !
+
𝑘 + 1
𝑘 + 2 !
= 1 −
1
𝑘 + 2 !
3
Hệ thức truy hồi
Ví dụ: Chứng minh 
𝒏𝟑 + 𝟏𝟏𝒏 𝒄𝒉𝒊𝒂 𝒉ế𝒕 𝒄𝒉𝒐 𝟔, ∀ 𝒏 ≥ 𝟏
Đặt p(n) = 𝒏𝟑 + 𝟏𝟏𝒏
Xét p(n) với n = 1
Giả sử p(k) = 𝑘𝟑 + 𝟏𝟏k chia hết cho 6
Chứng minh p(k+1) = (𝑘 + 1)𝟑+𝟏𝟏 k + 1 ⋮ 6
3
Hệ thức truy hồi
Định nghĩa: Công thức truy hồi của dãy 𝑆0, 𝑆1,
𝑆2, là công thức xác định 𝑆𝑛 qua 1 hay
nhiều số hạng đi trước của dãy.
Điều kiện ban đầu là các giá trị gán cho 1 số
hữu hạn các phần tử đầu
- Công thức truy hồi của n!
𝑆𝑛 = n . 𝑆𝑛−1 với ∀n≥2 & S(0) = 1
- Dãy số Fibonacci
𝑓𝑛 = 𝑓𝑛−1 + 𝑓𝑛−1với ∀n≥2 & f(0) = f(1) = 2
3
Giải công thức truy hồi
Định nghĩa: Giải công thức truy hồi là tìm 1
công thức rõ ràng cho 𝑆𝑛 mà không phải tính
thông qua các phần tử trước nó
a) Giải công thức truy hồi bằng phương pháp
lặp
b) Giải công thức truy hồi bằng phương pháp
trình bày đặc trưng
3
Giải công thức truy hồi
Bằng phương pháp lặp: Thay thế liên tiếp
công thức truy hồi vào chính nó, mỗi lần thay
bậc n giảm đi ít nhất 1 đơn vị, cho đến khi đạt
giá trị ban đầu
3
Giải công thức truy hồi
Ví dụ: Trên một mặt phẳng kẻ n đường thẳng
sao cho không có 2 đường nào song song
hay 3 đường nào đồng quy. Hỏi mặt phẳng
chia làm mấy phần ?
Gọi số phần mặt phẳng chia bởi n đường
thẳng là S(n). Giả sử đã kẻ (n-1) đường
thẳng, nếu kẻ thêm 1 đường thẳng nữa thì số
phần mặt phẳng được thêm bằng số giao
điểm +1
Vậy ta có công thức truy hồi
S(n) = S(n-1) + n với n≥2 & S(1) = 1
3
Giải công thức truy hồi
Giải công thức truy hồi bằng phương pháp lặp
S(n) = n + S(n-1)
S(n) = n + (n-1) + S(n-2)
S(n) = n + (n-1) + (n-2) + S(n-3)
Vậy S(n) =
𝑛(𝑛+1)
2
+ 1
3
Giải công thức truy hồi
Bằng phương pháp trình bày đặc trưng: Một
hệ thức truy hồi tuyến tính thuần nhất bậc k là
hệ thức truy hồi có dạng
𝑆𝑛 = 𝐶1𝑆𝑛−1 + 𝐶2𝑆𝑛−2 +⋯+ 𝐶𝑘𝑆𝑛−𝑘
Trong đó 𝐶1, 𝐶2, 𝐶𝑘 là các số thực và 𝐶𝑘 ≠ 0
Điều kiện đầu là 𝑆0 = 𝐶0, 𝑆1 = 𝐶1,  , 𝑆𝑘−1 = 𝐶𝑘−1
Phương trình sau là phương trình đặc trưng của
công thưc truy hồi
𝑟𝑘 − 𝐶1𝑟
𝑘−1 − 𝐶2𝑟
𝑘−2 −⋯− 𝐶𝑘 = 0
3
Giải công thức truy hồi
Định lý: Giả sử phương trình đặc trưng
𝑟𝑘 − 𝐶1𝑟
𝑘−1 − 𝐶2𝑟
𝑘−2 −⋯− 𝐶𝑘 = 0
Có k nghiệm phân biệt 𝑟1, 𝑟2,  , 𝑟𝑘 khi đó dãy
{Sn} là nghiệm của hệ thức truy hồi
𝑆𝑛 = 𝛼1𝑟1
𝑛 + 𝛼2𝑟2
𝑛 +⋯+ 𝛼𝑘𝑟𝑘
𝑛
Với n = 0,1,2 trong đó 𝛼1, 𝛼2,  , 𝛼𝑘là các hằng
số.
3
Giải công thức truy hồi
Ví dụ: Giải công thức truy hồi
𝑓𝑛 = 6𝑓𝑛−1 − 11𝑓𝑛−2+6𝑓𝑛−3
Với f(0)=2, f(1)=5, f(2) =15
Phương trình đặc trưng
𝑟3 − 6𝑟2 + 11𝑟 − 6 = 0
 𝑟1 = 1 𝑟2 = 3 𝑟3 = 2
𝑆𝑛 = 𝛼11
𝑛 + 𝛼23
𝑛 + 𝛼32
𝑛 (∗)
Thay f(0),f(1),f(2) ta có
2 = 𝛼1 + 𝛼2 + 𝛼3 => 𝛼1 = 1
5 = 𝛼1 + 3𝛼2 + 2𝛼3 => 𝛼2 = 2
15 = 𝛼1 + 9𝛼2 + 4𝛼3 => 𝛼3 = -1 3
Giải công thức truy hồi
Ví dụ: Giải công thức truy hồi
𝑓𝑛 = 6𝑓𝑛−1 − 11𝑓𝑛−2+6𝑓𝑛−3
Với f(0)=2, f(1)=5, f(2) =15
 Công thức truy hồi
𝑓𝑛 = 1
𝑛 + 2. 3𝑛 − 2𝑛
3
Giải công thức truy hồi
Ví dụ: Giải công thức truy hồi
𝑓𝑛 = 6𝑓𝑛−1 − 9𝑓𝑛−2
Với f(0)=2, f(1)=6
Công thức truy hồi
𝑓𝑛=3
𝑛 + 𝑛. 3𝑛
3
Bài tập
Giải các hệ thức truy hồi sau
1. S(n) = 2.n.S(n-1) với n≥ 1, 𝑆 0 = 1
2. S(n) = S(n-1) + n với ≥ 1, 𝑆 0 = 1
3. S(n) = S(n-1) +1 + 2𝑛−1 với ≥ 1, 𝑆 0 = 0
4. S(n) = 5S(n-1) – 6S(n-2) với S(0)=1, S(1)=0
5. S(n) = S(n-1) + 6S(n-2) với S(0)=3, S(1)=0
6. S(n) = -6S(n-1) - 9S(n-2) với n≥ 2, 𝑆 0 = 3,
𝑆 1 = −3
7. S(n) = 2S(n-1) + 5S(n-2) - 6S(n-3) với n≥3,
S(0) = 7, S(1) = -4, S(2) = 8
3
Bài tập
Giải các hệ thức truy hồi sau (tiếp)
8. S(n) = 7.S(n-1)-10S(n-2) với n ≥ 2, 𝑆 0 =
2, 𝑆 1 = 1
9. S(n) = 2 S(n-1) + S(n-2) – 2S(n-3) với n≥3,
S(0) = 7, S(1) = -4, S(2) = 8
10. S(n) = S(n-1) + 2n + 3 với S(0) = 4
11. S(n) = 2S(n-1) - S(n-2) với n≥2 và S(0) =4
và S(1) =1
12. S(n) = -4S(n-1) + -4S(n-2) với n≥2, S(0)=0,
S(1) =1
3
Bài tập
Giải các hệ thức truy hồi sau (tiếp)
13. S(n) = 5.S(n-1)-6S(n-2) với n ≥ 2, 𝑆 0 =
0, 𝑆 1 = 1
14. S(n) = S(n-1) + 4S(n-2) – 4S(n-3) với S(0) =
0, S(1) = 1, S(2) = -1
3
Bài tập
Tìm số nghiệm nguyên không âm của phương
trình
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 = 31
Trong các trường hợp sau
1. 𝑥1 ≥ 16
2. 3 ≤ 𝑥1 ≤ 10
3. 𝑥1 ≥ 3 với i = 1,2,3,4,5
4. 1 ≤ 𝑥1 ≤ 6 và 4 ≤ 𝑥3 ≤ 15 và 𝑥5 ≥ 8
3
Bài tập
Tìm số nghiệm nguyên không âm của phương
trình
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 = 21
Trong các trường hợp sau
1. 𝑥1 ≥ 1
2. 0 ≤ 𝑥1 ≤ 10
3. 𝑥1 ≥ 2 với i = 1,2,3,4,5
4. 0 ≤ 𝑥1 ≤ 3 và 1 ≤ 𝑥2 ≤ 4 và 𝑥3 ≥ 15
3
Bài tập
Tìm số nghiệm nguyên không âm của phương
trình
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 = 21
Trong các trường hợp sau
1. 𝑥1 ≥ 5
2. 5 ≤ 𝑥1 ≤ 10
3. 𝑥1 ≥ 3 với i = 1,2,3,4,5
4. 0 ≤ 𝑥1 ≤ 3 và 1 ≤ 𝑥2 ≤ 4 và 𝑥3 ≥ 15
3