ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
PHẠM THỊ BÍCH HỒNG
MỘT SỐ ỨNG DỤNG
CỦA LÝ THUYẾT TỔ HỢP
TRONG TOÁN CẤP
LUẬN VĂN THẠC TOÁN HỌC
Thái Nguyên - 2013
.
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
PHẠM THỊ BÍCH HỒNG
MỘT SỐ ỨNG DỤNG
CỦA LÝ THUYẾT TỔ HỢP
TRONG TOÁN CẤP
LUẬN VĂN THẠC TOÁN HỌC
Chuyên ngành : PHƯƠNG PHÁP TOÁN CẤP
số :60 46 01 13
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS. TS NÔNG QUỐC CHINH
THÁI NGUYÊN - 2013
1
.
LỜI CẢM ƠN
Luận văn y được hoàn thành dưới sự hướng dẫn khoa học của PGS.TS
Nông Quốc Chinh. Em xin được tỏ lòng cảm ơn chân thành nhất tới thầy
v sự giúp đỡ nhiệt tình từ khi y dựng đề cương, viết và hoàn thành luận
văn. Tiếp theo em xin chân thành cảm ơn các thầy giáo phản biện đã đọc
và góp ý để em hoàn thiện luận văn của mình. Em xin được cảm ơn chân
thành nhất tới khoa Toán - Tin, phòng ĐT KH QHQT, Trường Đại học
Khoa học Đại học Thái Nguyên, nơi em đã được một học vấn căn bản. Xin
cảm ơn gia đình, đồng nghiệp đã cảm thông chia sẻ, ủng hộ và giúp đỡ trong
thời gian em học cao học và viết luận văn.
2
.
Mục lục
1 KIẾN THỨC BẢN 7
1.1 Những nguyên đếm bản: . . . . . . . . . . . . . . . . . 7
1.2 Nguyên Dirichlet . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Hoán vị: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Chỉnh hợp: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.1 Chỉnh hợp: . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.2 Chỉnh hợp lặp: . . . . . . . . . . . . . . . . . . . . 15
1.5 T hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.1 T hợp : . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.2 T hợp lặp: . . . . . . . . . . . . . . . . . . . . . . . . 16
2 ỨNG DỤNG CỦA LÝ THUYẾT TỔ HỢP TRONG ĐẠI SỐ
CẤP 18
2.1 Bài toán 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 Bài toán 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Bài toán 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Bài toán 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Bài toán 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.6 Bài toán 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.7 Bài toán 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 ỨNG DỤNG CỦA LÝ THUYẾT TỔ HỢP TRONG HÌNH
HỌC 28
3.1 Bài toán 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Bài toán 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Bài toán 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.4 Bài toán 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Bài toán 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3
.
4 ỨNG DỤNG NGUYÊN LÝ DIRICHLET 34
4.1 Bài toán 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2 Bài toán 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3 Bài toán 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.4 Bài toán 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.5 Bài toán 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.6 Bài toán 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.7 Bài toán 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.8 Bài toán 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.9 Bài toán 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.10 Bài toán 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.11 Bài toán 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.12 Bài toán 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.13 Bài toán 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.14 Bài toán 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.15 Bài toán 15 . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.15.1 Bài toán tương tự . . . . . . . . . . . . . . . . . . . . 48
4.16 Bài toán 16 . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Kết luận 51
Tài liệu tham khảo 52
4
.