Kiến thức

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

Chi Thuc Nguyen

Chi Thuc Nguyen

Aug 19, 2019·12 min read

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 tt 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 n phần tử A = {a₁, a₂, a₃,...,aₙ}.

Hoán vị

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

Ví dụ: với tập A = {1, 2, 3}, có tất cả 6 hoán vị của 3 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 Pₙ là số lượng hoán vị của n phần tử. Dễ thấy:

Giải thích: có n cách chọn phần tử thứ nhất của hoán vị, n-1 cách chọn phần tử thứ 2 (phải khác phần tử đầu), n-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 1 cách chọn (khác tất cả n-1 phần tử đầu).

Bạn đang xem:

Bài toán 1

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

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

Bài toán 2

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

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

Hoán vị vòng quanh

Mỗi cách sắp xếp n phần tử của A 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 n phần tử. Ở đây ta phân biệt thứ tự theo chiều kim đồng hồ và ngược chiều kim đồng hồ và 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}, chỉ có 2 hoán vị vòng quanh là {1, 2, 3}{1, 3, 2}. Các hoán vị như {2, 3, 1}{3, 1, 2} cũng chính là hoán vị {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 n phần tử được ký hiệu là Qₙ​.

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

Bài toán

Có bao nhiêu cách sắp xếp 5 người vào một bàn tròn có 5 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 5 phần tử, tức là 4! = 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 AABC.

Nhận xét: chuỗi có 4 phần tử, nếu 4 phần tử này khác nhau, ta sẽ có P(4) = 4! = 24 hoán vị. Tuy nhiên do chữ A xuất hiện 2 lần, nên các hoán vị của 2 chữ A này (2!=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! = 12 hoán vị.

Ta có thể dễ dàng liệt kê 12 hoán vị này: AABC, AACB, ABAC, ABCA, ACAB, ACBA, BAAC, BACA, BCAA, CAAB, CABA, CBAA.

Hoán vị của n 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 n phần tử đó.

Tổng quát: cho n phần tử, trong đó có k giá trị khác nhau. Giá trị thứ nhất xuất hiện n₁ lần, giá trị thứ 2 xuất hiện n₂ lần…, giá trị thứ k xuất hiện nₖ lần (n₁ + n₂ + ... + nₖ = n).

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

Xem thêm: Các định luật về chuyển động của Newton – Wikipedia tiếng Việt

Bài toán

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

Lời giải: chuỗi trên có 11 ký tự, trong đó có 4 chữ I, 4 chữ S, 2 chữ P và 1 chữ M. Đâ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à:

Chỉnh hợp

Mỗi cách chọn ra k (n ≥ k ≥ 0) phần tử của A và sắp xếp theo một thứ tự nào đó được gọi là một chỉnh hợp chập k của nphần tử.

Ví dụ, với tập A = {1, 2, 3, 4}, các chỉnh hợp chập 2 của A 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 k phần tử trong một chỉnh hợp, có n cách chọn phần tử đầu tiên, n-1 cách chọn phần tử thứ 2, … n-k+1 cách chọn phần tử thứ k.

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

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

Bài toán 1

Có bao nhiêu cách xếp 5 người vào một băng ghế có 7 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 5 của 7, tức là: 7! ÷ (7-5)! = 2520 cách.

Bài toán 2

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

Lời giải: có 5 cách chọn chữ số đầu tiên (chữ số này phải khác 0). Còn lại 3 vị trí và 5 chữ số, số cách chọn cho 3 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 × A(3, 5) = 5 × 5! ÷ (5-3)! = 300 số.

Chỉnh hợp lặp

Một dãy bao gồm k phần tử của A, 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 k của n phần tử.

Ví dụ, với tập A = {1, 2, 3}, các chỉnh hợp lặp chập 2 của A 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ố k phần tử của chỉnh hợp lặp đểu có thể nhận n 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 k của n phần tử sẽ là:

Xem thêm: BÀI 36. VẤN ĐỀ PHÁT TRIỂN KINH TẾ-XÃ HỘI Ở DUYÊN HẢI …

Bài toán

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

Lời giải: F(6,10) cách chọn ra 6 chữ số, và F(2, 24) cách chọn ra 2 chữ cái (bảng chữ cái tiếng Anh có 26 chữ cái, trừ đi 2 chữ OI do dễ nhầm với số 01). Vậy kết quả là: 10⁶ × 24² = 576.000.000 ôtô.

Tổ hợp

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

Ví dụ, với tập A = {1, 2, 3, 4}, các tổ hợp chập 2 của A 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 k phần tử có thể tạo ra k! chỉnh hợp chập k phần tử bằng cách hoán vị k phần tử của tổ hợp này. Do vậy, số lượng tổ hợp chập k có thể dễ tính tính được thông qua số lượng chỉnh hợp như sau:

Bài toán 1

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

Đáp án: C(4, 10) = 10! ÷ 4! ÷ (10-4)! = 210 cách chọn.

Bài toán 2

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

Lời giải:

  • 1 nữ, 2 nam: 3 × C(2, 5) = 30
  • 2 nữ, 1 nam: C(2,3) × 5 = 15
  • 3 nữ: C(3,3) = 1

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

Xem thêm: Hướng dẫn sử dụng máy tính casio tính nhanh giá trị biểu thức mũ-logarit-Công thức nguyên hàm

Bài toán 3

Có bao nhiêu số có 4 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 4 chữ số khác nhau (từ 10 chữ số 0, 1, …, 9), ta tạo được thành đúng 1 số có 4 chữ số thỏa mãn yêu cầu. Vậy số lượng các số như vậy sẽ là C(4, 10) = 10! ÷ 4! ÷ (10-4)! = 210 số.

Tổ hợp lặp

Một dãy bao gồm k phần tử (k có thể lớn hơn n) của A, 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 k của n phần tử.

Ví dụ, với tập A = {1, 2, 3}, các tổ hợp lặp chập 2 của A 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 k của n 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 k của n phần tử có thể biểu diễn bằng một dãy gồm k dấu * (ứng với k phần tử) và n-1 thanh | (để chia k dấu * thành n ngăn, ứng với n giá trị). Ngăn thứ i có thêm một dấu * mỗi lần một phần tử thứ i của tập A xuất hiện trong tổ hợp lặp.

Ở ví dụ trên, n = 3k = 2, các tổ hợp lặp chập 2 của A 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 k của n phần tử chính là số cách chọn ra k dấu * từ dãy n+k-1 ký tự *| (hoặc cách chọn n-1 dấu | từ dãy n+k-1 ký tự *|).

Bài toán 1

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

  • a) Số cách xếp khác nhau n viên bi vào m cái hộp là C(n, m+n-1)
  • b) Trong C(n, m+n-1)​ cách xếp đó cóC(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 n cái kẹo bởi n dấu *, và dùng m-1 vách ngăn | để chia n cái kẹo này vào m hộp.

Ví dụ: 3 vạch để chi 9 cái kẹo vào 4 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+m-1 ký tự (cả *|), ta cần chọn ra m-1 vị trí để đặt các vạch | (hoặc n vị trí để đặt các dấu *), do vậy, số cách xếp sẽ là: C(n, m+n-1) = C(m-1, n+m-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ó n-1 vị trí giữa các dấu *, ta cần chọn ra m-1 vị trí để đặt các vạch đứng. Vậy số cách sẽ là C(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 x₁ + x₂ + x₃ + ... + xₘ = n C(n, m+n-1).

b) Số nghiệm nguyên dương của phương trình x₁ + x₂ + x₃ + … + xₘ = n (m≤n)C(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 x₁ + x₂ + x₃ + x₄ = 20 thỏa điều kiện x₁ ≤ 3; x₂ ≥ 2; x₃ > 4.

Lời giải:

Viết lại 3 điều kiện trên thành: x₁ ≤ 3; x₂ ≥ 2; x₃ ≥ 5.

Ta sẽ tính số nghiệm của phương trình với điều kiện x₂ ≥ 2; x₃ ≥ 5 (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à: x₁ ≥ 4; x₂ ≥ 2; x₃ ≥ 5 (2).

(1). Đặt y₁=x₁; y₂=x₂-2; y₃=x₃-5; y₄=x₄, bài toàn trở thành tính số nghiệm nguyên không âm của phương trình: y₁ + y₂ + y₃ + y₄ = 13. Theo hệ quả ở trên, số nghiệm là: C(4-1, 4+13-1) = C(3,16) = 560.

(2). Đặt y₁=x₁-4; y₂=x₂-2; y₃=x₃-5; y₄=x₄, bài toàn trở thành tính số nghiệm nguyên không âm của phương trình: y₁ + y₂ + y₃ + y₄ = 9. Theo hệ quả ở trên, số nghiệm là: C(4-1, 9+4+-1) = C(3,12) = 220.

Kết quả cuổi cùng: (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

:

Bài toán liệt kê: Phương Pháp Sinh và thuật toán Quay Lui (Backtracking)

Phương pháp liệt kê là phương pháp giải quyết bài toán hết sức tự nhiên mà chúng ta thường dùng khi giải toán từ những…

medium.com

Chuyên mục: Kiến thức

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Back to top button