Hoán vị, chỉnh hợp, tổ hợp

Mức độ: Cơ bản

Ba cái tên nghe “học thuật” này thật ra chỉ là ba trường hợp hay gặp của quy tắc nhân (bài Quy tắc cộng, quy tắc nhân). Điều quan trọng là nhận ra đề đang hỏi trường hợp nào: có quan tâm thứ tự không, và chọn hết hay chỉ chọn một phần.

	Có thứ tự	Không thứ tự
Xếp tất cả n phần tử	hoán vị: n!	(chỉ có 1 cách)
Chọn k trong n phần tử	chỉnh hợp: n × (n - 1) × … (k thừa số)	tổ hợp: C(n, k)

Hoán vị: xếp tất cả

Xếp n bạn thành một hàng: người đầu n cách, người thứ hai n - 1 cách, …, người cuối 1 cách. Số cách là n! = n × (n - 1) × … × 1.

Ví dụ xếp 4 chữ cái của từ COLD: 4! = 24 cách.

Chỉnh hợp: chọn k người và xếp vào k vị trí khác nhau

Lớp có 40 bạn, chọn lớp trưởng, lớp phó, thủ quỹ (ba chức vụ khác nhau): lớp trưởng 40 cách, lớp phó 39 cách, thủ quỹ 38 cách: 40 × 39 × 38 = 59280 cách.

Đây là chỉnh hợp chập 3 của 40: nhân k thừa số giảm dần bắt đầu từ n.

Tổ hợp: chọn k người, không phân biệt thứ tự

Chọn 3 bạn đi trực nhật (không có chức vụ) từ 40 bạn. Nếu đếm như chỉnh hợp thì mỗi nhóm 3 bạn bị đếm nhiều lần: nhóm An, Bình, Chi được đếm ở cả 6 thứ tự (ABC, ACB, BAC, BCA, CAB, CBA). Vậy phải chia cho 3! = 6:

C(40, 3) = (40 × 39 × 38) / (3 × 2 × 1) = 59280 / 6 = 9880.

Công thức chung: C(n, k) = n × (n - 1) × … × (n - k + 1) / k!

Hai tính chất dễ nhớ:

• C(n, k) = C(n, n - k): chọn k người đi trực nhật cũng là chọn n - k người ở lại.
• C(n, 2) = n × (n - 1) / 2: chính là số cái bắt tay trong bài bắt tay.

Tính C(n, k) trong code không bị tràn số

Tính 60! rồi chia thì tràn long long (60! có 82 chữ số), dù C(60, 30) chỉ khoảng 1,2 × 10¹⁷. Cách an toàn: nhân rồi chia xen kẽ:

kq = 1, rồi với i từ 1 đến k: kq = kq × (n - k + i) / i

Sau bước thứ i, kq bằng C(n - k + i, i), luôn là số nguyên, nên phép chia luôn chia hết.

Python

def to_hop(n, k):
    if k < 0 or k > n:
        return 0
    k = min(k, n - k)            # C(n, k) = C(n, n - k), chọn vế ít bước hơn
    kq = 1
    for i in range(1, k + 1):
        kq = kq * (n - k + i) // i
    return kq

print(to_hop(40, 3))     # 9880
print(to_hop(60, 30))    # 118264581564861424

C++

#include <iostream>
using namespace std;

long long toHop(long long n, long long k) {
    if (k < 0 || k > n) return 0;
    k = min(k, n - k);           // C(n, k) = C(n, n - k), chọn vế ít bước hơn
    long long kq = 1;
    for (long long i = 1; i <= k; i++) kq = kq * (n - k + i) / i;
    return kq;
}

int main() {
    cout << toHop(40, 3) << endl;     // 9880
    cout << toHop(60, 30) << endl;    // 118264581564861424
    return 0;
}

