Máy Tính Tập Con

Nhập phép tính

Kích thước tập hợp (n)

Kích thước tập con (k) — tùy chọn

Kết quả

Tổng số tập con

32

= 2^5 (includes the empty set and the full set)

Tập con thực sự / khác rỗng (2ⁿ − 1)	31
Subsets of size k = 2 — C(n,k)	10

Máy Tính Tập Con là gì?

Tập con là một cách chọn ra các phần tử từ một tập hợp lớn hơn, bao gồm cả tập rỗng và chính tập hợp đó. Công cụ này giải đáp hai câu hỏi quen thuộc trong tổ hợp: một tập hợp gồm n phần tử có tổng cộng bao nhiêu tập con, và trong số đó có bao nhiêu tập con chứa đúng k phần tử. Đây là công cụ hữu ích cho học sinh, sinh viên đang học lý thuyết tập hợp, xác suất và toán rời rạc, cũng như bất kỳ ai cần đếm số tổ hợp khả dĩ.

Một tập hợp 3 phần tử có \(2^3 = 8\) tập con, bao gồm cả tập rỗng và tập đầy đủ.

Cách sử dụng

Nhập kích thước tập hợp của bạn vào ô n (số phần tử phân biệt). Máy tính sẽ lập tức trả về tổng số tập con, bằng \(2^n\), và số tập con thực sự / khác rỗng, bằng \(2^n - 1\). Nếu muốn, bạn có thể nhập thêm kích thước tập con k để biết số tập con chứa đúng k phần tử, được tính bằng hệ số nhị thức \(C(n, k)\). Cứ để trống k nếu bạn chỉ cần biết tổng số.

Giải thích công thức

Mỗi phần tử của tập hợp có thể được chọn hoặc không chọn vào một tập con một cách độc lập — tức là 2 lựa chọn cho mỗi phần tử. Với n phần tử độc lập, tổng số khả năng là

$$\text{Tổng số tập con} = 2 \times 2 \times \dots \times 2 = 2^n$$

Để đếm số tập con có kích thước cố định k, ta dùng công thức tổ hợp

$$\binom{n}{k} = \frac{n!}{k!\,(n - k)!}$$

tức là chọn k phần tử mà không quan tâm đến thứ tự. Khi cộng \(C(n, k)\) với mọi k chạy từ 0 đến n, ta thu lại đúng giá trị \(2^n\).

Quảng cáo

Tổng số tập con tăng theo \(2^n\), trong khi \(C(n,k)\) đếm các tập con có kích thước cố định k.

Ví dụ minh họa

Giả sử n = 5. Tổng số tập con là \(2^5 = 32\), và số tập con khác rỗng là 31. Số tập con gồm 2 phần tử là

$$C(5, 2) = \frac{5!}{2! \cdot 3!} = \frac{120}{2 \cdot 6} = 10$$

Vậy từ một tập hợp 5 phần tử, ta có đúng 10 cặp khả dĩ.

Câu hỏi thường gặp

Tổng số có bao gồm tập rỗng không? Có. Giá trị \(2^n\) tính cả tập rỗng lẫn toàn bộ tập hợp. Trừ đi 1 để có số tập con khác rỗng, hoặc trừ 2 để có số tập con thực sự khác rỗng.

Nếu k lớn hơn n thì sao? Khi đó không tồn tại tập con nào như vậy, nên \(C(n, k) = 0\) mỗi khi \(k > n\) hoặc \(k < 0\).

Vì sao giới hạn tối đa vào khoảng 170? \(2^n\) và giai thừa tăng cực kỳ nhanh; vượt quá khoảng n = 170, các giá trị sẽ lớn hơn phạm vi mà số dấu phẩy động tiêu chuẩn có thể biểu diễn.