Tóm lược một số kiến thức về đại số tổ hợp ứng dụng trong tin học

u Code

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.

Toán học tổ hợp được dùng nhiều trong khoa học máy tính với các bài toán cơ bản như:

  • 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

Bài viết nêu tóm tắt khái niệm và một số ví dụ, cũng như công thức đếm cho một số loại cấu hình phổ biến trên một tập hợp hữu hạn các số. Trong bài viết này, ta xét tập hợp gồm nn phần tử A={a1,a2,a3,...,an}A = \{a_1, a_2, a_3,...,a_n\}.

Hoán vị

Mỗi cách sắp xếp nn phần tử của AA theo một thứ tự nào đó được gọi là một hoán vị của nn phần tử đó.

Ví dụ: với tập A={1,2,3}A = \{1, 2, 3\}, có tất cả 66 hoán vị của 33 phần tử này là:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Gọi PnP_n là số lượng hoán vị của n phần tử. Dễ thấy:

Pn=n×(n1)××2×1=n!P_n = n \times (n-1) \times \cdots \times 2 \times 1 = n!

Giải thích: có nn cách chọn phần tử thứ nhất của hoán vị, n1n-1 cách chọn phần tử thứ 2 (phải khác phần tử đầu), n2n-2 cách chọn phần tử thứ 3 (khác hai phần tử đầu tiên)... đến phần tử cuối cùng chỉ còn 11 cách chọn (khác tất cả n1n-1 phần tử đầu).

Bài toán 1

Có bao nhiêu cách xếp 55 người thành một hàng?

Đáp án: P(5)=5!=120P(5) = 5! = 120 cách

Bài toán 2

Từ các chữ số 0,1,2,3,40, 1, 2, 3, 4 có thể lập được bao nhiêu số tự nhiên có 55 chữ số khác nhau

Lời giải:44 cách để chọn ra chữ số hàng chục ngàn (do chứ số này phải khác 00). Vậy còn 44 chữ số và có 4!=244!=24 hoán vị của chúng. Vậy có 4×4!=964 \times 4! = 96 số.

Hoán vị vòng quanh

Mỗi cách sắp xếp nn phần tử của AA thành một vòng khép kín theo một thứ tự nào đó được gọi là một hoán vị vòng quanh của nn phần tử. Ở đây ta phân biệt thứ tự theo chiều kim đồng hồngược chiều kim đồng hồkhông phân biệt điểm bắt đầu của vòng.

Ví dụ với tập A={1,2,3}A = \{1, 2, 3\}, chỉ có 22 hoán vị vòng quanh là {1,2,3}\{1, 2, 3\}{1,3,2}\{1, 3, 2\}. Các hoán vị như {2,3,1}\{2, 3, 1\}{3,1,2}\{3, 1, 2\} cũng chính là hoán vị {1,2,3}\{1, 2, 3\} với điểm bắt đầu khác.

Số lượng các hoán vị vòng quanh của nn phần tử được ký hiệu là QnQ_n​.

Do nn hoán vị bình thường sẽ cho ra cùng 11 hoán vị vòng quanh (với điểm bắt đầu khác nhau), nên dễ thấy:

Qn=Pnn=(n1)!Q_n = \frac{P_n}{n}=(n-1)!

Bài toán 1

Có bao nhiêu cách sắp xếp 55 người vào một bàn tròn có 55 chỗ, biết hai cách sắp xếp là khác nhau nếu từ cách sắp xêp thứ nhất ta không thể thu được cách xếp thứ hai khi xoay cùng chiều tất cả mọi người theo cùng một khoảng cách?

Đáp án: đây chính là số hoán vị vòng quanh của 55 phần tử, tức là 4!=244! = 24 cách.

Hoán vị lặp

Để dễ hình dung, ta bắt đầu từ một bài toán: có bao nhiêu hoán vị của các chữ cái trong chuỗi AABCAABC.

Nhận xét: chuỗi có 44 phần tử, nếu 44 phần tử này khác nhau, ta sẽ có P(4)=4!=24P(4) = 4! = 24 hoán vị. Tuy nhiên do chữ AA xuất hiện 22 lần, nên các hoán vị của 22 chữ AA này (2!=22!=2 hoán vị) sẽ không được tính, vậy số lượng hoán vị trong trường hợp này sẽ là 4!÷2!=124! \div 2! = 12 hoán vị.

Ta có thể dễ dàng liệt kê 1212 hoán vị này: AABCAABC, AACBAACB, ABACABAC, ABCAABCA, ACABACAB, ACBAACBA, BAACBAAC, BACABACA, BCAABCAA, CAABCAAB, CABACABA, CBAACBAA.

Hoán vị của nn phần tử, trong đó một số giá trị có thể lặp lại được gọi là hoán vị lặp của nn phần tử đó.

