Question

Suppose that A A is a set containing 13 13 elements. Find the number of different subsets of A.

Answer 1

Answer:

number of subsets of a set with 13 elements are: $2^{13}$

Step-by-step explanation:

In order to solve this intuitively, we can start by a set with lesser elements. This will reveal a pattern that will be used to solve for the subsets of the 13 element set.

If we start with a set B. which contains only 3 elements.

$B = \{1,2,3\}$

how many subsets of B are there? well we can count them. [the set containing {1,2} and {2,1} are the same, arrangement doesn't matter]

$B_{0} = \{\}\\B_{1a}=\{1\}\\B_{1b}=\{2\}\\B_{1c}=\{3\}\\B_{2a}=\{1,2\}\\B_{2b}=\{2,3\}\\B_{2c}=\{3,1\}\\B_{3a}=\{1,2,3\}$

there are a total of 9 subsets here.

Similarly, if you try a with a subset with only two elements you'll find that it has a total of 4 subsets.

We can see that combinatorics is at play here.

for the set B. the number of subsets can be written as:

$\text{\# of subsets of B} = ^3C_0+^3C_1+^3C_2+^3C_3\\\text{\# of subsets of B} = 1+3+3+1\\\\text{\# of subsets of B} = 8$

if we try with a 2-element set:

$\text{\# of subsets} = ^2C_0+^2C_1+^2C_2\\\text{\# of subsets} = 1+2+1\\\ \text{\# of subsets} = 4$

We can use the same technique to find the number of subsets of the 13 element set.

But if you recognize a pattern here that this sets of combinations are actually part of the pascal triangle, the sum of each row of the triangle is 2^{the row's number}. hence.

$\text{\# of subsets of B} = 2^3\\\ \text{\# of subsets of B} = 8$

So finally, the subsets of a 13-element set A will be

$\text{\# of subsets of A} = ^{13}C_0+^{13}C_1+^{13}C_2+^{13}C_3\cdots+^{13}C_{12}+^{13}C_{13}\\OR\\\text{\# of subsets of A} = 2^{13}\\\text{\# of subsets of A} = 8192$