I. MỞ ĐẦU
1.1. Sơ lược về tổ hợp
Tổ hợp như là một lĩnh vực của toán học rời rạc, xuất hiện vào đầu thế kỷ 17. Trong một thời gian dài, dường như tổ hợp nằm ngoài guồng máy phát triển của toán học cũng như ứng dụng của nó. Tình thế bắt đầu đối khác khi xuất hiện các máy tính và cũng với nó là sự phát triển của toán hữu hạn. Hiện nay lý thuyết tổ hợp được áp dụng trong nhiều lĩnh vực khác nhau: lý thuyết số, hình học hữu hạn, biểu diễn nhóm, đại số không giao hoán, quá trình ngẫu nhiên, thống kê xác suất, quy hoạch thực nghiệm,…
1.1.1. Các bài toán tổng quát
Tổ hợp đụng chạm đến nhiều vấn đề khác nhau của toán học, do đó khó có thể định nghĩa nó một cách hình thức. Nói chung, lý thuyết tổ hợp gắn liền với việc nghiên cứu 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 đấy, tuỳ 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ế được gọi là một cấu hình tổ hợp.
Trong các tài liệu về tổ hợp, thường gặp các dạng bài toán dưới đây:
a) Bài toán đếm: đây là các bài toán nhằm trả lời câu hỏi “có bao nhiêu cấu hình thoả mãn điều kiện đã nêu ?”. Phương pháp đếm thường dựa vào một số nguyên lý cơ bản và một số kết quả đếm các cấu hình đơn giản. Bài toán đếm được áp dụng một cách có hiệu quả vào những công việc mang tính chất đánh giá như tính xác suất của một sự kiện, tính độ phức tạp của một thuật toán…..
b) Bải toán liệt kê: bài toán này quan tâm đến tất cả cấu hình có thể có được, vì thế lời giải của nó cần được biểu diễn dưới dạng thuật toán “vết cạn” tất cả các cấu hình. Lời giải trong từng trường hợp cụ thể sẽ được máy tính điện từ giải quyết theo thuật toán đã nêu. Bài toán liệt kê được làm “nến” cho nhiều bài toán khác. Hiện nay, một số bài toán đếm, tối ưu, tốn tại vẫn chưa có cách nào giải, ngoài cách giải liệt kê. Nếu trước đây, cách giải liệt kê còn mang nặng tỉnh lý thuyết, thì bây giờ nó ngày càng khả thì nhờ sự phát triển nhanh chóng của máy tính điện tử.
c) Bài toán tối ưu khác với bải bài toán liệt kê, bài toán tối ưu chỉ quan tâm đến một cấu hình “tốt nhất theo một nghĩa nào đây. Đây là bài toán có nhiều ứng dụng trong thực tiên và lý thuyết tổ hợp đã đóng góp một phần đáng kể trong việc xây dựng được những thuật toán hữu hiệu.
d) Bài toàn tồn tại: nếu như trong các bài toán trên, việc tồn tại các câu bình là hiển nhiên thì trong bài toán này, vấn đề “có hay không có” cấu hình còn là điều nghi vấn. Các bài toán loại này thường bị kẹt trong tình huống nan giải: không chỉ ra được cấu hình nào nhưng cũng không khẳng định được là chúng không tồn tại. Lịch sử toán học thưởng để lại những bài toán khó trong lĩnh vực này và việc cố gắng giải quyết chúng đã thúc đấy không ít sự phát triển của nhiều ngành toán học.
1.1.2. Vài nét về lịch sử
Có thể nói tư duy về tổ hợp ra đời từ rất sớm. Vào thời nhà Chu, người ta đã biết đến các hình vẽ có liên quan đến những hình vuông thần bí. Thời cổ Hy lạp, nhà triết học Kxenokrat, sống ở thế kỷ thứ 4 trước công nguyên, đã biết cách tính số các từ khác nhau, lập từ một bảng chữ cái cho trước. Nhà toán học Pitagor và các học trò của ông đã tìm ra được nhiều con số có các tính chất đặc biệt, chẳng hạn số 36 không những là tổng của 4 số chấn và 4 số lẻ đầu tiên mà còn là tổng lập phương của 3 số tự nhiên đấu tiên. Một định lý nổi tiếng của trường phái này là định lý về độ dài các cạnh của một tam giác vuông, và từ đó họ đã tìm ra các số mà bình phương của một số này bằng tống bình phương của hai số khác. Việc tìm ra được các số như vậy, đòi hỏi phải có một nghệ thuật tổ hợp nhất định. Tuy nhiên, có thể nói rằng, lý thuyết tổ hợp được hình thành như một ngành toán học mới, vào quãng thế kỷ 17 bằng một loạt các công trình nghiên cứu nghiêm túc của các nhà toán học xuất sắc như Pascal, Fermat, Leibnitz, Euler…
