TIFR CSE 2021 | Part A | Question: 5

Question

Let $n, m$ and $k$ be three positive integers such that $n \geq m \geq k$. Let $S$ be a subset of $\left \{ 1, 2,\dots, n \right \}$ of size $k$. Consider sampling a function $f$ uniformly at random from the set of all functions mapping $\left \{ 1,\dots, n \right \}$ to $\left \{ 1,\dots, \text{m} \right \}$. What is the probability that $f$ is not injective on the set $S$, i.e., there exist $i,j  \in S$ such that $f(i) = f(j)$?

In the following, the binomial coefficient $\binom{n}{k}$ counts the number of $k$-element subsets of an $n$-element set.

• A. $1-\frac{k!}{k^{k}}$

• A. $1-\frac{m!}{m^{k}}$

100. $1-\frac{k!\binom{m}{k}}{m^{k}}$

500. $1-\frac{k!\binom{n}{k}}{n^{k}}$

• A. $1-\frac{k!\binom{n}{k}}{m^{k}}$

Answer 1

Option $(C)$

$P(\text{f is not injective}) = 1 – P(\text{f is injective})$

$= 1 – \frac{\text{injective functions}}{\text{total fuctions}}$

$= 1 – \frac{\text{(choosing k values from m)} * \text{(permuting each value from set S to these k values)}}{m^k}$

$= 1 – \frac{\binom{m}{k} \times k!}{m^k}$

Comments

I think the amswer for it is option E. We have mapping from {1....n} to {1.... m}. So didnt we have to choose k elements from {1....n}

---

No .

we can think it like ,

we have one k element subset here.

How many functions are possible from k element set to → m element set.

it is $m^{k}$.

How many injective function possible here ?

m*(m-1)*(m-2)*...*(m-k+1) [1^st element has m choice ,2^nd has m-1 choice, so on]

=$\frac{m!}{(m-k)!}$

=$\binom{m}{k}*k!$

so our desired probability

=1-$\frac{\binom{m}{k}*k!}{m^{k}}$

in option E,

I think it will if the inverse function from m to n exist then it can be possible from m to n.

 

 

 

---

Ohhh thankyou for clearification.