The Gateway to Computer Science Excellence
+2 votes
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!$ 
in Set Theory & Algebra by Boss (17.5k points)
recategorized by | 23 views

1 Answer

+3 votes
$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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,321 answers
198,400 comments
105,155 users