Đề tài
NGUYÊN LÝ BÙ TRỪ TỔNG QUÁT & ỨNG DỤNG
NHÓM 8
STT Họ tên Công việc
(theo mục lục)
Chữ ký Nhận xét của
giáo viên
1 Lê Diêm Hùng
Chương 1: Đại cương về tổ
hợp
2 Hồ Thị Mộng Điệp Chương 2: Lý thuyết bù trừ
3 Đào Thị Anh Thư Chương 3: Ứng dụng
4 Nguyễn Thị Phương Anh
Chương 3: Ứng dụng và báo
cáo
MỤC LỤC
1
Chương 1. Đại cương về tổ hợp …………………………………………………3
1.1. Bài toán tổ hợp…………………………………… ……………………….3
1.2. Các cấu hình tổ hợp cơ bản…………………………………………………4
1.3. Các cấu hình tổ hợp mở rộng………………………… ………………… 4
Chương 2. Nguyên lý bù trừ tổng quát……………………….…………………6
2.1. Nguyên lý bù trừ……………………………………… ………………… 6
2.2. Phân hoạch tập hợp, số sterling loại 2 và số bell………….……………… 6
2.3. Tổ hợp lặp tổng quát…………………………… …… …………………7
2.4. Nguyên lý bù trừ tổng quát……………………… ……………………… 7
Chương 3. Ứng dụng của nguyên lý bù trừ……………….…………………….9
3.1. Bài toán đếm số sinh viên…………… ……… …………………………10
3.2. Bài toán đếm số nghiệm nguyên không âm nhỏ hơn một số của một phương
trình………………………….…………………………………………….13
3.2.1. Bài toán 1……………… ………………….…………………………… 13

được mô tả bằng các quy tắc sắp xếp và A
1
, A
2
, …, A
n
là các điều
kiện ràng buộc lên mỗi sắp xếp theo sơ đồ S. Khi đó mỗi cách sắp xếp các phần tử
của A
1
, A
2
, …, A
n
thỏa mãn các điều kiện R
1
, R
2
, …, R
m
gọi là một cấu hình tổ
hợp trên các tập A
1
, A
2
, …, A
n
.
Trong tổ hợp người ta thường gặp 4 dạng bài toán sau:
Bài toán tồn tại

1.3. Các cấu hình tổ hợp mở rộng
1.3.1. Hoán vị lặp
Định nghĩa 1.6. Hoán vị lặp là hoán vị mà trong đó mỗi phần tử được ấn
định một số lần lặp lại cho trước.
Định lý 1.5. Số hoán vị lặp của k phần tử khác nhau, trong đó phần tử thứ nhất lặp
n
1
lần, phần tử thứ 2 lặp n
2
lần, …, phần tử thứ k lặp n
k
lần là
!! !
!
), ,,(
21
21
k
k
nnn
n
nnnP =
với n = n
1
+ n
2
+… +n
k
4
Định lý 1.6. Số cách phân phối n đồ vật khác nhau vào k hộp khác nhau sao cho

2
,…,n
k
thoả n
1
+ n
2
+… +n
k
= r. Số các phân hoạch
thứ tự tổ hợp chập r của X dạng {S
1
, S
2
,…,S
k
}có |S
1
| = n
1
, |S
2
| = n
2
,…, |S
k
| = n
k

được ký hiệu là C(n, n

p
k
= n. Một hệ thống các
tập con của X gồm p
1
tập có n
1
phần tử, p
2
tập có n
2
phần tử, …, p
k
tập có n
k
phần
tử gọi là phân hoạch không thứ tự của X.
Định lý 1.9. Số phân hoạch không thứ tự của X với p
1
tập có n
1
phần tử, p
2
tập có
n
2
phần tử, …, p
k
tập có n
k

,…,n
k
) số n
1
lặp lại p
1
lần, số n
2
lặp lại p
2
lần, …,
số n
k
lặp lại p
k
lần).
5
CHƯƠNG 2
NGUYÊN LÝ BÙ TRỪ TỔNG QUÁT
2.1. Nguyên lý bù trừ
Đơn giản
Cho hai tập A,B. Có |A∪B|=|A|+|B|-|A∩B| (Công thức 1)
Cho ba tập A,B,C.
Có |A∪B∪C| = |A|+|B|+|C| -|A∩B|-|A∩C|-|B∩C| +|A∩B∩C|
Định lý 2.1. (Nguyên lý bù trừ) Cho X
1
, X
2
,…, X
n

