Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools

How to Count Subsets

Each element of an nn-element set is either in a subset or out of it, so there are 2n2^n subsets in all. Conditions change only the number of free choices: a fixed size uses (nk)\binom{n}{k}, a forced element removes one choice, and "at least one" is counted from its opposite.

Recognize the task

The question asks how many subsets, not which: "how many subsets does {a,b,c,d,e}\{a, b, c, d, e\} have", "proper subsets", "subsets with 33 elements", "subsets that contain 11 but not 22", "subsets with at least one even number". Test: you need a number, so do not list unless nn is tiny.
Subset counting is explained in the number of subsets lesson.

Ways to do it

All subsetsusual
∣P(A)∣=2n|\mathcal{P}(A)| = 2^{n}
The size of the power set; for proper subsets use the proper subset count 2n−12^n - 1.
Fixed sizesize k
(nk)\binom{n}{k}
Subsets with exactly kk elements are combinations; the combinations method counts them.
Forced elementsconditions
2 n−m2^{\,n - m}
If mm elements must be in or must be out, only the other n−mn - m elements are free choices.

Steps

StepOn subsets of {1,2,3,4,5,6}\{1, 2, 3, 4, 5, 6\} that contain 11 but not 22
1Count the elements. Every element of the set is one in or out choice.n=6n = 6
2Fix the forced elements. An element that must be in, or must be out, has no choice left.11 in, 22 out: m=2m = 2
3Give each free element two choices. In or out, independently of the others.26−2=242^{6 - 2} = 2^4
4Compute and adjust for the wording. Subtract 11 for "proper" (the set itself) or for "nonempty" (the empty set), if the question says so.1616 subsets

Worked examples

Example 1 · all and proper subsets

all, proper
{a,b,c,d,e}\{a, b, c, d, e\}: n=5n = 5
count the elements
25=322^5 = 32 subsets
two choices per element
32−1=3132 - 1 = 31 proper subsets
leave out the set itself

Example 2 · a fixed size

size k
subsets of size 33 from 66 elements
order inside a set never matters
(63)=6⋅5⋅43!\binom{6}{3} = \dfrac{6 \cdot 5 \cdot 4}{3!}
combinations
2020 subsets
simplify

Example 3 · at least one even number

complement
subsets of {1,…,8}\{1, \ldots, 8\}: 28=2562^8 = 256
all subsets
no even number: subsets of {1,3,5,7}\{1, 3, 5, 7\}, 24=162^4 = 16
count the opposite
256−16=240256 - 16 = 240
subtract
The "count the opposite" step is the complementary counting method. See all subsets of a small set at once in the power set tool.

See it happen

Line the elements up and give each a switch, in or out. Every subset is one row of switch settings, and there are 2n2^n rows. Fixing a switch halves the count, which is why each forced element turns 2n2^n into 2n−12^{n-1}. Grouping the rows by how many switches are on gives the binomial row sum (n0)+(n1)+⋯+(nn)=2n\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n.

Common mistakes

Removing two subsets for "proper"

✗ proper subsets of a 55-element set: 25−2=302^5 - 2 = 30
✓ only the set itself is left out: 25−1=312^5 - 1 = 31
The empty set is a proper subset of every nonempty set.

Squaring instead of using powers of 2

✗ subsets of a 55-element set: 52=255^2 = 25
✓ 25=322^5 = 32

Using a power of 2 for a fixed size

✗ subsets of size 22 from 55 elements: 22=42^2 = 4
✓ (52)=10\binom{5}{2} = 10