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|
–BA: |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 = 2ố ậ ợ ủ m
–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: (aộ ộ ầ ử 1, a2, …, an) Sn
s các b n ph n t c a S = mố ộ ầ ử ủ n
–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