Name: Counting With Bijections
Uploaded: 2019-07-19
Duration: 11 min 43 s
Description: In this informative video, you will learn about the Bijection principle in algebra. Let's watch, understand and master this concept right away!

Question

Let

X

be a set containing

n

elements. Find the number of all ordered triples

(A, B, C)

of subsets of

X

such that

A

is a subset of

B

and

B

is a proper subset of

C

.

Accepted Answer

Any element has $2$ choices whether to be a part of any subset or not.

Let us denote by $0$ or $1$ the absence or presence of an element of $X$ in the sets $X$ .

For any fixed element of $X$ , following are the possibilities

Case $A$ $B$ $C$

$p$ $0$ $0$ $0$

$q$ $0$ $0$ $1$

$r$ $0$ $1$ $0$

$s$ $1$ $0$ $0$

$t$ $0$ $1$ $1$

$u$ $1$ $X$ $1$

$v$ $1$ $1$ $0$

$w$ $1$ $1$ $1$

There are only four choices to conform with $A \subset B \subset C$ , namely, $000$ , $001$ , $011$ , $111$ .

Any element has four possibilities as shown above, so in total there are $4^{n}$ possibilities.

But $B \neq C$ as $B$ is a proper subset of $C$ .

So now only three choices $000$ , $011$ , $111$ are possible for ordered triples of form $(A, B, B)$ .

Total number of ordered triples $= Total - Triples of form (A, B, B)$

There are $3^{n}$ triples $(A, B, B)$ which could be of the form $000, 011, 111$ .

Therefore, the number of triples $(A, B, C)$ with $A \subset B \subset C$ but $B \neq C$ equals $4^{n} - 3^{n}$ .

Let $X$ be a set containing $n$ elements. Find the number of all ordered triples $(A, B, C)$ of subsets of $X$ such that $A$ is a subset of $B$ and $B$ is a proper subset of $C$ .

Important Questions on Combinatorics

Learn and Prepare for any exam you want !

Let X be a set containing n elements. Find the number of all ordered triples A,B,C of subsets of X such that A is a subset of B and B is a proper subset of C.

Important Questions on Combinatorics

Learn and Prepare for any exam you want !

Let $X$ be a set containing $n$ elements. Find the number of all ordered triples $(A, B, C)$ of subsets of $X$ such that $A$ is a subset of $B$ and $B$ is a proper subset of $C$ .