I. Các khái niệm cơ bản

Toán tổ hợp là một chuyên đề lớn và có tính ứng dụng cao trong lập trình thi đấu, đặc biệt trong các bài toán đếm. Chuyên đề Toán học tổ hợp trong Tin học sẽ đề cập tới những vấn đề cơ bản và quan trọng nhất của Toán tổ hợp gắn liền với những bài toán của nó trong lập trình thi đấu. Nắm vững Toán học tổ hợp sẽ giúp cho các bạn có năng lực giải được nhiều bài toán khó về chủ đề số học trong lập trình thi đấu.
Trước khi đọc chuyên đề này, bạn đọc cần nắm vững những kiến thức lập trình căn bản, các kiến thức toán học về Số học đồng dư, Lũy thừa modulo và Phép nhân Ấn Độ, nhằm phục vụ cho quá trình lập trình giải các bài toán áp dụng các công thức tổ hợp phức tạp.

1. Lý thuyết tập hợp

1.1. Định nghĩa

Tập hợp (Sets) là khái niệm cơ bản nhất trong Toán học. Định nghĩa tập hợp là một tập gồm các phần tử phân biệt với nhau. Lấy ví dụ, $3,5,7$ là các phần tử phân biệt khi chúng ta xét từng số một, nhưng nếu nhóm ba số đó lại thì ta được một tập hợp gồm ba phần tử là $\{3,5,7\}$.

1.2. Tập hợp con (Subset)

Nếu như mọi phần tử của tập hợp $A$ cũng là các phần tử của tập hợp $B,$ thì $A$ gọi là tập hợp con của $B$. Kí hiệu:

$$A\subset B$$

hoặc có thể viết là:

$$B\supset A$$

nghĩa là $B$ là tập cha của $A,$ hay $B$ chứa $A$.

Quan hệ cha-con giữa các tập hợp còn được gọi là quan hệ chứa nhau (containment) hay quan hệ bao hàm (inclusion).

Nếu một tập hợp $A$ là tập con của tập hợp $B$ nhưng không bằng $B,$ thì $A$ gọi là tập con không tầm thường (proper subset) hay tập con chân chính, tập con thực sự của B, kí hiệu:

$$A⊊B$$

và $B$ được gọi là tập cha không tầm thường (proper superset) của $A,$ kí hiệu:

$$B⊋A$$

Một tập hợp $A$ khác rỗng luôn luôn có ít nhất hai tập hợp con là tập hợp rỗng (kí hiệu $\varnothing$) và chính nó. Hai tập hợp này gọi là các tập con tâm thường của $A$.

Hai tập hợp $A$ và $B$ gọi là bằng nhau nếu như $A$ là tập con của $B$ và $B$ cũng là tập con của $A,$ kí hiệu:

$$A=B$$

Ví dụ:

• $\{3,5\}\subset \{3,5,9,11\}$.
• $\{1,2,3,4\}\supset \{1,2\}$.
• $\{100,1000\}=\{100,1000\}$.

1.3. Phân hoạch tập hợp

Giả sử có một họ các tập con $P$ gồm $N$ tập con {p1,p2,…,pn}{p_1, p_2,…, p_n}{p1​,p2​,...,pn​} của tập hợp $X$. Khi đó, $P$ được gọi là một phân hoạch của tập hợp $X$ khi và chỉ khi:

• Họ $P$ không chứa tập hợp rỗng: $\varnothing \notin P$.
• Hợp của các tập con trong $P$ bằng $X$: (p1∪p2∪⋯∪pn)=X(p_1 cup p_2 cup cdots cup p_n) = X(p1​∪p2​∪⋯∪pn​)=X.
• Giao của bất kỳ hai tập hợp nào trong $P$ đều là tập rỗng: pi∩pj=∅;∀pi≠pjp_i cap p_j = emptyset; forall p_i ne p_jpi​∩pj​=∅;∀pi​​=pj​.

Ví dụ, tập hợp $\{1,2,3\}$ có $5$ phân hoạch là:

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

1.4. Các phép toán trên tập hợp

Xét hai tập hợp $A=\{1,2,3,4\}$ và $B=\{2,3,5,7\},$ ta có các phép toán sau trên hai tập hợp $A$ và $B$:

