M Đ UỞ Ầ
Lý thuy t t h p là m t ph n quan tr ng c a toán h c r i r c chuyên nghiênế ổ ợ ộ ầ ọ ủ ọ ờ ạ
c u s s p x p các đ i t ng.Thông th ng các ph n t này là h u h n và vi c phânứ ự ắ ế ố ượ ườ ầ ử ữ ạ ệ
b chúng ph i tho mãn nh ng đi u ki n nh t đ nh nào đó, tùy theo yêu c u c a bàiố ả ả ữ ề ệ ấ ị ầ ủ
toán c n nghiên c u. Ch đ này đ c nghiên c u t th k 17 khi nh ng câu h i v tầ ứ ủ ề ượ ứ ừ ế ỷ ữ ỏ ề ổ
h p đ c nêu ra trong nh ng công trình nghiên c u c a các trò ch i may r i. Li t kê,ợ ượ ữ ứ ủ ơ ủ ệ
đ m, s p x p các đ i t ng có nh ng tính ch t nào đó là m t ph n quan tr ng c a lýế ắ ế ố ượ ữ ấ ộ ầ ọ ủ
thuy t t h p.ế ổ ợ
M t bài toán khác trong lý thuy t t h p là vi c t o ra các cách s p x p theoộ ế ổ ợ ệ ạ ắ ế
m t ki u nào đó. V n đ này r t quan tr ng trong các mô ph ng máy tính. Chúng taộ ể ấ ề ấ ọ ỏ
cũng s đ a ra nh ng thu t toán t o các cách s p x p theo nhi u ki u khác nhau.ẽ ư ữ ậ ạ ắ ế ề ể
Các bài toán t h p có đ c tr ng bùng n t h p v i s c u hình t h p kh ngổ ợ ặ ư ổ ổ ợ ớ ố ấ ổ ợ ổ
l . Vi c gi i chúng đòi h i m t kh i l ng tính toán kh ng l (có tr ng h p m t hàngồ ệ ả ỏ ộ ố ượ ổ ồ ườ ợ ấ
ch c năm). Vì v y trong th i gian dài, khi mà các ngành toán h c nh phép tính vi phân,ụ ậ ờ ọ ư
phép tính tích phân, ph ng trình vi phân…phát tri n nh vũ b o, thì nó nh n m ngoàiươ ể ư ả ư ằ
s phát tri n và ng d ng c a toán h c. Tình th thay đ i t khi xu t hi n máy tính vàự ể ứ ụ ủ ọ ế ổ ừ ấ ệ
s phát tri n c a toán h c h u h n. Nhi u v n đ t h p đã đ c gi i quy t trên máyự ể ủ ọ ữ ạ ề ấ ề ổ ợ ượ ả ế
tính. T ch ch nghiên c u các trò ch i, t h p đã tr thành ngành toán h c phát tri nừ ỗ ỉ ứ ơ ổ ợ ở ọ ể
m nh m , có nhi u ng d ng trong các lĩnh v c toán h c phát tri n m nh m , có nhi uạ ẽ ề ứ ụ ự ọ ể ạ ẽ ề
ng d ng trong lĩnh v c toán h c, tin h c…ứ ụ ự ọ ọ
Khi hai công vi c có th đ c làm đ ng th i, chúng ta không th dùng quy t cệ ể ượ ồ ờ ể ắ
c ng đ tính s cách th c hi n nhi m v g m c 2 vi c c ng s cách làm m i vi c sộ ể ố ự ệ ệ ụ ồ ả ệ ộ ố ỗ ệ ẽ
d n đ n s trùng l p, vì nh ng cách làm c hai vi c s đ c tính 2 l n. Đ tính đúngẫ ế ự ậ ữ ả ệ ẽ ượ ầ ể
s cách th c hi n nhi m v này c ng s cách làm m i 1 trong 2 vi c r i tr đi s cáchố ự ệ ệ ụ ộ ố ỗ ệ ồ ừ ố
làm đ ng th i c 2 vi c. Đó là nguyên lý bù tr .ồ ờ ả ệ ừ
2
Ch ng I: Đ I C NG V T H Pươ Ạ ƯƠ Ề Ổ Ợ
I. S l c v toán h c t h pơ ượ ề ọ ổ ợ
1.1 M t s nguyên lý c b nộ ố ơ ả
1.1.1. Nguyên lý nhân
Gi s m t c u hình t h p đ c xây d ng qua k b c, b c 1 có th đ cả ử ộ ấ ổ ợ ượ ự ướ ướ ể ượ
th c hi n nự ệ 1 cách, b c 2 có th đ c th c hi n nướ ể ượ ự ệ 2 cách, …, b c k có th đ c th cướ ể ượ ự
hi n nệk cách. Khi đó s c u hình t h p làố ấ ổ ợ
n1. n2…. nk
1.1.2. Nguyên lý c ngộ
Gi s {Xả ử 1, X2,…,Xn} là m t phân ho ch c a t p S. Khi đóộ ạ ủ ậ
1 2 n
S X X ... X= + + +
1.2. Các c u hình t h p đ n gi nấ ổ ợ ơ ả
Nh ng c u hình này th ng đ c làm c s cho phép đ mữ ấ ườ ượ ơ ở ế
1.2.1. Ch nh h p l pỉ ợ ặ
Đ nh nghĩa:ị M t ch nh h p l p ch p k c a n ph n t khác nhau là m t b cóộ ỉ ợ ặ ậ ủ ầ ử ộ ộ
th t g m k thành ph n l y t n ph n t đã cho. Các thành ph n có th đ c l p l i.ứ ự ồ ầ ấ ừ ầ ử ầ ể ượ ặ ạ
M t ch nh h p l p ch p k c a n có th xem nh m t ph n t c a tích Đ -Các Xộ ỉ ợ ặ ậ ủ ể ư ộ ầ ử ủ ề k, v iớ
X là t p n ph n t . Nh v y s t t c các ch nh h p l p ch p k c a n là nậ ầ ử ư ậ ố ấ ả ỉ ợ ặ ậ ủ k
1.2.2. Ch nh h p không l pỉ ợ ặ
Đ nh nghĩa:ị M t ch nh l p không l p ch p k c a n ph n t khác nhau là m tộ ỉ ợ ặ ậ ủ ầ ử ộ
b có th t g m k thành ph n l y t n ph n t đã cho. Các thành ph n không đ c l pộ ứ ự ồ ầ ấ ừ ầ ử ầ ượ ặ
l i.ạ
M t ch nh h p không l p ch p k c a n có th đ c xây d ng qua k b c k ti p nhộ ỉ ợ ặ ậ ủ ể ượ ự ướ ế ế ư
sau:
Ch n thành ph n đ u tiên: có n kh năng ọ ầ ầ ả
Ch n thành ph n th hai: có n -1 kh năng ọ ầ ứ ả
…..
3
Ch n thành ph n th k: có n – k + 1 kh năngọ ầ ứ ả
Nh v y theo nguyên lý nhân, s t t c ch nh h p không l p ch p k c a n ph n t là ư ậ ố ấ ả ỉ ợ ặ ậ ủ ầ ử
A(n,k) = n(n - 1)…. (n – k + 1) =
n!
(n k)!
−
1.2.3. Hoán vị
Đ nh nghĩa:ị M t hoán v c a n ph n t khác nhau là m t cách s p x p th tộ ị ủ ầ ử ộ ắ ế ứ ự
các ph n t đó.ầ ử
Hoán v có th coi nh tr ng h p riêng c a ch nh h p không l p ch p k c a n trong đóị ể ư ườ ợ ủ ỉ ợ ặ ậ ủ
k = n. Ta có s hoán v là ố ị
P(n) = n!
1.2.4. T h pổ ợ
Đ nh nghĩa:ị M t t h p ch p k c a n ph n t khác nhau là m t b không kộ ổ ợ ậ ủ ầ ử ộ ộ ể
th t g m k thành ph n khác nhau l y t n ph n t đã cho. Nói cách khác ta có th coiứ ự ồ ầ ấ ừ ầ ử ể
m t t h p ch p k c a n ph n t khác nhau là m t t p con có k ph n t t n ph n t đãộ ổ ợ ậ ủ ầ ử ộ ậ ầ ử ừ ầ ử
cho.
Ký hi u s t h p ch p k c a n ph n t là C(n, k). Ta cóệ ố ổ ợ ậ ủ ầ ử
A(n, k) = C(n, k).k!
Suy ra
C(n, k) =
n!
k!(n k)!
−
1.2.5. Hoán v l pị ặ
Đ nh nghĩa:ị
Hoán v l p là hoán v trong đó m i ph n t đ c n đ nh s l n l p cho tr c.ị ặ ị ỗ ầ ử ượ ấ ị ố ầ ặ ướ
Đ nh líị
S hoán v l p c a k ph n t khác nhau trong đó s ph n t th nh t l p nố ị ặ ủ ầ ử ố ầ ử ứ ấ ặ 1 l n,ầ
s ph n t th 2 l p nố ầ ử ứ ặ 2 l n,..., s ph n t th k l p nầ ố ầ ử ứ ặ k l n làầ
P( n; n1, n2,.....nk ) =
1 2
!
! !..... !
k
n
n n n
H quệ ả
4
Gi s t p S có n ph n t khác nhau, trong đó có nả ử ậ ầ ử 1 ph n t ki u 1, nầ ử ể 2 ph n tầ ử
ki u 2,..., nểk ph n t ki u k. Khi đó s các hoán v n ph n t c a t p S làầ ử ể ố ị ầ ử ủ ậ
P( n; n1, n2, ..., nk ) =
1 2
!
! !..... !
k
n
n n n
1.2.6. T h p l p:ổ ợ ặ
Đ nh nghĩa:ị
T h p l p ch p k t n ph n t là m t nhóm không phân bi t th t g m k ph nổ ợ ặ ậ ừ ầ ử ộ ệ ứ ự ồ ầ
t trích t n ph n t đã cho, trong đó các ph n t có th l p l i.ử ừ ầ ử ầ ử ể ặ ạ
Đ nh lý:ị
Gi s X có n ph n t khác nhau. Khi đó s t h p l p ch p k t n ph n t c a X, kýả ử ầ ử ố ổ ợ ặ ậ ừ ầ ử ủ
hi u CR(n, k) là:ệ
CR(n, k) = C(k+n–1,n-1) = C(k+n-1, k)
5
Ch ng II: NGUYÊN LÝ BÙ TRươ Ừ
Công th c 1:ứ Cho 2 t p h p A,B. Theo nguyên lý c ng ta có:ậ ợ ộ
BA ∪
=
A
+
B
-
BA ∩
Công th c 2:ứ Cho t p h p X và n t p con Xậ ợ ậ 1, X2 , ….., Xn, ta có:
n
XXX ∪∪∪ .......
21
=
Trong đó: X(n,k)=
∑≤<<≤
∩∩∩
nii
iii
k
k
xxx
...1 1
21 .....
Trong t ng X(n,k), b (iổ ộ 1,i2, …..,ik) l y t t c các t h p ch p k c a n và nh v yấ ấ ả ổ ợ ậ ủ ư ậ
X(n,k) là t ng c a C(n,k) s h ng. ổ ủ ố ạ Nói riêng ta có
X(n,1) =
1
X
+
2
X
+……+
n
X
và X(n,n) =
n
XXX ∩∩∩ .......
21
T công th c 2,s d ng tính ch t: ừ ứ ử ụ ấ
=∩∩∩ n
XXX .......
21
n
XXX ∪∪∪ ....
21
=
−X
n
XXX ∪∪∪ ....
21
Ta nh n đ c công th c sau:ậ ượ ứ
Công th c 3 (Sieve):ứ
),()1(.......
0
2
1knXXXX
n
k
k
n∑
=
−=∩∩∩
Trong đó: X(n,0) =
X
6