edited by
1,629 views
2 votes
2 votes
Consider a function F from set A to B having A={1,2,...n} and B={1,2,....m} Find number's of f in F where f is defined as :

1. f(i)<=f(j) and 1<=i<=j<=n

2.f(i)< f(j) and 1<=i<=j<=n

3. f(i) >=f(j) and 1<=i<=j<=n

4. f(i) > f(j) and   1<=i<=j<=n.
edited by

1 Answer

Best answer
2 votes
2 votes

Case 1: Indicates that function is non-decreasing. Which means that, from the co-domain of the first $m$ numbers, we have to pick elements such that all $n$ numbers get a value assigned to them. This assignment is a bijection. To understand this let's assume $k$ numbers are the ones assigned. These k numbers have a single ordering to be assigned to the $n$ numbers in the domain.

An example for $n=4$ and $m=5$, if you know that in the image of $f$ there are two $1$s, two $4$s . Then the only function with that property (which is non-decreasing) is:

\begin{align}
f(1)=1\\
f(2)=1\\
f(3)=4\\
f(4)=4\\
\end{align}

Thus, we can see that this is same as finding the number of solutions for : $\,x_1+x_2+\cdots+x_m=n$. Which is: $$ \bbox[yellow,5px,border:2px solid red]
{\;\binom{n+m-1}{n}
}
$$

Case 2: Indicates that the function is strictly increasing. Thus the numbers in the range are clearly distinct. This is simply choosing n numbers from the set of m numbers. Which is: 

$$ \bbox[yellow,5px,border:2px solid red]
{\;\binom{m}{n}
}
$$

Case 3: Indicates that function is non-increasing. This is similar to case 1 and the same bijection in the reverse order applies. So the answer would be same as Case 1 : $\color{blue}{\binom{n+m-1}{n}}$

Case 4: Symmetric case of Case 2 : $\color{red}{\binom{m}{n}}$

Hope it helps.. 

selected by

Related questions

1 votes
1 votes
2 answers
2
Lakshman Bhaiya asked Oct 7, 2018
666 views
The function $f_{N}\rightarrow_{N}$ is one to one and the sum of all intercepts of its graph is $10$, the sum of all the intercept of the graph of $y =f^{-1}(x) is:$$A) 1...
2 votes
2 votes
0 answers
3
Lakshman Bhaiya asked Oct 7, 2018
588 views
Let $f(x)$ mean that function $f$ ,applied to $x$,and $f^{n}(x)$ mean $f(f(........f(x)))$,that is $f$ applied to $x$ ,$n$ times.Let $g(x) = x+1$ and $h_{n}(x)=g^{n}(x).$...