Tổng quát: cho nn phần tử, trong đó có kk giá trị khác nhau. Giá trị thứ nhất xuất hiện n1n_1 lần, giá trị thứ 2 xuất hiện n2n_2 lần..., giá trị thứ kk xuất hiện nkn_k lần (n1+n2++nk=nn_1 + n_2 + \cdots + n_k = n).

Khi đó, số lượng các hoán vị lặp của n phần tử này sẽ là:

Pn(n1,n2,,nk)=n!n1!×n2!××nk!P_n(n_1, n_2, \cdots , n_k) = \frac{n!}{n_1!\times n_2! \times \cdots \times n_k!}

Bài toán 1

Có bao nhiêu hoán vị của chuỗi MISSISSIPPIMISSISSIPPI?

Lời giải: chuỗi trên có 1111 ký tự, trong đó có 44 chữ II, 44 chữ SS, 22 chữ PP11 chữ MM. Đây chính là ví dụ điển hình của hoán vị lặp, và tổng số hoán vị sẽ là:

11!4!×4!×2!×1!=34,650\frac{11!}{4! \times 4! \times 2! \times 1!}=34{,}650

Chỉnh hợp

Mỗi cách chọn ra kk (nk0)(n \ge k \ge 0) phần tử của AAsắp xếp theo một thứ tự nào đó được gọi là một chỉnh hợp chập kk của nn phần tử.

Ví dụ, với tập A={1,2,3,4}A = \{1, 2, 3, 4\}, các chỉnh hợp chập 22 của AA sẽ là:

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

Với kk phần tử trong một chỉnh hợp, có nn cách chọn phần tử đầu tiên, n1n-1 cách chọn phần tử thứ 2,... nk+1n-k+1 cách chọn phần tử thứ kk.

Do vậy, số lượng các chỉnh hợp chập kk của nn phần tử:

Ank=n×(n1)××(nk+1)=n!(nk)!A^{k}_{n} = n \times (n-1) \times \cdots \times (n-k+1) = \frac{n!}{(n-k)!}

Lưu ý: với k=nk = n, các chỉnh hợp trở thành các hoán vị:

Ank=PnA^{k}_{n} = P_n

Bài toán 1

Có bao nhiêu cách xếp 55 người vào một băng ghế có 77 chỗ?

Đáp án: đây chính là mô hình của bài toán chỉnh hợp, đáp số chính là số lượng chỉnh hợp chập 55 của 77, tức là: 7!(75)!=2,520\frac{7!}{(7-5)!} = 2{,}520 cách.

Bài toán 2

Có bao nhiêu số tự nhiên có 44 chữ số khác nhau, được tạo thành bởi các chữ số {0,1,2,3,4,5}\{0, 1, 2, 3, 4, 5\}?

Lời giải:55 cách chọn chữ số đầu tiên (chữ số này phải khác 00). Còn lại 33 vị trí và 55 chữ số, số cách chọn cho 33 vị trí này chính là số chỉnh hợp chập $3 của $5 chữ số còn lại. Kết quả: 5×A53=5×5!(53)!=3005 \times A^3_5 = 5 \times \frac{5!}{(5-3)!} = 300 số.

Chỉnh hợp lặp

Một dãy bao gồm kk phần tử của AA, trong đó mỗi phần tử có thể được lặp lại nhiều lần, sắp xếp theo một thứ tự nhất định được gọi là một chỉnh hợp lặp chập kk của nn phần tử.

Ví dụ, với tập A={1,2,3}A = \{1, 2, 3\}, các chỉnh hợp lặp chập 22 của AA sẽ là:

1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

Mỗi phần tử trong số kk phần tử của chỉnh hợp lặp đểu có thể nhận nn giá trị khác nhau (do các giá trị có thể lặp lại). Vì vậy, số lượng các chỉnh hợp lặp chập kk của nn phần tử sẽ là:

Fnk=nkF^k_n=n^k

Bài toán 1

Biển đăng kí ô tô có 66 chữ số và 22 chữ cái tiếng Anh, không dùng chữ OOII . Hỏi số lượng ô tô có thể được đăng kí nhiều nhất là bao nhiêu?

Lời giải:F106F^6_{10} cách chọn ra 66 chữ số, và F242F^2_{24} cách chọn ra 22 chữ cái (bảng chữ cái tiếng Anh có 2626 chữ cái, trừ đi 22 chữ OOII do dễ nhầm với số 0011).

Vậy kết quả là: 106×242=576,000,00010^6 \times 24^2 = 576{,}000{,}000 ôtô.

Tổ hợp

Mỗi cách chọn ra kk (nk0)(n \ge k \ge 0) phần tử của AA (không tính đến thứ tự của chúng) được gọi là một tổ hợp chập kk của nn phần tử.

