Question

How many subsets does an n-element set have? Provide a combinatorial proof.

a) 2ⁿ
b) n²
c) n!
d) 2×n

Answer 1

The number of subsets of an n-element set is 2^n.

Step-by-step explanation:

To find the number of subsets of an n-element set, we can use a combinatorial proof. Each element in the set can either be included or excluded in each subset. So, for each element, there are 2 choices (included or excluded). Since there are n elements in the set, the total number of subsets is 2^n.