Tóm tắt kiến thức: Bài viết tổng hợp các khái niệm nền tảng về lý thuyết tập hợp, tính chất tập con, bộ sắp thứ tự, công thức xác định số ...
Tóm tắt kiến thức: Bài viết tổng hợp các khái niệm nền tảng về lý thuyết tập hợp, tính chất tập con, bộ sắp thứ tự, công thức xác định số phần tử của hợp các tập hợp (nguyên lý bao hàm - loại trừ) cùng với phát biểu tổng quát về quy tắc cộng trong Đại số Tổ hợp.
CHƯƠNG 1 - CƠ SỞ LÍ THUYẾT VỀ TỔ HỢP
Chương này nhắc lại một số lý thuyết về tập hợp và hệ thống lý thuyết cơ bản của toán tổ hợp như: Hoán vị, chỉnh hợp, tổ hợp. Các nội dung này được giảng dạy cho học sinh trung học phổ thông hệ cơ bản, nâng cao và hệ chuyên ngành toán.
1.1 Nhắc lại về tập hợp
Tập hợp con
Định nghĩa: Cho tập hợp \(A\). Tập hợp \(B\) gọi là tập con của tập \(A\) khi mọi phần tử của tập \(B\) đều thuộc \(A\).
\[ B \subset A \Leftrightarrow (\forall x \in B \Rightarrow x \in A) \]
Tính chất:
- Mọi tập hợp \(A\) đều có 2 tập con là \(\phi\) và \(A\).
- Tập \(A\) có \(n\) phần tử thì số tập con của \(A\) là \(2^n\).
Tập hợp sắp thứ tự
Một tập hợp hữu hạn có \(m\) phần tử được gọi là sắp thứ tự nếu với mỗi phần tử của tập hợp đó ta cho tương ứng một số tự nhiên từ \(1\) đến \(m\), sao cho với những phần tử khác nhau ứng với những số khác nhau.
Khi đó bộ sắp thứ tự \(m\) phần tử là một dãy hữu hạn \(m\) phần tử và hai bộ sắp thứ tự \((a_1, a_2, \dots, a_m)\) và \((b_1, b_2, \dots, b_m)\) bằng nhau khi mọi phần tử tương ứng bằng nhau:
\[ (a_1, a_2, \dots, a_m) = (b_1, b_2, \dots, b_m) \Leftrightarrow a_i = b_i, \quad i = 1, 2, \dots, m \]
Số phần tử của một số tập hợp
Tập hợp \(A\) có hữu hạn phần tử thì số phần tử của \(A\) được kí hiệu là: \(|A|\) hoặc \(n(A)\).
Cho \(A, B, C\) là 3 tập hợp hữu hạn, khi đó:
\(|A \cup B| = |A| + |B| - |A \cap B|\)
\(|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|\)
Tổng quát: Cho \(A_1, A_2, \dots, A_n\) là \(n\) tập hợp hữu hạn (\(n > 1\)). Khi đó:
\[ |A_1 \cup A_2 \cup \dots \cup A_n| = \sum_{i=1}^{n} |A_i| - \sum_{1 \le i < k \le n} |A_i \cap A_k| + \sum_{1 \le i < k < l \le n} |A_i \cap A_k \cap A_l| + \dots + (-1)^{n-1} |A_1 \cap A_2 \cap \dots \cap A_n| \]
1.2 Quy tắc cộng và quy tắc nhân
Quy tắc cộng
Định nghĩa: Một công việc được hoàn thành bởi một trong hai hành động. Nếu hành động này có \(m\) cách thực hiện, hành động kia có \(n\) cách thực hiện không trùng với bất kì cách nào của hành động thứ nhất thì công việc đó có \(m + n\) cách thực hiện.
Tổng quát: Một công việc được hoàn thành bởi một trong các hành động \(T_1, T_2, \dots, T_n\).
- \(T_1\) có \(m_1\) cách thực hiện.
- \(T_2\) có \(m_2\) cách thực hiện.
- ...
- \(T_n\) có \(m_n\) cách thực hiện.
Giả sử không có hai việc nào có thể làm đồng thời thì công việc đó có \(m_1 + m_2 + \dots + m_n\) cách thực hiện.
Biểu diễn dưới dạng tập hợp: Nếu \(X, Y\) là hai tập hợp hữu hạn, không giao nhau thì \(|X \cup Y| = |X| + |Y|\).