Ví dụ, với tập A={1,2,3,4}A = \{1, 2, 3, 4\}, các tổ hợp chập 22 của AA sẽ là:

1 2
1 3
1 4
2 3
2 4
3 4

Nhận xét: mỗi tổ hợp chập kk phần tử có thể tạo ra k!k! chỉnh hợp chập kk phần tử bằng cách hoán vị kk phần tử của tổ hợp này. Do vậy, số lượng tổ hợp chập kk có thể dễ tính tính được thông qua số lượng chỉnh hợp như sau:

Cnk=Ankk!=n!k!×(nk)!C^{k}_{n} = \frac{A^k_n}{k!} = \frac{n!}{ k! \times (n-k)!}

Bài toán 1

Có bao nhiêu cách chọn ra 44 cuốn sách trong số 1010 cuốn sách cho trước.

Đáp án: C104=10!4!×(104)!=210C^4_{10} = \frac{10!}{4! \times (10-4)! }= 210 cách chọn.

Bài toán 2

Một nhóm có 55 nam và 33 nữ. Có bao nhiêu cách chọn ra 33 người sao cho trong đó có ít nhất 11 nữ?

Lời giải:

  • 1 nữ, 2 nam: 3×C52=303 \times C^2_5 = 30
  • 2 nữ, 1 nam: C32×5=15C^2_3 \times 5 = 15
  • 3 nữ: C33=1C^3_3 = 1

Tổng cộng: 30+15+1=4630 + 15 + 1 = 46 cách.

Bài toán 3

Có bao nhiêu số có 44 chữ số khác nhau mà các chữ số giảm dần theo chiều từ trái qua phải.

Lời giải:

Với mỗi cách chọn 44 chữ số khác nhau (từ 1010 chữ số 0,1,...,90, 1, ..., 9), ta tạo được thành đúng 11 số có 44 chữ số thỏa mãn yêu cầu. Vậy số lượng các số như vậy sẽ là C104=10!4!×(104)!=210C^4_{10} = \frac{10!}{4! \times (10-4)!} = 210 số.

Tổ hợp lặp

Một dãy bao gồm kk phần tử (kk có thể lớn hơn nn) của AA, trong đó mỗi phần tử có thể được lặp lại nhiều lần (không tính đến thứ tự sắp xếp của chúng) được gọi là một tổ hợp lặp chập kk của nn phần tử.

Ví dụ, với tập A={1,2,3}A = \{1, 2, 3\}, các tổ hợp lặp chập 22 của AA sẽ là:

1 1
1 2
1 3
2 2
2 3
3 3

Phần tính toán số lượng các tổ hợp lặp chập kk của nn phần tử sẽ khó hơn một chút so với các loại cấu hình ở trên.

Mỗi tổ hợp lặp chập kk của nn phần tử có thể biểu diễn bằng một dãy gồm kk dấu * (ứng với kk phần tử) và n1n-1 thanh | (để chia kk dấu * thành nn ngăn, ứng với nn giá trị).

Ngăn thứ ii có thêm một dấu * mỗi lần một phần tử thứ ii của tập A xuất hiện trong tổ hợp lặp.

Ở ví dụ trên, n=3n = 3k=2k = 2, các tổ hợp lặp chập 22 của AA sẽ tương ứng với các dãy *| như sau:

1 1   **||
1 2   *|*|
1 3   *||*
2 2   |**|
2 3   |*|*
3 3   ||**

Như vậy, số lượng các tổ hợp lặp chập kk của nn phần tử chính là số cách chọn ra kk dấu * (hoặc cách chọn n1n-1 dấu |) từ dãy n+k1n+k-1 ký tự *|.

Knk=Cn+k1k=Cn+k1n1=(n+k1)!k!×(n1)!K^k_n = C^k_{n+k-1} = C^{n-1}_{n+k-1} = \frac{(n+k-1)!}{k! \times (n-1)!}

Bài toán 1

Giả sử có nn viên bi giống nhau và mm cái hộp (n>m)(n>m), ta xếp bi vào các hộp. Gọi xix_i​ với i=1,2,3...mi = 1, 2, 3 ... m là số bi ở hộp ii. Chứng minh rằng:

  • a) Số cách xếp khác nhau nn viên bi vào mm cái hộp là C^n_

  • b) Trong Cm+n1nC^n_{m+n-1}​ cách xếp đó có Cn1m1C^{m-1}_{n-1}​ cách xếp cho tất cả các hộp đều có bi.

Lời giải:

a) Ta biểu diễn nn cái kẹo bởi nn dấu *, và dùng m1m-1 vách ngăn | để chia nn cái kẹo này vào mm hộp.

