The formula |\mathcal{P}(A)| = 2^{|A|} is one of the first cards combinatorics puts on the table. A set with 3 elements has 2^3 = 8 subsets. A set with 10 elements has 2^{10} = 1024 subsets. A set with 20 elements has more than a million subsets. But why is the count a power of two? Where does the doubling come from?

The answer is a beautiful one-line argument. Building a subset is a sequence of independent two-way choices, one per element, and the number of ways to make those choices multiplies together.

The two-choice argument

Let A = \{a_1, a_2, \dots, a_n\} — a set with n elements. You want to build a subset S \subseteq A. What are you actually choosing?

Go through the elements of A one by one. For each element a_i, you have exactly two choices:

  1. Put a_i into S.
  2. Leave a_i out of S.

That is the entire decision for element a_i. No other option exists — either a_i \in S or a_i \notin S. And the choice for a_i does not depend on what you did for a_1, \dots, a_{i-1}: each element's decision is independent.

So to specify a subset S, you make n independent binary decisions — one per element. By the multiplication principle of counting, the total number of different subsets is

\underbrace{2 \times 2 \times 2 \times \dots \times 2}_{n \text{ factors}} = 2^n.

That is the formula, and that is exactly why it is 2^n and not something else: two choices, n times, multiplied together.

Why multiplication and not addition: imagine you had 2 shirts and 3 pants. The number of outfits is 2 \times 3 = 6, not 2 + 3 = 5. Each pant can be combined with each shirt, independently. Subset-building is the same — each element can be "in or out" independently of what the other elements do, and independent choices multiply.

Walk through n = 3

Let's check the formula for A = \{a, b, c\}. We claim |\mathcal{P}(A)| = 2^3 = 8. Let's list the subsets and count.

Use a three-digit binary code: the i-th digit is 1 if a_i is in, 0 if out. So (1, 0, 1) means a \in S, b \notin S, c \in S, which gives S = \{a, c\}.

Code Subset
(0, 0, 0) \varnothing
(0, 0, 1) \{c\}
(0, 1, 0) \{b\}
(0, 1, 1) \{b, c\}
(1, 0, 0) \{a\}
(1, 0, 1) \{a, c\}
(1, 1, 0) \{a, b\}
(1, 1, 1) \{a, b, c\}

Eight rows, one for each of the 2^3 = 8 binary codes of length 3. Every row is a distinct subset, and every subset appears as some row. The bijection between subsets and binary codes is what locks the count in place: there are exactly as many subsets as there are three-digit binary strings, and three-digit binary strings number 2^3.

Binary tree of choices building the eight subsets of a three-element set A rooted binary tree with three levels of branching. Each level corresponds to deciding whether an element of the set is in or out of the subset. The root branches into two choices for element a, each of those into two choices for element b, each of those into two choices for element c, giving eight leaves at the bottom, each labelled with a subset from the empty set through to the full set. start a out a in b out b in b out b in ∅ {c} {b} {b,c} {a} {a,c} {a,b} {a,b,c} 2 × 2 × 2 = 8 leaves one per subset of {a, b, c}
Building a subset of $\{a, b, c\}$ is a three-step process: decide whether $a$ is in, then whether $b$ is in, then whether $c$ is in. The tree has two branches at each level, and $2 \times 2 \times 2 = 8$ leaves — one per subset. The pattern generalises: for $n$ elements, the tree has $2^n$ leaves.

Why the formula is exactly right, not an approximation

Two subtleties worth being explicit about:

Every subset appears exactly once. Each binary code of length n produces one subset, and different codes produce different subsets (because they disagree on the in-or-out choice for at least one element). So the count is exact, not an upper bound.

The empty set and the full set are included. When all n choices are "out," you get \varnothing. When all n choices are "in," you get A itself. Both are legitimate subsets, both count, and both are why the total is 2^n and not 2^n - 1 or 2^n - 2.

Three common variants that come up on exams:

Check which variant the problem asks for before writing down 2^n.

The edge cases

n = 0. What if A has 0 elements? The formula gives 2^0 = 1. That matches: \mathcal{P}(\varnothing) = \{\varnothing\} is a one-element set whose only element is the empty set. See Is the Power Set of the Empty Set Also Empty? for the full walk-through.

n = 1. A singleton \{a\} has 2^1 = 2 subsets: \varnothing and \{a\}. Correct.

n = 2. A pair \{a, b\} has 2^2 = 4 subsets: \varnothing, \{a\}, \{b\}, \{a, b\}. Correct.

The formula works from n = 0 upward, without any special cases.

Connection to binomial coefficients

There is a second angle on the same count that is worth knowing for JEE.

The number of subsets of A with exactly k elements is \binom{n}{k} — the binomial coefficient, "n choose k." So the total number of subsets, summing over all possible sizes, is

\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n}.

This is a well-known sum — it is the total of a row of Pascal's triangle, and that total is exactly 2^n. You can prove it by expanding (1 + 1)^n with the binomial theorem:

(1 + 1)^n = \sum_{k=0}^{n} \binom{n}{k} \cdot 1^{n-k} \cdot 1^k = \sum_{k=0}^{n} \binom{n}{k} = 2^n.

So 2^n can be arrived at in two ways: the direct two-choice argument above, or by summing the sizes-of-subsets separately and recognising the result as a binomial row. Both give the same answer because they are both counting the same thing — the total number of subsets of an n-element set. This agreement is one of the first places combinatorics and set theory lock together.

Why the formula grows so fast

2^n grows exponentially in n — faster than any polynomial. A table to make the growth visceral:

n 2^n
0 1
1 2
2 4
5 32
10 1024
20 1{,}048{,}576
30 1{,}073{,}741{,}824
50 \approx 1.1 \times 10^{15}

A 20-element set has more subsets than there are seconds in eleven days. A 50-element set has more subsets than grains of sand on most medium-sized beaches. The formula starts small and then explodes — which is exactly the kind of qualitative behaviour that makes exponents so important in combinatorics, cryptography, and probability. The related page Chessboard Rice Grains Doubling Visualisation is a dramatic visual of the same kind of growth.

The one-line summary

A set with n elements has 2^n subsets because building a subset requires n independent two-way decisions (in or out), and the number of ways to make n independent binary decisions is 2 \times 2 \times \dots \times 2 = 2^n. The formula is exact, works for all n \geq 0, and agrees with the sum of a row of Pascal's triangle.

Related: Sets — Introduction · Power Set Explorer: All 8 Subsets · Is the Power Set of the Empty Set Also Empty? · Chessboard Rice Grains Doubling