TOÁN HỌC RỜI RẠC
PHẦN 2
DISCRETE MATHEMATICS
PART TWO
NỘI DUNG
1. PHÉP ĐẾM
a. Nguyên lý cộng, nhân & bù trừ
b. Giải tích tổ hợp
c. Nguyên lý Dirichlet
d. Công thức đệ quy
2. LÝ THUYẾT ĐỒ THỊ
a. Đại cương
b. Đồ thị liên thông
c. Đường đi ngắn nhất
d. Cây khung trọng lượng tối tiểu
e. Luồng cực đại
2. SỐ HỌC
a. Lý thuyết chia hết
b. Lý thuyết đồng dư
2
PHÉP ĐẾM (1)
•NGUYÊN LÝ CỘNG, NHÂN, BÙ
–A là một tập hợp, ký hiệu |A| bản số của A, trong trường hợp A là
tập hữu hạn, |A| chính là số phần tử của A
–|A ∪ B|=|A| + |B| -|A ∩ B|
nếu A ∩ B = ∅ thì |A ∪ B|=|A| + |B|
–|A x B| = |A| * |B|
–B⊆A: |A – B| = |A| - |B|
•GIẢI TÍCH TỔ HỢP
–S là một tập hợp hữu hạn, |S| = m
–Số các tập hợp con của S = 2m
–Số các tập con n phần tử của S (n ≤ m) =
–Một bộ n phần tử cũa S: (a1, a2, …, an) ∈ Sn
số các bộ n phần tử của S = mn
–Số các hoán vị của một dãy m phần tử = m!
3
!)!(
!
nnm
m
n
m
−
=
PHÉP ĐẾM (2)
•CÁC VÍ VỤ
–Trong một phòng họp có n người, mỗi người bắt tay với mỗi
người khác đúng một lần. Số bắt tay?
–Dùng n bit để biểu diễn nhị phân cho các số nguyên không âm,
số số nguyên có thể được biểu diễn?
–Có bao nhiêu số thập phân có 6 chữ số? Bao nhiêu số thập
phân có số chữ số nhỏ hơn sáu?
–Có bao nhiêu cách sắp xếp chỗ ngồi cho n người xung quanh
một chiếc bàn họp tròn?
Bây giờ giả sử ông chủ tịch cuộc họp được sắp ngồi ở một ghế
xác định, có bao nhiêu cách sắp xếp chỗ ngồi cho các người còn
lại?
–Có bao nhiêu dãy số nguyên dương, có tổng bằng n?
–Có bao nhiêu dãy k số nguyên dương có tổng bằng n?
–Có bao nhiêu cách phân phát n món quà (khác nhau đô một)
cho k đứa trẻ?
4
PHÉP ĐẾM (3)
–Có bao nhiêu cách sắp xếp 8 các quân xe trong bàn cờ 8x8 sao
cho không quân xe nào « bị tấn công »?
–Cây nhị phân chiều cao h có nhiều nhất bao nhiêu nút lá?
–Trong mặt phẳng, cho n đường thẳng đôi một cắt nhau và không
có ba đường thẳng nào đồng quy. n đường thẳng này chia mặt
phẳng thành bao nhiêu miền?
–Cho n giác lồi, không có ba đường chéo nào đồng quy, các
đường chéo của đa giác chia da giác thành bao nhiêu miền?
5