# ISI 2014 PCB A2

627 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).$
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}$

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.

5

@MiNiPanda

copying the given answer violates the copyright.

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
Great approach, but instead of copying should have given the link.
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.

## Related questions

1
358 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{pmatrix}X_1 &X_2\\ X_3 &X_4\end{pmatrix}$ is nonsingular equals $1/2$ $3/8$ $5/8$ $1/4$
Read the C code given below. What would be the output of the following program? Justify your answer. #include <stdio.h> int myrecurse(int a, int b){ return (b == 1 ? a: myrecurse(a, b-1) + a); } main() { int a[]= {2,3,4,5,6}; int i, x; ... . Give an $O(n log n)$ algorithm to determine whether the given sequence $S$ has a subsequence whose sum is zero, and justify the correctness of the algorithm.
Let $A$ be a 30 40 matrix having 500 non-zero entries. For $1 \leq i \leq 30$, let $r_i$ be the number of non-zero entries in the $i$-th row, and for $1 \leq j \leq 40$, let $m_j$ be the number of non-zero entries in the $j$-th column. Suppose ... top of the stack contains the value $max_{1\leq i \leq 30} r_i$. Write pseudo-code for creating such a stack using a single scan of the matrix $A$.
Let $A$ be a $30 \times 40$ matrix having $500$ non-zero entries. For $1 \leq i \leq 30$, let $r_i$ be the number of non-zero entries in the $i$-th row, and for $1 \leq j \leq 40$, let $m_j$ be the number of non-zero entries in the $j$-th column. Show that there is a k such that $1 \leq k \leq 30$, $r_k \geq 17$ and there is an $l$ such that $1 \leq l \leq 40$, $m_l \leq 12$.