Tập con, hai tập hợp bằng nhau, đếm số tập con

Xét $A \subset B$ khi hai tập liệt kê

1. Với từng phần tử của $A$, kiểm tra có thuộc $B$ không. Một phần tử không thuộc là kết luận $A \not\subset B$.
2. Khi $A$ chứa tham số $m$: cho các phần tử còn lại của $A$ vào $B$, rồi để $m$ nhận các giá trị làm phần tử của $A$ thuộc $B$.
3. Quan trọng: nếu hai biểu thức trong $A$ cho cùng giá trị thì tập chỉ có một phần tử đó (ví dụ $m = 1$ trong $\{1; m\}$).

Chứng minh $A = B$ / tìm tham số để $A = B$

1. Viết $A$, $B$ dạng liệt kê.
2. Cân bằng các phần tử, nhớ rằng thứ tự không quan trọng.
3. Thử lại để chắc không có hai phần tử trùng nhau làm số phần tử thay đổi.

Đếm số tập con

1. Gọi $n$ là số phần tử, tổng số tập con là $2^n$.
2. Có điều kiện "chứa phần tử $x$", "không chứa $y$": bỏ các phần tử cố định ra, còn $n - k$ phần tử tự do, số tập con là $2^{n-k}$.
3. Điều kiện "có đúng $k$ phần tử": đếm tổ hợp hoặc liệt kê.
4. Điều kiện "ít nhất một phần tử": lấy $2^n - 1$ (bỏ $\varnothing$).

Gọi $a_n$ là số tập con của $\{1; 2; \dots; n\}$ không chứa hai số nguyên liên tiếp (kể cả $\varnothing$).

1. Tính các giá trị đầu: $a_1 = 2$ ($\varnothing$, $\{1\}$), $a_2 = 3$ ($\varnothing$, $\{1\}$, $\{2\}$).
2. Chia theo phần tử $n$:
   • $n$ không thuộc tập: còn lại là tập con của $\{1; \dots; n-1\}$ không có hai số liên tiếp, có $a_{n-1}$ tập;
   • $n$ thuộc tập: khi đó $n - 1$ không thuộc, phần còn lại là tập con của $\{1; \dots; n-2\}$ không có hai số liên tiếp, có $a_{n-2}$ tập.
3. Suy ra truy hồi $a_n = a_{n-1} + a_{n-2}$ (dãy kiểu Fi-bô-na-xi). Tính liên tiếp tới $n$ cần tìm.
4. Nếu hỏi các tập con có đúng $k$ phần tử: số đó là $\binom{n-k+1}{k}$.