1
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
TRẦN LÊ HẠNH ĐOAN
NGUYÊN LÝ BAO HÀM & LOẠI TRỪ VÀ
ỨNG DỤNG
Chuyên ngành: Phương pháp Toán sơ cấp
Mã số: 60.46.40
TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC
Đà Nẵng - Năm 2011
2
Công trình ñược hoàn thành tại
ĐẠI HỌC ĐÀ NẴNG
Người hướng dẫn khoa học: PGS.TSKH.Trần Quốc
Chiến
Phản biện 1: TS. Cao Văn Nuôi
Phản biện 2: PGS. TS. Trần Đạo Dõng
Luận văn sẽ ñược bảo vệ tại Hội ñồng chấm Luận văn
tốt nghiệp thạc sĩ khoa học tại Đại học Đà Nẵng ngày
29 tháng 05 năm 2011.
Có thể tìm hiểu luận văn tại:
- Trung tâm thông tin - Học liệu, Đại học Đà Nẵng
- Thư viện trường Đại học sư phạm, Đại học Đà
Nẵng.
3
MỞ ĐẦU
1. Lý do chọn ñề tài
Cùng với sự phát triển với tốc ñộ nhanh của công nghệ thông
tin, lý thuyết tổ hợp ñã trở thành lĩnh vực toán học quan trọng và cần
thiết cho nhiều lĩnh vực khoa học và ứng dụng. Nhiều bài toán hiện
nay ñược giải quyết bằng cách quy chúng về các bài toán tổ hợp.
Lý thuyết tổ hợp nghiên cứu việc phân bố, sắp xếp các phần tử
của một hoặc nhiều tập hợp, thoả mãn một số ñiều kiện nào ñó.
Các bài toán tổ hợp rất phong phú và ña dạng: 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. Trong các bài toán
ñó thì bài toán ñếm ñược ứng dụng rộng rãi và ña dạng. Từ các cấu
hình tổ hợp cơ bản người ta hình thành nên hệ thống các cấu hình tổ
hợp mở rộng và nâng cao.
Công thức xác ñịnh số phần tử của hợp một số tập hữu hạn
thường ñược dùng trong nhiều bài toán ñếm. Một trong những công
thức ñó là nguyên lý bao hàm và loại trừ của tập hợp. Sử dụng
nguyên lý này và phối hợp một số phương pháp khác trên tập hợp
chẳng hạn phương pháp ánh xạ, ta có thể giải một số dạng toán.
Trong lý thuyết tổ hợp, nguyên lý bao hàm và loại 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. Trong các kỳ thi học sinh giỏi quốc gia, thi Olympic toán
quốc tế, thi Olympic sinh viên giữa các trường ñại học và cao ñẳng
các bài toán liên quan ñến dạng này hay ñược ñề cập và thường thuộc
loại rất khó.
Chính vì các lý do trên, tôi ñã nghiên cứu và chọn:
“NGUYÊN LÝ BAO HÀM & LOẠI TRỪ VÀ ỨNG DỤNG ” làm
ñề tài luận văn thạc sĩ của mình.
4
2. Mục ñích nghiên cứu
Từ các ứng dụng nguyên lý bao hàm và loại trừ giải lớp các bài
toán tương tự cụ thể.
3. Đối tượng nghiên cứu
Đối tượng nghiên cứu: nguyên lý bao hàm và loại trừ.
Phạm vi nghiên cứu: nội dung của nguyên lý bao hàm và loại
trừ, ứng dụng của nguyên lý này.
4. Phương pháp nghiên cứu
Gián tiếp thông qua các tài liệu: sách, giáo trình, tạp chí toán
học tuổi trẻ, truy cập các trang web.
Trực tiếp thông qua sự hướng dẫn của thầy và việc trao ñổi
thảo luận với các bạn.
5. Ý nghĩa khoa học và thực tiễn
Đề tài góp phần nghiên cứu, hỗ trợ học sinh khi học phần tổ
hợp, giải một số bài toán số học mà việc giải chúng có nhiều ứng
dụng trong trong các lĩnh vực toán học, tin học.
6. Nội dung luận văn
1) Mở ñầu
2) Chương 1. Đại cương về tổ hợp
3) Chương 2. Nguyên lý bao hàm và loại trừ
4) Chương 3. Ứng dụng của nguyên lý bao hàm và loại trừ
5) Kết luận
5
CHƯƠNG 1. ĐẠI CƯƠNG VỀ TỔ HỢP
1.1 Sơ lược lịch sử
1.2 Các quy tắc ñếm cơ bản
1.2.1 Quy tắc tương ứng một – một. Nếu tồn tại tương ứng
một – một giữa các phần tử của các tập hữu hạn A
1
và A
2
, thì A
1
và A
2
có cùng số các phần tử.
Giả sử A
1
, A
2
,...A
n
là các tập hữu hạn bất kỳ. Ta ñịnh nghĩa
tích Đề-các của A
1
, A
2
,...A
n
, kí hiệu là A
1
×
A
2
...
×
A
n
, là tập
bao gồm tất cả các bộ có thứ tự
)
1 2
, , ...,
n
a a a
gồm n thành phần
1 2
, , ...,
n
a a a
sao cho
1 1 2 2
, ,...,
n n
a A a A a A
∈ ∈ ∈
1.2.2 Quy tắc nhân. Nếu A
1
, A
2
,...A
n
là các tập hữu hạn bất
kỳ và A
1
×
A
2
...
×
A
n
là tích Đề các của các tập ñó thì
nn
AAAAAA ......
2121
=×××
1.2.3 Quy tắc cộng. Nếu A
1
, A
2
,...A
n
là các tập hữu hạn ñôi
một rời nhau, tức là
i J
A A
φ
∩ =
nếu
i j
≠
thì
nn
AAAAAA +++=∪−∪∪ ......
2121
Ở ñây
i
A
là lực lượng ( số các phần tử ) của tập A
i
1.3 Cấu hình tổ hợp cơ bản
1.3.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.
6
Nếu ta ký hiệu số chỉnh hợp có lặp chập k của n phần tử của A
bằng AR (n, k) thì
AR (n, k) = n
k
1.3.2 Chỉnh hợp không lặp
•
Định nghĩa. Một chỉnh hợ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. Chỉnh hợp không lặp ñơn
giản gọi là chỉnh hợp.
Kí hiệu số các chỉnh hợp chập k của n phần tử của A là A(n, k)
ta có
( ) ( )
!
!
,
0
n
khi k n
n k
A n k
khi k n
≤
−
=
>
1.3.3 Hoán vị không lặp
•
Đị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 là 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.4 Hoán vị vòng quanh
Số hoán vị vòng quanh của n phần tử khác nhau
(
)
n
Q
ñược
tính bằng công thức
( 1)!
n
Q n
= −
1.3.5 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ử
7
ñã 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.
Nếu ta ký hiệu số tổ hợp chập k của n phần tử của A bằng C(n,
k) thì
( ) ( )
>
≤≤
−
=
nkkhi
nkkhi
knk
n
knC
0
1
!!
!
,
Mỗi tổ hợp chập k của n phần tử của A có thể xem như là 1 tập
con lực lượng k của A. Vì vậy C(n, k) chính bằng số các tập con lực
lượng k của A. Với k = 0, vì chỉ có 1 tập con của A lực lượng 0 là tập
rỗng nên ta có thể ñịnh nghĩa một cách tự nhiên rằng C(n, 0) = 1. Khi
ñó ñẳng thức
!
( , )
!( )!
n
C n k
k n k
=− cũng ñúng cho cả k = 0.
1.4 Cấu hình tổ hợp mở rộng
1.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 một số lần lặp lại cho trước.
Ký hiệu số các hoán vị có lặp của các phần tử
1 2
, , ... ,
n
a a a
với tham số lặp
1 2
, , ...,
n
m m m
là
(
)
1 2
; , , ...,
n
P m m m m
.
•
Định lý 1. Số hoán vị lặp của n phần tử khác nhau, trong ñó
phần tử thứ nhất lặp
1
m
lần, phần tử thứ hai lặp
2
m
lần, ... , phần tử
thứ n lặp
n
m
lần là
P (m; m
1
, m
2
,...m
n
) = m!
m
1
!m
2
!...m
n
!
8
với
1 2
...
n
m m m m
= + + +
.
•
Hệ quả. Giả sử tập S có n phần tử, trong ñó có
1
n
phần tử
kiểu 1,
2
n
phần tử kiểu 2, ... ,
k
n
phần tử kiểu k. Khi ñó số các hoán
vị n phần tử của S là
( )
1 2
1 2
!
; , , . .. ,
! ! . . . !
k
k
n
P n n n n
n n n
=
1.4.2 Tổ hợp lặp
•
Định nghĩa. Tổ hợp lặp chập k từ n phần tử khác nhau 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ể ñược lặp lại.
•
Định lý 2. 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.4.3 Phân hoạch của tập hợp. Số Sterling loại 2 và số Bell
Giả sử A là tập hữu hạn với
A n
=
, còn k là 1 số nguyên
dương. Ta cũng giả sử
1
A A
=
.
S là sơ ñồ sắp xếp “tập
{
}
1 2
, , ... ,
k
X X X
với
1 2
, , ... ,
k
X X X
cũng là các “tập” ñể ta xếp các phần tử của A
1
vào ”,
1
R
là ñiều kiện “mọi phần tử của A
1
ñều ñược sắp xếp vào
một trong các “tập”
1 2
, , ... ,
k
X X X
”,
2
R
là ñiều kiện “với mọi i = 1, ... , k có ít nhất một phần tử của
1
A
ñược xếp vào
i
X
”.
9
Khi ñó, một cấu hình tổ hợp trên
1
A
theo S thỏa mãn các ñiều
kiện
1
R
và
2
R
ñược gọi là một phân hoạch của A thành k khối.
Số tất cả các phân hoạch thành k khối của một tập A lực lượng
n ñược gọi là số Sterling loại 2 và ñược ký hiệu là S(n, k). Dễ thấy
rằng S(n, k) = 0 nếu k > n. Ta cũng quy ước rằng S(n, 0) = 0.
Số
(
( , 1) , 2 ... ( , )
n
T S n S n S n n
= + + +
ñược gọi là số
Bell. Như vậy, số Bell chính là số tất cả các phân hoạch của tập A lực
lượng n.
Việc tính S(n, k) và
n
T
sẽ ñược trình bày trong phần ứng dụng
của nguyên lý bao hàm và loại trừ.
1.4.4 Phân hoạch thứ tự tổ hợp
•
Định nghĩa. Cho X là tập n phần tử khác nhau,
r n
≤
và
S X
⊂
có r phần tử. Một phân hoạch
{
}
1 2
, , ... ,
n
S S S
có thứ tự của
S gọi là 1 phân hoạch thứ tự tổ hợp chập r của X. Nếu r = n, thì gọi là
phân hoạch thứ tự của X.
Cho các số nguyên dương
1 2
, , ... ,
k
n n n
thỏa
1 2
...
k
n n n r
+ + + =
. Số các phân hoạch thứ tự tổ hợp chập r của
X dạng
{
}
1 2
, , ... ,
k
S S S
có
1 1 2 2
, , ... ,
k k
S n S n S n
= = =
ñược
ký hiệu là C
(
)
1 2
; , , ... ,
k
n n n n
.
•
Định lý3.
C
( ) ( )
1 2 1 2
1 2
!
; , , ... , ( ; , , ..., , )
!. !... ! !
k k
k
n
n n n n P n n n n n r
n n n n r
= = −
−
C
)
1 2
; , , ... ,
k
n n n n
ñược gọi là hệ số ña thức.
10
1.4.5 Phân hoạch không thứ tự tổ hợp
•
Định nghĩa. Cho X là tập n phần tử khác nhau, các số
nguyên dương
1 2
, , ... ,
k
n n n
và
1 2
, , ... ,
k
p p p
thỏa
1 1 2 2
...
k k
n p n p n p n
+ + + =
Một hệ thống các tập con của X gồm
1
p
tập lực lượng
1
n
,
2
p
tập lực lượng
2
n
, ... ,
k
p
tập lực lượng
k
n
gọi là phân hoạch không
thứ tự của X.
•
Định lý 4. Số phân hoạch không thứ tự của X với
1
p
tập lực
lượng
1
n
,
2
p
tập lực lượng
2
n
, ... ,
k
p
tập lực lượng
k
n
là
(
)
( ) ( ) ( )
k
p
kk
pp
k
kk
npnpnp
n
ppp
nnnnnnnC
!!...!!!!
!
!!...!
,...,,,...,,...,;
21
2211
21
2211 =
(trong tử số
(
)
1 1 2 2
; , ..., , , ... , , , ... ,
k k
C n n n n n n n
số
1
n
lặp lại
1
p
lần, số
2
n
lặp lại
2
p
lần,..., số
k
n
lặp lại
k
p
lần).
◊
Ví dụ 9
(i) Số cách chia 21 học sinh vào 3 lớp học buổi sáng, buổi
chiều và buổi tối, mỗi lớp 7 sinh viên là
( ) ( )
3
21!
21; 7, 7, 7
7!
C=
(phân hoạch thứ tự)
(ii) Số cách chia 21 học sinh thành 3 tổ, mỗi tổ 7 học sinh là
(
)
( )
3
21; 7, 7, 7
21!
3!
7! 3!
C= (phân hoạch không thứ tự).