23 views

Suppose $X$ and $Y$ are finite sets, each with cardinality $n$. The number of bijective functions from $X$ to $Y$ is

1. $n^n$
2. $n \log_2 n$
3. $n^2$
4. $n!$

recategorized | 23 views

$1^{st|}$ element of $X$ can map to any $1$ element of $Y$ i.e. $n$ choices.

$2^{nd}$ element of $X$ can map to any $1$ element of remaining $n-1$ elements of $Y$ i.e. $n-1$ choices.

$3^{rd}$ element of $X$ can map to any $1$ element of remaining $n-2$ elements of $Y$ i.e. $n-2$ choices.

.......

$(n-1)^{th}$ last element of $X$ can map to any $1$ element of remaining $2$ elements of $Y$ i.e. $2$ choices.

$n^{th}$ element of $X$ can map to only last remaining element of $Y$ i.e. $1$ choice.

So number of bijective function possible $=n*(n-1)*(n-2)......3*2*1 = n!$

Hence Option $D.$ is the correct answer.
by Boss (24k points)

+1 vote