ISI2015-DCG-36

Question

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

• A. $n^n$
• B. $n \log_2 n$
• C. $n^2$
• D. $n!$ 

Answer 1

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