“Đá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
39 trang |
Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 329 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Bài giảng Toán rời rạc - Chương 3: Một số công thức tổ hợp - Bùi Thị Thủy, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
TOÁN RỜI RẠC
(DISCRETE MATHEMATICS)
Bùi Thị Thủy
Đặng Xuân Thọ
Support
Full name: Đặng Xuân Thọ
Mobile: 091.2629.383
Email: thodx@hnue.edu.vn
Website:
Toán Rời Rạc - ĐHSPHN
2
NỘI DUNG
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
3
Chương 3. Một số công thức tổ hợp
“Đá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
4
Cơ sở của phép đếm
Toán Rời Rạc - ĐHSPHN
5
Cơ sở của phép đếm
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
6
Số phần tử của tích Đêcac
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
n1n2nk phần tử. Nghĩa là:
𝐴1 × 𝐴2 ×⋯×𝐴𝑘 = 𝐴1 × 𝐴2 × 𝐴𝑘
Đặc biệt ta có: 𝐴𝑛 = 𝐴 𝑛
Toán Rời Rạc - ĐHSPHN
7
Số phần tử của tích Đêcac
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
8
Hai nguyên lý cơ bản
Toán Rời Rạc - ĐHSPHN
9
Cơ sở của phép đếm (1/2)
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ụ:
Hà Nội TP. HCM
3 hãng hàng không
2 hãng tàu thủy
15 hãng giao thông
đường bộ Có 3 + 2 + 15 = 20 cách
10
Cơ sở của phép đếm (2/2)
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ụ:
Hà Nội TP. HCM
4 cách 8 cách
Có 8 * 4 = 32 cách
Đà Nẵng
Toán Rời Rạc - ĐHSPHN
11
Một Số Công Thức Tổ Hợp
Toán Rời Rạc - ĐHSPHN
12
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!
Hoán vị
Toán Rời Rạc - ĐHSPHN
13
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?
Hoán vị
Toán Rời Rạc - ĐHSPHN
14
Hoán vị trên đường tròn
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
15
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)!
Hoán vị trên đường tròn
Toán Rời Rạc - ĐHSPHN
16
Chỉnh hợp
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
17
Chỉnh hợp
Đị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
18
Chỉnh hợp lặp
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
19
Chỉnh hợp với tần số lặp cho trước
Đị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à:
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.
1 2
1 2
!
( , ,..., )
! !... !
n
n
k
P k k k
k k k
Toán Rời Rạc - ĐHSPHN
20
Tổ hợp chập k của n phần tử là số các tập
hợp con k phần tử của một tập n phần tử cho
trước (không có thứ tự).
Ví dụ: Cho tập hợp A={a,b,c,d}. Tìm tất cả các
tập hợp hai phần tử của A?
{a,b}; {a,c}; {a,d}; {b,c}; {b,d}; {c,d}
Định lý. Số tập hợp con k phần tử của một tập
A có n phần tử cho trước là:
Tổ hợp
Toán Rời Rạc - ĐHSPHN
21
Ví dụ 1. Có bao nhiêu cách tuyển 5 trong số
10 cầu thủ của một đội bóng để đi thi đấu tại
một trường khác?
Ví dụ 2. Trong 10 cầu thủ trên, có 3 cầu thủ
nữ. Hỏi có bao nhiêu cách chọn 5 cầu thủ đi
thi đấu trong đó có 2 cầu thủ nữ.
Tổ hợp
Toán Rời Rạc - ĐHSPHN
22
Luyện tập
1. Có bao nhiêu số tự nhiên có 5 chữ số đôi một
khác nhau?
2. Có bao nhiêu máy điện thoại có 6 chữ số?
Và trường hợp 6 chữ số đôi một khác nhau?
3. Cho A={1,2,3,4,5,6,7}. Có bao nhiêu số tự
nhiên có 5 chữ số lấy từ A sao cho:
Có chữ số đầu là 3
Không tận cùng bằng chữ số 4
Cứ 2 chữ số kề nhau là khác nhau
Không bắt đầu bằng 123
23
Luyện tập
Toán Rời Rạc - ĐHSPHN
24
4. Một lớp học có 40 học sinh với 25 nam và 15
nữ. Có mấy cách chọn 4 học sinh sao cho:
a. Chọn nam, nữ tùy ý
b. Chọn 2 nam và 2 nữ
c. Tính xác suất để chọn ít nhất một nữ
5. Tìm số đường chéo của đa giác lồi có n cạnh.
(Đa giác lồi là đa giác có tính chất kéo dài bất kỳ cạnh
nào đều không cắt đa giác. Khi đó 2 đỉnh bất kỳ nối
lại, được hoặc cạnh hoặc đường chéo.)
Luyện tập
Toán Rời Rạc - ĐHSPHN
25
6. Từ tập A = {0,1,2,3,4,5} lập được bao nhiêu số tự
nhiên có 8 chữ số sao cho:
- chữ số 2 có mặt 3 lần
- mỗi chữ số còn lại có mặt 1 lần
7. Xét tam giác có đỉnh lấy từ một đa giác lồi có 20
cạnh.
a. Có bao nhiêu tam giác nói trên?
b. Tính xác suất để chọn được tam giác có đúng 1 cạnh
chung với đa giác?
c. Có bao nhiêu tam giác có đúng 2 cạnh chung với đa giác?
d. Tính xác suất để chọn được tam giác không có cạnh
chung với đa giác?
Khai triển lũy thừa của đa thức
Toán Rời Rạc - ĐHSPHN
26
Hệ số tam giác Pascal
Toán Rời Rạc - ĐHSPHN
27
(a+b)2 = a2 + 2ab + b2
(a+b)3 = a3 + 3a2b + 3ab2 + b3
(a+b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4
1 2 1
1 3 3 1
1 4 6 4 1
Nhị thức Newton
Định lý. Cho mỗi số tự nhiên n 1 ta có:
= C0nb
n + C1nab
n-1 + C2na
2bn-2 + + Cn-1na
n-1b + Cnna
n
Toán Rời Rạc - ĐHSPHN
28
n
k
kknk
n
n
baCba
0
Nhị thức Newton
Toán Rời Rạc - ĐHSPHN
29
Tính chất:
1
1 1
1 1 1
1 2
1.
2.
3. ...
k n k
n n
k k k
n n n
k k k k
n n n n k
C C
C C C
C C C C
Ví dụ
Toán Rời Rạc - ĐHSPHN
30
Ví dụ 1: Tính A = C0n + C
1
n + + C
n
n
Chọn x=1 thì: 2n = C0n + C
1
n + + C
n
n
n
k
kk
n
n
k
knkk
n
n
xCxCx
00
11
= C0n + C
1
nx + C
2
nx
2 + + Cn-1nx
n-1 + Cnnx
n
Luyện tập
Toán Rời Rạc - ĐHSPHN
31
8. CM: C02n+C
2
2n+..+C
2n
2n=C
1
2n+C
3
2n+..+C
2n-1
2n
n
k
kk
n
n
k
knkk
n
n
xCxCx
2
0
2
2
0
2
2
2
11
Với x = -1 thì:
0 = C02n - C
1
2n + C
2
2n – C
3
2n+-C
2n-1
2n+C
2n
2n
C02n+C
2
2n++C
2n
2n = C
1
2n+C
3
2n++C
2n-1
2n
Luyện tập
Toán Rời Rạc - ĐHSPHN
32
9. Khai triển đa thức:
P(x)=(x+1)10 + (x+1)11 + (x+1)12 + (x+1)13 + (x+1)14
ra dạng: P(x) = a0 + a1x + a2x
2 + + a14x
14.
tính a10?
Khai triển lũy thừa của đa thức
Định lý. Cho m, n là 2 số nguyên dương. Khi
đó ta có:
tổng được lấy trên tất cả các bộ m số tự nhiên
(k1,k2,,km) sao cho k1 + k2 ++ km = n.
1 2
1 2
1 2 1 2
... 1 2
!
( ... ) ...
! !... !
m
m
kk kn
m m
k k k n m
n
x x x x x x
k k k
Toán Rời Rạc - ĐHSPHN
33
Ví dụ
Toán Rời Rạc - ĐHSPHN
34
Tất cả các bộ (k1,k2,k3) sao cho k1+k2+k3=3 là:
(3,0,0), (2,1,0), (2,0,1), (1,2,0), (1,0,2), (1,1,1),
(0,3,0), (0,2,1), (0,1,2), (0,0,3).
3
321
321
3
321
321
321
!!!
!3
kkk
kkk
xxx
kkk
xxx
Công thức Tổ hợp trong tập hợp 35
Toán Rời Rạc - ĐHSPHN
Số phần tử của một hợp các tập hợp
Toán Rời Rạc - ĐHSPHN
36
Ví dụ: Bài kiểm tra Toán có 2 câu hỏi. Cả lớp
có 30 em làm được câu thứ nhất, 20 em làm
được câu thứ hai, và chỉ có 10 em làm được
cả hai câu. Tìm số học sinh cả lớp?
A tập hợp học sinh giải được câu thứ nhất
B tập hợp học sinh giải được câu thứ hai
A∩B là tập hợp học sinh giải được cả hai câu
|A∪B| = |A| + |B| - |A∩B| = 30+20–10 = 40 em
Số phần tử của một hợp các tập hợp
Toán Rời Rạc - ĐHSPHN
37
|A∪B| = |A| + |B| - |A∩B|
|A∪B∪C| = |A|+|B|+|C|-|A∩B|-|B∩C|-|C∩A|+|A∩B∩C|
Định lý: cho trước các tập hợp A1,A2,..An. Khi đó:
|A1∪A2∪⋯An|= |Ai|- |Ai∩Bj|++(-1)
n+1|A1∩A2∩⋯An|
Luyện tập
Toán Rời Rạc - ĐHSPHN
38
10. Trong một kỳ thi học sinh giỏi Toán, Lý, Hóa.
Biết rằng có 20 em thi Toán, 14 em thi Lý, 6 em
thi cả Toán và Lý, 5 em thi cả Lý và Hóa, 2 em
thi cả Toán và Hóa, và có 1 em tham gia cả 3
môn. Hỏi có bao nhiêu em?
11. Tính số các mật khẩu tạo được bằng cách
hoán vị các chữ cái của từ “TINHOCTRE” sao
cho không có hai chữ cái nào giống nhau đứng
cạnh nhau?
THANK YOU!