a) Phép lấy phần bù

Phần bù (complement) của $A$ trong $X,$ kí hiệu CXA,C_X^A,CXA​, hoặc A‾overline AA là tập hợp các phần tử của $X$ mà không thuộc $A$:

A‾={x∈X:x∉A}overline A = {x in X:x notin A}
A={x∈X:x∈/​A}

Ví dụ: Phần bù của $A$ trong tập số tự nhiên $N$ là:

A‾={x∈N∣x≠{1,2,3,4}}overline A = {x in N mid x ne {1, 2, 3, 4}}
A={x∈N∣x​={1,2,3,4}}

b) Phép hợp

Hợp (Union) của $A$ và $B,$ kí hiệu $A\cup B,$ là tập hợp các phần tử thuộc vào $A$ hoặc thuộc vào $B$:

$$A\cup B=\{x:x\in A\text{ hoặc }x\in B\}$$

Ví dụ:$A\cup B=\{1,2,3,4,5,7\}$.

c) Phép giao

Giao (Intersection) của $A$ và $B$, kí hiệu $A\cap B,$ là tập các phần tử đồng thời thuộc cả $A$ và $B$:

$$A\cap B=\{x:x\in A\text{ vaˋ }x\in B\}$$

Ví dụ:$A\cap B=\{2,3\}$.

d) Phép lấy hiệu

Phép lấy hiệu (difference) giữa $A$ và $B,$ kí hiệu $AB,$ là tập hợp các phần tử thuộc $A$ nhưng không thuộc $B$:

$$AB=\{x:x\in A\text{ vaˋ }x\notin B\}$$

Ví dụ:$AB=\{1,4\}$.

1.5. Tính chất của các phép toán trên tập hợp

Kết hợp:

$$(A\cup B)\cup C=A\cup (B\cup C)$$

$$(A\cap B)\cap C=A\cap (B\cap C)$$

Giao hoán:

$$A\cup B=B\cup A$$

$$A\cap B=B\cap A$$

Phân phối:

$$A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$$

$$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$$

Đối ngẫu (Luật De Morgan):

A∪B‾=A‾∩B‾overline {A cup B} = overline A cap overline B
A∪B=A∩B

A∩B‾=A‾∪B‾overline {A cap B} = overline A cup overline B
A∩B=A∪B

1.5. Tích Descartes của các tập hợp

Tích Descartes ghép hai tập hợp:

$$A\times B=\{(a,b)\mid a\in A,b\in B\}$$

Tích Descartes mở rộng ghép nhiều tập hợp:

A1×A2×…×Ak={(a1,a2,…,ak)∣ai∈Ai,1≤i≤k}A_1 times A_2 times … times A_k = {(a_1, a_2, …, a_k) mid a_i in A_i, 1 le i le k }
A1​×A2​×...×Ak​={(a1​,a2​,...,ak​)∣ai​∈Ai​,1≤i≤k}

2. Nguyên lí cộng và nguyên lí nhân

Nguyên lí cộng và nguyên lí nhân là những nguyên lí cơ bản của tổ hợp, được sử dụng rộng rãi trong các bài toán đếm, còn được gọi là quy tắc cộng (sum rule) và quy tắc nhân (product rule).

2.1. Nguyên lí cộng

Định nghĩa: Nếu như có một công việc mà ta có thể thực hiện theo $N$ phương án khác nhau, trong đó:

• Phương án thứ nhất có m1m_1m1​ cách thực hiện.
• Phương án thứ hai có m2m_2m2​ cách thực hiện.
  $...$
• Phương án thứ $N$ có mnm_nmn​ cách thực hiện.

thì tổng số cách hoàn thành công việc đã cho là: m1+m2+m3+⋯+mnm_1 + m_2 + m_3 + cdots + m_nm1​+m2​+m3​+⋯+mn​.

Đối với lý thuyết tập hợp, nguyên lí cộng được phát biểu như sau: Nếu $A$ và $B$ là hai tập hợp rời nhau thì:

$$|A\cup B|=|A|+|B|$$

với $|A|,|B|$ là số lượng phần tử của hai tập hợp $A$ và $B$.

