Subsets of a power set.

How many subsets T of the power set of A contain at most 2 elements if the cardinality of A is n where n is a natural number ?

The number of elements in power set A = 2^n. But i dont know how to work out the number of subsets of the power set that contain at most 2 elements. Any answers and i will be grateful.

• Those are all singletons (there are $n$ of them) and all unique pairs of different elements (there are $(n^2-n)/2$ of them); alternatively, all unique pairs of elements where a pair $(x,x)$ counts as a singleton, so $\frac12n(n+1)$ with either approach. – Ilya Nov 28 '14 at 11:52
• What about the empty set ? – Namch96 Nov 28 '14 at 11:57
• and (unlike me) don't forget to add the empty susbet – Ilya Nov 28 '14 at 11:58
• Haha ok thanks :) – Namch96 Nov 28 '14 at 11:58

Suppose $A=\{a_1,a_2,\dots,a_n\}$, then $$\mathcal P(A)=\{\emptyset,\overbrace{\{a_1\},\{a_2\},\dots,\{a_n\}}^{\binom{n}{1} \text{ sets}},\overbrace{\{a_1,a_2\},...}^{\binom{n}{2}\text{ sets}},\overbrace{\{a_1,a_2,a_3\}}^{\binom{n}{3} \text{ sets}},...,A\}.$$

Recall that $\binom{n}{k}$ tells you the number of sets you can make with $k$ elements from a set of $n$ elements.

Then if we add everything:

$$|\mathcal P(A)|=\sum\limits_{i=0}^n\binom{n}{i}=\sum\limits_{i=0}^n\binom{n}{i}(1^i)(1^{n-i})\stackrel{\text{by Binomial Theorem}}{=}(1+1)^n=2^n.$$ Why do we sum $\binom{n}{0}$ and $\binom{n}{n}$? Because of the number of sets with no elements (this is the empty set) and the number of sets with $n$ elements (this is $A$). Therefore you are interested in:

$$\sum\limits_{i=0}^2\binom{2^n}{i}.$$

If $Card (A)=n$ which $n \in \mathbb N$ then the number of subsets of $A$ that have exactly $j$ elements is $\binom {n}{j}$

Then the answer of the questin is

${1+ \binom{n}{1} + \binom{n}{2}}$= ${ \frac{n^2+n+2}{2}}$

Note : 1 is for empty set

• The question was about subsets of the power set of $A$, not subsets of $A$ itself, so don't you have to replace $n$ with $2^n$ in your expression? – bof Nov 28 '14 at 12:12