Đề tài nguyên lý bù trừ và ứng dụng 1
MỤC LỤC
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ự phân bố, sắp xếp các phần tử hoặc nhiều tập hợp. 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. Mỗi cách phân bố như
vậy gọi là một cấu hình tổ hợp. Chủ đề này đã được nghiên cứu từ thế kỉ XVII, khi
những vấn đề về tổ hợp được nêu ra trong những công trình nghiên cứu các trò chơi
may rủi, cho đến nay đã được áp dụng trong nhiều lĩnh vực khác nhau như lý thuyết
số, hình học, đại số, xác suất thống kê, quy hoạch thực nghiệm, khoa học máy tính,
hóa học,…
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ở
GVHD: PGS.TSKH Trần Quốc Chiến Nhóm thực hiện: Nhóm 5
Đề tài nguyên lý bù trừ và ứng dụng 2
thành ngành toán học phát triển mạnh mẽ, cho đến nay đã được áp dụng trong nhiều
lĩnh vực khác nhau như lý thuyết số, hình học, đại số, xác suất thống kê, quy hoạch
thực nghiệm, khoa học máy tính, hóa học,…
Các bài toán tổ hợp thường được phân thành các dạng sau: bài toán tồn tại,
bài toán đếm, bài toán liệt kê và bài toán tối ưu. 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.
Trong bài toán đếm, 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ả hai 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 hai lần. Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm

nhà triết học Kxenokrat đã biết cách tính số các từ khác nhau lập từ bảng chữ cái
cho trước. Nhà toán học Pitagor và học trò đã tìm ra được nhiều số có tính chất đặc
biệt. Chẳng hạn 36 không những là tổng 4 số chẵn và 4 số lẻ đầu tiên, mà còn là
tổng lập phương của 3 số tự nhiên đầu tiên.
Từ định lý Pitagor người ta cũng đã tìm ra những số mà bình phương của nó
bằng tổng bình phương của hai số khác. Các bài toán như vậy đòi hỏi phải có nghệ
thuật tổ hợp nhất định. Tuy nhiên có thể nói rằng, lý thuyết tổ hợp đã được hình
thành như một ngành toán học mới vào thế kỷ XVII bằng một loạt công trình nghiên
cứu của các nhà toán học xuất sắc như Pascal, Euler, Leibnitz,
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 cả 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ương trình vi phân,…phát triển như vũ bão, thì dường như nó nằm
GVHD: PGS.TSKH Trần Quốc Chiến Nhóm thực hiện: Nhóm 5
Đề tài nguyên lý bù trừ và ứng dụng 4
ngoài sự phát triển và ứng dụng của toán học. Tình thế thay đổi 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ừ việc nghiên cứu các trò chơi, tổ hợp trở thành một ngành toán học
phát triển mạnh mẽ với một số bài toán tổ hợp nổi tiếng trong lịch sử như: bài toán
tháp Hà Nội, bài toán xếp n cặp vợ chồng, bài toán đường đi quân ngựa trên bàn cờ,
hình vuông la tinh, hình lục giác thần bí.
1.2. BÀI TOÁN TỔ HỢP
Qua các bài toán trên ta thấy bài toán tổ hợp rất đa dạng, liên quan đến nhiều
lĩnh vực khoa học và đời sống khác nhau.
Có thể nói một cách tổng quát rằng lý thuyết tổ hợp nghiên cứu sự phân bố,
sắp xếp các phần tử hoặc nhiều tập hợp, thỏa mãn một số điều kiện nào đó.
Một cách phân bố, sắp xếp như thế gọi là một cấu hình tổ hợp.
1.2.1. Cấu hình tổ hợp
Cho các tập A
1

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.
• Ví dụ . Xét sự bố trí các quân cờ trên bàn cờ vua. Mỗi thế cờ có thể coi là một cấu
hình tổ hợp. Ở đây ta có thể định nghĩa
A là tập hợp các quân cờ trắng
B là tập hợp các quân cờ đen
S là sơ đồ sắp xếp các quân cờ trên bàn cờ
R là hệ thống các điều kiện được xác định bằng luật cờ vua.
• Ví dụ .Bài toán tháp Hà Nội
A là tập hợp n đĩa
S là sơ đồ sắp xếp các đĩa trên 3 cọc
R
1
là điều kiện mỗi lần chuyển 1 đĩa từ một cọc sang cọc khác
GVHD: PGS.TSKH Trần Quốc Chiến Nhóm thực hiện: Nhóm 5
Đề tài nguyên lý bù trừ và ứng dụng 5
R
2
là điều kiện đĩa nằm dưới lớn hơn đĩa nằm trên
Cấu hình tổ hợp là một cách sắp xếp các đĩa trên 3 cọc thỏa mãn các điều
kiện R
1
, R
2

