Khác biệt giữa bản sửa đổi của “Toán học tổ hợp”
Nội dung được xóa Nội dung được thêm vào
Đã lùi lại sửa đổi 55395363 của 2402:800:6101:12F0:35F9:DFEF:5883:ED6 (thảo luận) Thẻ: Lùi sửa |
|||
Dòng 1:
{{chú thích trong bài}}
== Các bài toán cơ bản ==▼
'''Toán học tổ hợp''' (hay '''giải tích tổ hợp''', '''đại số tổ hợp''', '''lý thuyết tổ hợp''') là một ngành [[toán học rời rạc]], nghiên cứu về các cấu hình kết hợp các phần tử của một tập hợp có hữu hạn phần tử. Các cấu hình đó là các [[hoán vị]], [[chỉnh hợp]], [[tổ hợp (toán học)|tổ hợp]],... các phần tử của một [[tập hợp]].
Nó có liên quan đến nhiều lĩnh vực khác của [[toán học]], như [[đại số]], [[lý thuyết xác suất]], [[lý thuyết ergod]] (''ergodic theory'') và [[hình học]], cũng như đến các ngành ứng dụng như [[khoa học máy tính]] và [[vật lý thống kê]].
'''Toán học tổ hợp''' liên quan đến cả khía cạnh giải quyết vấn đề lẫn xây dựng cơ sở lý thuyết, mặc dù nhiều phương pháp lý thuyết vững mạnh đã được xây dựng, tập trung vào cuối thế kỷ XX (xem trang [[Danh sách các chủ đề trong toán học tổ hợp]]). Một trong những mảng lâu đời nhất của toán học tổ hợp là [[lý thuyết đồ thị]], mà bản thân lý thuyết này lại có nhiều kết nối tự nhiên đến các lĩnh vực khác.
Toán học tổ hợp được dùng nhiều trong [[khoa học máy tính]] để có được công thức và ước lượng trong [[phân tích thuật toán]].
# Bài toán đếm: Đếm các cấu hình thỏa mãn những tính chất nào đó
# Bài toán liệt kê tổ hợp: Liệt kê tất cả các cấu hình thỏa mãn một tính chất nào đó
# Bài toán tìm kiếm: Tìm kiếm một hoặc một số cấu hình thỏa mãn một tính chất nào đó
# Bài toán tồn tại: Chỉ ra sự tồn tại/không tồn tại một cấu hình tổ hợp thoả mãn một tính chất nào đó
# Bài toán sinh ngẫu nhiên
== Một số cấu hình chính ==
Cho tập hữu hạn gồm n phần tử A =<math>\{a_1,a_2,...,a_n\}</math>
Hàng 8 ⟶ 23:
* '''Tổ hợp''' chập k các phần tử của A (<math>0\le k \le n</math>)là một tập con k phần tử (0<=k<=n) của tập A.
* '''Chỉnh hợp lặp với tần số cho trước''' <math>k_1,k_2,...,k_n</math> là chỉnh hợp lăp chập k với <math>k = k_1+k_2+...+k_n</math> trong đó <math>a_1</math> xuất hiện đúng <math>k_1</math> lần, <math>a_2</math> xuất hiện <math>k_2</math> lần, <math>a_n</math> xuất hiện <math>k_n</math> lần.
* '''Tổ hợp bội''' hay '''tổ hợp lặp''' chập k các phần tử của một tập hợp n phần tử là một cách lấy ra k lần (k <math>\ge</math> 0) các phần tử của một tập hợp, trong đó
* Ví dụ cho <math>A =\{1,2,3,4,5,6,7\}</math> và k = 5
** Các chỉnh hợp lặp chập 5 của 7 phần tử có thể là: 24355, 11111, 22334, 43215,...
** Các chỉnh hợp không lặp chập 5 của 7 như: 12345, 23456, 73241...
** Các tổ hợp chập 5 như: {1,2,3,4,5}, {2,3,4,5,6}, {3,4,5,6,7}...
** Chỉnh hợp lặp 22234557777 là chỉnh hợp lặp với tần số 0,3,1,1,2,0,4
Hàng 22 ⟶ 41:
::<math>y=y_1y_2...y_n</math>
::<math>\forall j\le i\,:\, x_j =y_j </math>
::<math>x_{j+1}</math> đứng trước <math>y_{j+1}</math>
| |||