---
title
Tổ hợp cơ bản
---

Tổ hợp cơ bản
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# Giới thiệu chung
[ T, Ổ, H, Ợ, P, TỔ, TH, TỢ, TP, ỔH, ỔỢ, ỔP, HỢ, HP, ỢP, TỔH, TỔỢ, TỔP, THỢ, THP, TỢP, ỔHỢ, ỔHP, ỔỢP, HỢP, TỔHỢ, TỔHP, TỔỢP, THỢP, ỔHỢP, TỔHỢP ]

Hoán vị, chỉnh hợp và tổ hợp là một trong những chủ đề toán học rất phổ biến và kinh điển trong tin học nói chung và lập trình thi đấu nói riêng. Ở trên tựa đề chính là các tổ hợp cách tạo ra một xâu mới từ các kí tự trong xâu TỔHỢP mà không hoán đổi vị trí của chúng. Vậy, làm sao để nhanh chóng tính ra được con số này? Hãy đọc bài viết này của chúng mình để biết nhé!

# Quy tắc cộng và quy tắc nhân
## Quy tắc cộng
- Giả sử một công việc có thể thực hiện theo phương án *A* hoặc phương án *B*. Phương án *A* có $m$ cách thực hiện, phương án *B* có $n$ cách thực hiện không trùng với bất kì cách nào của phương án *A*. Khi đó, công việc có thể thực hiện theo $m+n$ cách.
- **Ví dụ**: Lớp A có 30 học sinh, lớp B có 40 học sinh, số cách để chọn một học sinh bất kì thuộc 1 trong 2 lớp A và B là: $30+40=70$.

## Quy tắc nhân
- Giả sử một công việc được chia thành hai công đoạn. Công đoạn thứ nhất có $m$ cách thực hiện và ứng với mỗi cách đó có $n$ cách thực hiện công đoạn thứ hai. Khi đó, công việc có thể thực hiện theo $m \cdot n$ cách.
- Tương tự, nếu có $n$ công đoạn, công đoạn thứ nhất có $n_1$ cách thực hiện và ứng với mỗi cách đó có $n_2$ cách thực hiện công đoạn thứ hai...$n_n$ cách để thực hiện công đoạn thứ $n$. Như vậy số cách khác nhau để thực hiện được công việc trên là: $n_1 \cdot n_2 \cdot n_3 \cdot...\cdot n_{n-1} \cdot n_n$.
- **Ví dụ**: Bạn C có 3 chiếc áo, 5 chiếc quần và 7 đôi giày, số bộ đồ khác nhau gồm 1 áo, 1 quần và một đôi giày mà bạn C có thể phối là: $3 \cdot 5 \cdot 7 = 105$ cách.

# Hoán vị
- Cho tập hợp $A$ có $n$ phần tử $(n \ge 1)$. Mỗi cách sắp xếp $n$ phần tử của $A$ theo một thứ tự gọi là một **hoán vị** các phần tử đó. Số hoán vị của một tập hợp có $n$ phần tử được kí hiệu là: $P_n$.
- **Ví dụ**: Tập hợp $a$ = {$1, 2, 3$} có $6$ hoán vị khác nhau:
1. {$1, 2, 3$}
2. {$1, 3, 2$}
3. {$2, 1, 3$}
4. {$2, 3, 1$}
5. {$3, 1, 2$}
6. {$3, 2, 1$}
- Xét một tập hợp $B$ có $n$ phần tử, số cách chọn phần tử ở vị trí $1$ là: $n$ cách tương ứng với $n$ số khác nhau trong tập hợp $B$. Số cách chọn phần tử ở vị trí $2$ sao cho phần tử này khác với phần tử đầu tiên là: $n-1$ phần tử. Số cách chọn phần tử ở vị trí $3$ sao cho phần tử này khác với $2$ phần tử ở vị trí đầu tiên: $n-3$ cách,...số cách chọn phần tử ở vị trí $n$ là: $1$ cách.
- Theo quy tắc nhân, ta có: Số hoán vị khác nhau của một tập hợp có $n$ phần tử là: $$P_n = n(n-1)(n-2)...2\cdot 1 = n!$$

# Chỉnh hợp
- Cho tập hợp $A$ có $n$ phần tử $(n \ge 1)$ và số nguyên $k$ với $1 \le k \le n$. Mỗi cách lấy $k$ phần tử của $A$ và sắp xếp chúng theo một thứ tự gọi là một **chỉnh hợp** chập $k$ của $n$ phần tử đó. Số tổ hợp chập $k$ của $n$ kí hiệu là: $A^k_n$.
- Tương tự như cách tính số **hoán vị**, số cách chọn phần tử đầu tiên trong $k$ số là: $n$ cách. Số cách chọn phần tử thứ 2 trong $k$ phần tử sao cho phần tử này khác với phần tử đầu tiên là: $n-1$ cách. Tương tự, số cách để chọn phần tử thứ $k$ là: $n-k+1$ cách.
- Theo quy tắc nhân, ta có: Số chỉnh hợp chập $k$ của $n$ là: $$A^k_n=n(n-1)(n-2)...(n-k+1) = {n! \over (n-k)!}$$
- **Ví dụ:** Tập hợp $a$ = {$1, 2, 3$} có 3 phần tử, có $6$ chỉnh hợp chập $2$ của $3$ khác nhau:
- {$1, 2$}
- {$2, 1$}
- {$1, 3$}
- {$3, 1$}
- {$2, 3$}
- {$3, 1$}

:::info
**Giải thích**
Ta cần chọn k phần tử, ta sẽ chia công việc thành $k$ công đoạn:
- Công đoạn 1: chọn phần tử đầu tiên: có $n$ cách chọn
- Công đoạn 2: chọn phần tử thứ 2 khác phần tử đầu: có $n-1$ cách chọn
- Công đoạn 3: chọn phần tử thứ 3 khác 2 phần tử đầu: có $n-2$ cách chọn
...
- Công đoạn k: chọn phần tử thứ k khác k-1 phần tử đầu: có $n-k+1$ cách chọn
Áp dụng quy tắc nhân cho $k$ công đoạn, ta sẽ được công thức chỉnh hợp
:::

# Tổ hợp
- Cho tập hợp $A$ có $n$ phần tử $(n \ge 1)$. Mỗi tập con gồm $k$ phần tử của $A$ được gọi là một **tổ hợp** chập $k$ của $n$ phần tử. Số tổ hợp chập $k$ của $n$ kí hiệu là: $C^k_n$.
- Số tổ hợp chập $k$ của $n$ là: $$C^k_n = {n! \over k!(n-k)!}$$
- **Ví dụ:** Tập hợp $a$ = {$1, 2, 3$} có 3 phần tử, có $6$ chỉnh hợp chập $2$ của $3$ khác nhau:
- {$1, 2$}
- {$1, 3$}
- {$2, 3$}

:::info
**Giải thích**
Ta có thể thấy, điểm khác nhau giữa tổ hợp và chỉnh hợp là chỉnh hợp thì có xếp thứ tự các phần tử của tập hợp con, còn tổ hợp thì không.
Với mỗi tập con $k$ phần tử của $a$ ứng với $1$ tổ hợp, có đến $k!$ chỉnh hợp khác nhau. Khi đó ta thấy: $$A^k_n = k!C^k_n$$
$\Rightarrow C^k_n = {A^k_n \over k!} = {n! \over k!(n-k)!}$
:::

# Cách tính hoán vị, tổ hợp, chỉnh hợp trong C++
## Dùng công thức cơ bản
- Cách đơn giản nhất để tính hoán vị, tổ hợp, chỉnh hợp trong C++ đó là sử dụng một mảng `f` để lưu lại các phép tính giai thừa từ 1 đến giới hạn của đề bài và sử dụng các công thức ở phần trên. Vì kích thước tối đa của mảng trong C++ là khoảng hơn $10^7$ nên cách làm này chỉ áp dụng với những bài có $k, n \le 10^7$.
- Cài đặt:

#include <bits/stdc++.h>

using namespace std;

long long f[10000005];

void factorial(int n)
{
    f[0] = 1;
    for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i;
}

long long Akn(int k, int n)
{
    return f[n] / f[n - k];
}

long long Ckn(int k, int n)
{
    return f[n] / (f[k] * f[n - k]);
}

- Tuy nhiên, thường các tổ hợp có kết quả rất lớn, ví dụ $C^{25}_{50} = 126410606437752$, thậm chí với $n$ lớn hơn có thể dẫn đến tràn số
- Đó là lý do mà đa số các bài tập liên quan đến tổ hợp, đề bài sẽ yêu cầu in ra kết quả chia dư cho 1 số nguyên tố (thương là $10^9+7$ hoặc $998244353$).
- Ở bài viết [Toán và số học](https://hackmd.io/EomwVdxnT663LQaC80_Zig#%C4%90%E1%BB%93ng-d%C6%B0-th%E1%BB%A9c), ta đã được học cách xử lí phép cộng, trừ, nhân có modulo. Tuy nhiên, để tính tổ hợp ta còn cần phải sử dụng đến phép chia modulo. Khi này, ta cần sử dụng định lý sau:

### Định lý [Fermat nhỏ](https://vi.wikipedia.org/wiki/%C4%90%E1%BB%8Bnh_l%C3%BD_nh%E1%BB%8F_Fermat)
Nó được phát biểu như sau: Nếu $p$ là một số nguyên tố, và với số nguyên $a$ bất kỳ thì: $$a^p \equiv a \text{ (mod m)}$$
- Áp dụng định lý Fermat nhỏ: $a^p \equiv a \text{ (mod p)}$.
- Chia 2 vế cho $a$ ta được: $a^{p-1} \equiv 1 \text{ (mod p)}$.
- Tiếp tục chia 2 vế cho $a$, ta được: $a^{p-2} \equiv a^{-1} \text{ (mod p)}$.
- Về mặt toán học, $a^{-1}$ chính là $1 \over a$.
- Vậy: $\frac{a}{b} \text{ (mod m)} = a * b^{-1} \text{ (mod m)} = a * b^{p - 2} \text{ (mod m)}$
- Trong phạm vi kiến thức của kì thi tuyển sinh 10, thường thì các bài toán tổ hợp nói riêng và các bài toán có yêu cầu kiến thức chia modulo nói chung sẽ sử dụng modulo là một số nguyên tố. Tuy nhiên, nếu bạn đọc muốn tìm hiểu sâu hơn về phần này thì có thể tham khảo thêm ***Nghịch đảo modulo*** ở [Series số học của HackerEarth được dịch lại trên VNOI Wiki](https://vnoi.info/wiki/Home#series-s%E1%BB%91-h%E1%BB%8Dc-c%E1%BB%A7a-hackerearth).
- Để sử dụng công thức trên, ta cần tối ưu bước tính $b^{p - 2}$ bằng thuật toán **Lũy thừa nhị phân** tính nhanh $a^b$

### Thuật toán lũy thừa nhị phân
- Nếu $b = 0$: $a^b = 1$.
- Nếu $b$ là số lẻ: $a^b = a^{b-1 \over 2} \space \times a^{b-1 \over 2} \space \times a$.
- Nếu $b$ là số chẵn: $a^b = a^{b \over 2} \space \times a^{b \over 2}$.
- Trong trường hợp $b \neq 0$, ta có thể chỉ cần tính thừa số $a^{b-1 \over 2}$ hoặc $a^{b \over 2}$ 1 lần.
::: spoiler **Cài đặt**

long long binpow(long long a, long long b, long long m)
{
    if(b == 0) return 1; // b = 0
    long long temp = binpow(a, b / 2, m);
    if(b % 2 == 1) return temp * temp % m * a % m; // b lẻ
    return temp * temp % m; // b chẵn
}

:::

### Ứng dụng định lý và thuật toán trên vào bài toán tính tổ hợp với đáp án modulo m
#### Hoán vị
- Bước tính hoán vị chỉ sử dụng phép nhân nên không có gì phức tạp:

void factorial(int n, long long m)
{
    f[0] = 1;
    for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i % m;
}

#### Chỉnh hợp
- Ta có: $$A^k_n = {n! \over (n-k)!} \text{ mod m} = {n! \times ((n-k)!)^{-1}} \text{ mod m} = {n! \times ((n-k)!)^{m-2}} \text{ mod m}$$

long long Akn(int k, int n, long long m)
{
    return f[n] * binpow(f[n - k], m - 2, m) % m;
}

#### Tổ hợp
- Ta có: $$C^k_n = {n! \over k!(n-k)!} \text{ mod m} = {n! \times (k!(n-k)!)^{-1}} \text{ mod m} = {n! \times (k!(n-k)!)^{m-2}} \text{ mod m}$$

long long Ckn(int k, int n, long long m)
{
    return f[n] * binpow(f[k] * f[n - k] % m, m - 2, m) % m;
}

- **Lưu ý 1:** Để tránh tràn số khi thực hiện phép nhân, mảng `f` ban đầu cần được khai báo với kiểu dữ liệu `long long`.
- **Lưu ý 2:** Vì có thể xảy ra trường hợp $k!(n - k)! > m$ nên để tránh tràn số khi luỹ thừa $m - 2$ thì ta phải truyền tham số `f[k] * f[n - k] % m` vào hàm `binpow` thay vì tham số `f[k] * f[n - k]`.

## Quy hoạch động bằng công thức $C^k_n = C^k_{n - 1} + C^{k - 1}_{n - 1}$
- Đối với những bài tập có $min(n * k, n * n) \le 10^7$ thì ta có thể quy hoạch động dựa trên công thức $C^k_n = C^k_{n - 1} + C^{k - 1}_{n - 1}$ và từ đó tính được $A^k_n = C^k_n * k!$.
:::spoiler Chứng minh công thức
$\displaystyle C^k_{n - 1} + C^{k - 1}_{n - 1}$
$\displaystyle = \frac{(n - 1)!}{k![(n - 1) - k]!} + \frac{(n - 1)!}{(k - 1)![(n - 1) - (k - 1)]!}$
$\displaystyle = \frac{(n - 1)!}{k!(n - k - 1)!} + \frac{(n - 1)!}{(k - 1)!(n - k)!}$
$\displaystyle = \frac{(n - 1)!}{k!(n - k)!\frac{1}{n - k}} + \frac{(n - 1)!}{k!\frac{1}{k}(n - k)!}$
$\displaystyle = \frac{(n - 1)!(n- k)}{k!(n - k)!} + \frac{(n - 1)!k}{k!(n - k)!}$
$\displaystyle = \frac{(n - 1)!(n - k) + (n - 1)!k}{k!(n - k)!}$
$\displaystyle = \frac{(n - 1)!(n - k + k)}{k!(n - k)!}$
$\displaystyle = \frac{(n - 1)!n}{k!(n - k)!}$
$\displaystyle = \frac{n!}{k!(n - k)!}$
$\displaystyle = C^k_n$
:::
- Ngoài ra, khi quy hoạch động, ta cũng phải nhớ trường hợp gốc là `dp[0][i] = dp[i][i] = 1` ($1 \le i \le k$) và `dp[0][i] = 1` ($1 \le i \le n$) vì $C^0_n = C^n_n = 1$.
- **Lưu ý:**
+ Trong một số bài tập, ta có thể sẽ gặp các trường hợp $C^k_n$, $A^k_n$ với $k > n$ (do đề bài không giới hạn $k \le n$ hoặc do cách ta cài đặt). Điều này đặc biệt nguy hiểm với các bài tập với giới hạn theo dạng $n * k \le 10^6$ chứ không phải $n, k \le 10^3$ vì ta sẽ phải sử dụng mảng/vector đúng theo kích thước $n$ và $k$ của đề bài nên có thể sẽ xảy ra việc truy cập vào vị trí nằm ngoài mảng/vector. Để xử lí vấn đề này thì ta nên thêm điều kiện `if (k <= n)` vào trong hàm tính $C^k_n$ và $P^k_n$.
+ Với những bài yêu cầu modulo thì ta vẫn modulo bình thường với phép nhân và phép cộng.
- Cài đặt:

#include <bits/stdc++.h>

using namespace std;

void factorial(int n)
{
    f[0] = 1;
    for (long long i = 1; i <= n; i++) f[i] = f[i - 1] * i;
}

void calc(int k, int n)
{
    for (int i = 0; i <= k; i++) dp[0][i] = dp[i][i] = 1;
    for (int i = k + 1; i <= n; i++) dp[0][i] = 1;
    for (int i = 1; i <= k; i++)
    {
        for (int j = i; j <= n; j++) dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
    }
}

long long Ckn(int k, int n)
{
    if (k <= n) return dp[k][n];
    else return 0;
}

long long Akn(int k, int n)
{
    if (k <= n) return dp[k][n] * f[k];
    else return 0;
}

- Khi output các kết quả của mảng 2 chiều `dp` ra thì ta có thể thấy rằng chúng tạo thành [tam giác Pascal](https://vi.wikipedia.org/wiki/Tam_giác_Pascal).

# Bài tập vận dụng
## [Codeforces - 1828C](https://codeforces.com/contest/1828/problem/C)
### Đề bài
Cho 2 mảng $a$ và $b$ có $n$ phần tử. Không có phần tử nào của $a$ bằng nhau. Tìm số cách xếp lại thứ tự của mảng $a$ sao cho $a_i > b_i$ ($1 \le i \le n$), modulo $10^9+7$. Hai cách sắp xếp được gọi là khác nhau nếu tồn tại ít nhất một vị trí mà hai phần tử tại vị trí đó của hai cách sắp xếp là khác nhau.

### Input
- Dòng đầu tiên gồm một số nguyên $t$ ($1 \le t \le 10^4$) là số lượng bộ test cần tính toán.
- Dòng đầu tiên của mỗi bộ test gồm một số nguyên $n$ ($1 \le n \le 2 * 10^5$).
- Dòng thứ hai của mỗi bộ test gồm $n$ số nguyên $a_i$ ($1 \le a_i \le 10^9$) là các phần tử của mảng $a$.
- Dòng thứ ba của mỗi bộ test gồm $n$ số nguyên $b_i$ ($1 \le b_i \le 10^9$) là các phần tử của mảng $b$.

Đảm bảo rằng tổng $n$ của các bộ test không vượt quá $2 * 10^5$.

### Output
- Cho mỗi bộ test, in ra một dòng là kết quả của bộ test đó, modulo $10^9+7$.

### Sample input

5
6
9 6 8 4 5 2
4 1 5 6 3 1
3
4 3 2
3 4 9
1
2
1
3
2 3 4
1 3 3
12
2 3 7 10 23 28 29 50 69 135 420 1000
1 1 2 3 5 8 13 21 34 55 89 144

### Sample output

32
0
1
0
13824

## [Bài 3 HSTP9 2022-2023](http://www.chuyentin.pro/2023/03/e-thi-hoc-sinh-gioi-lop-9-mon-tin-hoc_20.html)
### Đề bài
Cho một mảng $A$ có $n$ phần tử. Xét tất cả các đoạn con (**không liên tiếp**) có $K$ phần tử của mảng $A$, tính tổng của các số lớn nhất của các đoạn con này và modulo $10^9 + 7$.

### Input
- Dòng đầu tiên gồm hai số nguyên $n, K$ ($1 \le n \le 10^5$, $1 \le K \le 5$).
- Dòng thứ hai gồm $n$ số nguyên $A_i$ ($1 \le A_i \le 10^6$) là các phần tử của mảng $A$.

### Output
- Một dòng duy nhất là kết quả của bài toán, modulo $10^9 + 7$.

### Sample input

4 2
6 7 6 5

### Sample output

39

## [Codeforces - 1462E2](https://codeforces.com/contest/1462/problem/E2)
### Đề bài
Cho một mảng $a$ có $n$ phần tử là các số nguyên từ $1$ đến $n$. Mảng $a$ có thể chứa các phần tử giống nhau. Cho $m$ và $k$, tìm số lượng bộ $m$ phần tử của mảng $a$ sao cho phần tử lớn nhất lớn hơn phần tử nhỏ nhất không quá $k$ đơn vị. Tức là tìm số lượng bộ $m$ chỉ số $1 \le i_1 < i_2 < ... < i_m \le n$ của mảng $a$ sao cho $max(a_{i_1}, a_{i_2}, ..., a_{i_m}) - min(a_{i_1}, a_{i_2}, ..., a_{i_m}) \le k$. Kết quả được modulo $10^9 + 7$.
Ví dụ:
- Nếu $n = 4$, $m = 3$, $k = 2$ và $a = [1, 2, 4, 3]$ thì có **2** bộ $k$ phần tử của mảng $a$ thoả mãn đề bài ($i = 1, j = 2, z = 4$ và $i = 2, j = 3, z = 4$)
- Nếu $n = 4$, $m = 2$, $k = 1$ và $a = [1, 1, 1, 1]$ thì cả **4** bộ $k$ phần tử của mảng $a$ đều thoả mãn đề bài.

### Input
- Dòng đầu tiên gồm một số nguyên $t$ ($1 \le t \le 2 * 10^5$) là số lượng bộ test cần tính toán.
- Dòng đầu tiên của mỗi bộ test gồm ba số nguyên $n$, $m$, $k$ ($1 \le n \le 2 * 10^5$, $1 \le m \le 100$, $1 \le k \le n$).
- Dòng thứ hai của mỗi bộ test gồm $n$ số nguyên $a_i$ ($1 \le a_i \le n$) là các phần tử của mảng $a$.

Đảm bảo rằng tổng $n$ của các bộ test không vượt quá $2 * 10^5$.

### Output
- Cho mỗi bộ test, in ra một dòng là kết quả của bộ test đó, modulo $10^9 + 7$.

### Sample input

4
4 3 2
1 2 4 3
4 2 1
1 1 1 1
1 1 1
1
10 4 3
5 6 1 3 2 9 8 1 2 4

### Sample output

2
6
1
20

## [CSES - Distributing Apples](https://cses.fi/problemset/task/1716)
### Đề bài
Có $n$ bạn nhỏ và $m$ quả táo. Đếm số lượng cách chia táo cho các bạn nhỏ. Lưu ý rằng trong một cách chia, không nhất thiết bạn nào cũng có táo nhưng phải có ít nhất một bạn có táo. Kết quả được modulo $10^9 + 7$.

### Input
- Một dòng duy nhất gồm hai số nguyên $n$, $m$ ($1 \le n, m \le 10^6$)

### Output
- Một dòng duy nhất là kết quả của bài toán, modulo $10^9 + 7$.

### Sample input

3 2

### Sample output

6

## Bài tập thêm
- [CSES - Christmas Party](https://cses.fi/problemset/task/1717)
- [Codeforces - 1931G](https://codeforces.com/contest/1931/problem/G)

# Tài liệu tham khảo