edited by
3,089 views
24 votes
24 votes
How many true inclusion relations are there of the form $A \subseteq B$, where $A$ and $B$ are subsets of a set $S$ with $n$ elements?
edited by

2 Answers

Best answer
28 votes
28 votes
Number of subsets of a set of $n$ elements $ = 2^n$

$\quad = {}^nC_0 + {}^nC_1+\ldots + {}^nC_n$

Each of these terms ${}^nC_k$ denotes the number of possible subsets of size $k.$

Now given a subset of size $k,$ how many subsets can it have? $\implies 2^k.$

So, in this way number of inclusive relations on subsets of a set with $n$ elements

$\quad = 2^0 \times {}^nC_0 +2^1 \times {}^nC_1+\ldots +2^n \times {}^nC_n = 3^n$

PS: $3^n = (2+1)^n = {}^nC_0 \times2^0\times1^n + {}^nC_1\times 2^1 \times1^{n-1} \ldots {}^nC_n\times 2^n\times1^0$
selected by
0 votes
0 votes
There are 2^n true inclusion relations of the form A ⊆ B, where A and B are subsets of a set S with n elements.

Related questions

24 votes
24 votes
4 answers
1
makhdoom ghaya asked Nov 14, 2016
5,794 views
How many binary relations are there on a set $A$ with $n$ elements?
22 votes
22 votes
4 answers
2
makhdoom ghaya asked Nov 9, 2016
5,426 views
State whether the following statements are TRUE or FALSE:The union of two equivalence relations is also an equivalence relation.
3 votes
3 votes
1 answer
3
23 votes
23 votes
3 answers
4
makhdoom ghaya asked Nov 14, 2016
4,239 views
How many one-to-one functions are there from a set $A$ with $n$ elements onto itself?