Toán Học Tổ Hợp – Wikipedia Tiếng Việt

Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. Mời bạn giúp hoàn thiện bài viết này bằng cách bổ sung chú thích tới các nguồn đáng tin cậy. Các nội dung không có nguồn có thể bị nghi ngờ và xóa bỏ. (Tìm hiểu cách thức và thời điểm xóa thông báo này)

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,... 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.

Các bài toán cơ bản

[sửa | sửa mã nguồn]

1. Bài toán đếm: Đếm các cấu hình thỏa mãn những tính chất nào đó
2. 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 đó
3. 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 đó
4. 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 đó
5. Bài toán sinh ngẫu nhiên

Một số cấu hình chính

[sửa | sửa mã nguồn]

Cho tập hữu hạn gồm n {\displaystyle n} phần tử: A = { a 1 , a 2 , . . . , a n } {\displaystyle A=\{a_{1},a_{2},...,a_{n}\}}

• Chỉnh hợp lặp chập k của n phần tử đó là một bộ sắp thứ tự k phần tử của A, các phần tử có thể lấy lặp lại.
• Chỉnh hợp (không lặp) chập k ( 0 ≤ k ≤ n {\displaystyle 0\leq k\leq n} ) của n phần tử đó là một bộ sắp thứ tự k phần tử của A, các phần tử đôi một khác nhau.
• Hoán vị của n phần tử đã cho là một cách sắp xếp các phần tử của nó trên đường thẳng.
• Hoán vị vòng quanh của n phần tử đã cho là một cách sắp xếp các phần tử của nó trên đường tròn.
• Tổ hợp chập k các phần tử của A ( 0 ≤ k ≤ n ) {\displaystyle (0\leq k\leq n)} là một tập con k phần tử ( 0 ≤ k ≤ n ) {\displaystyle (0\leq k\leq n)} của tập A.
• Chỉnh hợp lặp với tần số cho trước k 1 , k 2 , . . . , k n {\displaystyle k_{1},k_{2},...,k_{n}} là chỉnh hợp lăp chập k với k = k 1 + k 2 + . . . + k n {\displaystyle k=k_{1}+k_{2}+...+k_{n}} trong đó a 1 {\displaystyle a_{1}} xuất hiện đúng k 1 {\displaystyle k_{1}} lần, a 2 {\displaystyle a_{2}} xuất hiện k 2 {\displaystyle k_{2}} lần, a n {\displaystyle a_{n}} xuất hiện k n {\displaystyle k_{n}} 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 {\displaystyle k} lần ( k ≥ 0 ) {\displaystyle (k\geq 0)} các phần tử của một tập hợp, trong đó mỗi phần tử có thể lấy ra nhiều lần.
• Ví dụ cho A = { 1 , 2 , 3 , 4 , 5 , 6 , 7 } {\displaystyle A=\{1,2,3,4,5,6,7\}} và k = 5 {\displaystyle 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 , . . . {\displaystyle 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 } . . . {\displaystyle \{1,2,3,4,5\},\{2,3,4,5,6\},\{3,4,5,6,7\}...}
  • Tổ hợp lặp 22234557777 là tổ hợp lặp với tần số 0,3,1,1,2,0,4

Một số công thức tính

[sửa | sửa mã nguồn]

1. Công thức tính số các chỉnh hợp lặp chập k của n phần tử là F ( n , k ) = n k {\displaystyle F(n,k)=n^{k}}
2. Số hoán vị của n phần tử là n!
3. Công thức tính số các chỉnh hợp chập k của n phần tử là A n k = n ! ( n − k ) ! {\displaystyle A_{n}^{k}={\frac {n!}{(n-k)!}}}
4. Công thức tính số các tổ hợp chập k của n phần tử là C n k = n ! k ! ( n − k ) ! {\displaystyle C_{n}^{k}={\frac {n!}{k!(n-k)!}}}
5. Công thức tính số 0 ngăn cách thành n nhóm số 1, trong đó có k lần xuất hiện số 1 vì mỗi số 1 tương ứng với một phần tử được chọn và số thứ tự phần tử được chọn là số thứ tự của nhóm. Một nhóm trong đó có thể là rỗng nếu không có số 1 nào giữa hai số 0 liên tiếp. Như vậy mỗi một chuỗi (n – 1 + k) số như trên tương đương một chỉnh hợp lặp chặp k của n phần tử. Chuỗi trên có phân biệt vị trí trước và sau gồm hai phần là phần số 0 và phần số 1. Nếu ta chọn ra k vị trí để đánh số 1 thì các vị trí còn lại trong n + k – 1 vị trí sẽ phải là 0. Số cách chọn như vậy lại là số tổ hợp chập k của n + k – một phần tử. Vậy số chỉnh hợp lặp có công thức như đã nêu trên.

Bài toán liệt kê

[sửa | sửa mã nguồn]

Thứ tự từ điển

[sửa | sửa mã nguồn]

Trong các bộ từ điển, các từ được liệt kê theo thứ tự được gọi là thứ tự từ điển. Cho hai từ dưới dạng xâu của các ký tự

x = x 1 x 2 . . . x m {\displaystyle x=x_{1}x_{2}...x_{m}} y = y 1 y 2 . . . y n {\displaystyle y=y_{1}y_{2}...y_{n}}

Từ x được gọi là đứng trước từ y theo thứ tự từ điển nếu tồn tại chỉ số i, 1 ≤ i ≤ m i n { m , n } {\displaystyle 1\leq i\leq min\{m,\,n\}} sao cho

∀ j ≤ i : x j = y j {\displaystyle \forall j\leq i\,:\,x_{j}=y_{j}} x i {\displaystyle x_{i}} đứng trước y i {\displaystyle y_{i}}

Chú ý: Nếu j > m {\displaystyle j>m} thì ta coi x j {\displaystyle x_{j}} là ký tự rỗng, tương tự nếu j > n {\displaystyle j>n} thì coi y j {\displaystyle y_{j}} là ký tự rỗng, ký tự rỗng đứng trước mọi ký tự khác.

Liệt kê các hoán vị của tập n phần tử

[sửa | sửa mã nguồn]

Việc liệt kê toàn bộ các hoán vị của tập X = { x 1 , x 2 , . . . , x m } {\displaystyle X=\{x_{1},x_{2},...,x_{m}\}} được quy về việc liệt kê tất cả n! hoán vị của tập chỉ số { 1 , 2 , . . . , n } {\displaystyle \{1,2,...,n\}} . Ta sẽ liệt kê các hoán vị của n số tự nhiên { 1 , 2 , . . . , n } {\displaystyle \{1,2,...,n\}} theo thứ tự từ điển. Nhận xét rằng, khi xếp theo thứ tự từ điển, hoán vị đứng trước tiên sẽ là hoán vị ( 1 , 2 , 3 , . . . , n − 1 , n ) {\displaystyle (1,2,3,...,n-1,n)} , hoán vị đứng cuối cùng sẽ là hoán vị ( n , n − 1 , . . . , 2 , 1 ) {\displaystyle (n,n-1,...,2,1)} . Ví dụ với n=5, hoán vị đứng đầu là (1,2,3,4,5), đứng cuối là (5,4,3,2,1). Trong hoán vị đầu tiên mỗi số đều nhỏ hơn số đứng ngay sau nó, trong hoán vị cuối cùng thì ngược lại. Vậy kế tiếp sau hoán vị đầu tiên là hoán vị nào?

Hoán vị kế tiếp của một hoán vị (theo thứ tự từ điển)

[sửa | sửa mã nguồn]

Giả sử có hoán vị

x = ( x 1 , x 2 , . . . , x n − 1 , x n ) {\displaystyle x=(x_{1},x_{2},...,x_{n-1},x_{n})} của n số 1 , 2 , . . . , n {\displaystyle 1,2,...,n} .

• Thuật toán sinh hoán vị kế tiếp
  1. Tìm từ bên phải sang chỉ số i {\displaystyle i} sao cho x i − 1 < x i {\displaystyle x_{i-1}<x_{i}} .
  2. Nếu không tìm thấy thì trả lời x là hoán vị cuối cùng, không có hoán vị kế tiếp.
  3. Nếu có i như vậy:
     • sắp xếp các giá trị x i , . . . , x n {\displaystyle x_{i},...,x_{n}} theo thứ tự tăng dần.
     • đổi chỗ x i − 1 {\displaystyle x_{i-1}} cho phần tử lớn hơn x i − 1 {\displaystyle x_{i-1}} gần nhất trong các giá trị x i , . . . , x n {\displaystyle x_{i},...,x_{n}}

Ví dụ: với n=5

• kế tiếp của hoán vị ( 1 , 2 , 3 , 4 , 5 ) {\displaystyle (1,2,3,4,5)} là hoán vị ( 1 , 2 , 3 , 5 , 4 {\displaystyle (1,2,3,5,4} )
• kế tiếp của hoán vị ( 1 , 2 , 3 , 5 , 4 ) {\displaystyle (1,2,3,5,4)} là hoán vị ( 1 , 2 , 4 , 3 , 5 ) {\displaystyle (1,2,4,3,5)}
• kế tiếp của hoán vị ( 1 , 2 , 4 , 3 , 5 ) {\displaystyle (1,2,4,3,5)} là hoán vị ( 1 , 2 , 4 , 5 , 3 ) {\displaystyle (1,2,4,5,3)}

...

• kế tiếp của hoán vị ( 5 , 4 , 3 , 1 , 2 ) {\displaystyle (5,4,3,1,2)} là hoán vị ( 5 , 4 , 3 , 2 , 1 ) {\displaystyle (5,4,3,2,1)}

Thuật toán liệt kê tất cả các hoán vị của n số 1,2,...,n

[sửa | sửa mã nguồn]

1. Khởi tạo: x = ( 1 , 2 , . . . , n ) {\displaystyle x=(1,2,...,n)}
2. Tìm x' là hoán vị kế tiếp của x
3. Nếu không tìm được thì dừng.
4. Nếu thấy, thay x bằng x' quay lại 2.

Ví dụ: Liệt kê 24 hoán vị của 1,2,3,4 theo thứ tự từ điển

1234	1243	1324	1342	1423	1432
2134	2143	2314	2341	2413	2431
3124	3142	3214	3241	3412	3421
4123	4132	4213	4231	4312	4321

Liệt kê các tổ hợp chập k của tập n phần tử 1,2,3,4,5,6

[sửa | sửa mã nguồn]

Ví dụ

[sửa | sửa mã nguồn]

Cho tập A gồm 5 chữ số hệ thập phân A={1,2,3,4,5}

1. Số các số tự nhiên 4 chữ số lập thành từ 5 chữ số trên là 5 4 = 625 {\displaystyle 5^{4}=625} .
2. Số các số tự nhiên gồm 3 chữ số khác nhau lập thành từ 5 chữ số trên là A 5 3 = 5 ! 2 ! = 60 {\displaystyle A_{5}^{3}={\frac {5!}{2!}}=60} .
3. Số các tập con 3 phần tử của 5 chữ số trên là C 5 3 = 5 ! 2 ! 3 ! = 10 {\displaystyle C_{5}^{3}={\frac {5!}{2!3!}}=10} .
4. Số các hoán vị của 5 số đó là 5 ! = 120 {\displaystyle 5!=120} .
5. Số các hoán vị vòng quanh là Q ( n ) = 4 ! = 24 {\displaystyle Q(n)=4!=24} .
6. Số các hoán vị khác nhau có thể có khi hoán vị các chữ cái trong từ XAXAM là 5 ! 2 ! 2 ! 1 ! = 30 {\displaystyle {\frac {5!}{2!2!1!}}=30} .
7. Số cách chia 7 chiếc kẹo cho 4 trẻ em là tổ hợp lặp chập 4 của 7

Tham khảo

[sửa | sửa mã nguồn] Wikimedia Commons có thêm hình ảnh và phương tiện về Toán học tổ hợp.

x t s Toán học
Lịch sử Dòng thời gian Tương lai Đại cương Danh sách Ký hiệu
Nền tảng	Logic toán Lý thuyết hình thái Lý thuyết phạm trù Lý thuyết tập hợp Lý thuyết thông tin Triết học toán học
Đại số	Đa tuyến tính Đồng điều Giao hoán Lý thuyết nhóm Phổ dụng Sơ cấp Trừu tượng Tuyến tính
Giải tích	Giải tích điều hòa Giải tích hàm Giải tích phức Giải tích thực Lý thuyết độ đo Phương trình vi phân Vi tích phân
Rời rạc	Lý thuyết đồ thị Lý thuyết thứ tự Tổ hợp
Hình học	Đại số Euclid Giải tích Hữu hạn Rời rạc Số học Vi phân
Lý thuyết số	Số học Đại số Giải tích Hình học Diophantos
Tô pô	Đại số Hình học Đại cương Vi phân Lý thuyết đồng luân
Ứng dụng	Hóa học Kinh tế Lý thuyết điều khiển tự động Lý thuyết trò chơi Sinh học Tài chính Tâm lý Thống kê toán học Xác suất Thống kê Vật lý
Tính toán	Khoa học máy tính Lý thuyết tính toán Lý thuyết độ phức tạp tính toán Đại số máy tính Giải tích số Tối ưu hóa
Liên quan	Toán học giải trí Toán học và nghệ thuật Giáo dục toán học
Thể loại · Chủ đề · Commons · Dự án

x t s Khoa học máy tính
Chú ý: Bản mẫu này cơ bản dựa trên Hệ thống xếp loại điện toán ACM năm 2012.
Phần cứng	Mạch in Thiết bị ngoại vi Vi mạch Vi mạch tích hợp Hệ thống trên vi mạch (SoC) Tiêu thụ năng lượng (Điện toán xanh) Tự động hóa thiết kế điện tử Tăng tốc phần cứng Bộ xử lý Kích thước / Dạng thức
Tổ chức hệ thống máy tính	Kiến trúc máy tính Độ phức tạp tính toán Độ tin cậy hệ thống Hệ thống nhúng Hệ thống thời gian thực
Mạng máy tính	Kiến trúc mạng Giao thức mạng Phần cứng mạng Bộ lập lịch trình mạng Hiệu suất mạng Dịch vụ mạng
Tổ chức phần mềm	Trình thông dịch Middleware Máy ảo Hệ điều hành Chất lượng phần mềm
Ký pháp và công cụ phần mềm	Mẫu hình lập trình Ngôn ngữ lập trình Trình biên dịch Ngôn ngữ miền chuyên biệt Ngôn ngữ mô hình hóa Khung phần mềm Môi trường phát triển tích hợp Quản lý cấu hình phần mềm Thư viện phần mềm Kho chứa phần mềm
Phát triển phần mềm	Biến điều khiển Quy trình phát triển phần mềm Phân tích yêu cầu Thiết kế phần mềm Xây dựng phần mềm Triển khai phần mềm Công nghệ phần mềm Bảo trì phần mềm Nhóm lập trình Mô hình nguồn mở
Lý thuyết tính toán	Mô hình tính toán Ngẫu nhiên Ngôn ngữ hình thức Lý thuyết Automat Lý thuyết khả tính Lý thuyết độ phức tạp tính toán Logic Ngữ nghĩa
Thuật toán	Thiết kế thuật toán Phân tích thuật toán Hiệu quả thuật toán Thuật toán ngẫu nhiên Hình học tính toán
Toán học về điện toán	Toán học rời rạc Xác suất Thống kê Phần mềm toán học Lý thuyết thông tin Giải tích toán học Giải tích số Khoa học máy tính lý thuyết
Hệ thống thông tin	Hệ quản trị cơ sở dữ liệu Hệ thống lưu trữ thông tin Hệ thống thông tin doanh nghiệp Hệ thống thông tin xã hội Hệ thống thông tin địa lý Hệ thống hỗ trợ ra quyết định Hệ thống điều khiển quá trình Hệ thống thông tin đa phương tiện Khai phá dữ liệu Thư viện số Nền tảng máy tính Tiếp thị kỹ thuật số World Wide Web Truy hồi thông tin
Bảo mật	Mật mã học Các phương pháp hình thức Hacker bảo mật Dịch vụ bảo mật Hệ thống phát hiện xâm nhập Bảo mật phần cứng Bảo mật mạng An toàn thông tin Bảo mật ứng dụng
Tương tác người–máy	Thiết kế tương tác Điện toán xã hội Điện toán khắp nơi Trực quan hóa Khả năng tiếp cận
Tương tranh	Tính toán tương tranh Tính toán song song Điện toán phân tán Đa luồng Đa xử lý
Trí tuệ nhân tạo	Xử lý ngôn ngữ tự nhiên Biểu diễn tri thức và suy luận Thị giác máy tính Lập kế hoạch và lên lịch tự động Phương pháp tìm kiếm Phương pháp điều khiển Triết học về trí tuệ nhân tạo Trí tuệ nhân tạo phân tán
Học máy	Học có giám sát Học không có giám sát Học tăng cường Học đa tác vụ Kiểm chứng chéo
Đồ họa	Hoạt hình Thực tế mở rộng Tăng cường Hỗn hợp Ảo Kết xuất Thao túng hình ảnh Bộ xử lý đồ họa Nén ảnh Mô hình hóa dạng khối
Điện toán ứng dụng	Điện toán lượng tử Thương mại điện tử Phần mềm doanh nghiệp Toán học tính toán Vật lý tính toán Hóa học tính toán Sinh học tính toán Khoa học xã hội tính toán Kỹ thuật tính toán Điện toán khả vi Y tế tính toán Nghệ thuật số Xuất bản điện tử Chiến tranh mạng Bầu cử điện tử Trò chơi video Soạn thảo văn bản Vận trù học Công nghệ giáo dục Quản lý tài liệu
Thể loại Đề cương Thuật ngữ