Ví dụ: $3 $vạch để chi 99 cái kẹo vào 44 hộp: **|***||**** (hộp 1 có 2 kẹo, hộp 2 có 3 kẹo, hộp 3 có 0 kẹo, hộp 4 có 4 kẹo)

Như vậy, có n+m1n+m-1 ký tự (cả *|), ta cần chọn ra m1m-1 vị trí để đặt các vạch | (hoặc nn vị trí để đặt các dấu *), do vậy, số cách xếp sẽ là: Cm+n1n=Cm+n1m1C^n_{m+n-1} = C^{m-1}_{m+n-1}.

b) Trong trường hợp mỗi hộp cần có ít nhất một viên kẹo, các vạch | không được đứng cạnh nhau và phải đứng giữa các dấu *. Có n1n-1 vị trí giữa các dấu *, ta cần chọn ra m1m-1 vị trí để đặt các vạch đứng. Vậy số cách sẽ là Cn1m1C^{m-1}_{n-1}.

Hệ quả: Từ bài toán trên ta suy ra hai hệ quả thú vị sau:

a) Số nghiệm nguyên không âm của phương trình x1+x2+x3+...+xm=nx_1 + x_2 + x_3 + ... + x_m = nCm+n1nC^n_{ m+n-1}.

b) Số nghiệm nguyên dương của phương trình x1+x2+x3+...+xm=n(mn)x_1 + x_2 + x_3 + ... + x_m = n (m \le n)Cn1m1C^{m-1}_{n-1}.

Bài toán 2

Tìm số nghiệm nguyên không âm của phương trình x1+x2+x3+x4=20x_1 + x_2 + x_3 + x_4 = 20 thỏa điều kiện x13;x22;x3>4x_1 \le 3; x_2 \ge 2; x_3 > 4.

Lời giải:

Viết lại 3 điều kiện trên thành: x13;x22;x35x_1 \le 3; x_2 \le 2; x_3 \ge 5.

Ta sẽ tính số nghiệm của phương trình với điều kiện x22;x35x_2 \le 2; x_3 \ge 5 (1)(1) và trừ đi số nghiệm của cùng phương trình đó với điều ngược của điều kiện thứ nhất, tức là: x14;x22;x35x_1 \ge 4; x_2 \le 2; x_3 \ge 5 (2)(2).

(1)(1). Đặt y1=x1y_1=x_1; y2=x22y_2=x_2-2; y3=x35y_3=x_3-5; y4=x4y_4=x_4, bài toàn trở thành tính số nghiệm nguyên không âm của phương trình: y1+y2+y3+y4=13y_1 + y_2 + y_3 + y_4 = 13. Theo hệ quả ở trên, số nghiệm là: C4+13141=C163=560C^{4-1}_{4+13-1} = C^3_{16} = 560.

(2)(2). Đặt y1=x14y_1=x_1-4; y2=x22y_2=x_2-2; y3=x35y_3=x_3-5; y4=x4y_4=x_4, bài toàn trở thành tính số nghiệm nguyên không âm của phương trình: y1+y2+y3+y4=9y_1 + y_2 + y_3 + y_4 = 9. Theo hệ quả ở trên, số nghiệm là: C4+9141=C123=220C^{4-1}_{4+9-1} = C^3_{12} = 220.

Kết quả cuổi cùng: (1)(2)=560220=340(1) - (2) = 560 - 220 = 340.

Bài toán liệt kê trong tin học

Trong lập trình, một lớp bài toán phổ biến là bài toán liệt kê tất cả các cấu hình của một loại tổ hợp nào đó.

Ví dụ: liệt kê các tập hợp con của một tập hợp, liệt kê tất cả các cách xếp hàng, liệt kê các hoán vị của một xâu để tìm hoán vị phù hợp...

Các bài toán liệt kê có thể được giải bằng phương pháp sinh lần lượt tất cả các cấu hình như vậy. Để làm được điều này, bài toán cần thỏa mãn hai điều kiện sau:

  • Có thể xác định được một thứ tự trên tập các cấu hình tổ hợp cần liệt kê (thứ tự từ điển). Từ đó có thể biết được cấu hình đầu tiên và cấu hình cuối cùng trong thứ tự đó.
  • Xây dựng được thuật toán từ một cấu hình chưa phải cấu hình cuối, sinh ra được cấu hình kế tiếp nó.

Thứ tự từ điển và một số thuật toán sinh cấu hình kế tiếp phổ biến được trình bày chi tiết hơn tại đây:

Courses

Tags

Blog

Tags

About

uCode offers interactive Python, Scratch, C/C++, Algorithms, Pascal, Web, Game. Mobile App… courses for everyone from primary students to adults. Learn from a team of expert teachers in the comfort of your browser with video lessons and fun coding challenges and projects