Trong giải toán tổ hợp, việc xác định số lượng phần tử của một tập hợp hợp nhất từ nhiều tập con là một chủ đề nền tảng thường gặp. Khi các tập hợp không rời nhau, ta áp dụng Nguyên lý bù trừ (Inclusion-Exclusion Principle):
- Với hai tập hợp bất kỳ: \(|A \cup B| = |A| + |B| - |A \cap B|\).
- Với bài toán xếp có lặp gồm \(n\) phần tử đôi một khác nhau, mỗi phần tử \(a_i\) có tần số xuất hiện \(k_i\) (với tổng số phần tử \(k = \sum_{i=1}^{n} k_i\)), số cách sắp xếp được xác định theo công thức hoán vị lặp: \[ P(k_1, k_2, \ldots, k_n) = \frac{k!}{k_1! k_2! \ldots k_n!} \]
I. Mở đầu về công thức tính số phần tử của hợp các tập hợp
Ví dụ 1: Trong một bài kiểm tra toán có hai bài toán. Trong cả lớp có 30 em làm được bài thứ nhất và 20 em làm được bài thứ hai. Chỉ có 10 em làm được cả hai bài toán kiểm tra. Hãy tính số học sinh trong lớp (biết rằng mỗi học sinh đều làm được ít nhất một bài).
Lời giải:
Gọi \(A\) là tập hợp học sinh giải được bài toán thứ nhất, và \(B\) là tập hợp học sinh giải được bài toán thứ hai. Khi đó, \(A \cap B\) là tập hợp học sinh giải được cả hai bài toán. Bài toán quy về tìm số phần tử của \(A \cup B\).
Nếu hai tập hợp \(A\) và \(B\) rời nhau thì: \[ |A \cup B| = |A| + |B| \]
Trong trường hợp \(A\) và \(B\) có giao khác rỗng thì công thức trên không còn đúng nữa, mà ta có:
\[ |A \cup B| = |A| + |B| - |A \cap B| \]bởi vì trong tổng \(|A| + |B|\) thì các phần tử chung trong \(|A \cap B|\) (của cả \(A\) và \(B\)) đã bị tính lặp lại đúng hai lần.
Áp dụng công thức trên, số học sinh của lớp là:
\[ 30 + 20 - 10 = 40 \text{ em.} \]Ví dụ 2: Lớp 12A phải làm một bài kiểm tra Toán gồm có ba bài toán. Biết rằng mỗi em trong lớp đều làm được ít nhất một bài, trong lớp có 20 em làm được bài toán thứ nhất, 14 em giải được bài toán thứ hai, 10 em giải được bài toán thứ ba, 6 em giải được cả hai bài toán thứ nhất và thứ ba, 5 em giải được cả hai bài thứ hai và thứ ba, 2 em giải được cả hai bài thứ nhất và thứ hai, và có một em được 10 điểm vì đã giải được cả ba bài toán. Hỏi rằng lớp học có bao nhiêu em tất cả?
Phân tích:
Gọi \(A, B, C\) lần lượt là tập hợp các em học sinh giải được bài toán thứ nhất, thứ hai và thứ ba. Bài toán yêu cầu tính số phần tử của tập hợp \(A \cup B \cup C\). Việc mở rộng tính số phần tử của hợp gồm nhiều tập con là một công cụ mạnh để giải quyết các bài toán đếm phức tạp.
II. Xếp có lặp với tần số cho trước (Hoán vị lặp)
Một phần tử \(a_i\) của một dãy \(k\) phần tử cho trước \(a_1 a_2 \ldots a_k\) được nói là có tần số lặp \(k_i\), nếu như nó xuất hiện trong dãy đúng \(k_i\) lần.
Bài toán tổng quát: Cho trước một tập hợp \(A = \{a_1; a_2; \ldots; a_n\}\) và \(k\) là một số dương nguyên cùng với các số tự nhiên \(k_1, k_2, \ldots, k_n\) thỏa mãn \(\sum_{i=1}^n k_i = k\). Hãy tính số \(P(k_1, k_2, \ldots, k_n)\) các dãy \(k\) phần tử của tập hợp \(A\) sao cho phần tử \(a_i\) của \(A\) có tần số lặp là \(k_i\) cho mọi \(i \leqslant n\).
Để đơn giản hóa trình bày, ta nói gọn là dãy \(k\) phần tử có lặp \((k_1, k_2, \ldots, k_n)\) nếu \(k_i\) là tần số lặp của phần tử \(a_i\) trong dãy.
Ví dụ 3: Cho tập hợp \(A = \{a; b; c; d\}\). Tất cả các dãy có lặp \((3, 2, 0, 0)\) của \(A\) là:
\(aaabb\), \(aabba\), \(abbaa\), \(bbaaa\), \(aabab\), \(ababa\), \(babaa\), \(abaab\), \(baaba\), \(baaab\).
Định lý 1: Cho trước một tập hợp \(A\) có \(n\) phần tử \(a_1, a_2, \ldots, a_n\). Số các dãy có độ dài \(k\) với \(k = \sum_{i=1}^n k_i\) phần tử sao cho phần tử \(a_i\) xuất hiện đúng \(k_i\) lần trong dãy là:
\[ P(k_1, k_2, \ldots, k_n) = \frac{k!}{k_1! k_2! \ldots k_n!} \]Chứng minh:
Không mất tính tổng quát, có thể giả sử \(k_i \geqslant 1\) cho mọi giá trị \(i \leqslant n\). Ta xét tập hợp:
\[ B = \{a_1^1; a_1^2; \ldots; a_1^{k_1}; a_2^1; a_2^2; \ldots; a_2^{k_2}; \ldots; a_n^1; a_n^2; \ldots; a_n^{k_n}\} \]Như vậy mỗi dãy có lặp \((k_1, k_2, \ldots, k_n)\) là một hoán vị của các phần tử của \(B\) (tất cả có \((k_1 + k_2 + \cdots + k_n)! = k!\) hoán vị). Trong đó, mỗi dãy bị tính lặp \(k_1! k_2! \ldots k_n!\) lần, do khi đổi chỗ các phần tử \(a_i^j\) (\(1 \leqslant j \leqslant k_i\)) với nhau ta vẫn chỉ thu được chính dãy đó mà thôi.
Vậy số các dãy có lặp \((k_1, k_2, \ldots, k_n)\) là:
\[ P(k_1, k_2, \ldots, k_n) = \frac{k!}{k_1! k_2! \ldots k_n!} \]Ví dụ 4: Tính số các số tự nhiên có bảy chữ số, trong đó có ba chữ số 1, hai chữ số 2 và hai chữ số 3.
Lời giải:
Số các số tự nhiên cần tìm là:
\[ P(3, 2, 2) = \frac{7!}{3!2!2!} = 210. \]