UBND TỈNH QUẢNG NAM
TRƯỜNG ĐẠI HỌC QUẢNG NAM
KHOA TOÁN
----------
ĐẶNG THỊ THÙY TRANG
ỨNG DỤNG NGUYÊN LÝ BÙ TRỪ
VÀ PHÂN HOẠCH TẬP HỢP
GIẢI MỘT SỐ BÀI TOÁN TỔ HỢP
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Qung Nam, tháng 5 năm 2015
UBND TỈNH QUẢNG NAM
TRƯỜNG ĐẠI HỌC QUẢNG NAM
KHOA TOÁN
----------
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
ỨNG DỤNG NGUYÊN LÝ BÙ TRỪ
VÀ PHÂN HOẠCH TẬP HỢP
GIẢI MỘT SỐ BÀI TOÁN TỔ HỢP
Sinh viên thực hiện
ĐẶNG THỊ THÙY TRANG
MSSV: 2111010158
CHUYÊN NGÀNH: SƯ PHẠM TOÁN
KHÓA: 2011 – 2015
Cán bộ hướng dẫn
ThS. DƯƠNG THỊ THU THÚY
MSCB: T34-15111-26747
Qung Nam, tháng 5 năm 2015
LỜI CẢM ƠN
Qua 4 năm học tập rèn luyện tại trường Đại Học Quảng Nam, ới sự
dạy dỗ của quý Thầy giáo, tôi đã tích lũy cho mình những kiến thức kinh
nghiệm quý báu cvề chuyên môn lẫn nghiệp vụ. Khóa luận này chính thành
quả quan trọng của quá trình đó. Khóa luận được hoàn thành dưới sự hướng dẫn
tận tình chu đáo của giáo ThS. Dương Thị Thu Thúy. Qua đây, vi tt c
sự kính trọng lòng biết ơn sâu sắc tôi xin được gửi đến lời cảm ơn chân
thành nhất.
Tôi cũng xin đưc cm ơn toàn thquý Thầy đã giảng dạy lớp ĐHSP
Toán K11( khóa 2011-2015) trường Đại Học Quảng Nam, đặc biệt quý Thy
khoa Toán trường Đại Học Quảng Nam, những người không những cho tôi
kiến thức còn quan tâm động viên, nhiệt tình giúp đỡ tôi trong quá trình học
tập cũng như trong thời gian thực hiện khóa luận.
Mặc dù, bản thân tôi đã rất cố gắng trong quá trình học tập nghiên cứu
đề tài của khóa luận tốt nghiệp, nhưng do thời gian hạn, khả năng nghiên cứu
kiến thức còn nhiều hạn chế nên khóa luận của tôi vẫn không thể tránh khỏi
những thiếu sót nhất định. Rất mong nhận được sự đóng góp chân thành từ quý
Thầy Cô giáo để khóa luận của tôi được hoàn thiện hơn nữa.
Tôi xin chân thành cảm ơn!
Tam Kỳ, tháng 05 năm 2015
Sinh viên thc hin
Đặng Thị Thùy Trang
MỤC LỤC
Phần 1. MỞ ĐẦU ................................................................................................. 1
1.1. Lý do chọn đề tài. .......................................................................................... 1
1.2. Mục tiêu của đề tài. ....................................................................................... 1
1.3. Đối tượng và phạm vi nghiên cứu. ............................................................... 1
1.4. Nhiệm vụ nghiên cứu. ................................................................................... 2
1.5. Phương pháp nghiên cứu. ............................................................................. 2
1.6. Đóng góp của đề tài . ..................................................................................... 2
1.7. Cấu trúc đề tài. .............................................................................................. 2
Phần 2. NỘI DUNG NGHIÊN CỨU. ................................................................. 3
Chương 1. MT S KIN THC LIÊN QUAN ĐN TP HP VÀ
NGUYÊN LÝ ĐẾM CƠ BẢN. ............................................................................ 3
1.1. Tập hợp và nguyên lý đếm cơ bản. .............................................................. 3
1.1.1. Tập hợp. ...................................................................................................... 3
1.1.2. Nguyên lý đếm cơ bản. ............................................................................... 3
1.1.2.1. Quy tắc cộng. ........................................................................................... 3
1.1.2.2. Quy tắc nhân. ........................................................................................... 4
1.2. Giải tích tổ hợp. ............................................................................................. 6
1.2.1. Hoán vị. ....................................................................................................... 6
1.2.2. Hoán vị lặp không hạn chế. ....................................................................... 6
1.2.3. Hoán vị lặp hạn chế. ................................................................................... 7
1.2.4. Chỉnh hợp k vật từ n vật ( k ≤ n). ............................................................. 7
1.2.5. Tập con k phần tử từ tập n phần tử ( k ≤ n). ........................................... 7
1.2.6. Tổ hợp lặp. .................................................................................................. 8
1.3. Quy nạp toán học. ......................................................................................... 9
1.4. Nguyên lý Dirichlet. ...................................................................................... 9
1.5. Nguyên lý bù trừ. ......................................................................................... 10
1.5.1. Nhận xét. .................................................................................................. 10
1.5.2. Nguyên lý bù trừ. ...................................................................................... 10
1.6. Phân hoạch tập hợp - Số Stirling loại hai và số Bell. ............................... 12
2.1. Ứng dụng nguyên lý bù trừ giải toán. ....................................................... 15
2.1.1. Bài toán mở rộng biểu đồ Vent phổ thông bằng nguyên lý bù trừ. ..... 15
2.1.2. Bài toán đếm số. ........................................................................................ 20
2.1.2.1 Bài toán đếm số thỏa mãn các tính chất số học. .................................. 20
2.1.2.2 Bài toán đếm số bộ nghiệm nguyên. ..................................................... 24
2.1.3. Bài toán Bernoulli – Euler. ...................................................................... 27
2.2. Ứng dụng phân hoạch tập hợp giải toán. .................................................. 30
PHẦN 3. KẾT LUẬN VÀ KIẾN NGHỊ. .......................................................... 37
1. Kết luận ........................................................................................................... 37
2. Kiến nghị ......................................................................................................... 37
PHẦN 4. TÀI LIỆU THAM KHẢO. ................................................................ 38