Tiểu Luận Bài toán xếp đối tượng trên hàng ngang, vòng tròn và ứng dụng

Bài toán xếp đối tượng trên hàng ngang, vòng tròn và ứng dụng
MỤC LỤC
MỤC LỤC 1
LỜI MỞ ĐẦU 3
CHƯƠNG 1: SƠ LƯỢC VỀ TỔ HỢP. 5
1. Những nguyên lý đếm 5
1.1 Nguyên lý nhân. 5
1.2. Nguyên lýcộng. 5
1.3. Nguyên lý bù trừ. 6
2. Các cấu hình tổ hợp cơ bản. 8
2.1. Chỉnh hợp lặp. 8
2.2. Chỉnh hợp không lặp. 8
2.3. Hoán vị 9
2.4. Tổ hợp: 9
3. Các cấu hình tổ hợp mở rộng. 10
3.1. Hoán vị lặp. 10
3.2. Tổ hợp lặp. 11
3.3. Phân hoạch thứ tự tổ hợp. 11
3.4. Phân hoạch không thứ tự. 12
CHƯƠNG 2: BÀI TOÁN XẾP ĐỐI TƯỢNG TRÊN HÀNG NGANG, VÒNG TRÒN 13
1. Bài toán xếp đối tượng trên hàng ngang. 13
1.1. Xếp n đối tượng vào m chỗ . 13
1.2. Xếp n đối tượng vào n chỗ. 13
2. Xếp đối tượng trên vòng tròn. 14
2.1. Bài toán xếp đối tượng trên vòng tròn có đánh thứ tự. 14
2.2. Bài toán xếp đối tượng trên vòng tròn không đánh thứ tự. 14
CHƯƠNG 3: ỨNG DỤNG CỦA BÀI TOÁN XẾP ĐỐI TƯỢNG TRÊN HÀNG NGANG, VÒNG TRÒN. 14
1. Bài toán đếm số. 14
1.1. Dạng 1: Số tạo thành là số chẵn hoặc số lẻ, số lẻ, số chia hết cho . 14
1.2. Dạng 2 : Số tạo thành chứa các chữ số định trước. 16
1.3. Dạng 3: Số tạo thành không chứa 2 chữ số định trước cạnh nhau. 17
1.4. Dạng 4: Số tạo thành chứa chữ số lặp lại. 17
2. Bài toán đếm cách xếp chỗ. 18
2.1. Bài toán xếp trên hàng ngang. 18
2.2. Bài toán xếp trên vòng tròn. 20
2.3. Bài toán n cặp vợ chồng (Lucas). 23
3. Bài toán phân phối 25
4. Bài toán tìm số bộ nghiệm nguyên của phương trình. 26
KẾT LUẬN 27
TÀI LIỆU THAM KHẢO 28



LỜI MỞ ĐẦU
Tổ hợp là một lĩnh vực quan trọng đề cập tới nhiều vấn đề khác nhau trong toán học. Lý thuyết tổ hợp nghiên cứu việc phân bố các phần tử vào các 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.
Những dạng bài toán quan trọng mà lý thuyết tổ hợp đề cập đó là 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 đó, bài toán đếm là bài toán gần gũi với chương trình phổ thông cũng như trong cuộc sống.
Bài toán xếp các đối tượng trên hàng ngang và đường tròn là bài toán mang tính chất thực tế nên làm cho người giải rất dễ hình dung. Tuy nhiên, ứng dụng của bài toán xếp các đối tượng trên hàng ngang và đường tròn không chỉ dừng lại đối với các bài toán sắp xếp nói riêng, mà còn được dùng hầu hết trong các bài toán số (đưa về dạng xếp các chữ số vào các vị trí) và các bài toán phân phối (ví dụ như phân phối quà, hàng giống nhau cho một số người)
Nhằm nghiên cứu sâu hơn về vấn đề này, cũng như tạo tài liệu cho công tác giảng dạy sau này, nhóm chúng tôi chọn đề tài: “Bài toán xếp đối tượng trên hàng ngang, vòng tròn và ứng dụng”
Nội dung đề tài gồm 3 phần:
- Sơ lược về tổ hợp.
- Bài toán xếp đối tượng trên hàng ngang, vòng tròn.
- Ứng dụng của bài toán xếp đối tượng trên hàng ngang, vòng tròn