298 views

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).$
| 298 views
+4

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.

I hope this helps.

0
Nice approach
0

@Kushagra
Can you please explain this new function g in more detail?

0
Are you asking me the reason why g is strictly increasing when f is non - decreasing ?
+2
I didn't get how you make function g.
But, now I got it.
It's like sequence $0<1<2<n-1$ is strictly increasing.
Now $f(1) + 0< f(2)+1<f(3)+ 2< f(n)+ n-1$
where $f(1)\leq f(2)\leq f(3)\leq…\leq f(n)$
will be strictly increasing sequence only as if $u < v$ and $w \leq x$ then $u+w<v+x$

Am I right ?

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

by Boss (16.3k points)
+1
0
I feel there are mistakes in the last lines as well.
0

@ankitgupta.1729

I agree that the reference should have been mentioned but as long as the solution is correct whats the harm in selecting it as the best one? Its beneficial for the future users as they can rely on this.

+2

@MiNiPanda

There are many beautiful answers( some are with 2-3 lines) are available on math.stackexchange for ISI questions. Anyone can copy and paste it here. My point was : atleast write it in your own words after reading that answer :)

+1 vote

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.

by Loyal (9.8k points)