An Initiative by SAARTHI IAS
Maarg Manthan · Topic 23.10

Number of Subsets and the Power Set of a Given Set

Quantitative Aptitude › Set Theory, Functions and Graphs · Topic 23.10

A set with n elements has 2ⁿ subsets, because each element is either in or out of a subset. The collection of all subsets is the power set. There are 2ⁿ - 1 proper subsets, 2ⁿ - 2 non-empty proper subsets, and nCr subsets with exactly r elements.

Share:
Number of Subsets and the Power Set of a Given Set - Quantitative Aptitude - MaargX UPSC Maarg Manthan

Quick Answer

A set with n elements has 2ⁿ subsets, because each element is either in or out of a subset. The collection of all subsets is the power set. There are 2ⁿ – 1 proper subsets, 2ⁿ – 2 non-empty proper subsets, and nCr subsets with exactly r elements.

At a Glance

  • All subsets 2ⁿ
  • Proper subsets 2ⁿ – 1
  • Non-empty proper 2ⁿ – 2
  • Exactly r elements nCr
  • Power set size 2ⁿ

Where Does It Fit?

This topic follows Set Theory – Union, Intersection, Complement and Venn Diagram Problems and uses the counting principle of Fundamental Principle of Counting (Addition and Multiplication Rules). The combinations used are in Combination and Selection Problems.

What Is the Formula for the Number of Subsets?

In short: for each of the n elements there are two choices, to include it or leave it out, so there are 2 × 2 × … × 2 = 2ⁿ subsets.

Elements n Subsets 2ⁿ Proper subsets 2ⁿ – 1 Non-empty proper subsets 2ⁿ – 2
1 2 1 0
2 4 3 2
3 8 7 6
4 16 15 14
5 32 31 30
10 1024 1023 1022

The empty set is a subset of every set, and every set is a subset of itself. A proper subset is any subset other than the set itself.

What Is the Power Set?

In short: the power set of A is the set of all subsets of A, and it has 2ⁿ members.

  • Example: for A = {a, b, c}, the power set is {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}, which has 8 members.
  • Power set of a power set: a set with 2 elements has a power set with 4 elements, and that power set has 2⁴ = 16 subsets.

How Do You Count Subsets with Conditions?

In short: fix the required elements, then count freely over the rest.

Conditional counts for an n-element set

  • Subsets with exactly r elements: nCr.
  • Subsets containing a particular element: 2ⁿ⁻¹.
  • Subsets containing a elements and excluding b elements: 2ⁿ⁻ᵃ⁻ᵇ.
  • Subsets with at least one element: 2ⁿ – 1.

The formula nCr is explained in Combination and Selection Problems.

Solved Examples

Example 1

Question: List the subsets of A = {a, b, c} and count them.

  1. Subsets with 0 elements: ∅ (1).
  2. With 1 element: {a}, {b}, {c} (3); with 2 elements: {a, b}, {a, c}, {b, c} (3); with 3 elements: {a, b, c} (1).
  3. Total = 1 + 3 + 3 + 1 = 8 = 2³.

Answer: There are 8 subsets.

Example 2

Question: A set has 5 elements. Find the number of subsets, proper subsets and non-empty proper subsets.

  1. Subsets = 2⁵ = 32.
  2. Proper subsets = 32 – 1 = 31.
  3. Non-empty proper subsets = 32 – 2 = 30.

Answer: 32 subsets, 31 proper subsets and 30 non-empty proper subsets.

Example 3

Question: How many subsets of a 6-element set have exactly 2 elements?

  1. The count is 6C2 = (6 × 5)/2.

Answer: There are 15 subsets.

Example 4

Question: In a 5-element set, how many subsets contain a particular element, and how many do not?

  1. Fix the element inside: the other 4 elements are free, giving 2⁴ = 16.
  2. Fix it outside: also 2⁴ = 16.
  3. Check: 16 + 16 = 32.

Answer: 16 contain the element and 16 do not.

Example 5

