0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ilya Nov 28 '14 at 11:52
  • $\begingroup$ What about the empty set ? $\endgroup$ – Namch96 Nov 28 '14 at 11:57
  • 1
    $\begingroup$ and (unlike me) don't forget to add the empty susbet $\endgroup$ – Ilya Nov 28 '14 at 11:58
  • $\begingroup$ Haha ok thanks :) $\endgroup$ – Namch96 Nov 28 '14 at 11:58
1
$\begingroup$

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}.$$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – bof Nov 28 '14 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.