
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
Quảng 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
Quảng Nam, tháng 5 năm 2015

LỜI CẢM ƠN
Qua 4 năm học tập và rèn luyện tại trường Đại Học Quảng Nam, dưới sự
dạy dỗ của quý Thầy Cô giáo, tôi đã tích lũy cho mình những kiến thức và kinh
nghiệm quý báu cả về chuyên môn lẫn nghiệp vụ. Khóa luận này chính là 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 và chu đáo của Cô giáo ThS. Dương Thị Thu Thúy. Qua đây, với tất cả
sự kính trọng và lòng biết ơn sâu sắc tôi xin được gửi đến Cô lời cảm ơn chân
thành nhất.
Tôi cũng xin được cảm ơn toàn thể quý Thầy Cô đã 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 là quý Thầy
Cô 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 mà 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 và nghiên cứu
đề tài của khóa luận tốt nghiệp, nhưng do thời gian có hạn, khả năng nghiên cứu
và 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 thực hiện
Đặ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. MỘT SỐ KIẾN THỨC LIÊN QUAN ĐẾN TẬP HỢP 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