Tiểu Luận Nguyên lý bù trừ và ứng dụng

MỤC LỤC
MỤC LỤC 1
MỞ ĐẦU 2
CHƯƠNG 1: ĐẠI CƯƠNG VỀ TỔ HỢP 4
1.1. SƠ LƯỢC LỊCH SỬ 4
1.2. BÀI TOÁN TỔ HỢP 4
1.2.1. Cấu hình tổ hợp. 5
1.2.2. Các dạng bài toán tổ hợp. 5
1.3. BÀI TOÁN ĐẾM . 7
1.3.1. Giai thừa. 7
1.3.2. Nguyên lý nhân và nguyên lý cộng. 7
1.3.2.1. Nguyên lý nhân. 7
1.3.2.2. Nguyên lý cộng. 7
1.3.3. Các cấu hình tổ hợp cơ bản. 7
1.3.3.1. Chỉnh hợp lặp. 7
1.3.3.2. Chỉnh hợp không lặp. 8
1.3.3.3. Hoán vị 8
1.3.4. Cấu hình tổ hợp mở rộng. 9
1.3.4.1. Hoán vị lặp. 9
1.3.4.2. Tổ hợp lặp. 9
1.3.4.3. Phân hoạch thứ tự tổ hợp. 9
1.3.4.4. Phân hoạch không thứ tự 10
Chương II: NGUYÊN LÝ BÙ TRỪ 11
Chương iii: bài toán Ứng dỤng và các ví dỤ 13
3.1.Bài toán Ứng dỤng 13
3.1.1. Bài toán bỏ thư 13
3.1.2. Bài toán xếp n cặp vợ chồng (Lucas) 14
3.1.3. Bài toán đếm số toàn ánh. 16
3.2. Các ví dỤ 17
KẾT LUẬN 22






MỞ ĐẦU
Lý thuyết tổ hợp là một phần quan trọng của toán học rời rạc chuyên nghiên cứu sự phân bố, sắp xếp các phần tử hoặc nhiều tập hợp. Thông thường các phần tử này là hữu hạn và việc phân bố chúng phải thoả mãn những điều kiện nhất định nào đó, tùy theo yêu cầu của bài toán cần nghiên cứu. Mỗi cách phân bố như vậy gọi là một cấu hình tổ hợp. Chủ đề này đã được nghiên cứu từ thế kỉ XVII, khi những vấn đề về tổ hợp được nêu ra trong những công trình nghiên cứu các trò chơi may rủi, cho đến nay đã được áp dụng trong nhiều lĩnh vực khác nhau như lý thuyết số, hình học, đại số, xác suất thống kê, quy hoạch thực nghiệm, khoa học máy tính, hóa học,
Các bài toán tổ hợp có đặc trưng bùng nổ tổ hợp với số cấu hình tổ hợp khổng lồ. Việc giải chúng đòi hỏi một khối lượng tính toán khổng lồ (có trường hợp mất hàng chục năm). Vì vậy trong thời gian dài, khi mà các ngành toán học như phép tính vi phân, phép tính tích phân, phương trình vi phân phát triển như vũ bảo, thì nó như nằm ngoài sự phát triển và ứng dụng của toán học. Tình thế thay đổi từ khi xuất hiện máy tính và sự phát triển của toán học hữu hạn. Nhiều vấn đề tổ hợp đã được giải quyết trên máy tính. Từ chỗ chỉ nghiên cứu các trò chơi, tổ hợp đã trở thành ngành toán học phát triển mạnh mẽ, cho đến nay đã được áp dụng trong nhiều lĩnh vực khác nhau như lý thuyết số, hình học, đại số, xác suất thống kê, quy hoạch thực nghiệm, khoa học máy tính, hóa học,
Các bài toán tổ hợp thường được phân thành các dạng sau: 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. Liệt kê, đếm, sắp xếp các đối tượng có những tính chất nào đó là một phần quan trọng của lý thuyết tổ hợp.
Trong bài toán đếm, khi hai công việc có thể được làm đồng thời, chúng ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc cộng số cách làm mỗi việc sẽ dẫn đến sự trùng lập, vì những cách làm cả hai việc sẽ được tính hai lần. Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc đó là nội dung của nguyên lý bù trừ. Nhóm chúng tôi mong muốn hiểu sâu về vấn đề này nên chọn đề tài nghiên cứu là : Nguyên lý bù trừ và ứng dụng.
Đề tài gồm 3 chương xoay quanh nguyên lý bù trừ. Chương 1 nêu đại cương về tổ hợp, chương 2 nghiên cứu sâu về nguyên lý bù trừ, chương 3 nêu những ứng dụng của nguyên lý này.