Lý thuyết Tập hợp
I. Mở đầu về Toán học tổ hợp
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.
II. Lý thuyết tập hợp
1. Định nghĩa tập hợp
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ụ, 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à .
2. Tập hợp con (Subset)
Nếu như mọi phần tử của tập hợp cũng là các phần tử của tập hợp thì gọi là tập hợp con của . Kí hiệu:
hoặc có thể viết là:
nghĩa là là tập cha của hay chứ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 là tập con của tập hợp nhưng không bằng thì 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:
và được gọi là tập cha không tầm thường (proper superset) của kí hiệu:
Một tập hợp 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 ) 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 .
Hai tập hợp và gọi là bằng nhau nếu như là tập con của và cũng là tập con của kí hiệu:
Ví dụ:
- .
- .
- .
3. Phân hoạch tập hợp
Giả sử có một họ các tập con gồm tập con của tập hợp . Khi đó, được gọi là một phân hoạch của tập hợp khi và chỉ khi:
- Họ không chứa tập hợp rỗng: .
- Hợp của các tập con trong bằng : .
- Giao của bất kỳ hai tập hợp nào trong đều là tập rỗng: .
Ví dụ, tập hợp có phân hoạch là:
- .
- .
- .
- .
- .
4. Các phép toán trên tập hợp
Xét hai tập hợp và ta có các phép toán sau trên hai tập hợp và :
a) Phép lấy phần bù
Phần bù (complement) của trong kí hiệu hoặc là tập hợp các phần tử của mà không thuộc :
Ví dụ: Phần bù của trong tập số tự nhiên là:
b) Phép hợp
Hợp (Union) của và kí hiệu là tập hợp các phần tử thuộc vào hoặc thuộc vào :
Ví dụ: .
c) Phép giao
Giao (Intersection) của và , kí hiệu là tập các phần tử đồng thời thuộc cả và :
Ví dụ: .
d) Phép lấy hiệu
Phép lấy hiệu (difference) giữa và kí hiệu là tập hợp các phần tử thuộc nhưng không thuộc :
Ví dụ: .
5. Tính chất của các phép toán trên tập hợp
Kết hợp:
Giao hoán:
Phân phối:
Đối ngẫu (Luật De Morgan):
1.5. Tích Descartes của các tập hợp
Tích Descartes ghép hai tập hợp:
Tích Descartes mở rộng ghép nhiều tập hợp:
II. 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).
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 phương án khác nhau, trong đó:
- Phương án thứ nhất có cách thực hiện.
- Phương án thứ hai có cách thực hiện.
- Phương án thứ có cách thực hiện.
thì tổng số cách hoàn thành công việc đã cho là: .
Đối với lý thuyết tập hợp, nguyên lí cộng được phát biểu như sau: Nếu và là hai tập hợp rời nhau thì:
với là số lượng phần tử của hai tập hợp và .
Nguyên lí cộng mở rộng cho nhiều tập hợp con rời nhau: Nếu là một phân hoạch của tập hợp thì:
Ví dụ: Đếm số lượng số có chữ số có đúng chữ số
Lời giải: Gọi số đó là các trường hợp có thể xảy ra là: . Có khả năng chọn số khả năng chọn số khả năng chọn số và khả năng chọn số . Vậy kết quả là tổng số cách chọn của các trường hợp: .
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 giai đoạn liên tiếp, trong đó:
- Giai đoạn có cách thực hiện.
- Giai đoạn có cách thực hiện.
- Giai đoạn có cách thực hiện.
thì tổng số cách để hoàn thành công việc là: .
Đố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 thành phần nếu mỗi bộ có phương án lựa chọn thì tổng số bộ được tạo ra là tích số của các khả năng này: .
Hệ quả: .
Ví dụ: Từ Hà Nội đến Huế có tuyến xe khác nhau, từ Huế tới Thành phố Hồ Chí Minh có 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 giai đoạn bắt buộc: Giai đoạn là đi từ Hà Nội tới Huế, giai đoạn này có cách làm ( tuyến xe khác nhau); giai đoạn là đi từ Huế tới Thành phố Hồ Chí Minh, giai đoạn này có 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à cách.
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 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ó cách để hoàn thành việc tạo ra một số có chữ số có chứa chữ số nhưng chúng ta có thể bỏ bớt đi 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 giai đoạn liên tiếp nhau, nghĩa là giai đoạn thứ chỉ được phép thực hiện sau khi đã thực hiện xong các giai đoạn 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ế.
III. 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.
1. Chỉnh hợp lặp
Xét tập hữu hạn gồm phần tử . Một chỉnh hợp lặp chập của phần tử là một bộ có thứ tự gồm phần tử củ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 của sẽ là :
Cài đặt: Tính số lượng chỉnh hợp lặp chập của đưa ra kết quả sau khi chia cho và lấy số dư:
long long M = 1e9 + 7;
long long repetition_permutation(long long N, long long K)
{
if (K == 0)
return 1;
long long half = repetition_permutation(N, K / 2) % M;
if (K % 2 == 0)
return (half * half) % M;
else
return ((half * half) % M * (N % M)) % M;
}
2. Chỉnh hợp không lặp
Một chỉnh hợp không lặp chập của phần tử là một bộ có thứ tự gồm thành phần lấy từ 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ứ mỗi thành phần có số cách chọn giảm đi . Theo nguyên lí nhân, tổng số cách chọn là . Do đó số chỉnh hợp không lặp chập của là:
Cài đặt: Tính số lượng chỉnh hợp không lặp chập của đưa ra kết quả sau khi chia cho và lấy số dư:
long long M = 1e9 + 7;
long long distinct_permutation(long long N, long long K)
{
long long res = 1;
for (long long i = N - K + 1; i <= N; ++i)
res = ((res % M) * (i % M)) % M;
return res;
}
3. Tổ hợp không lặp
Một tổ hợp chập của phần tử là một bộ không xét đến thứ tự gồm thành phần khác nhau lấy từ 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:
Một số tính chất khá quan trọng của tổ hợp cần ghi nhớ:
- .
- .
- .
- chính là số lượng dãy nhị phân độ dài mà có đúng số vì ta chọn ra vị trí khác nhau trong vị trí để đặt làm số .
Cài đặt: Đếm số lượng tổ hợp chập của đưa ra kết quả sau khi chia cho 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).
*/
long long M = 1e9 + 7;
long long modular_exponentiation(long long A, long long B, long long M) // Lũy thừa modulo A^B % M.
{
if (B == 0)
return 1;
long long half = modular_exponentiation(A, B / 2, M) % M;
if (B & 1)
return ((half * half) % M * (A % M)) % M;
else
return (half * half) % M;
}
long long modular_inverse(long long A, long long M) // Nghịch đảo modulo M của A.
{
return modular_exponentiation(A, M - 2, M);
}
long long ckn(long long N, long long K)
{
long long x = 1, y = 1;
for (long long i = N - K + 1; i <= N; ++i) // x = (N - K + 1) * ... * N.
x = (x * i) % M;
for (long long i = 1; i <= K; ++i) // y = K!
y = (y * i) % M;
y = modular_inverse(y, M); // Tính (1/y) % M.
long long res = (x * y) % M; // Kết quả cuối cùng là C(K, N).
return res;
}
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 của phần tử là một cách chọn ra 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 của là:
Một tính chất rất thú vị của tổ hợp lặp đó là: chính là số nghiệm nguyên không âm của phương trình: với là hằng số nguyên dương.
Cài đặt: Đếm số lượng tổ hợp chập của đưa ra kết quả sau khi chia cho 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)
*/
long long M = 1e9 + 7;
long long modular_exponentiation(long long A, long long B, long long M)
{
if (B == 0)
return 1;
long long half = modular_exponentiation(A, B / 2, M) % M;
if (B & 1)
return ((half * half) % M * (A % M)) % M;
else
return (half * half) % M;
}
long long modular_inverse(long long A, long long M)
{
return modular_exponentiation(A, M - 2, M);
}
long long repetition_ckn(int N, int K)
{
long long x = 1, y = 1;
for (long long i = N; i <= N + K - 1; ++i)
x = (x * i) % M;
for (long long i = 1; i <= K; ++i) // y = K!
y = (y * i) % M;
y = modular_inverse(y, M);
long long res = (x * y) % M;
return res;
}
5. Hoán vị
Một hoán vị của phần tử là một cách sắp xếp thứ tự các phần tử đó. Hoán vị của 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 do đó, số lượng hoán vị của là
Cài đặt: Đếm số lượng hoán vị của phần tử, đưa ra kết quả sau khi chia cho và lấy phần dư:
long long M = 1e9 + 7;
long long permutation(int N)
{
long long res = 1;
for (long long 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à 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ừ tới . 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 phần tử sẽ chính bằng .
- Hoán vị Josephus: Được phát biểu dưới dạng một trò chơi như sau: Cho người đứng quanh vòng tròn theo chiều kim đồng hồ được đánh số từ tới . Họ bắt đầu đếm từ người thứ nhất theo chiều kim đồng hồ, người nào đếm đến thì bị loại khỏi vòng tròn và người kế tiếp sẽ đếm lại từ . 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 người theo thứ tự mà họ bị loại khỏi vòng tròn thì ta được một hoán vị của dãy số gọi là hoán vị Josephus .
- Hoán vị derangements: Một hoán vị của phần tử được gọi là một derangement khi và chỉ khi . Số lượng derangements của là .
IV. Tài liệu tham khảo
- https://www.geeksforgeeks.org/eulerian-number/
- https://vnoi.info/wiki/translate/he/Number-Theory-5
- https://www.hackerearth.com/practice/notes/number-theory-ii/
- https://vnoi.info/wiki/translate/he/Number-Theory-7.md
- Tài liệu giáo khoa chuyên Tin quyển 1 - thầy Hồ Sĩ Đàm
©️ Tác giả: Vũ Quế Lâm từ Viblo
All Rights Reserved