logo

The Number of Subsets of a Finite Set with n Elements 📂Lemmas

The Number of Subsets of a Finite Set with n Elements

Formula

Sum of Binomial Coefficients 1

The sum of binomial coefficients is as follows.
$$ 2^{n} = \sum_{k=0}^{n} \binom{n}{k} $$

Corollary: Cardinality of the Power Set

If the cardinality of a finite set $S$ is $n = |S|$, then the cardinality of its power set $2^{S}$ is $2^{n}$.

Derivation

Binomial Theorem:
$$ (x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k} y^{n-k} $$

Substituting $x = y = 1$ gives $2^{n} = \sum_{k=0}^{n} \binom{n}{k} 1^{k} 1^{n-k}$.


  1. Bóna, M. (2025). Introduction to enumerative and analytic combinatorics: p28. ↩︎