Xem mẫu
- TOÁN RỜI RẠC
(DISCRETE MATHEMATICS)
Bùi Thị Thủy
Đặng Xuân Thọ
- Support
2
Full name: Đặng Xuân Thọ
Mobile: 091.2629.383
Email: thodx@hnue.edu.vn
Website: http://cs.fit.hnue.edu.vn/~tho/
Toán Rời Rạc - ĐHSPHN
- NỘI DUNG
3
Chương 1. Logic mệnh đề
Chương 2. Lý thuyết tập hợp
Chương 3. Một số công thức tổ hợp
Chương 4. Suy luận và kiểm chứng chương trình
Chương 5. Đại số Boole và cấu trúc mạch logic
Chương 6. Thuật toán
Chương 7. Lý thuyết đồ thị
Toán Rời Rạc - ĐHSPHN
- Chương 3. Một số công thức tổ hợp
4
“Đánh giá số điện thoại nhiều nhất có thể có
trong Hà Nội.”
“Xác định số mật khẩu, mỗi mật khẩu gồm
sáu, bảy, hoặc tám ký tự; mỗi ký tự có thể chữ
hoặc số; mỗi mật khẩu chứa ít nhất một chữ.”
Một số công thức tổ hợp
Chỉnh hợp
Hoán vị
Hoán vị trên đường tròn
…
Toán Rời Rạc - ĐHSPHN
- 5 Cơ sở của phép đếm
Toán Rời Rạc - ĐHSPHN
- Cơ sở của phép đếm
6
Phần này chúng ta chỉ giải quyết xác định lực
lượng của tập hợp hữu hạn.
Nếu tập hợp A là tập hợp hữu hạn, thì lực
lượng của nó là số lượng phần tử của nó, ký
hiệu là 𝐴 .
Định lý: Nếu Ai (i=1,2,..n) là một phân hoạch
của tập hợp A thì ta có 𝑛𝑖=1 𝐴𝑖 = 𝐴 .
Toán Rời Rạc - ĐHSPHN
- Số phần tử của tích Đêcac
7
Ví dụ: Cho tập hợp A={a,b}. Tìm tất cả các
dãy ký tự có ba phần tử được tạo thành từ A?
aaa, aab, bbb, bba, abb, baa, aba, bab
Định lý: cho trước các tập hợp hữu hạn Ai
(i=1,..,k) trong đó tập hợp Ai có đúng ni phần
tử. Khi đó tích Đêcac A1 x A2 x … x Ak có đúng
n1n2…nk phần tử. Nghĩa là:
𝐴1 × 𝐴2 × ⋯ × 𝐴𝑘 = 𝐴1 × 𝐴2 × 𝐴𝑘
Đặc biệt ta có: 𝐴𝑛 = 𝐴 𝑛
Toán Rời Rạc - ĐHSPHN
- Số phần tử của tích Đêcac
8
Ví dụ: Có bao nhiêu số tự nhiên có chín chữ
số mà trong biểu diễn thập phân của nó không
có mặt chữ số nào trong tập hợp {0,3,7,9}?
Mỗi số tự nhiên có chín chữ số không được viết
bởi các chữ số {0,3,7,9} là một dãy chín kí tự có
lặp của tập hợp {1,2,4,5,6,8}.
69
Toán Rời Rạc - ĐHSPHN
- 9 Hai nguyên lý cơ bản
Toán Rời Rạc - ĐHSPHN
- Cơ sở của phép đếm (1/2)
10
Nguyên lý cộng
Giả sử có các công đoạn E1, E2,…, Ek. Để thực
hiện E ta chỉ cần thực hiện một trong những Ei
(i = 1..k) trong đó số cách thực hiện Ei là ni. Khi
đó số cách thực hiện E là n1 + n2 + …+ nk.
Ví dụ: 3 hãng hàng không
2 hãng tàu thủy
Hà Nội TP. HCM
15 hãng giao thông
đường bộ Có 3 + 2 + 15 = 20 cách
- Cơ sở của phép đếm (2/2)
11
Nguyên lý nhân
Giả sử có công đoạn E được thực hiện lần lượt
qua các công đoạn E1, E2, …, Ek trong đó số cách
thực hiện Ei là ni (i = 1, k). Khi đó số cách thực
hiện E là n1 x n2 x … x nk
Ví dụ:
8 cách 4 cách TP. HCM
Hà Nội Đà Nẵng
Có 8 * 4 = 32 cách
Toán Rời Rạc - ĐHSPHN
- 12 Một Số Công Thức Tổ Hợp
Toán Rời Rạc - ĐHSPHN
- Hoán vị
13
Khái niệm. Hoán vị của một tập các đối tượng
khác nhau là một cách sắp xếp có thứ tự các
đối tượng này.
Bài toán. Cho tập A có n phần tử. Hãy tính số
các hoán vị khác nhau của tập A.
Ví dụ: cho A={a,b,c,d} tìm tất cả các hoán vị có thể có
của tập hợp A?
Định lý. Số các hoán vị khác nhau của một
tập n phần tử là Pn = n!
Toán Rời Rạc - ĐHSPHN
- Hoán vị
14
Ví dụ: Hãy tính số các số sau:
Có năm chữ số được viết bởi đúng 5 chữ số 1, 2,
3, 4 và 5?
Có năm chữ số được viết bởi đúng 5 chữ số 1, 2,
3, 4 và 5 trong đó ba chữ số đầu là ba chữ số lẻ,
hai chữ số sau là hai chữ số chẵn?
Toán Rời Rạc - ĐHSPHN
- Hoán vị trên đường tròn
15
Ví dụ: Cho tập hợp A = {a,b,c,d}. Tìm tất cả
các hoán vị khác nhau của các phần tử của A
trên đường tròn?
Toán Rời Rạc - ĐHSPHN
- Hoán vị trên đường tròn
16
Bài toán: Tính số các hoán vị khác nhau của
một tập hợp A gồm n phần tử nằm trên một
đường tròn?
Định lý: Số các hoán vị tròn khác nhau của
tập hợp A có n phần tử là Qn = (n – 1)!
Toán Rời Rạc - ĐHSPHN
- Chỉnh hợp
17
Bài toán: Cho tập A có n phần tử và số k≤n
(kN). Mỗi dãy độ dài k được xếp bởi các
phần tử của tập A trong đó mỗi phần tử có
mặt không quá một lần được gọi là một dãy
k phần tử không lặp của A.
Tính số các dãy đó?
Toán Rời Rạc - ĐHSPHN
- Chỉnh hợp
18
Định lý: Cho trước tập A có n phần tử và một
số tự nhiên k ≤ n. Số các dãy k phần tử không
lặp của A là:
Ví dụ: có bao nhiêu số có 4 chữ số mà trong
biểu diễn thập phân của nó không có 2 chữ số
nào giống nhau và không có mặt chữ số
chẵn?
Toán Rời Rạc - ĐHSPHN
- Chỉnh hợp lặp
19
Cho tập A có n phần tử. Khi đó số dãy gồm k
phần tử có lặp thuộc tập A là nk và được gọi là
chỉnh hợp lặp chập k của n phần tử.
Ví dụ: có bao nhiêu số tự nhiên có 9 chữ số
mà trong biểu diễn thập phân của nó không có
mặt chữ số nào trong tập hợp {0,1,2,3,4,5}?
Toán Rời Rạc - ĐHSPHN
- Chỉnh hợp với tần số lặp cho trước
20
Định lý: Cho trước một tập hợp A có n phần
tử. Số các dãy k phần tử có lặp (k1+k2+…+kn)
và (k=k1+…+kn) là:
k!
P(k1 , k2 ,..., kn )
k1 !k2 !...kn !
Ví dụ: Tính các số tự nhiên có 7 chữ số, trong
đó có 3 chữ số 1, 2 chữ số 2 và 2 chữ số 3.
Toán Rời Rạc - ĐHSPHN
nguon tai.lieu . vn