Question: A set has 1024 subsets. How many elements does it have? Two disjoint sets with 4 and 3 elements are combined; how many subsets does the union have?

  1. 2ⁿ = 1024 = 2 to the power 10, so n = 10.
  2. The union has 4 + 3 = 7 elements, so 2⁷ = 128 subsets.

Answer: The set has 10 elements, and the union has 128 subsets.

Shortcuts and Tricks

  • Use 2ⁿ for all subsets and subtract for proper or non-empty ones.
  • For conditions, fix the required elements and count the rest as 2 to the power of the leftover count.
  • For exactly r elements, use nCr.
  • Remember the powers of 2: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024.
  • The sum of nCr over r from 0 to n equals 2ⁿ.

Common Mistakes

  • Forgetting that the empty set is a subset.
  • Using n² or 2n instead of 2ⁿ.
  • Counting the set itself as a proper subset.
  • Not fixing the required element when it is conditioned.
  • Confusing a subset with an element of the set.

Practice Questions

  1. Find the number of subsets of a 7-element set.
  2. A set has 63 proper subsets. How many elements has it?
  3. How many subsets of an 8-element set have exactly 3 elements?
  4. How many subsets of {1, 2, 3, 4} contain 1 but not 2?
  5. How many subsets of {1, 2, 3, 4} have at least 2 elements?
  6. How many elements are in the power set of the power set of a 2-element set?

Answers: 1) 128; 2) 6; 3) 56; 4) 4; 5) 11; 6) 16.

Why Is This Topic Important?

  • Counting It links set ideas with the basic counting rule.
  • Exam use Questions ask for proper or conditional subsets.
  • Link It prepares for Combination and Selection Problems.

What Comes Next?

The final topic of the macro is Relations Between Sets – Reflexive, Symmetric and Transitive Properties, which studies relations between sets.

Key Terms and Formulas

  • Subset A set whose elements all belong to another set
  • Proper subset A subset that is not the whole set
  • Power set The set of all subsets
  • Empty set The set with no elements

Exam Corner

Points to Remember

  • Number of subsets = 2ⁿ.
  • Proper subsets = 2ⁿ – 1.
  • Subsets with exactly r elements = nCr.
  • The empty set is a subset of every set.

Do Not Confuse With

  • Subset vs proper subset A proper subset is not equal to the set itself.
  • Subset vs element An element is a member; a subset is a collection of members.
  • Power set vs set The power set contains subsets as its members.

Memory Hook

In or out for each element: two to the power n.

GS Relevance

Counting subsets for SSC CGL and CAT quantitative aptitude: the 2 to the power n rule, proper subsets and conditions on elements.

Frequently Asked Questions

What is the number of subsets of a set with n elements?

A set with n elements has 2 to the power n subsets. Each element can be either included or left out, giving two choices per element, so the choices multiply to 2 raised to n, and the total includes both the empty set and the set itself.

What is the power set of a set?

The power set of a set is the set of all its subsets, including the empty set and the set itself. For the set a, b, c, the power set has 8 members, in general 2 to the power n for a set with n elements.

How many proper subsets does a set have?

A set with n elements has 2 to the power n minus 1 proper subsets, because only the set itself is excluded. The number of non-empty proper subsets is 2 to the power n minus 2, since the empty set is also left out of that count.

How many subsets have exactly r elements?

The number of subsets with exactly r elements of an n-element set is nCr, the number of ways to choose r elements from n. For a 6-element set, the subsets with exactly 2 elements number 6C2, which is 15.

How many subsets contain a particular element?

A set of n elements has 2 to the power n minus 1 subsets containing a particular element, because that element is fixed inside and the remaining n minus 1 elements are free. For a 5-element set this gives 16 subsets.

PYQ Practice — Statement Analysis

1 A set with 5 elements has 32 subsets.
True

2⁵ = 32.

2 The empty set is a subset of every set.
True

It has no element outside any set.

3 A set with 3 elements has 7 non-empty proper subsets.
False

It has 6, since 2³ - 2 = 6.

4 The number of subsets with exactly 2 elements of a 6-element set is 15.
True

6C2 = 15.

Share: