Lý thuyết tổ hợp - Toán học rời rạc

Lý thuyết tổ hợp là một phần qun trọng của toán học rời rạc chuyên viên nghiên cứu sự sắp xếp các đối tượng . 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 nghiên cứu .
Nội dung trích xuất từ tài liệu:
Lý thuyết tổ hợp - Toán học rời rạc 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ự sắp xếp các đối tượng.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. Chủ đề này được nghiên cứu từ thế kỷ 17 khi những câu hỏi về tổ hợp được nêu ra trong những công trình nghiên cứu của các trò chơi may rủi. 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. Một bài toán khác trong lý thuyết tổ hợp là việc tạo ra các cách sắp xếp theo một kiểu nào đó. Vấn đề này rất quan trọng trong các mô phỏng máy tính. Chúng ta cũng sẽ đưa ra những thuật toán tạo các cách sắp xếp theo nhiều kiểu khác nhau. 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ẽ, có nhiều ứng dụng trong các lĩnh vực toán học phát triển mạnh mẽ, có nhiều ứng dụng trong lĩnh vực toán học, tin học… 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ả 2 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 2 lần. Để tính đúng số cách thực hiện nhiệm vụ này cộng số cách làm mỗi 1 trong 2 việc rồi trừ đi số cách làm đồng thời cả 2 việc. Đó là nguyên lý bù trừ. 2 Chương I: ĐẠI CƯƠNG VỀ TỔ HỢP I. Sơ lược về toán học tổ hợp 1.1 Một số nguyên lý cơ bản 1.1.1. Nguyên lý nhân Giả sử một cấu hình tổ hợp được xây dựng qua k bước, bước 1 có thể được thực hiện n1 cách, bước 2 có thể được thực hiện n2 cách, …, bước k có thể được thực hiện nk cách. Khi đó số cấu hình tổ hợp là n1. n2…. nk 1.1.2. Nguyên lý cộng Giả sử {X1, X2,…,Xn} là một phân hoạch của tập S. Khi đó S = X1 + X 2 + ... + X n 1.2. Các cấu hình tổ hợp đơn giản Những cấu hình này thường được làm cơ sở cho phép đếm 1.2.1. Chỉnh hợp lặp Định nghĩa: Một chỉnh hợp lặp chập k của n phần tử khác nhau là một bộ có thứ tự gồm k thành phần lấy từ n phần tử đã cho. Các thành phần có thể được lặp lại. Một chỉnh hợp lặp chập k của n có thể xem như một phần tử của tích Đề-Các X k, với X là tập n phần tử. Như vậy số tất cả các chỉnh hợp lặp chập k của n là nk 1.2.2. Chỉnh hợp không lặp Định nghĩa: Một chỉnh lợp không lặp chập k của n phần tử khác nhau là một bộ có thứ tự gồm k thành phần lấy từ n phần tử đã cho. Các thành phần không được lặp lại. Một chỉnh hợp không lặp chập k của n có thể được xây dựng qua k bước kế tiếp như sau: Chọn thành phần đầu tiên: có n khả năng Chọn thành phần thứ hai: có n -1 khả năng ….. 3 Chọn thành phần thứ k: có n – k + 1 khả năng Như vậy theo nguyên lý nhân, số tất cả chỉnh hợp không lặp chập k của n phần tử là n! A(n,k) = n(n - 1)…. (n – k + 1) = (n − k)! 1.2.3. Hoán vị Định nghĩa: Một hoán vị của n phần tử khác nhau là một cách sắp xếp thứ tự các phần tử đó. Hoán vị có thể coi như trường hợp riêng của chỉnh hợp không lặp chập k của n trong đó k = n. Ta có số hoán vị là P(n) = n! 1.2.4. Tổ hợp Định nghĩa: Một tổ hợp chập k của n phần tử khác nhau là một bộ không kể thứ tự gồm k thành phần khác nhau lấy từ n phần tử đã cho. Nói cách khác ta có thể coi một tổ hợp chập k của n phần tử khác nhau là một tập con có k phần tử từ n phần tử đã cho. Ký hiệu số tổ hợp chập k của n phần tử là C(n, k). Ta có A(n, k) = C(n, k).k! Suy ra n! C(n, k) = k!(n − k)! 1.2.5. Hoán vị lặp Định nghĩa: Hoán vị lặp là hoán vị trong đó mỗi phần tử được ấn định số lần lặp cho trước. Định lí Số hoán vị lặp của k phần tử khác nhau trong đó số phần tử thứ nhất lặp n 1 lần, số phần tử thứ 2 lặp n2 lần,..., số phần tử thứ k lặp ...