niii
iii
k
k
XXX
1
21
21
| |
(Công thức 2)
Trong tổng X(n,k), bộ (i
1
,i
2
,…,i
k
) 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.
Hệ quả 2.1. (Công thức Sieve)
∑
=
−=∩∩∩
n
k
k
n
knXXXX
0
21
),()1(| |

, B
2
, …, B
k
ta thấy một phân bố
như vậy sẽ sinh k! toàn ánh từ tập X vào tập { B
1
, B
2
, …, B
k
}.
Suy ra
∑
=
−−=
k
r
nr
rkrkCknSk
0
)).(,()1(),(!
nên
∑
=
−−=
k
r
nr
rkrkC

tử thứ i lặp lại không quá k
i
lần (i=1,2,…,n) với k
1
+ k
2
+ …+k
n
≥ k là
( )
( )
∑ ∑
= ≤<<≤








−+++−+−−+−+=
n
m nii
ii
m
n
k
n
m

k
iii
aaa , ,,
21
và n(
k
iii
aaa , ,,
21
)=|
k
iii
X
, ,,
21
|
Tiếp theo, ký hiệu s
0
= |X|, s
k
=
mkaaan
miii
iii
k
k
, ,2,1,), ,,(
1
21
21

aaa , ,,
21
, xét tập
k
iii
X
, ,,
21
.
Trên tập
k
iii
X
, ,,
21
ta có (m – k) tính chất α
j
, j ϵ J = {1,2,…,m}\{i
1
, i
2
, …, i
k
}
7
Kí hiệu
k
iii
e
, ,,

iii
X
, ,,
21
| x thỏa tính chất α
j
},
∀
j ϵ J
Theo công thức
∑
=
−=∩∩∩
n
k
k
n
knXXXX
0
21
),()1(

Trong đó: X(n,0) = |X|
Và
nkXXXknX
nii
ikii
k
, ,1 ),(
1

Jj
j
km
Jjj
jj
Jj
jiii
Jj
jiii
aan
aanann
YYYYXYe
−
−
⊂∈
∈
−
⊂∈
∈
−+−
+−=
−+−∩+−==
∑∑
∑∑
αα
ααααααααα

Suy ra

{ }

1
2
1
, ,,
1
11
1 21
211
1
1
1
1
1
21
−−+−+++−=
−+−
+−==
−
++
≤<<≤
−
≤<<≤ ⊂≤<<≤ ∈≤<<≤≤<<≤
∑
∑ ∑∑ ∑∑∑
−
αα
ααααααααα
Định lý 2.3. f
k
= s

= s
k
– C(k+1,1).s
k+1
+ C(k+2,2).s
k+2
- … + (-1)
m-k
C(m,m-
k).s
m
+ s
k+1
- C(k+1,1).s
k+2
+ C(k+2,2).s
k+3
- … + (-1)
m-k-1
C(m-1,m-k-1).s
m
= s
k
– C(k,1).s
k+1
+ C(k+1,2).s
k+2
- … + (-1)
m-k
C(m-1,m-k).s

i
n
i
i
XXXXXX
1111 ====
−=⇒+=

nên

n
i
i
n
nji
ji
n
i
i
n
i
i
n
i
i
n
i
i
XXXXXXXXX
1

a. Hãy tính số sinh viên của khóa học
b. Tính số sinh viên chỉ học đúng 1, 2, 3 ngoại ngữ
c. Tính số sinh viên học ít nhất 1, 2, 3 ngoại ngữ
Giải
Gọi N là tổng số sinh viên của khóa học
Khi đó, |X| = N
Kí hiệu: X
A
là số sinh viên học A,
X
B
là số sinh viên học B,
X
C
là số sinh viên học C,
X
D
là số sinh viên học D
Ta có tập X có 4 tập con X
A
, X
B
, X
C
, X
D
Trong đó, theo đề ta có
|X
A
| = 12 ; |X

|
= 3
| X
A
∩ X
B
∩X
C
| = 3; | X
A
∩ X
B
∩X
D
| = 2 ; | X
B
∩ X
C
∩X
D
| = 2 ; | X
A
∩ X
C
∩X
D
| = 3
| X
A
∩ X

∪X
C
∪X
D
|
=> |X| = | ͞X
A
∩ ͞͞X
B
∩ ͞X
C
∩ ͞X
D
| + | X
A
∪ X
B
∪X
C
∪X
D
| = 71 + | X
A
∪ X
B
∪X
C
∪X
D
|(*)

= X(4,1) - X(4,2) + X(4,3) - X(4,4)
= s
1
– s
2
+ s
3
– s
4
(*) => |X| = 71 + s
1
– s
2
+ s
3
– s
4
Mà
s
1
= X(4,1) = |X
A
| + |X
B
| + |X
C
| + |X
D
| = 12 + 20 + 20 + 8 = 60
s

A
∩ X
B
∩X
C
|+ | X
A
∩ X
B
∩X
D
| + | X
B
∩ X
C
∩X
D
| + | X
A
∩
X
C
∩X
D
|
= 3 + 2 + 2 + 3 = 10
s
4
= X(4,4) = | X
A

m
• Số sinh viên chỉ học đúng 1 ngoại ngữ k= 1
e
1
= s
1
– C(1+1,1).s
1+1
+ C(1+2,2).s
1+2
– C(1+3,3).s
1+3
= s
1
– C(2,1).s
2
+ C(3,2).s
3
– C(4,3).s
4
= 60 – C(2,1).39 + C(3,2).10 – C(4,3).2
= 4
• Số sinh viên chỉ học đúng 2 ngoại ngữ k= 2
11
e
2
= s
2
– C(2+1,1).s
2+1

k
= s
k
– C(k,1).s
k+1
+ C(k+1,2).s
k+2
- … + (-1)
m-k
C(m-1,m-k).s
m
• Số sinh viên học ít nhất 1ngoại ngữ k=1
f
1
= s
1
– C(1,1).s
1+1
+ C(1+1,2).s
1+2
– C(1+2,3).s
1+3
= s
1
– C(1,1).s
2
+ C(2,2).s
3
– C(3,3).s
4

3
– C(3,1).s
4

= 10 – C(3,1).2
= 4
3.2. Bài toán đếm số nghiệm nguyên không âm nhỏ hơn một số của một
phương trình
12
3.2.1. Bài toán 1: Phương trình x
1
+ x
2
+x
3
=11 có bao nhiêu nghiệm nguyên
không âm thoả mãn x
1
≤ 3, x
2
≤ 4, x
3
≤ 6?
Giải.
Gọi A, A
1
, A
2
và A
3

3
| = CR(3,4) = C(6,2) = 15,
|A
1
∩A
2
| = CR(3,2) = C(4,2) = 6,
|A
1
∩A
3
| = CR(3,0) = C(2,2) = 1,
|A
2
∩A
3
| = 0
|A
1
∩A
2
∩A
3
| = 0
Vậy, theo nguyên lý bù trừ, số nghiệm nguyên không âm của phương trình
trên sao cho | ͞A
1
∩ ͞͞A
2
∩ ͞A

A(3,2) + (-1)
3-1
A(3,3)
= A(3,1) - A(3,2) + A(3,3)
= s
1
– s
2
+ s
3

Mà
13
s
1
= A(3,1) = |A
1
| + |A
2
| + |A
3
| = 36 + 28 + 15 = 79
s
2
= A(3,2) = |A
1
∩A
2
| + |A
1

| = |A| - (s
1
– s
2
+ s
3
)
= 78 – (79 – 7 + 0 )
= 6
3.2.1. Bài toán 2: Cho phương trình x
1
+ x
2
+ x
3
+ x
4
= 29 có bao nhiêu nghiệm
nguyên không âm thoả mãn x
1
< 4, x
2
< 13, x
3
< 6, x
4
< 11?
Giải.
Gọi A là tập tất cả các nghiệm nguyên không âm của phương trình
A

i
phần tử loại i với i =
1,2,3,4 trong đó có ít nhất 4 phần tử loại một.
Vì thế, đầu tiên chọn 4 phần tử loại một rồi chọn thêm 25 phần tử nữa nên
|A
1
| = CR(4,25) = C(25+4-1,4-1) = C(28,3) = 3276.
Tương tự, ta có |A
2
| = CR(4,16)= C(19,3) = 969,
|A
3
| = CR(4,23) = C(26,3)= 2600,
|A
4
| = CR(4,18) = C(21,3)=1330
14
Mặt khác, x
1
+ x
2
≥ 4 + 13 = 17 có nghĩa chọn 17 phần tử loại một và hai, chọn
thêm 29 – 17 = 12 phần tử nữa nên ta có |A
1
∩A
2
| = CR(4,12)= C(15,3)= 455
Tương tự ta có |A
1
∩A

1
∩A
2
∩A
4
| = CR(4,1)= C(4,3)= 4, |A
2
∩A
3
∩A
4
| =0,
| A
1
∩ A
3
∩A
4
|= CR(4,8)=C(11,3) = 165,
|A
1
∩A
2
∩A
3
∩A
4
| = 0
Vậy, theo nguyên lý bù trừ, số nghiệm nguyên không âm của phương trình trên
sao cho | ͞A

1
1
),4()1(
k
k
kA
= (-1)
1-1
A(4,1) + (-1)
2-1
A(4,2) + (-1)
3-1
A(4,3) + (-1)
4-1
A(4,4)
= A(4,1) - A(4,2) + A(4,3) - A(4,4)
= s
1
– s
2
+ s
3
– s
4
Mà
s
1
= A(4,1) = |A
1
| + |A

∩A
4
|
= 455 + 1540 + 680 + 286 + 56 + 455 = 3472
s
3
= A(4,3) = | A
1
∩ A
2
∩A
3
| + | A
1
∩ A
2
∩A
4
| + | A
2
∩ A
3
∩A
4
| + | A
1
∩ A
3
∩A
4

4
| = |A| - (s
1
– s
2
+ s
3
– s
4
)
15
= 4960 – (8175 – 3472 + 253 – 0)
= 4
3.3. Ứng dụng nguyên lý bừ trừ tổng quát để tính hàm trọng lượng
Định nghĩa 3.2. Một hàm ω từ một tập X vào tập số thực được gọi là hàm trọng
lượng của X. Nếu X là hữu hạn và A là một tập con của X thì trọng lượng của A, kí
hiệu là ω(A), là tổng tất cả ω(x) với x ϵ A.
Nếu ∏ là tập có m tính chất, A
j
với j = 0,1,…,m là tập tất cả các phần tử trong X
thỏa mãn đúng j tính chất và B
j
với j=1,2,…,m là tập tất cả các phần tử trong X
thỏa mãn ít nhất j tính chất. Với mỗi j, đặt E
j
= ω(A
j
) và F
j
= ω(B

m
Định lý 3.3. Với mọi j=1,…,m
ta có F
j
= Sj – C(j,1).S
j+1
+ C(j+1,1).S
j+2
-…+ (-1)
m-j
C(m-1,m-j).S
m

16
KẾT LUẬN
Từ các ứng dụng của nguyên lý bù trừ ta có thể giải lớp các bài
toán. Bằng cách thay đổi các tập hợp, số lượng các phần tử của tập hợp và quan hệ
giữa các phần tử ta có thể tạo ra nhiều bài toán khác nhau mà việc giải chúng giúp
cho ta có thể củng cố và rèn luyện việc sử dụng linh hoạt các cấu hình tổ hợp cơ
bản và mở rộng.
17
TÀI LIỆU THAM KHẢO
• Tiếng Việt
[1] Trần Quốc Chiến (2005), Giáo trình lý thuyết tổ hợp. (Giáo trình cho
học viên cao học Toán, ĐHĐN.)
[2] Hà Văn Chương (2004), Tuyển chọn 351 bài toán giải tích tổ hợp,
NXB Đại học quốc gia TP Hồ Chí Minh.
[3] Vũ Đình Hoà (2003), Lý thuyết tổ hợp và các bài toán ứng dụng, NXB
Giáo dục.
[4] Nguyễn Ngọc Thu (2003), Hướng dẫn giải toán tổ hợp, NXB Đại học