Lý thuyết tổ hợp trong toán học

Lý thuyết tổ hợp (còn gọi là giải tích tổ hợp, đại số tổ hợp, lý thuyết tổ hợp) là một lĩnh vực toán học rời rạc, nghiên cứu về các cách kết hợp các phần tử trong một tập hợp hữu hạn. Những kết hợp này bao gồm hoán vị, chỉnh hợp, tổ hợp,... của các phần tử trong tập hợp đó.

Lĩnh vực này liên quan đến nhiều khía cạnh 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ư các ứng dụng trong khoa học máy tính và vật lý thống kê.

Lý thuyết tổ hợp không chỉ giải quyết các bài toán mà còn xây dựng cơ sở lý thuyết, với nhiều phương pháp lý thuyết quan trọng được phát triển, đặc biệt vào cuối thế kỷ XX (xem Danh sách các chủ đề trong toán học tổ hợp). Một trong những lĩnh vực lâu đời nhất là lý thuyết đồ thị, có nhiều kết nối tự nhiên với các lĩnh vực khác.

Lý thuyết tổ hợp được ứng dụng rộng rãi trong khoa học máy tính để phát triển các công thức và ước lượng trong phân tích thuật toán.

Những bài toán cơ bản

1. Bài toán đếm: Tính số lượng cấu hình phù hợp với các điều kiện nhất định
2. Bài toán liệt kê tổ hợp: Liệt kê toàn bộ các cấu hình thỏa mãn một điều kiện cụ thể
3. Bài toán tìm kiếm: Tìm một hoặc nhiều cấu hình đáp ứng các yêu cầu nhất định
4. Bài toán tồn tại: Xác định sự tồn tại hoặc không tồn tại của một cấu hình tổ hợp thỏa mãn yêu cầu
5. Bài toán sinh ngẫu nhiên

Các cấu hình quan trọng

Xem xét một tập hữu hạn gồm $n$ phần tử: $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 dãy k phần tử có thể lặp lại của A.
• Chỉnh hợp (không lặp) chập k ($0\le <!--\; \le \; -->k\le <!--\; \le \; -->n$) của n phần tử là một dãy k phần tử của A, với các phần tử không trùng lặp.
• Hoán vị của n phần tử là cách sắp xếp tất cả các phần tử của nó trên một đường thẳng.
• Hoán vị vòng quanh của n phần tử là cách sắp xếp tất cả các phần tử của nó trên một vòng tròn.
• Tổ hợp chập k các phần tử của A $(0\le <!--\; \le \; -->k\le <!--\; \le \; -->n)$ là một tập con k phần tử của A.
• Chỉnh hợp lặp với tần số cho trước $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$ trong đó $a_1$ xuất hiện đúng $k_1$ lần, $a_2$ xuất hiện $k_2$ lần, $a_{\mathrm{n}}$ xuất hiện $k_{\mathrm{n}}$ lần.

Các công thức tính toán cơ bản

1. Công thức để tính số chỉnh hợp lặp chập k của n phần tử là $F(n,k)=n^k$
2. Số lượng hoán vị của n phần tử được tính bằng n!
3. Công thức để tính số chỉnh hợp chập k của n phần tử là $A_n^k=\frac{n!}{(n-k)!}$
4. Công thức tính số tổ hợp chập k của n phần tử là $C_n^k=\frac{n!}{k!(n-k)!}$
5. Công thức tính số cách phân chia n nhóm số 1 bằng cách sử dụng k số 1, trong đó mỗi số 1 đại diện cho một phần tử được chọn và thứ tự của phần tử là số thứ tự của nhóm. Một nhóm có thể rỗng nếu không có số 1 nào giữa hai số 0 liên tiếp. Do đó, mỗi chuỗi (n – 1 + k) số tương đương với một chỉnh hợp lặp chập k của n phần tử. Chuỗi này phân biệt giữa số 0 và số 1. Nếu chọn k vị trí cho số 1, các vị trí còn lại trong n + k – 1 vị trí sẽ là số 0. Số cách chọn này tương ứng với số tổ hợp chập k của n + k – 1 phần tử. Do đó, số chỉnh hợp lặp được tính theo công thức như đã nêu.

