GATE CSE 1997 | Question: 13

Question

Let $F$ be the set of one-to-one functions from the set $\{1, 2, \dots, n\}$ to the set $\{1, 2,\dots, m\}$ where $m\geq n\geq1$.

1. How many functions are members of $F$?

2. How many functions $f$ in $F$ satisfy the property $f(i)=1$ for some $i, 1\leq i \leq n$?

3. How many functions $f$ in $F$ satisfy the property $f(i)<f(j)$ for all $i,j \ \ 1\leq i \leq j \leq n$?

Comments

Hi pranay2022 i have a small doubt if we are selecting m element  from n element then it can contain anything let say it contain 1 also so who will map to 1 because everyone greater then 1 and it should be strictly increasing order.

---

@Nirmalya, Hi. The whole point is that we are not concerned about assignment of elements in those selected N elements. Because we only care till choosing them. After you chose them, you only have one possible way i.e arranging them in increasing order

So if 1 is in the N elements we selected, then it’ll get assigned to first element becuase it is the least one. So even if we choose the last N elements out of the M elements in codomain, the (M-N)the element is assigned to first one.

---

@Deepak Poonia

sir not able to understand option c 

Answer 1

(a) A function from A to B must map every element in A. Being one-one, each element must map to a unique element in B. So, for $n$ elements in A, we have $m$ choices in B and so we can have $^m\mathbb{P}_n$ functions.

(b) Continuing from (a) part. Here, we are forced to fix $f(i) = 1$. So, one element from A and B gone with $n$ possibilities for the element in A and 1 possibility for that in B, and we get $n \times$ $^{m-1}\mathbb{P}_{n-1}$ such functions.

(c) $f(i) < f(j)$ means only one order for the $n$ selection permutations from B is valid. So, the answer from (a) becomes $^m\mathbb{C}_n$ here.

Comments

Should not (1,3) (2,2) (3,4)  be included as one of the function

---

@Arjun sir. For part B can't we say

               mPn - (m-1)Pn?

All the mPn functions except those which doesnt use 1 in the domain(m-1)Pn? 

---

@Shubhanshu thank you well explained   

Answer 2

Below image contain the answers 

 

Answer 3

A) ^mP_n

B) ^mP_n - ^m-1P_n

C) (m*(m-1))/2

Comments

Option C ans is surely incorrect !  B does  not look promising either !

---

i am not getting b and c can someone explain?

---

b is correct just have to simplify this further we will get the same answer .