Lưu ý: viết kq *= (n - k + i) / i là sai, vì (n - k + i) / i bị làm tròn xuống trước khi nhân. Phải nhân trước rồi mới chia. Khi n lớn hơn khoảng 60, tích trung gian vẫn có thể tràn; lúc đó dùng phép chia lấy dư như bài Lũy thừa nhanh.

Tam giác Pascal

Xét đồ vật cuối cùng: hoặc không chọn nó (chọn k từ n - 1 đồ còn lại), hoặc chọn nó (chọn thêm k - 1 từ n - 1 đồ còn lại). Theo quy tắc cộng:

C(n, k) = C(n - 1, k) + C(n - 1, k - 1)

Viết các C(n, k) thành tam giác, mỗi số bằng tổng hai số ngay phía trên:

            1
          1   1
        1   2   1
      1   3   3   1
    1   4   6   4   1
  1   5  10  10   5   1

Hàng n là C(n, 0), C(n, 1), …, C(n, n). Tam giác Pascal chỉ dùng phép cộng nên rất hợp khi cần nhiều giá trị C(n, k) với n nhỏ.

Chia kẹo: kỹ thuật “vách ngăn”

Chia 10 viên kẹo giống nhau cho 3 bạn, mỗi bạn ít nhất 1 viên. Xếp 10 viên thành hàng, giữa chúng có 9 khe. Đặt 2 vách ngăn vào 2 trong 9 khe để chia hàng thành 3 phần: mỗi cách đặt vách ứng với đúng một cách chia.

● ● ● | ● ● | ● ● ● ● ●      An 3, Bình 2, Chi 5

Số cách: C(9, 2) = 36. Tổng quát: chia n vật giống nhau cho k người, mỗi người ít nhất 1 vật: C(n - 1, k - 1).

Luyện tập

Gồm 26 bài, chia thành 5 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Hoán vị

Bài 1. Sắp xếp chữ cái khác nhau

Nhập một từ gồm các chữ cái in hoa đôi một khác nhau (độ dài không quá 20). In ra số cách sắp xếp các chữ cái của từ đó (kể cả cách ban đầu).

Ví dụ: nhập COLD thì in ra 24.

Kiểm tra: nhập PYTHON.

Xem đáp số

720

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Sắp xếp chữ cái có lặp lại

Nhập một từ gồm các chữ cái in hoa (độ dài không quá 20, chữ cái có thể lặp lại). In ra số cách sắp xếp khác nhau các chữ cái của từ đó.

Ví dụ: nhập BANANA thì in ra 60.

Kiểm tra: nhập MISSISSIPPI.

Xem đáp số

34650

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Ngồi quanh bàn tròn

Có n bạn (n ≤ 20) ngồi quanh một bàn tròn. Hai cách ngồi coi là giống nhau nếu xoay bàn thì trùng nhau (mỗi bạn vẫn có cùng người bên trái, bên phải). Có bao nhiêu cách ngồi?

Ví dụ: nhập 4 thì in ra 6.

Kiểm tra: nhập 6.

Xem đáp số

120

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Vòng hạt

Xâu n hạt khác màu (3 ≤ n ≤ 20) thành một vòng đeo tay. Hai vòng coi là giống nhau nếu xoay hoặc lật vòng này thì được vòng kia. Có bao nhiêu vòng khác nhau?

Ví dụ: nhập 4 thì in ra 3.

Kiểm tra: nhập 6.

Xem đáp số

60

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. An đứng trước Bình

Có n bạn (2 ≤ n ≤ 20) xếp thành một hàng, trong đó có An và Bình. Có bao nhiêu cách xếp sao cho An đứng trước Bình (không nhất thiết đứng sát nhau)?

Ví dụ: nhập 3 thì in ra 3.

Kiểm tra: nhập 5.

Xem đáp số

60

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Hoán vị thứ k

Viết mọi hoán vị của 1, 2, …, n (n ≤ 12) theo thứ tự từ điển (123, 132, 213, …). Nhập n và k (1 ≤ k ≤ n!), in ra hoán vị thứ k, các số cách nhau một dấu cách.

