Toán học tổ hợp

Đánh giá bài viết

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.

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

Cho tập hữu hạn gồm n {displaystyle n} ${displaystyle n}$ phần tử: A = { a 1 , a 2 , . . . , a n } {displaystyle 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 0leq kleq n} ${displaystyle 0leq kleq 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 (0leq kleq n)} ${displaystyle (0leq kleq n)}$ là một tập con k phần tử ( 0 ≤ k ≤ n ) {displaystyle (0leq kleq n)} ${displaystyle (0leq kleq 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}} ${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}} ${displaystyle k=k_{1}+k_{2}+...+k_{n}}$ trong đó a 1 {displaystyle a_{1}} ${displaystyle a_{1}}$ xuất hiện đúng k 1 {displaystyle k_{1}} ${displaystyle k_{1}}$ lần, a 2 {displaystyle a_{2}} ${displaystyle a_{2}}$ xuất hiện k 2 {displaystyle k_{2}} ${displaystyle k_{2}}$ lần, a n {displaystyle a_{n}} ${displaystyle a_{n}}$ xuất hiện k n {displaystyle 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} ${displaystyle k}$ lần ( k ≥ 0 ) {displaystyle (kgeq 0)} ${displaystyle (kgeq 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,…} ${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}…} ${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

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}} ${displaystyle F(n,k)=n^{k}}$
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à A n k = n ! ( n − k ) ! {displaystyle A_{n}^{k}={frac {n!}{(n-k)!}}} ${displaystyle A_{n}^{k}={frac {n!}{(n-k)!}}}$
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)!}}} ${displaystyle C_{n}^{k}={frac {n!}{k!(n-k)!}}}$
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.

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}} ${displaystyle x=x_{1}x_{2}...x_{m}}$ y = y 1 y 2 . . . y n {displaystyle 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 1leq ileq min{m,,n}} ${displaystyle 1leq ileq min{m,,n}}$ sao cho

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

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

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}}} ${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}} ${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}} ${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)} ${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)} ${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?

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})} ${displaystyle x=(x_{1},x_{2},...,x_{n-1},x_{n})}$ của n số 1 , 2 , . . . , n {displaystyle 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} ${displaystyle i}$ sao cho x i − 1 < x i {displaystyle 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}} ${displaystyle x_{i},...,x_{n}}$ theo thứ tự tăng dần.
  - đổi chỗ x i − 1 {displaystyle x_{i-1}} ${displaystyle x_{i-1}}$ cho phần tử lớn hơn x i − 1 {displaystyle 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}} ${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)} ${displaystyle (1,2,3,4,5)}$ là hoán vị ( 1 , 2 , 3 , 5 , 4 {displaystyle (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)} ${displaystyle (1,2,3,5,4)}$ là hoán vị ( 1 , 2 , 4 , 3 , 5 ) {displaystyle (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)} ${displaystyle (1,2,4,3,5)}$ là hoán vị ( 1 , 2 , 4 , 5 , 3 ) {displaystyle (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)} ${displaystyle (5,4,3,1,2)}$ là hoán vị ( 5 , 4 , 3 , 2 , 1 ) {displaystyle (5,4,3,2,1)} ${displaystyle (5,4,3,2,1)}$

Khởi tạo: x = ( 1 , 2 , . . . , n ) {displaystyle x=(1,2,…,n)} ${displaystyle x=(1,2,...,n)}$
Tìm x’ là hoán vị kế tiếp của x
Nếu không tìm được thì dừng.
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

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

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} ${displaystyle 5^{4}=625}$ .
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} ${displaystyle A_{5}^{3}={frac {5!}{2!}}=60}$ .
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} ${displaystyle C_{5}^{3}={frac {5!}{2!3!}}=10}$ .
Số các hoán vị của 5 số đó là 5 ! = 120 {displaystyle 5!=120} ${displaystyle 5!=120}$ .
Số các hoán vị vòng quanh là Q ( n ) = 4 ! = 24 {displaystyle Q(n)=4!=24} ${displaystyle Q(n)=4!=24}$ .
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} ${displaystyle {frac {5!}{2!2!1!}}=30}$ .
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