# GATE1997-13

2.3k views

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

edited
0

In above question we have calculate the number of strictly-increasing functions. But if you also want to understand that how to calculate the total number of monotonically increasing functions (or say non-decreasing functions) then refer to below link :-

https://math.stackexchange.com/questions/1396896/number-of-non-decreasing-functions

It is difficult to understand. But after reading from above link, you will able to remember the generalized formula easily.

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

edited
14
For case (C). i , j  are  from set A(i.e. from n) which is domain of any one to one function , but mapped element f(i) , f(j) are  from range to specific one to one function .
I've considered an example , with n=3(1,2,3) and m=4(1,2,3,4)
for strictly increasing function , if I've mapped (1,2) then for element 2 from set A , I can't map (2,2) since it is one to one , and also I can't map (2,1) because it can't satisfy the property f(i)<f(j) , i.e. 2 !<1 , so element 2 should be map in remaining set element except 1 and 2 so, I've mapped with element(2,3) { I can map with other element of set , but ,we should remember the satifyng property and property of a function.}
Similary , for element 3 , I can't map with below with element 3 of set B ,  so , remaining number elements is 4 only . so , it should be (3,4).

final mapping ,
example :
A(1,2,3)         B(1,2,3,4)
for the satsfying condition f(i)<f(j)  .where i , j are from set A and f(i) , f(j) from set B
Total number of such functions are :
1.{(1,1) ,(2,2), (3,3)}
2.{(1,1),(2,2),(3,4)}
3.{(1,1),(2,3),(3,4)}
4.{(1,2),(2,3),(3,4)}

(1,2,3),(1,2,4),(1,3,4),(2,3,4) , is similar to choose (we can see here , odere is not matter) 3 element from 4 element
Only 4 such possible functions .
So , the possible functions are choose n element from m element  , i.e., mCn
2
Yes. Also, we can consider all permutations of the range- and only 1 is valid.
0
yes, dividing by $n!$.
0
Nice Explanation.
0
thats indeed a nice way of thinking !!
20
part C:- They are talking about strictly increasing functions, strictly increasing functions are always One-One, therefore when i am dealing with strictly increasing then i do not need to think about One-One.

In case function is monotonically increasing ($f(i) \leq f(j)$) then total number of such functions are = $m+n-1\choose n-1$
18
Yes Sachin Sir, In case of monotonically increasing functions (f(i) <= f(j)), the total no of such functions will be Selecting N element from the set of distinct M element such that repetition is allowed.

N element in domain and M element in co-domain. This will be  $\binom{M + N - 1}{N}$. which is also same as $\binom{M + N - 1}{M - 1}$
0
Well explained .Thank u Sir.
0
Can anyone provide more clarification for c?
2

Option B) can also be written as P(m,n) - P(m-1,n) ...

0
@hemant , u r applying (m+n-1,n-1) but this is choclate problem where any person might not get any choclate , but here it has said that f(i)<f(j) so u cant apply this above formula since equality has not given
12

option C is correct, you have to just select any n number from m which can be done in C(m,n) ways, and coming to the arrangement, that chosen n numbers should be in strictly increasing order, so you have just 1 way to arrange them. Hence if you do selection followed by arrangement it will be C(m,n) * 1, which will be simply C(m,n)

0

Best explained @Shubhanshu Thanks

0

Proofs of the number of strictly increasing and monotonically increasing functions. - https://gateoverflow.in/215132/isi-2014-pcb-a2

5
0
@Arjun sir, please solve option c. I am not getting doubt in option c.
1
@ayush... It is given $1\leqslant i\leqslant j\leqslant n$. Suppose a function f maps i=1 f(i=1) to x. But it says j can be equal to i. If j=1 then f(j)= y where f(i)< f(j) i.e x is less than y. But this violates the condition of function as the same value is getting mapped to two different value.
0

for all i,j  1≤ijn?

Doesn't that imply that no such function exists?Because when i=j, f(i)<f(j) cannot happen.

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

Below image contain the answers

A) mPn

B) mPn - m-1Pn

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

0
Option C ans is surely incorrect !  B does  not look promising either !
0
i am not getting b and c can someone explain?

## Related questions

1
1.2k views
Let $R$ be a reflexive and transitive relation on a set $A$. Define a new relation $E$ on $A$ as $E=\{(a, b) \mid (a, b) \in R \text{ and } (b, a) \in R \}$ Prove that $E$ is an equivalence relation on $A$. Define a relation $\leq$ on the equivalence classes of $E$ as $E_1 \leq E_2$ if $\exists a, b$ such that $a \in E_1, b \in E_2 \text{ and } (a, b) \in R$. Prove that $\leq$ is a partial order.
The number of equivalence relations of the set $\{1,2,3,4\}$ is $15$ $16$ $24$ $4$
A partial order $≤$ is defined on the set $S=\left \{ x, a_1, a_2, \ldots, a_n, y \right \}$ as $x$ $\leq _{i}$ $a_{i}$ for all $i$ and $a_{i}\leq y$ for all $i$, where $n ≥ 1$. The number of total orders on the set S which contain the partial order $≤$ is $n!$ $n+2$ $n$ $1$
A polynomial $p(x)$ is such that $p(0) = 5, p(1) = 4, p(2) = 9$ and $p(3) = 20$. The minimum degree it should have is $1$ $2$ $3$ $4$