Ví dụ: nhập 3 4 thì in ra 2 3 1.

Kiểm tra: nhập 5 100.

Xem đáp số

5 1 3 4 2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Chỉnh hợp

Bài 7. Bầu ban cán sự

Lớp có n bạn, cần bầu k chức vụ khác nhau (lớp trưởng, lớp phó, …), mỗi bạn giữ nhiều nhất một chức vụ (k ≤ n ≤ 10⁶, kết quả không quá 10¹⁸). Có bao nhiêu cách bầu?

Ví dụ: nhập 5 2 thì in ra 20.

Kiểm tra: nhập 40 3.

Xem đáp số

59280

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Số có chữ số khác nhau từ 1 đến 9

Dùng các chữ số từ 1 đến 9 (không dùng 0), lập được bao nhiêu số có k chữ số đôi một khác nhau? Nhập k (1 ≤ k ≤ 9).

Ví dụ: nhập 2 thì in ra 72.

Kiểm tra: nhập 4.

Xem đáp số

3024

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Chỉnh hợp theo modulo

Nhập n, k (0 ≤ k ≤ n ≤ 10⁶). In ra n × (n - 1) × … × (n - k + 1) chia lấy dư cho 10⁹ + 7.

Ví dụ: nhập 5 2 thì in ra 20.

Kiểm tra: nhập 1000000 500000.

Xem đáp số

765215884

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Tổ hợp

Bài 10. Tính C(n, k)

Nhập n, k (0 ≤ k ≤ n ≤ 60). In ra C(n, k), số cách chọn k đồ vật từ n đồ vật khác nhau.

Ví dụ: nhập 5 2 thì in ra 10.

Kiểm tra: nhập 60 30.

Xem đáp số

118264581564861424

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Chọn đội 3 nam 2 nữ

Lớp có a bạn nam và b bạn nữ (a, b ≤ 1000). Chọn một đội gồm đúng 3 nam và 2 nữ. Có bao nhiêu cách chọn?

Ví dụ: nhập 4 3 thì in ra 12.

Kiểm tra: nhập 10 8.

Xem đáp số

3360

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Đội có ít nhất một bạn nữ

Lớp có a bạn nam và b bạn nữ (a + b ≤ 60). Chọn một đội k bạn (k ≤ a + b) sao cho có ít nhất một bạn nữ. Có bao nhiêu cách?

Ví dụ: nhập 3 2 2 thì in ra 7.

Kiểm tra: nhập 10 8 5.

Xem đáp số

8316

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Đường chéo của đa giác

Một đa giác lồi có n cạnh (3 ≤ n ≤ 10⁹). Có bao nhiêu đường chéo?

Ví dụ: nhập 5 thì in ra 5.

Kiểm tra: nhập 20.

Xem đáp số

170

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Nhóm có mặt bạn An

Có n bạn (n ≤ 60), trong đó có An. Chọn một nhóm k bạn (1 ≤ k ≤ n) sao cho có An. Có bao nhiêu cách?

Ví dụ: nhập 4 2 thì in ra 3.

Kiểm tra: nhập 10 4.

Xem đáp số

84

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Dãy nhị phân có đúng k số 1

Có bao nhiêu dãy nhị phân độ dài n có đúng k chữ số 1? Nhập n, k (0 ≤ k ≤ n ≤ 60).

Ví dụ: nhập 4 2 thì in ra 6.

Kiểm tra: nhập 20 7.

Xem đáp số

77520

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Ra đề có ít nhất hai câu khó

Ngân hàng có a câu dễ và b câu khó (a + b ≤ 60). Một đề gồm k câu khác nhau, có ít nhất 2 câu khó. Có bao nhiêu đề khác nhau (không tính thứ tự câu)?

Ví dụ: nhập 3 2 2 thì in ra 1.

Kiểm tra: nhập 10 6 5.

Xem đáp số

2856

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Tổ hợp trên hình

Bài 17. Tam giác từ n điểm