Nguyên lí cộng mở rộng cho nhiều tập hợp con rời nhau: Nếu {A1,A2,…,Ak}{A_1, A_2,…, A_k}{A1​,A2​,...,Ak​} là một phân hoạch của tập hợp $X$ thì:

∣X∣=∣A1∣+∣A2∣+…+∣Ak∣|X| = |A_1| + |A_2| + … + |A_k|
∣X∣=∣A1​∣+∣A2​∣+...+∣Ak​∣

Ví dụ: Đếm số lượng số có $4$ chữ số có đúng $3$ chữ số $9?$

Lời giải: Gọi số đó là abcd‾,overline {abcd},abcd, các trường hợp có thể xảy ra là: {a999‾,9b99‾,99c9‾,999d‾}{overline {a999}, overline {9b99}, overline{99c9}, overline{999d} }{a999,9b99,99c9,999d}. Có $9$ khả năng chọn số $a,$$10$ khả năng chọn số $b,$$10$ khả năng chọn số $c$ và $10$ khả năng chọn số $d$. Vậy kết quả là tổng số cách chọn của các trường hợp: $9+10+10+10=39$.

2.2. Nguyên lí nhân

Định nghĩa: Nếu một công việc phải hoàn thành thông qua $N$ giai đoạn liên tiếp, trong đó:

• Giai đoạn $1$ có m1m_1m1​ cách thực hiện.
• Giai đoạn $2$ có m2m_2m2​ cách thực hiện.
  $...$
• Giai đoạn $N$ có mnm_nmn​ cách thực hiện.

thì tổng số cách để hoàn thành công việc là: m1×m2×⋯×mnm_1 times m_2 times cdots times m_nm1​×m2​×⋯×mn​.

Đối với lý thuyết tập hợp, nguyên lí nhân được phát biểu như sau: Xét một bộ có thứ tự gồm $k$ thành phần {a1,a2,…,ak},{a_1, a_2,…, a_k},{a1​,a2​,...,ak​}, nếu mỗi bộ aia_iai​ có mim_imi​ phương án lựa chọn $1\le i\le k$ thì tổng số bộ được tạo ra là tích số của các khả năng này: m1×m2×⋯×mnm_1 times m_2 times cdots times m_nm1​×m2​×⋯×mn​.

Hệ quả:∣A1×A2×⋯×Ak∣=∣A1∣×∣A2∣×⋯×∣Ak∣|A_1 times A_2 times cdots times A_k| = |A_1| times |A_2| times cdots times |A_k|∣A1​×A2​×⋯×Ak​∣=∣A1​∣×∣A2​∣×⋯×∣Ak​∣.

Ví dụ: Từ Hà Nội đến Huế có $7$ tuyến xe khác nhau, từ Huế tới Thành phố Hồ Chí Minh có $5$ tuyến xe khác nhau. Hỏi có bao nhiêu cách để đi từ Hà Nội tới Thành phố Hồ Chí Minh?

Lời giải: Ta chia công việc “Đi từ Hà Nội tới Thành phố Hồ Chí Minh” làm $2$ giai đoạn bắt buộc: Giai đoạn $1$ là đi từ Hà Nội tới Huế, giai đoạn này có $7$ cách làm ($7$ tuyến xe khác nhau); giai đoạn $2$ là đi từ Huế tới Thành phố Hồ Chí Minh, giai đoạn này có $5$ cách làm. Áp dụng nguyên lí nhân, ta có tổng số cách đi từ Hà Nội tới Thành phố Hồ Chí Minh là $7\times 5=35$ cách.

2.3. Phân biệt giữa nguyên lí nhân và nguyên lí cộng

Từ các ví dụ trên, ta nhận thấy sự khác biệt trong việc sử dụng nguyên lí nhân và nguyên lí cộng như sau:

• Nếu như khi thực hiện công việc, tồn tại $N$ phương án khác nhau nhưng nếu bỏ đi một phương án thì chúng ta vẫn hoàn thành được công việc đó bằng các phương án còn lại, khi đó ta áp dụng nguyên lí cộng. Chẳng hạn với bài toán ví dụ ở phần nguyên lí cộng, mặc dù có $4$ cách để hoàn thành việc tạo ra một số có $4$ chữ số có chứa $3$ chữ số $9,$ nhưng chúng ta có thể bỏ bớt đi $1$ cách thì vẫn tạo được số như ý muốn.
• Nếu như khi thực hiện công việc, cần phải thực hiện qua $N$ giai đoạn liên tiếp nhau, nghĩa là giai đoạn thứ $k$ chỉ được phép thực hiện sau khi đã thực hiện xong các giai đoạn $1,2,3,...,(k-1),$ và chỉ cần bỏ đi một giai đoạn thì công việc sẽ không thể hoàn thành, khi đó ta áp dụng nguyên lí nhân. Chẳng hạn với bài toán ví dụ ở phần nguyên lí nhân, nếu ta bỏ đi công đoạn đi từ Hà Nội tới Huế hoặc đi từ Huế tới Thành phố Hồ Chí Minh thì không thể nào đi được từ Hà Nội tới Huế.

3. Chỉnh hợp – Tổ hợp – Hoán vị

Chỉnh hợp, tổ hợp và hoán vị là những quy tắc đếm rất căn bản trong Toán học tổ hợp và thường xuyên được sử dụng trong các bài toán đếm. Dưới đây sẽ giới thiệu khái niệm, công thức và cài đặt C++ để tính toán các công thức khi cần thiết.

3.1. Chỉnh hợp lặp

Xét tập hữu hạn gồm $n$ phần tử A={a1,a2,…,an}A ={a_1, a_2,…, a_n}A={a1​,a2​,...,an​}. Một chỉnh hợp lặp chập $k$ của $n$ phần tử là một bộ có thứ tự gồm $k$ phần tử của $A,$ các phần tử có thể lặp lại. Theo nguyên lí nhân, số các chỉnh hợp lặp chập $k$ của $n$ sẽ là nkn^knk:

Pnk‾=nkoverline{P_n^k} = n^k
Pnk​​=nk

Cài đặt: Tính số lượng chỉnh hợp lặp chập $k$ của $n,$ đưa ra kết quả sau khi chia cho 109+710^9+7109+7 và lấy số dư:

longlong M =1e9+7;longlongrepetition_permutation(longlong N,longlong K){if(K ==0)return1;longlong half =repetition_permutation(N, K /2)% M;if(K %2==0)return(half * half)% M;elsereturn((half * half)% M *(N % M))% M;}

3.2. Chỉnh hợp không lặp

Một chỉnh hợp không lặp chập $k$ của $n$ phần tử $(k\le n)$ là một bộ có thứ tự gồm $k$ thành phần lấy từ $n$ phần tử của tập đã cho, các thành phần không được lặp lại. Để xây dựng một chỉnh hợp không lặp, ta xây dựng dần từng thành phần: Bắt đầu từ thành phần thứ nhất có n khả năng lựa chọn; từ thành phần thứ hai tới thành phần thứ $k,$ mỗi thành phần có số cách chọn giảm đi $1$. Theo nguyên lí nhân, tổng số cách chọn là $n\times (n-1)\times \cdots (n-k+1)$. Do đó số chỉnh hợp không lặp chập $k$ của $n$ là:

Pnk=n×(n−1)×⋯×(n−k+1)=n!(n−k)!P_n^k = ntimes (n – 1)times cdots times (n – k + 1) = frac{n!}{(n – k)!}
Pnk​=n×(n−1)×⋯×(n−k+1)=(n−k)!n!​

Cài đặt: Tính số lượng chỉnh hợp không lặp chập $k$ của $n,$ đưa ra kết quả sau khi chia cho 109+710^9+7109+7 và lấy số dư:

longlong M =1e9+7;longlongdistinct_permutation(longlong N,longlong K){longlong res =1;for(longlong i = N - K +1; i <= N;++i)
        res =((res % M)*(i % M))% M;return res;}

3.3. Tổ hợp không lặp

Một tổ hợp chập $k$ của $n$ phần tử $(k\le n)$ là một bộ không xét đến thứ tự gồm $k$ thành phần khác nhau lấy từ $n$ phần tử của tập đã cho. Trong tổ hợp, các bộ gồm các phần tử giống nhau nhưng có cách sắp xếp khác nhau vẫn chỉ tính là một bộ – điều này khác với chỉnh hợp. Ta có công thức:

Cnk=n×(n−1)×⋯×(n−k+1)k!=n!k!×(n−k)!C^k_n = frac{n times (n – 1) times cdots times (n – k + 1)}{k!} = frac{n!}{k! times (n – k)!}
Cnk​=k!n×(n−1)×⋯×(n−k+1)​=k!×(n−k)!n!​

Một số tính chất khá quan trọng của tổ hợp cần ghi nhớ:

• Cnk=Cnn−kC^k_n = C^{n – k}_nCnk​=Cnn−k​.
• Cn0=Cnn=1C^0_n = C^n_n = 1Cn0​=Cnn​=1.
• Cnk=Cn−1k−1+Cn−1k (0<k<n)C^k_n = C^{k – 1}_{n – 1} + C^k_{n – 1} (0 < k < n)Cnk​=Cn−1k−1​+Cn−1k​ (0<k<n).
• CnkC^k_nCnk​ chính là số lượng dãy nhị phân độ dài $n$ mà có đúng $k$ số $1,$ vì ta chọn ra $k$ vị trí khác nhau trong $n$ vị trí để đặt làm số $1$.

Cài đặt: Đếm số lượng tổ hợp chập $k$ của $n,$ đưa ra kết quả sau khi chia cho 109+710^9 + 7109+7 và lấy phần dư:

/*
    - Rút gọn công thức tính C(K, N), ta có: 
        C(K, N) = (N - K + 1)(N - K + 2)...N / K!
                = [(N - K + 1)(N - K + 2)...N] * 1/K!
    - Áp dụng công thức nghịch đảo modulo, ta có:
        C(K, N) = [(N - K + 1)(N - K + 2)...N] * inverse_modulo(K!, M).
                = [(N - K + 1)(N - K + 2)...N] * (K!)^(M - 2)
                  (vì M = 10^9 + 7 là số nguyên tố).
   - Tới đây chỉ cần áp dụng các công thức modulo để tính toán C(K, N).
*/longlong M =1e9+7;longlongmodular_exponentiation(longlong A,longlong B,longlong M)// Lũy thừa modulo A^B % M.{if(B ==0)return1;longlong half =modular_exponentiation(A, B /2, M)% M;if(B &1)return((half * half)% M *(A % M))% M;elsereturn(half * half)% M;}longlongmodular_inverse(longlong A,longlong M)// Nghịch đảo modulo M của A.{returnmodular_exponentiation(A, M -2, M);}longlongckn(longlong N,longlong K){longlong x =1, y =1;for(longlong i = N - K +1; i <= N;++i)// x = (N - K + 1) * ... * N.
        x =(x * i)% M;for(longlong i =1; i <= K;++i)// y = K!
        y =(y * i)% M;
    y =modular_inverse(y, M);// Tính (1/y) % M.longlong res =(x * y)% M;// Kết quả cuối cùng là C(K, N).return res;}

3.4. Tổ hợp lặp

Tương tự như chỉnh hợp lặp, một tổ hợp lặp chập $k$ của $n$ phần tử là một cách chọn ra $k$ phần tử thuộc tập hợp, mỗi phần tử được phép chọn nhiều lần nhưng không xét tính thứ tự. Công thức tính số tổ hợp lặp chập $k$ của $n$ là:

Cnk‾=(n+k−1)!k!×(n−1)!overline{C^k_n} = frac{(n + k – 1)!}{k!times (n – 1)!}
Cnk​​=k!×(n−1)!(n+k−1)!​

Một tính chất rất thú vị của tổ hợp lặp đó là: Cnk‾overline{C^k_n}Cnk​​ chính là số nghiệm nguyên không âm của phương trình: x1+x2+⋯+xn=k,x_1 + x_2 + cdots + x_n = k,x1​+x2​+⋯+xn​=k, với $k$ là hằng số nguyên dương.

Cài đặt: Đếm số lượng tổ hợp chập $k$ của $n,$ đưa ra kết quả sau khi chia cho 109+710^9 + 7109+7 và lấy phần dư:

/* 
Tương tự với tính tổ hợp không lặp, ta cần rút gọn công thức tổ hợp lặp để tính toán dễ 
dàng hơn. Công thức sẽ trở thành: 
        C'(K, N) = [N * (N + 1) * ... * (N + K - 1)] / K!

Tới đây tính x = [N * (N + 1) * ... * (N + K - 1)] % (1e9 + 7), y = (1 / K!) % (1e9 + 7),
rồi đưa ra kết quả cuối cùng là (x * y) % (1e9 + 7)
*/longlong M =1e9+7;longlongmodular_exponentiation(longlong A,longlong B,longlong M){if(B ==0)return1;longlong half =modular_exponentiation(A, B /2, M)% M;if(B &1)return((half * half)% M *(A % M))% M;elsereturn(half * half)% M;}longlongmodular_inverse(longlong A,longlong M){returnmodular_exponentiation(A, M -2, M);}longlongrepetition_ckn(int N,int K){longlong x =1, y =1;for(longlong i = N; i <= N + K -1;++i)
        x =(x * i)% M;for(longlong i =1; i <= K;++i)// y = K!
        y =(y * i)% M;
    y =modular_inverse(y, M);longlong res =(x * y)% M;return res;}

3.5. Hoán vị

Một hoán vị của $n$ phần tử là một cách sắp xếp thứ tự các phần tử đó. Hoán vị của $n$ phần tử có thể coi như một trường hợp đặc biệt của chỉnh hợp không lặp với $k=n,$ do đó, số lượng hoán vị của $n$ là $n!$

Cài đặt: Đếm số lượng hoán vị của $n$ phần tử, đưa ra kết quả sau khi chia cho 109+710^9 + 7109+7 và lấy phần dư:

longlong M =1e9+7;longlongpermutation(int N){longlong res =1;for(longlong i =1; i <= N;++i)
        res =(res * i)% M;return res;}

Hoán vị có một số dạng đặc biệt cần lưu tâm:

• Hoán vị vòng quanh (Circular Permutation): Là dạng hoán vị mà $n$ phần tử của tập được xoay chuyển quanh một vòng tròn có các vị trí được đánh số từ $1$ tới $n$. Theo đó, dãy các hoán vị vòng quanh được tạo ra bằng cách: Đưa phần tử cuối cùng lên đầu dãy, sau đó đẩy tất cả các phần tử còn lại về phía sau một vị trí, ta được hoán vị vòng quanh thứ nhất; tiếp tục lặp lại thao tác này tới khi thu được chính dãy ban đầu thì kết thúc. Như vậy, tổng số hoán vị vòng quanh của $n$ phần tử sẽ chính bằng $n$.
• Hoán vị Josephus: Được phát biểu dưới dạng một trò chơi như sau: Cho $n$ người đứng quanh vòng tròn theo chiều kim đồng hồ được đánh số từ $1$ tới $n$. Họ bắt đầu đếm từ người thứ nhất theo chiều kim đồng hồ, người nào đếm đến $m$ thì bị loại khỏi vòng tròn và người kế tiếp sẽ đếm lại từ $1$. Trò chơi tiếp diễn cho đến khi vòng tròn không còn lại người nào. Nếu ta xếp số hiệu của $n$ người theo thứ tự mà họ bị loại khỏi vòng tròn thì ta được một hoán vị (j1,j2,…,jn)(j_1, j_2,…, j_n)(j1​,j2​,...,jn​) của dãy số $(1,2,...,n)$ gọi là hoán vị Josephus $(n,m)$.
• Hoán vị derangements: Một hoán vị {p1,p2,…,pn}{p_1, p_2,…,p_n}{p1​,p2​,...,pn​} của $n$ phần tử $\{1,2,...,n\}$ được gọi là một derangement khi và chỉ khi pi≠i (∀i:1≤i≤n)p_i ne i (forall i: 1 le i le n)pi​​=i (∀i:1≤i≤n). Số lượng derangements của $n$ là D(n)=n!∑k=0n(−1)k×1k!D(n) = n!sum_{k=0}^n(-1)^ktimes frac{1}{k!}D(n)=n!∑k=0n​(−1)k×k!1​.