Các bài toán về liệt kê

Thứ tự từ điển

Trong các từ điển, từ được sắp xếp theo một quy tắc gọi là thứ tự từ điển. Đối với hai từ được biểu diễn dưới dạng chuỗi ký tự

$x=x_1{x}_2...x_m$

$y=y_1{y}_2...y_n$

Một từ x sẽ đứng trước từ y theo thứ tự từ điển nếu có một chỉ số i, $1\le <!--\; \le \; -->i\le <!--\; \le \; -->min\{m,n\}$ sao cho

$x_i$ đứng trước $$

y i {displaystyle y_{i}}

Chú ý: Nếu $j>m$ thì $x_j$ được coi là ký tự rỗng, và nếu $j>n$ thì $y_j$ cũng được coi là ký tự rỗng, ký tự rỗng đứng trước mọi ký tự khác.

Danh sách tất cả các hoán vị của một tập hợp gồm n phần tử

Việc liệt kê tất cả các hoán vị của tập $X=\{x_1,x_2,...,x_m\}$ được chuyển thành việc liệt kê tất cả n! hoán vị của tập số chỉ mục $\{1,2,...,n\}$. Để liệt kê các hoán vị của n số tự nhiên $\{1,2,...,n\}$ theo thứ tự từ điển, hoán vị đứng đầu sẽ là $(1,2,3,...,n-<!--\; -\; -->1,n)$, và hoán vị cuối cùng là $(n,n-<!--\; -\; -->1,...,2,1)$. Ví dụ, với n=5, hoán vị đứng đầu là (1,2,3,4,5) và hoán vị cuối cùng là (5,4,3,2,1). Trong hoán vị đầu tiên, mỗi số đều nhỏ hơn số kế tiếp, trong khi hoán vị cuối cùng thì ngược lại. Vậy hoán vị kế tiếp của hoán vị đầu tiên là gì?

Giả sử có hoán vị

$x=(x_1,x_2,...,x_{n-<!--\; -\; -->1},x_n)$ của n số $1,2,...,n$.

• Thuật toán để tìm hoán vị kế tiếp
  1. Tìm chỉ số $i$ từ bên phải sang sao cho là chỉ số nhỏ nhất sao cho .
  2. Hoán đổi và sắp xếp các phần tử từ vị trí $i+1$ đến $n-<!--\; -\; -->1$ theo thứ tự từ điển.

Ví dụ: khi n=5

• Hoán vị tiếp theo của $(1,2,3,4,5)$ là $(1,2,3,5,4$)
• Tiếp theo của hoán vị $(1,2,3,5,4)$ là $(1,2,4,3,5)$
• Hoán vị tiếp theo của $(1,2,4,3,5)$ là $(1,2,4,5,3)$

...

• Tiếp theo của hoán vị $(5,4,3,1,2)$ là $(5,4,3,2,1)$

1. Bước đầu: $x=(1,2,...,n)$
2. Tìm hoán vị tiếp theo của x, gọi là x'
3. Nếu không có hoán vị tiếp theo thì kết thúc.
4. Nếu có, cập nhật x bằng x' và quay lại bước 2.

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

Danh sách các tổ hợp chập k từ tập hợp n phần tử gồm 1,2,3,4,5,6

Ví dụ minh họa

Xét tập hợp A với 5 chữ số hệ thập phân A={1,2,3,4,5}

1. Số lượng các số tự nhiên có 4 chữ số được tạo từ 5 chữ số trên là $5^4=625$.
2. Số lượng số tự nhiên có 3 chữ số khác nhau từ 5 chữ số trên là $A_5^3=\frac{5!}{2!}=60$.
3. Số lượng tập con 3 phần tử của 5 chữ số trên là $C_5^3=\frac{5!}{2!3!}=10$.
4. Số lượng hoán vị của 5 số này là $5!=120$.
5. Số lượng hoán vị vòng quanh là $Q\left(n\right)=4!=24$.
6. Số cách hoán vị khác nhau của các chữ cái trong từ XAXAM là $\frac{5!}{2!2!1!}=30$.
7. Số cách phân chia 7 viên kẹo cho 4 trẻ em là số tổ hợp lặp chập 4 của 7