Cách tính số cách chọn

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

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à:

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

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ả * và |], 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 = nlà C[n, m+n-1].

b] Số nghiệm nguyên dương của phương trình x + x + x + + x = n [mn] là 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 = 20thỏ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.

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: