Chỉnh hợp

Chỉnh hợp (không lặp) chập

$k$ của

$n$ là số cách chọn

$k$ phần tử trong tập hợp

$n$ phần tử không lặp và có phân biệt thứ tự.
Kí hiệu:

$P(n,k)$ hoặc

$P_n^k$
Ví dụ: cho tập hợp

$\{1,2,3\}$,

$P_3^2$ mang nghĩa có bao nhiêu cách chọn 2 phần tử trong 3 phần tử sao cho các phần tử không lặp lại và có phân biệt thứ tự các phần tử.

$P_3^2=6$ vì có 6 cách chọn:

$\{1,2\},\{2,1\},\{1,3\},\{3,1\},\{2,3\},\{3,2\}$. Để ý thấy rằng

$\{1,2\},\{2,1\}$ được tính là 2 cách chọn khác nhau vì chỉnh hợp có phân biệt thứ tự.

Công thức:

$P_n^k=\frac{n!}{(n-k)!}$

Lưu ý:

$P_n^n$ còn được gọi là hoán vị (có bao nhiêu cách sắp xếp

$n$ phần tử), có công thức là

$n!$

Công thức chỉnh hợp lặp chập

$k$ của

$n$:

$F_n^k=n^k$

Tổ hợp

Tổ hợp chập

$k$ của

$n$ là số cách chọn

$k$ phần tử trong tập hợp

$n$ phần tử không lặp và không phân biệt thứ tự.
Kí hiệu:

$C(n,k)$ hoặc

$C_n^k$ hoặc

$(\genfrac{}{}{0ex}{}{n}{k})$
Ví dụ: cho tập hợp

$\{1,2,3\}$,

$(\genfrac{}{}{0ex}{}{3}{2})=3$ vì có 3 cách chọn:

$\{1,2\},\{1,3\},\{2,3\}$. Để ý thấy rằng

$\{1,2\},\{2,1\}$ được tính là 1 cách chọn giống nhau vì tổ hợp không phân biệt thứ tự.

Công thức:

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}$

Một số tính chất:

$$(\genfrac{}{}{0ex}{}{n}{0})=(\genfrac{}{}{0ex}{}{n}{n})=1$$

$$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n}{n-k})$$

$$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-1}{k})+(\genfrac{}{}{0ex}{}{n-1}{k-1})$$

$$\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})=(\genfrac{}{}{0ex}{}{n}{0})+(\genfrac{}{}{0ex}{}{n}{1})+(\genfrac{}{}{0ex}{}{n}{2})+\cdots +(\genfrac{}{}{0ex}{}{n}{n})=2^n$$

$$(\genfrac{}{}{0ex}{}{n}{k})=\frac{P(n,k)}{k!}$$

Công thức tổ hợp lặp chập

$k$ của

$n$:

$K_n^k=C_{n+k-1}^k$

Code

Code theo công thức định nghĩa:

long long factorial(long long x) {
    long long res = 1;
    for(int i = 1; i <= x; ++i)
        res = res * (long long)i;
    return res;
}

long long nCk(long long n, long long k) {
    return factorial(n) / (factorial(k) * factorial(n - k));
}

Tuy nhiên có thể thấy cách này khá tốn thời gian khi phải tính giai thừa nhiều lần, mỗi lần tính sẽ mất độ phức tạp

$\approx O(n+k)$, nếu có

$q$ truy vấn phải tính

$q$ lần thì sẽ mất

$O(q\cdot (n+k))$.
Vì vậy, ta có thể preprocess trước một mảng

$fact[]$ lưu lại giai thừa của các số:

const int MAXN = ...

long long fact[MAXN + 1];

void preprocess() {
    fact[0] = 1;
    for(int i = 1; i <= MAXN; ++i)
        fact[i] = fact[i - 1] * (long long)i;
}

long long nCk(long long n, long long k) {
    return fact[n] / (fact[k] * fact[n - k]);
}

Như vậy chỉ cần mất

$O(n)$ để preprocess ban đầu, sau đó với mỗi truy vấn chỉ mất

$O(1)$ để tính, vậy tổng là

$O(n+q)$.

Nhưng thật ra, chỉ cần

$n$ khoảng từ 20 trở lên, ta đã có thể bị tràn số do giá trị của giai thừa là rất lớn. Vì thế, hầu hết các bài có tính tổ hợp đều cho mod với một số nào đó vì giá trị của tổ hợp có thể rất lớn. Để ý trong công thức có dấu chia, vì thế phải dùng tới nghịch đảo modular:

const int MAXN = ...;
const long long mod = ...;

long long fact[MAXN + 1], inv[MAXN + 1], inv_fact[MAXN + 1];

void preprocess() {
    fact[0] = inv[0] = inv[1] = inv_fact[0] = inv_fact[1] = 1;
    for(int i = 1; i <= MAXN; ++i)
        fact[i] = fact[i - 1] * (long long)i % mod;
    for(int i = 2; i <= MAXN; ++i) {
        inv[i] = mod - (long long)(mod / i) * inv[mod % i] % mod;
        inv_fact[i] = inv_fact[i - 1] * inv[i] % mod;
    }
}

long long nCk(long long n, long long k) {
    return fact[n] * (inv_fact[k] * inv_fact[n - k] % mod) % mod;
}

Và độ phức tạp vẫn là

$O(n+q)$.

Ngoài ra, còn một cách tính dựa vào công thức:

$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-1}{k})+(\genfrac{}{}{0ex}{}{n-1}{k-1})$:

const int MAXN = ...;
const long long mod = ...;

long long C[MAXN + 1][MAXN + 1];

long long nCk(int n, int k) {
    if(k > n)
        return 0;
    if(C[n][k] != -1)
        return C[n][k];
    if(k == 0 || k == n)
        C[n][k] = 1;
    else
        C[n][k] = (nCk(n - 1, k) + nCk(n - 1, k - 1)) % mod;
    return C[n][k];
}

Lưu ý, ở đầu tiên trước các truy vấn phải fill full mảng C thành -1.
Nếu có

$q$ truy vấn tính, đpt sẽ là

$q+n^2$.