2
,x
3
, ,x
n
}.
GVHD: PGS.TSKH Trần Quốc Chiến Nhóm thực hiện: Nhóm 5
Đề tài nguyên lý bù trừ và ứng dụng 6
Giải. Một tập con của S có thể được xây dựng trong n bước kế tiếp như sau: Nhặt
hoặc không nhặt x
1
, nhặt hoặc không nhặt x
2
,…, nhặt hoặc không nhặt x
n
. Mỗi bước
được thực hiện nhiều nhất là 2 cách. Như vậy số tập con là
2.2.2… 2=2
n
Bài toán liệt kê
Các bài toán này nghiên cứu những thuật toán hiệu quả để xây dựng tất cả
các cấu hình tổ hợp đã cho. Nhiều vấn đề trong các lĩnh vực khác nhau thường được
đưa về bài toán liệt kê và kiểm tra xem các cấu hình tổ hợp có thỏa mãn tính chất
cho trước hay không.
• Ví dụ . Liệt kê tất cả các hoán vị của n phần tử.
Bài toán tối ưu tổ hợp
Trong nhiều vấn đề, mỗi cấu hình tổ hợp được gán một giá trị bằng số( chẳng
hạn như hiệu quả sử dụng, hay chi phí thực hiện). Khi đó bài toán tối ưu tổ hợp
nghiên cứu những thuật toán tìm cấu hình tổ hợp có giá trị tối ưu ( lớn nhất hoặc nhỏ
nhất).

2
…. n
k
1.3.2.2. Nguyên lý cộng
Nếu có m
1
cách chọn đối tượng x
1
, m
2
cách chọn đối tượng x
2
, …, m
n
cách
chọn đối tượng x
n
và nếu cách chọn x
i
không trùng với bất kỳ cách chọn x
j
nào (i
≠
j,
i, j = 1, ,n) thì có m
1
+ m
2
+… + m
n

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.3.3.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.3.4. Cấu hình tổ hợp mở rộng
1.3.4.1. 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; n
1

n
n n n
GVHD: PGS.TSKH Trần Quốc Chiến Nhóm thực hiện: Nhóm 5
Đề tài nguyên lý bù trừ và ứng dụng 9
1.3.4.2. 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)
1.3.4.3. Phân hoạch thứ tự tổ hợp
Định nghĩa: Cho X là tập n phần tử khác nhau,
nr ≤
và S
⊂
X có r phần tử.
Một phân hoạch {S
1
, S
2
,…, S
n
} có thứ tự của S gọi là một phân hoạch thứ tự tổ
hợp chập r của X. Nếu r = n, thì ta gọi là phân hoạch thứ tự của X.
Cho các số nguyên dương n
1
, n
2
, …, n
k

k
). Một cấu hình tổ hợp kiểu này được xây
dựng qua các bước như sau
Bước 1: chọn n
1
phần tử X cho S
1
, có C(n,n
1
) khả năng
Bước 2: chọn n
2
phần tử X \ S
1
cho S
2
, có C(n-n
1
,n
2
) khả năng

