Tập hợp n phần tử có bao nhiêu tập con?
Đây là câu hỏi kinh điển của chương Đại số tổ hợp trong Toán lớp 10 — bộ sách Kết nối tri thức. Câu trả lời gọn đến bất ngờ: 2ⁿ tập con, tính cả tập rỗng ∅ và chính tập hợp đó. Tập {🍎, 🍌, 🍇} có 2³ = 8 tập con; thêm quả cam 🍊 vào là lập tức có 16. Vì sao cứ thêm một phần tử thì số tập con lại nhân đôi? Trò chơi phía trên cho bạn nhìn thấy tận mắt.
Ý tưởng trực quan: nhân đôi bằng cách "sao chép"
Mỗi ô trong hình là một tập con: chấm màu sáng nghĩa là phần tử đó được chọn, chấm mờ là không. Hãy quan sát khi bấm "Thêm 1 phần tử":
- Bắt đầu với 1 phần tử: có đúng 2 tập con — tập rỗng ∅ và {🍎}.
- Thêm 🍌: mỗi tập con cũ tách thành hai bản — một bản không có 🍌 (giữ nguyên) và một bản có thêm 🍌 (viền sáng). Số tập con nhân đôi!
- Cứ thế: 2 → 4 → 8 → 16 → 32. Sau n lần, có 2×2×…×2 = 2ⁿ tập con.
- Nhìn các cột: cột k gom các tập con có đúng k phần tử, cao đúng C(n,k) ô — một hàng tam giác Pascal dựng đứng trước mắt bạn.
Vì sao đúng? Quy tắc nhân
Muốn tạo một tập con, ta duyệt từng phần tử và trả lời một câu hỏi có/không: "phần tử này có vào tập con không?". Mỗi phần tử có đúng 2 lựa chọn, các lựa chọn độc lập với nhau, nên theo quy tắc nhân:
Số tập con = 2 × 2 × … × 2 (n thừa số) = 2ⁿ
Cách đếm thứ hai: đếm theo kích cỡ. Số tập con có đúng k phần tử là C(n,k). Cộng tất cả các cỡ từ 0 đến n: C(n,0) + C(n,1) + … + C(n,n). Hai cách đếm cùng một thứ phải cho cùng kết quả, vậy tổng các hệ số tổ hợp trên một hàng Pascal bằng 2ⁿ — đây cũng chính là khai triển nhị thức Newton của (1+1)ⁿ.
Câu hỏi thường gặp
Tập hợp có n phần tử thì có bao nhiêu tập con? Có đúng 2ⁿ tập con, kể cả tập rỗng và chính tập đó. Mỗi phần tử có 2 lựa chọn — thuộc hoặc không thuộc — nên theo quy tắc nhân có 2×2×…×2 = 2ⁿ cách.
Công thức 2ⁿ liên hệ gì với tam giác Pascal? Số tập con gồm đúng k phần tử là C(n,k). Cộng theo mọi kích cỡ: C(n,0) + C(n,1) + … + C(n,n) = 2ⁿ — tổng các số trên hàng thứ n của tam giác Pascal luôn bằng 2ⁿ.
Ứng dụng thực tế
Phép nhân đôi 2ⁿ xuất hiện ở mọi nơi có lựa chọn có/không:
- 🍕 Tiệm pizza với 5 loại topping có thể phục vụ 2⁵ = 32 kiểu pizza khác nhau.
- 💻 Một byte 8 bit (mỗi bit bật/tắt) biểu diễn được 2⁸ = 256 giá trị — nền tảng của máy tính.
- 🔐 Mật khẩu, khóa mã hóa: mỗi bit thêm vào làm số khả năng nhân đôi, nên khóa 256 bit gần như không thể dò.
- 🧬 Xét nghiệm gộp nhóm, thiết kế thí nghiệm: mỗi yếu tố bật/tắt tạo ra 2ⁿ kịch bản cần cân nhắc.