The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+23 votes

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

asked in Set Theory & Algebra by Veteran (59.8k points)
edited by | 1.4k views

2 Answers

+28 votes
Best answer
(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.
answered by Veteran (395k points)
edited by
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)}

(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
Yes. Also, we can consider all permutations of the range- and only 1 is valid.
yes, dividing by $n!$.
Nice Explanation.
thats indeed a nice way of thinking !!
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$
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}$
Well explained .Thank u Sir.
Can anyone provide more clarification for c?

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

@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

@junaid ahmad

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)


Best explained @Shubhanshu Thanks 


Proofs of the number of strictly increasing and monotonically increasing functions. -

@Arjun sir, please solve option c. I am not getting doubt in option c.
@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.

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.

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

A) mPn

B) mPn - m-1Pn

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

answered by Active (4k points)
Option C ans is surely incorrect !  B does  not look promising either !
i am not getting b and c can someone explain?

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,071 questions
53,206 answers
70,424 users