Bước k: chọn n
k
phần tử
) (\
121 −
∪∪∪
k
SSSX

), ,,;(
21
21
21
rnnnnnP
rnnnn
n
nnnnC
k
k
k
−=
−
=
), ,,;(
21 k
nnnnC
được gọi là hệ số đa thức.
GVHD: PGS.TSKH Trần Quốc Chiến Nhóm thực hiện: Nhóm 5
Đề tài nguyên lý bù trừ và ứng dụng 10
1.3.4.4. Phân hoạch không thứ tự
Định nghĩa: Cho X là tập n phần tử khác nhau, các số nguyên dương n
1
, n
2
,
…, n
k
và p
1

lượng n
2
, …, p
k
tập lực lượng n
k
là
k
p
kk
pp
k
kk
npnpnp
n
ppp
nnnnnnnC
)!(! )!(!)!(!
!
!! !
), ,, ,, ,,, ,;(
21
2211
21
2211
=
(trong tử số
), ,, ,, ,,, ,;(
2211 kk
nnnnnnnC

2
, … , X
n
, ta có:
n
XXX ∪∪∪
21
=
),()1(
1
1
knX
k
n
k
−
=
∑
−
Trong đó:
∑
≤<<≤
∩∩∩=
nii
iii
k
k
xxxknX
1
1

XXX ∪∪∪
21
=
−X
n
XXX ∪∪∪
21
Ta nhận được công thức sau:
Công thức 3 (Sieve):
),()1(
0
2
1
knXXXX
n
k
k
n
∑
=
−=∩∩∩
Trong đó:
XnX =)0,(
∑
≤<<≤
∩∩∩=
nii
iii
k
k

k
X

là:
k
X
=
{
xXx∈
không thỏa mãn
}
k
α
Ký hiệu N là số cần đếm, theo công thức 3 ta có:

21
=∩∩∩=
n
XXXN
+X
knX
n
k
k
,()1(
1
∑
=
−
)

i) Gọi X là tập hợp tất cả các cách bỏ thư. Ta có
!nX =
. Gọi
k
α
(k là tính chất
lá thư k gửi đúng địa chỉ, X
k
là tập hợp cách bỏ thư sao cho lá thư k không gửi đúng
địa chỉ (k = 1,….,n). Ký hiệu N(n,r) là só cách bỏ thư sao cho có đúng r lá thư đúng
địa chỉ (r = 0, 1, …., n). Như vậy theo nguyên lý bù trừ số cách bỏ thư sao cho
không có lá thư nào gửi đúng địa chỉ là.
GVHD: PGS.TSKH Trần Quốc Chiến Nhóm thực hiện: Nhóm 5
Đề tài nguyên lý bù trừ và ứng dụng 13
∑
−= ),()1()0,( knXnN
k
Trong đó

( ,0) !N n X n= =

∑
≤<<≤
∩∩∩=
nii
iii
kk
k
XXXknX
1


−++−+−
!
1
)1(
!3
1
!2
1
!1
1
1!
n
n
n
Như vậy xác suất cần tìm là:






−++−+−
!
1
)1(
!3
1
!2
1








−
−+++−=








−
−+++−−=−=
−
−
)!(
1
)1(
!2
1
!1
1
1
!

1
)1(
!3
1
!2
1
!1
1
1
!
1
rnr
rn

3.1.2. Bài toán xếp n cặp vợ chồng (Lucas)
Một bàn tròn 2n ghế. Cần sắp n cặp vợ chồng sao cho đàn ông ngồi xen kẽ
với đàn bà và không có cặp nào ngồi cạnh nhau (có tính đến vị trí ghế và thứ tự chỗ
ngồi). Hỏi có bao nhiêu cách xếp ?
Giải:
Gọi số phải tìm là M
n
. Xếp các bà trước (cứ một ghế xếp thì dể một ghế trống
dành cho các ông). Với n ghế chẵn ta có n! cách xếp và với n ghế lẻ ta cũng có n!
cách xếp. Như vậy số cách xếp các bà là 2.n !. Gọi số cách xếp các ông ứng với một
cách xếp các bà là U
n
, ta có:
M
n
= 2.n ! U

là tính chất Q
i
. Tiếp theo ký hiệu X
i
là các số hoán vị của trong X
thỏa mãn tính chất P
i
, i = 1,…, 2n.
Như vậy theo nguyên lý bù trừ số cách xếp chỗ là:
),2()1(
2
0
knXU
k
n
k
n
∑
=
−=
Trong đó

(2 ,0) !X n X n= =
Và
X(2n,k) =
∑
≤<<≤
∩∩∩
nii
iii


nkknX >∀= 0),2(
Và kéo theo:
),2()1(
0
knXU
k
n
k
n
∑
=
−=
Gọi g(2n,k) là số cách lấy ra k tính chất thỏa mãn không thể xảy ra đồng thời
P
i
và Q
i
hoặc đồng thời P
i+1
và Q
i
(g(2n,0) = 1). Và với mỗi cách lấy k tính chất như
vậy ta có (n-k)! cách phân bố các tính chất còn lại. Như vậy ta có:

)!).(,2()1(
0
knkngU
k
n

= -
-
Như vậy số phân bố là:
)!).(,2(.
2
2
)1(
0
knkknC
kn
n
U
k
n
k
n
−−
−
−=
∑
=
3.1.3. Bài toán đếm số toàn ánh
Cho hai tập X, Y có
nX =
,
knkY ≥= ,
. Hãy đếm số toàn ánh từ X vào Y.
Giải:
Cho Y = {y
1

X k S k= =
Và
krSSSrkX
kii
iii
r
r
, ,1 ),(
1
1
21
=∀∩∩∩=
∑
≤<<≤
GVHD: PGS.TSKH Trần Quốc Chiến Nhóm thực hiện: Nhóm 5
Đề tài nguyên lý bù trừ và ứng dụng 17
Do
r
iii
SSS ∩∩∩
21
là tập hợp các ánh xạ từ X vào Y \{y
1
,…, y
r
}, nên
n
i
i
i

A
là tập các học sinh đăng kí học môn Tin học,
B
là tập các học sinh
đăng kí học môn Ngoại ngữ. Khi đó, tổng số học sinh của lớp 10A là
BA∪
và số
học sinh đăng kí học cả hai môn Tin học và Ngoại ngữ là
BA∩
. Vì vậy:
BA∪
=
A
+
B
-
BA∩
30 20 40 10A B A B A B⇒ ∩ = + − ∪ = + − =
Vậy có 10 học sinh đăng kí học cả hai môn Tin học và Ngoại ngữ.
Ví dụ 2: Đề thi học sinh giỏi toán của một trường phổ thông gồm 3 bài: hình
học, đại số và tổ hợp. Có 100 em tham gia dự thi. Kết quả cho thấy có 80 em giải
được bài hình học, 70 em giải được bài đại số, 50 em giải được bài tổ hợp, 60 em
giải được bài hình học và đại số, 50 em giải được bài hình học và tổ hợp, 40 em giải
được bài đại số và tổ hợp, 30 em giải được cả ba bài. Hỏi có bao nhiêu em giải được
ít nhất một bài thi.
Giải :
Gọi A là tập các học sinh giỏi toán của trường .
A
1
là tập các học sinh giải được bài hình học.

là tập hợp các số thuộc tập X chia hết cho 4
A
3
là tập hợp các số thuộc tập X chia hết cho 7
Khi đó:
1 2
A A∩
là tập các số thuộc tập X chia hết cho 3 và 4
2 3
A A∩
là tập các số thuộc tập X chia hết cho 4 và 7
1 3
A A∩
là tập các số thuộc tập X chia hết cho 3 và 7
Khi đó:
1 2 3
A A A∪ ∪
là số phần tử thuộc tập X chia hết cho 3, hoặc 4 hoặc 7.
Vậy số phần tử thuộc tập X không chia hết cho bất kỳ số nào trong các số 3;4;7 là:
( )
1
1 2 3 1 2 3 2 3
\A A A A A A A A A A∪ ∪ = ∪ ∪ = ∩ ∩
.
Ta có:
1 2 3
10000 10000 10000
3333, 2500, 1428
3 4 7
A A A

= 10000 - ( 3333 + 2500 +1428 ) + 833 + 476 + 357 - 119 = 4286
Vậy số phần tử thuộc tập X không chia hết cho bất kỳ số nào trong các số 3;4;7 là
4286
Ví dụ 4 : Một cuộc hội thao cấp Tỉnh có 4 môn thi gồm : cầu lông, bóng bàn,
chạy và cờ tướng. Đoàn A có 100 người bao gồm vận động viên và cổ động viên
tham gia trong đó: môn cầu lông có 18 vận động viên, môn bóng bàn có 26 vận
động viên, môn chạy có 19 vận động viên, môn cờ tướng có 24 vận động viên, có 5
người tham gia cả cầu lông và bóng bàn, 2 người tham gia cả cầu lông và chạy, 3
người tham gia cả cầu lông và cờ tướng, 5 người tham gia cả bóng bàn và chạy,4
người tham gia cả bóng bàn và cờ tướng, 3 người tham gia cả cờ tướng và chạy, 2
người tham gia cả cầu lông, chạy và cờ tướng, 4 người tham gia cả bóng bàn, chạy
và cờ tướng, 1 người tham gia cả bốn môn. Hỏi đoàn A có bao nhiêu người chỉ là cổ
động viên.
Giải :
Gọi A là tập các vận động viên và cổ động viên tham gia hội thao.
A
1
là tập các vận động viên cầu lông.
A
2
là tập các vận động viên bóng bàn.
A
3
là tập các vận động viên chạy.
A
4
là tập các vận động viên cờ tướng.
Khi đó:
1 2 3 4
A A A A∪ ∪ ∪

là tập nghiệm nguyên không âm của phương trình với x ≥ 4,
A
2
là tập nghiệm nguyên không âm của phương trình với y ≥ 5,
A
3
là tập nghiệm nguyên không âm của phương trình với z ≥ 7,
Vậy số nghiệm cần tìm là
( )
1
2 3 1 2 34 1 2 3
\A A A A A A A A A A∩ ∩ = ∪ ∪ = ∪ ∪
1
2 3
A A A∩ ∩
=
A
-|A
1
|-|A
2
|-|A
3
| + |A
1
∩A
2
| +|A
1
∩A

∩A
3
|=7
|A
1
∩A
2
∩A
3
| = 0. Vậy
1
2 3
A A A∩ ∩
= 6
GVHD: PGS.TSKH Trần Quốc Chiến Nhóm thực hiện: Nhóm 5
Đề tài nguyên lý bù trừ và ứng dụng 21
KẾT LUẬN
Nguyên lý bù trừ là đề tài rất hay, nó khơi dậy khả năng toán học cho người
học, đồng thời nó cũng kích thích được óc sáng tạo và tư duy định hướng cho người
học.
Nguyên lý này đã cuốn hút được sự quan tâm của nhiều người bởi tính đa
dạng và sự ứng dụng của nó. Do vậy, việc học tập, nghiên cứu chủ đề này là rất bổ
ích vì nó có thể giải quyết được nhiều vấn đề nảy sinh từ thực tế cuộc sống.
Trong đề tài này, mặt dù nhóm chúng tôi đã dành nhiều thời gian nghiên cứu,
thảo luận, và được sự hướng dẫn chu đáo của Thầy PGS.TSKH.Trần Quốc Chiến
nhưng do khả năng có hạn nên chắc chắn đề tài không tránh khỏi thiếu sót. Kính
mong Thầy và các anh chị trong lớp góp ý, bổ sung, chỉnh sửa để đề tài được hoàn
thiện hơn.
Thay mặt nhóm, tôi xin chân thành cảm ơn sự giúp đỡ và hướng dẫn nhiệt
tình, tận tụy của Thầy PGS.TSKH.Trần Quốc Chiến, cũng như sự động viên, khích