1,799 views
3 votes
3 votes

Let $m$ and $n$ be two integers such that $m \geq n \geq 1.$ Count the number of functions $f : \{1, 2, \ldots , n\} \to \{1, 2, \ldots , m\}$ of the following two types:

  1. strictly increasing; i.e., whenever $x < y, f(x) < f(y),$ and
  2. non-decreasing; i.e., whenever $x < y, f(x) ≤ f(y).$

2 Answers

7 votes
7 votes
a). Number of Strictly increasing functions $f:\{1,2,3,\ldots,n\}\to\{1,2,3,\ldots,m\}$ where $m\geq n \geq 1$ 

A function $f:\{1,2,3,\ldots,n\}\to \{1,2,3,\ldots,m\}$ is determined by how the values $f(1),f(2),f(3),\ldots,f(n)$ are assigned. Since $f$ is a strictly increasing function and for a strictly increasing function, each value in the domain is mapped to a distinct element in the co-domain.

$f(1)<f(2)<f(3)<\ldots<f(n)$

So the number of ways to select $n$ elements from a set with $m$ elements is  - $\Large\binom{m}{n}$

Once we have selected these elements, there is only one way to assign them -assigning the smallest element in the range to be f(1), the next smallest to be f(2), and so on. Hence, the number of strictly increasing functions is- - $\Large\binom{m}{n}$

b). Number of Non Decreasing functions $f:\{1,2,3,\ldots,n\}\to \{1,2,3,\ldots,m\}$ where $m \geq n \geq 1$ 

Since $f$ is a non-decreasing function, the function is completely determined by how many values of $j\in \{1,2,3,\ldots,n\}$ are assigned to equal $k\in \{1,2,3,\ldots,m\}.$

For example - consider non-decreasing functions

$f:\{1,2,3,4,5\}\to\{1,2,3,4,5,6,7\}$

Then we have - $x_1+x_2+x_3+x_4+x_5+x_6+x_7 = 5$

And suppose it is defined as - $f(1)=f(2)=3,f(3)=4,f(4)=f(5)=7$

so $x_1 = 0,x_2 = 0,x_3 = 2,x_4 = 1,x_5 = 0,x_6 = 0x_7 = 2$

Let $x_k, 1\leq k \leq m$,  be the number of values of $j\in \{1,2,3,\ldots,n\}$ such that $f(j)=k$ . Then

$x_1+x_2+x_1+\ldots +x_m = n$
which is an equation in the nonnegative integers.

It's solution is given by -  $\Large\binom{m+n-1}{n}$

So, number of non decreasing functions $f:\{1,2,3,\ldots,n\}→\{1,2,3,\ldots,m\}$ where $m\geq n \geq 1  = \Large\binom{m+n-1}{n}$

2 votes
2 votes

For strictly increasing function  mCn

Choose any number n nos. from the co-domain and map it to the domain

and for non - decreasing function the answer is m+n-1Cn 

Make a new function g : {1,2,....,n} → {1,2,3,....m,m+1,m+2,...,m+n-1}

such that g(1) = f(1), g(2) = f(2) +1 , g(3) = f(3) +2 ,.......g(n) = f(n) +(n-1)

If you look at the function closely you will find that if f is non-decreasing then g is strictly increasing. 

So, the answer is equal to no. of strictly increasing functions in g.

Related questions

2 votes
2 votes
3 answers
1
jjayantamahata asked Mar 15, 2018
666 views
Let $X_1,X_2,X_3,X_4$ be i.i.d. random variables each assuming the value $1$ and $-1$ with probability $\dfrac{1}{2}$ each. Then, the probability that the matrix $\begin{...