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]
- 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[sửa | sửa mã nguồn]
Cho tập hữu hạn gồm phần tử:
Một số công thức tính[sửa | sửa mã nguồn]
- 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à
- Số hoán vị của n phần tử là n!
- Công thức tính số các chỉnh hợp chập k của n phần tử là
- Công thức tính số các tổ hợp chập k của n phần tử là
- 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ự
Cho \[n\] phần tử khác nhau [\[n ≥ 1\]]. Mỗi cách sắp thứ tự của \[n\] phần tử đã cho, mà trong đó mỗi phần tử có mặt đúng một lần, được gọi là một hoán vị của \[n\] phần tử đó.
Định lí
Số các hoán vị của \[n\] phần tử khác nhau đã cho [\[n ≥ 1\]] được kí hiệu là \[P_n\] và bằng:
\[P_n = n[n - 1][n - 2]...2 . 1 = n!\]
Ví dụ:
Tính số cách xếp \[6\] bạn học sinh thành một hàng dọc.
Hướng dẫn:
Mỗi cách xếp \[6\] bạn học sinh thành một hàng dọc là một hoán vị của \[6\] phần tử.
Vậy số cách xếp \[6\] bạn học sinh thành một hàng dọc là \[{P_6} = 6! = 720\].
2. Chỉnh hợp
Định nghĩa
Cho tập hợp \[A\] gồm \[n\] phần tử \[\left[ {n \ge 1} \right]\].
Kết quả của việc lấy \[k\] phần tử khác nhau từ \[n\] phần tử của tập hợp \[A\] và sắp xếp chúng theo một thứ tự nào đó được gọi là một chỉnh hợp chập \[k\] của \[n\] phần tử đã cho.
Chú ý
Mỗi hoán vị của n phần tử khác nhau đã cho chính là một chỉnh hợp chập \[n\] của \[n\] phần tử đó.
Định lí
Số chỉnh hợp chập \[k\] của \[n\] phần tử khác nhau đã cho được kí hiệu là \[A_n^k\] và bằng
\[A_n^k = n[n – 1]…[n – k + 1] =\frac{n!}{[n - k]!} \] \[[1 ≤ k ≤ n]\]
Với quy ước \[0! = 1\].
Ví dụ:
Có bao nhiêu số tự nhiên gồm \[4\] chữ số khác nhau được lập thành từ các chữ số \[1,2,3,4,5,6,7\]?
Hướng dẫn:
Mỗi số tự nhiên gồm \[4\] chữ số khác nhau được lập bằng cách lấy \[4\] chữ số từ tập \[A = \left\{ {1;2;3;4;5;6;7} \right\}\] và xếp chúng theo một thứ tự nhất định.
Mỗi số như vậy được coi là một chỉnh hợp chập \[4\] của \[7\] phần tử.
Vậy số các số cần tìm là \[A_7^4 = 840\] số.
3. Tổ hợp
Định nghĩa
Cho \[n\] phần tử khác nhau [\[n ≥ 1\]]. Mỗi tập con gồm \[k\] phần tử khác nhau [không phân biệt thứ tự] của tập hợp \[n\] phần tử đã cho [\[0 ≤ k ≤ n\]] được gọi là một tổ hợp chập \[k\] của \[n\] phần tử đã cho [với quy ước tổ hợp chập \[0\] của n phần tử bất kỳ là tập rỗng].
Định lí
Số các tổ hợp chập \[k\] của \[n\] phần tử khác nhau đã cho được kí hiệu là \[C_n^k\] và bằng
\[C_n^k = \frac{n!}{k! [n - k]!}\] = \[\frac{A^k_{n}}{k!}\], [\[0 ≤ k ≤ n\]]
Ví dụ:
Một bàn học sinh có \[3\] nam và \[2\] nữ. Có bao nhiêu cách chọn ra \[2\] bạn để làm trực nhật?
Hướng dẫn:
Mỗi cách chọn ra \[2\] bạn để làm trực nhật là một tổ hợp chập \[2\] của \[5\] phần tử.
Vậy số cách chọn là: \[C_5^2 = 10\] [cách]
Định lí
Với mọi \[n ≥ 1; 0 ≤ k ≤ n\], ta có:
- \[C_n^k = C_n^{n-k}\]
- \[C_n^k + C_n^{k+1}\] = \[C_{n+1}^{k+1}\].
4. Một số dạng toán thường gặp
Dạng 1: Giải phương trình, hệ phương trình hoán vị, chỉnh hợp, tổ hợp
Phương pháp chung:
- Sử dụng các công thức tính số hoán vị, chỉnh hợp, tổ hợp để biến đổi phương trình.
- Kiểm tra điều kiện của nghiệm và kết luận.
Dạng 2: Giải bất phương trình hoán vị, chỉnh hợp, tổ hợp
Phương pháp chung:
- Sử dụng các công thức tính số hoán vị, chỉnh hợp, tổ hợp để biến đổi bất phương trình.
- Kiểm tra điều kiện của nghiệm và kết luận.
Loigiaihay.com
- Câu hỏi 1 trang 47 SGK Đại số và Giải tích 11 Hãy liệt kê tất cả các số gồm ba chữ số khác nhau từ các chữ số 1, 2, 3...
- Câu hỏi 2 trang 49 SGK Đại số và Giải tích 11 Trong giờ học môn Giáo dục quốc phòng, một tiểu đội học sinh gồm 10 người được xếp thành một hàng dọc. ..
- Câu hỏi 3 trang 49 SGK Đại số và Giải tích 11 Giải câu hỏi 3 trang 49 SGK Đại số và Giải tích 11. Trên mặt phẳng, cho bốn điểm phân biệt A, B, C, D...
- Câu hỏi 4 trang 51 SGK Đại số và Giải tích 11 Cho tập A = {1, 2, 3, 4, 5}. Hãy liệt kê các tổ hợp chập 3, chập 4 của 5 phần tử của A.
- Câu hỏi 5 trang 52 SGK Đại số và Giải tích 11 Có 16 đội bóng đá tham gia thi đấu...
\>> Xem thêm
Luyện Bài Tập Trắc nghiệm Toán 11 - Xem ngay
2K7 tham gia ngay group để nhận thông tin thi cử, tài liệu miễn phí, trao đổi học tập nhé!
\>> Lộ Trình Sun 2025 - 3IN1 - 1 lộ trình ôn 3 kì thi [Luyện thi TN THPT & ĐGNL; ĐGTD] tại Tuyensinh247.com. Đầy đủ theo 3 đầu sách, Thầy Cô giáo giỏi, 3 bước chi tiết: Nền tảng lớp 12; Luyện thi chuyên sâu; Luyện đề đủ dạng đáp ứng mọi kì thi.