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

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
…
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)!
−
3
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) =

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; n
1
, n
2
, , n
k
) =
1 2
!
! ! !
k
n
n n n
1.2.6. Tổ hợp lặp:
Định nghĩa:
4
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

−
Trong đó: X(n,k)=
∑
≤<<≤
∩∩∩
nii
iii
k
k
xxx
1
1
21

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. Nói riêng ta có
X(n,1) =
1
X
+
2
X
+……+
n

=
−=∩∩∩
Trong đó: X(n,0) =
X
X(n,k)=
∑
≤<<≤
∩∩∩
nii
iii
k
k
XXX
1
1
21nk ,1=∀
Bây giờ: ta cho các tính chất
n
αα
, ,
1
trên tập X. Xét bài toán:
* Bài toán đếm số phần tử trong X không thỏa mãn một tính chất
k
α
nào cả
Giải:

knX
n
k
k
,()1(
1
∑
=
−
)
trong đó X(n,k)=
∑
≤<<≤
∩∩∩
nii
iii
k
k
XXX
1
1
21nk ,1=∀
7
Chương III: MỘT SỐ VÍ DỤ VÀ BÀI TOÁN ỨNG DỤNG
3.1. Các ví dụ :
Ví dụ 1: Lớp 10A có 40 học sinh. Nhà trường bắt buộc mỗi học sinh trong lớp
phải học ít nhất một trong hai môn học tự chọn là Tin học hoặc Ngoại ngữ. Có 30 học

A
1
là tập các học sinh giải được bài hình học.
A
2
là tập các học sinh giải được bài đại số.
A
3
là tập các học sinh giải được bài tổ hợp.
Khi đó:
1 2
A A∩
là tập các học sinh giải được bài hình học và đại số
2 3
A A∩
là tập các học sinh giải được bài đại số và tổ hợp
1 3
A A∩
là tập các học sinh giải được bài hình học tổ hợp
Số học sinh giải được ít nhất một bài thi là :
1 2 3 1 2 3 1 2 2 3 1 3 1 2 3
( )A A A A A A A A A A A A A A A∪ ∪ = + + − ∩ + ∩ + ∩ + ∩ ∩
8
= 80 + 70 + 50 - 60 - 50 - 40 + 30 = 80
Ví dụ 3 : Trong tập hợp X = {1; 2; 3; …;10000} có bao nhiêu số không chia hết
cho bất kỳ số nào trong các số 3;4;7?
Giải :
Gọi A
1
là tập hợp các số thuộc tập X chia hết cho 3.

3 4 7
A A A
     
= = = = = =
     
     
1 2 1 3 2 3
10000 10000 10000
833, 476, 357
3 4 3 7 4 7
A A A A A A
     
∩ = = ∩ = = ∩ = =
     
× × ×
     
1 2 3
10000
119
3 4 7
A A A
 
∩ ∩ = =
 
× ×
 
Áp dụng công thức 3 (Sieve), ta có:
1
2 3 1 2 3 1 2 1 3 2 3 1 2 3
( )A A A A A A A A A A A A A A A A∩ ∩ = − + + + ∩ + ∩ + ∩ − ∩ ∩

( )
1
1 2 3 4 1 2 3 4 2 3 4
\A A A A A A A A A A A A A∪ ∪ ∪ = ∪ ∪ ∪ = ∩ ∩ ∩
là số cổ động viên.
Áp dụng công thức 3 (Sieve):
1
2 3 4 1 2 3 4 1 2 1 3 1 4 2 3
2 4 3 4 1 2 3 1 2 4 1 3 4 2 3 4
1 2 3 4
( )
( )
100 (18 26 19 24) (5 2 3 5 4 3) (2 3 2 4) 1 25
A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A
A A A A
∩ ∩ ∩ = − + + + + ∩ + ∩ + ∩ + ∩
+ ∩ + ∩ − ∩ ∩ + ∩ ∩ + ∩ ∩ + ∩ ∩
+ ∩ ∩ ∩ = − + + + + + + + + + − + + + + =
Vậy đoàn A có 25 người chỉ là cổ động viên.
Ví dụ 5 : Đếm số nghiệm nguyên không âm của phương trình x + y + z = 11, với
0≤ x≤3, 0≤ y≤4, 0≤ z≤6
Giải :
Gọi A là tập tất cả các nghiệm không âm của phương trình.
A
1
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,

