+7

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 moduloPhé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ụ, 3,5,73, 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}\{3, 5, 7\}.

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

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

ABA \subset B

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

BAB \supset A

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

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 AA là tập con của tập hợp BB nhưng không bằng B,B, thì AA 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:

ABA \subsetneq B

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

BAB \supsetneq A

Một tập hợp AA 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 \emptyset) 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 AA.

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

A=BA = B

Ví dụ:

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

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

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

  • Họ PP không chứa tập hợp rỗng: P\emptyset \notin P.
  • Hợp của các tập con trong PP bằng XX: (p1p2pn)=X(p_1 \cup p_2 \cup \cdots \cup p_n) = X.
  • Giao của bất kỳ hai tập hợp nào trong PP đều là tập rỗng: pipj=;pipjp_i \cap p_j = \emptyset; \forall p_i \ne p_j.

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

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

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}A=\{1, 2, 3, 4\}B={2,3,5,7},B=\{2, 3, 5, 7\}, ta có các phép toán sau trên hai tập hợp AABB:

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

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

A={xX:xA}\overline A = \{x \in X:x \notin A\}

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

A={xNx{1,2,3,4}}\overline A = \{x \in N \mid x \ne \{1, 2, 3, 4\}\}

b) Phép hợp

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

AB={x:xA hoặc xB}A \cup B = \{x: x \in A \text{ hoặc } x \in B\}

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

c) Phép giao

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

AB={x:xA vaˋ xB}A \cap B=\{x: x \in A \text{ và } x \in B\}

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

d) Phép lấy hiệu

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

A\B={x:xA vaˋ xB}A \backslash B=\{x: x \in A \text{ và } x \notin B\}

Ví dụ: A\B={1,4}A \backslash B = \{1, 4\}.

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

Kết hợp:

(AB)C=A(BC)(A \cup B) \cup C = A \cup (B \cup C)

(AB)C=A(BC)(A \cap B) \cap C = A \cap (B \cap C)

Giao hoán:

AB=BAA \cup B = B \cup A

AB=BAA \cap B = B \cap A

Phân phối:

A(BC)=(AB)(AC)A \cup (B \cap C) = (A \cup B) \cap (A \cup C)

A(BC)=(AB)(AC)A \cap (B \cup C) = (A \cap B) \cup (A \cap C)

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

AB=AB\overline {A \cup B} = \overline A \cap \overline B

AB=AB\overline {A \cap B} = \overline A \cup \overline 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×B={(a,b)aA,bB}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)aiAi,1ik}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 \}

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

Nguyên lí cộngnguyê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)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 NN phương án khác nhau, trong đó:

  • Phương án thứ nhất có m1m_1 cách thực hiện.
  • Phương án thứ hai có m2m_2 cách thực hiện. ......
  • Phương án thứ NNmnm_n 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_n.

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

AB=A+B|A \cup B| = |A| + |B|

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

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\} là một phân hoạch của tập hợp XX thì:

X=A1+A2+...+Ak|X| = |A_1| + |A_2| + ... + |A_k|

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

Lời giải: Gọi số đó là abcd,\overline {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} \}. Có 99 khả năng chọn số a,a, 1010 khả năng chọn số b,b, 1010 khả năng chọn số cc1010 khả năng chọn số dd. 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=399 + 10 + 10 + 10 = 39.

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 NN giai đoạn liên tiếp, trong đó:

  • Giai đoạn 11m1m_1 cách thực hiện.
  • Giai đoạn 22m2m_2 cách thực hiện. ......
  • Giai đoạn NNmnm_n 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_n.

Đố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 kk thành phần {a1,a2,...,ak},\{a_1, a_2,..., a_k\}, nếu mỗi bộ aia_imim_i phương án lựa chọn 1ik1 \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_n.

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|.

Ví dụ: Từ Hà Nội đến Huế có 77 tuyến xe khác nhau, từ Huế tới Thành phố Hồ Chí Minh có 55 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 22 giai đoạn bắt buộc: Giai đoạn 11 là đi từ Hà Nội tới Huế, giai đoạn này có 77 cách làm (77 tuyến xe khác nhau); giai đoạn 22 là đi từ Huế tới Thành phố Hồ Chí Minh, giai đoạn này có 55 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×5=357 \times 5 = 35 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 NN 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ó 44 cách để hoàn thành việc tạo ra một số có 44 chữ số có chứa 33 chữ số 9,9, nhưng chúng ta có thể bỏ bớt đi 11 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 NN giai đoạn liên tiếp nhau, nghĩa là giai đoạn thứ kk chỉ được phép thực hiện sau khi đã thực hiện xong các giai đoạn 1,2,3,...,(k1),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ế.

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 nn phần tử A={a1,a2,...,an}A =\{a_1, a_2,..., a_n\}. Một chỉnh hợp lặp chập kk của nn phần tử là một bộ có thứ tự gồm kk phần tử của 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 kk của nn sẽ là nkn^k:

Pnk=nk\overline{P_n^k} = n^k

Cài đặt: Tính số lượng chỉnh hợp lặp chập kk của n,n, đưa ra kết quả sau khi chia cho 109+710^9+7 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 kk của nn phần tử (kn)(k \le n) là một bộ có thứ tự gồm kk thành phần lấy từ nn 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,k, mỗi thành phần có số cách chọn giảm đi 11. Theo nguyên lí nhân, tổng số cách chọn là n×(n1)×(nk+1)n\times (n - 1) \times \cdots (n - k + 1). Do đó số chỉnh hợp không lặp chập kk của nn là:

Pnk=n×(n1)××(nk+1)=n!(nk)!P_n^k = n\times (n - 1)\times \cdots \times (n - k + 1) = \frac{n!}{(n - k)!}

Cài đặt: Tính số lượng chỉnh hợp không lặp chập kk của n,n, đưa ra kết quả sau khi chia cho 109+710^9+7 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 kk của nn phần tử (kn)(k \le n) là một bộ không xét đến thứ tự gồm kk thành phần khác nhau lấy từ nn 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×(n1)××(nk+1)k!=n!k!×(nk)!C^k_n = \frac{n \times (n - 1) \times \cdots \times (n - k + 1)}{k!} = \frac{n!}{k! \times (n - k)!}

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

  • Cnk=CnnkC^k_n = C^{n - k}_n.
  • Cn0=Cnn=1C^0_n = C^n_n = 1.
  • Cnk=Cn1k1+Cn1k (0<k<n)C^k_n = C^{k - 1}_{n - 1} + C^k_{n - 1} \ (0 < k < n).
  • CnkC^k_n chính là số lượng dãy nhị phân độ dài nn mà có đúng kk số 1,1, vì ta chọn ra kk vị trí khác nhau trong nn vị trí để đặt làm số 11.

Cài đặt: Đếm số lượng tổ hợp chập kk của n,n, đưa ra kết quả sau khi chia cho 109+710^9 + 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).
*/

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 kk của nn phần tử là một cách chọn ra kk 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 kk của nn là:

Cnk=(n+k1)!k!×(n1)!\overline{C^k_n} = \frac{(n + k - 1)!}{k!\times (n - 1)!}

Một tính chất rất thú vị của tổ hợp lặp đó là: Cnk\overline{C^k_n} 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, với kk là hằng số nguyên dương.

Cài đặt: Đếm số lượng tổ hợp chập kk của n,n, đưa ra kết quả sau khi chia cho 109+710^9 + 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)
*/

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 nn phần tử là một cách sắp xếp thứ tự các phần tử đó. Hoán vị của nn 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,k = n, do đó, số lượng hoán vị của nnn!n!

Cài đặt: Đếm số lượng hoán vị của nn phần tử, đưa ra kết quả sau khi chia cho 109+710^9 + 7 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à nn 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ừ 11 tới nn. 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 nn phần tử sẽ chính bằng nn.
  • Hoán vị Josephus: Được phát biểu dưới dạng một trò chơi như sau: Cho nn người đứng quanh vòng tròn theo chiều kim đồng hồ được đánh số từ 11 tới nn. Họ bắt đầu đếm từ người thứ nhất theo chiều kim đồng hồ, người nào đếm đến mm thì bị loại khỏi vòng tròn và người kế tiếp sẽ đếm lại từ 11. 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 nn 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) của dãy số (1,2,...,n)(1, 2,..., n) gọi là hoán vị Josephus (n,m)(n, m).
  • Hoán vị derangements: Một hoán vị {p1,p2,...,pn}\{p_1, p_2,...,p_n\} của nn phần tử {1,2,...,n}\{1, 2,..., n\} được gọi là một derangement khi và chỉ khi pii (i:1in)p_i \ne i \ (\forall i: 1 \le i \le n). Số lượng derangements của nnD(n)=n!k=0n(1)k×1k!D(n) = n!\sum_{k=0}^n(-1)^k\times \frac{1}{k!}.

IV. Tài liệu tham khảo


©️ Tác giả: Vũ Quế Lâm từ Viblo


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.