Trên mặt phẳng có n điểm (n ≤ 10⁶), không có ba điểm nào thẳng hàng. Có bao nhiêu tam giác có ba đỉnh là ba trong số các điểm đó?

Ví dụ: nhập 4 thì in ra 4.

Kiểm tra: nhập 12.

Xem đáp số

220

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Tam giác trên lưới điểm

Có m × n điểm xếp thành lưới m hàng, n cột (m, n ≤ 6), các điểm cách đều nhau. Có bao nhiêu tam giác có ba đỉnh là ba điểm của lưới?

Ví dụ: nhập 2 2 thì in ra 4.

Kiểm tra: nhập 3 4.

Xem đáp số

200

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Hai ô cùng hàng hoặc cùng cột

Bảng ô vuông có m hàng, n cột (m, n ≤ 10⁶). Có bao nhiêu cách chọn 2 ô khác nhau nằm cùng một hàng hoặc cùng một cột?

Ví dụ: nhập 2 2 thì in ra 4.

Kiểm tra: nhập 8 8.

Xem đáp số

448

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Đường đi bắt buộc qua một điểm

Trên lưới, đi từ điểm (0, 0) đến (m, n), mỗi bước sang phải 1 hoặc lên trên 1 (m, n ≤ 30). Có bao nhiêu đường đi bắt buộc đi qua điểm (p, q) với 0 ≤ p ≤ m, 0 ≤ q ≤ n? Nhập m, n, p, q.

Ví dụ: nhập 2 2 1 1 thì in ra 4.

Kiểm tra: nhập 5 5 2 3.

Xem đáp số

100

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 5. Chia kẹo, chọn có lặp, tam giác Pascal

Bài 21. Chia kẹo, mỗi bạn ít nhất một viên

Chia n viên kẹo giống nhau cho k bạn (1 ≤ k ≤ n ≤ 60), mỗi bạn được ít nhất 1 viên và chia hết số kẹo. Có bao nhiêu cách chia?

Ví dụ: nhập 4 2 thì in ra 3.

Kiểm tra: nhập 10 3.

Xem đáp số

36

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 22. Chia kẹo, có bạn được không viên nào

Chia n viên kẹo giống nhau cho k bạn (n ≤ 50, 1 ≤ k ≤ 10), có thể có bạn không được viên nào, và phải chia hết số kẹo. Có bao nhiêu cách chia?

Ví dụ: nhập 2 2 thì in ra 3.

Kiểm tra: nhập 10 3.

Xem đáp số

66

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 23. Chọn số không liền nhau

Chọn k số khác nhau từ 1, 2, …, n sao cho không có hai số liên tiếp nào được chọn (n ≤ 60). Có bao nhiêu cách?

Ví dụ: nhập 5 2 thì in ra 6.

Kiểm tra: nhập 10 3.

Xem đáp số

56

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 24. Số có chữ số tăng dần

Có bao nhiêu số có đúng n chữ số mà các chữ số tăng dần từ trái sang phải (ví dụ 1359)? Nhập n (1 ≤ n ≤ 10).

Ví dụ: nhập 2 thì in ra 36.

Kiểm tra: nhập 3.

Xem đáp số

84

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 25. Số có chữ số không giảm

Có bao nhiêu số có đúng n chữ số mà các chữ số không giảm từ trái sang phải (ví dụ 1135)? Nhập n (1 ≤ n ≤ 30).

Ví dụ: nhập 2 thì in ra 45.

Kiểm tra: nhập 3.

Xem đáp số

165

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 26. Hàng thứ n của tam giác Pascal

Nhập n (0 ≤ n ≤ 60). In ra hàng thứ n của tam giác Pascal: C(n, 0), C(n, 1), …, C(n, n), cách nhau một dấu cách.

Ví dụ: nhập 3 thì in ra 1 3 3 1.

Kiểm tra: nhập 6.

Xem đáp số

1 6 15 20 15 6 1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.