3
|-|A
1
∩A
2
∩A
3
|
10
Ta có
A
=C(13,2), |A
1
|+|A
2
|+|A
3
|=79, A
1
∩A
2
| +|A
1
∩A
3
| +|A
2
∩A
3
|=7

gửi đúng địa chỉ là.
∑
−= ),()1()0,( knXnN
k
Trong đó

( ,0) !N n X n= =

∑
≤<<≤
∩∩∩=
nii
iii
kk
k
XXXknX
1
),(
21
nk , ,1=∀
Với mỗi bộ k lá thư i
1
, i
2
, …, i
k
ta có (n-k)! cách bỏ thư, tức hoán vị các lá thư còn
lại, sao cho các lá thư i
1
, i

n
n
11
Như vậy xác suất cần tìm là:






−++−+−
!
1
)1(
!3
1
!2
1
!1
1
1
n
n
Một điều lý thú là xác suất trên tiến đến 1/ e khi n
∞→
.
Số N(n,0) trên cũng chính là tổng số hoán vị f(i) của tập (1, 2, …, n) thỏa mãn f(i)
≠
i . Vì vậy N(n,0) được gọi là số mất thứ tự và được ký hiệu là D
n

−
−
)!(
1
)1(
!2
1
!1
1
1
!
!
)!(
1
)1(
!2
1
!1
1
1)!).(,()0,().,(),(
rnr
n
rn
rnrnCrnNrnCrnN
rn
rn
Suy ra xác suất cần tìm là:




. 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
n
Bây giờ ta đi tính U
n
Đánh số các bà (đã xếp) từ 1 đến n. Đánh số các ông tương ứng với các bà (ông i
là chồng bà i). Đánh số các ghế trống theo nguyên tắc: ghế số i nằm giữa bà i và i + 1
(quy ước n +1 = 1). Mỗ cách xếp các ông được biểu diễn bằng một hoán vị f(i) của tập
12
{1, 2, ……,n} , tức ghế i được xếp cho ông f(i) . Để thỏa mãn yêu cầu bài toán f(i) phải
thỏa mãn

iif ≠)(
&
1)( +≠ iif
(*)
Như vậy số Un là số các hoán vị thỏa mãn (*). Số U
n
gọi là số phân bố.
Xét tập hợp X các hoán vị f của {1, 2, ….,n} . Ta gọi
Pi là tính chất f(i) = i
và Qi là tính chất f(i) = i +1
Ký hiệu P

k
XXX
2 1
1
21nk 2, ,1=∀
Chú ý rằng 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
tức là:
Φ=∩
+ini
XX
&
Φ=∩
++ ini
XX
1

ni , ,1=∀
Như vậy ta có:

nkknX >∀= 0),2(

n
−−=
∑
=
Bây giờ ta còn phải tính g(2n,k). Nếu xếp theo vòng tròn P
1
, Q
1
, P
2
, Q
2
,…., P
n
,
Q
n
ta thấy g(2n,k) chính là số cách lấy ra k phần tử sao cho không có hai phần tử kề nhau.
Đây chính là số cách xếp k số 0 với (2n - k) số 1 sao cho không có hai số 0 kề nhau. Ta
có:

2
(2 , ) (2 , )
2
n
g n k C n k k
n k
= -
-
Như vậy số phân bố:

hợp tất cả toàn ánh từ X vào Y . Hiển nhiên
n
kS =
.
Ký hiệu:
{ }
kiXfySfS
ii
, ,1)(/ =∀∉∈=
Theo nguyên lý bù trừ ta có:
).,()1(
0
rkXT
r
k
r
∑
=
−=
Trong đó:
( ,0)
n
X k S k= =
Và
krSSSrkX
kii
iii
r
r
, ,1 ),(

krSSS
r
iii
, ,1, ,,
21
=∀
Suy ra:
nr
k
r
rkrkCT )).(,()1(
0
−−=
∑
=
15
KẾT LUẬN
Nguyên lý bù trừ và ứng dụng là một phần quan trọng, hấp dẫn và lí thú của lý
thuyết tổ hợp, 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.
Bài toán 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 em đã 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 học
viên 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, em xin chân thành cảm ơn sự giúp đỡ và hướng dẫn nhiệt tình,
tận tuỵ của Thầy PGS.TSKH.Trần Quốc Chiến, cũng như sự động viên, khích lệ của tập
thể lớp để nhóm em hoàn thành tốt đề tài này.