The Gateway to Computer Science Excellence
+3 votes
300 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).$
in Set Theory & Algebra by (83 points) | 300 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 ?

2 Answers

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

by Boss (16.4k 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

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 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)

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,737 questions
57,388 answers
198,576 comments
105,414 users