Tên đề tài: NGUYÊN LÝ BÙ TRỪ VÀ ỨNG DỤNG
Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP
Khoá: 2005-2008
Người thực hiện: Trần Thu Hà
Người hướng dẫn: PGS.TSKH Trần Quốc Chiến

Lý do chọn đề tài:
Tư duy tổ hợp ra đời rất sớm. 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ỷ 17
Các bài toán tổ hợp có đặc trưng bùng nổ với số cấu hình tổ hợp khổng lồ. Từ khi máy tính phát
triển và thịnh hành, nhiều vấn đề tổ hợp đã được giải quyết trên máy tính và tổ hợp đã trở thành lĩnh
vực toán ứng dụng với sự phát triển mạnh mẽ.
Tư duy giải toán tổ hợp của học sinh còn yếu.
Trong hơn chục năm trở lại đây, bài toán tổ hợp thường xuyên có mặt trong các đề thi vào các
trường Đại học, Cao đẳng và Trung học chuyên nghiệp. Năm học 2005-2006, Vụ Trung học phổ
thông đã thống nhất 11 chuyên đề bồi dưỡng học sinh giỏi trong đó chuyên đề 11 là chuyên đề về tổ
hợp.
Trong lý thuyết tổ hợp, nguyên lý bù trừ là phương pháp đếm nâng cao giải các bài toán đếm,
nó có nhiều ứng dụng hay và từ các ứng dụng này ta có thể giải được lớp các bài toán tương tự mà
việc giải chúng giúp 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 – là điểm yếu của rất nhiều học sinh.
Chính vì các lý do trên, tôi chọn: Nguyên lý bù trừ và ứng dụng làm đề tài luận văn thạc sĩ
của mình.

Mục đích nghiên cứu
•
Từ các ứng dụng của nguyên lý bù trừ giải lớp các bài toán tương tự cụ thể.
Đối tượng và phạm vi nghiên cứu
•
Đối tượng nghiên cứu là nguyên lý bù trừ.

A
2
A
n
A
S
1
A
2
A
n
A
S
1
R
2
R
m
R
1
A
2
A
n
A
1
R
2
R
m

i
x
n
!n
n
n
))...(1(!)!( knnnkn
++=+
k
k
n
k
nnn ....
21
1
m
1
x
2
m
2
x
n
m
j
x
njiji ,...,2,1,;
=≠
n
mmm

!
!
),(
kn
n
knA
−
=
!)( nnP
=
( )
knC ,
( )
)!!.(
!
,
knk
n
knC
−
=

1.3.4. Các cấu hình tổ hợp mở rộng
1.3.4.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 lần, phần tử thứ
2 lặp lần, …, phần tử thứ k lặp lần là
với .
Đị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 có vật được đặt

nnnnP
=
k
nnnn +++= ...
21
i
n
ki ,...,2,1
=
!!....!.
!
21 k
nnn
n
),( knCR
)1,1(),(
−+−=
nknCknCR
nr
≤
XS ⊂
r
{ }
k
SSS ,...,,
21
S
nr
=
k

(trong số lặp lại lần, số lặp lại lần, …, số lặp lại lần).
),,...,,;(
)!(!!...!
!
),...,,;(
21
21
21
rnnnnnP
rnnnn
n
nnnnC
k
k
k
−=
−
=
kk
pppnnn ,...,,,,...,,
2121
npnpnpn
kk
=+++ ...
2211
1
p
1
n
2

nnnnnnnC
!!...!!!!
!
!!...!
),...,,...,,...,,,...,;(
21
2211
21
2211
=
),...,,...,,...,,,...,;(
2211 kk
nnnnnnnC
1
n
1
p
2
n
2
p
k
n
k
p