Báo Cáo Chỉnh hợp và tổ hợp suy rộng

Lời mở đầu
Lý thuyết tổ hợp là 1 phần quan trọng của toán rời rạc chuyên nghiên cứu sự
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 thỏa 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ư thế gọi là một cấu hình tổ
hợp.Chủ đề này đã được nghiên cứu vào thế kỉ 17,khi những câu hỏi về tổ hợp
được đưa ra trong các công trình nghiên cứu hay các trò chơi may rủi.Liệt kê,đếm
các đối tượng có những tính chất nào đólaf một phần quan trọng của lý thuyết tổ
hợp.Chúng ta cần phải đếm các đối tượng để giải nhiều bài toán khác nhau.Hơn
nữa các kĩ thuật đếm được dùng rất nhiều khi tính xác suất của các biến cố hay
trong đánh giá độ phức tạp của thuật toán.
Trong bài báo cáo này chúng tôi sẽ trình bày các nội dung cơ bản về chỉnh hợp
và tổ hợp suy rộng cùng với các vấn đề liên quan . Cuối báo cáo là thuật toán liệt
kê tất cả các hoán vị của các kí tự trong một xâu ( Với files chương trình và mã
nguồn đi kèm trong CD).
Mục đính của bài thảo luận :
 Cung cấp kiến thức cơ bản về hoán vị, tổ hợp và chỉnh hợp suy rộng
 Minh họa thuật toán liệt kê các hoán vị của các kí tự trong một xâu cho
trước.
Dù đã rất cố gắng nhưng với thời gian hạn chế chắc chắn báo cáo này vẫn còn
rất nhiều thiếu sót, rất mong nhận được sự góp ý của thầy cô và các bạn.
Nhóm các sinh viên Thanh, Tiến, Trọng, Phượng, Quyến, Trung, Trường xin cảm
ơn!
Mục lục
1. Lời mở đầu 2
2. Cơ sở phép đếm . 5
3. Chỉnh hợp 13
4. Hoán vị . 15
5. Tổ hợp 19
6. Thuật toán liệt kê các hoán vị của các kí tự trong xâu 23
7. Một số nội dung mở rộng 24
8. Tài liệu tham khảo 32
9. Lời kết thúc 33
10. Nhận xét của giáo viên phụ trách 33