Let $A = \{1,2,3,\dots,10\}$ and $B = \{1,2,3,\dots,20\}$.

Find the number of non-decreasing functions from $A$ to $B$.

What I tried:

Number of non-decreasing functions = (Total functions) - (Number of decreasing functions)

Total functions are $20^{10}$. And I think there are ${20 \choose 10}$ decreasing functions. Since you choose any $10$ codomain numbers and there's just one way for them to be arranged so that the resultant is a decreasing function.

However my answer doesn't match. Where am I going wrong?

How can I directly compute the non-decreasing functions like without subtracting from total?


Given a non-decreasing function $f:A\to B$, consider the function $\hat f:A\to\{1,2,\ldots,29\}$ given by

$$\hat f(n)=f(n)+n-1$$

In other words,

$$\hat f(1)=f(1),\ \hat f(2)=f(2)+1,\ \ldots,\ \hat f(10)=f(10)+9$$

Then $f$ is non-decreasing if and only if $\hat f$ is strictly increasing. If you look closely you will see that this transformation of $f$ to $\hat f$ is a bijection from {non-decreasing functions from $A$ to $B$} to {strictly increasing functions from $A$ to $\{1,2,\ldots,29\}$}. I need to rush off now so I can't type the details, but I think they will be clear: let me know if you need me to add details when I get back.

The strictly increasing functions are easy to count, since there is a bijection from those functions to the sets of the same size of the domain taken from a set of the same size as the co-codomain. I.e. given a set of size $10$ taken from the set $\{1,2,\ldots,29\}$ we take $\hat f(1)$ as the smallest member of the set, $\hat f(2)$ as the second-smallest, etc.

These two bijections show that your desired number of non-decreasing functions is

$${29 \choose 10}$$

To make things more clear, here is how to get a non-decreasing function $f:\{1,2,\ldots,10\}\to\{1,2,\ldots,20\}$.

First, choose any $10$ distinct numbers from $\{1,2,\ldots,29\}$. Sort them in increasing order. Then we define $f(1)$ as the smallest of those chosen numbers. We define $f(2)$ as the second-smallest of those chosen numbers minus $1$. (This is guaranteed to be greater than or equal to $f(1)$). We define $f(3)$ as the third-smallest of those chosen numbers minus $2$. (This is guaranteed to be greater than or equal to $f(2)$). ... We define $f(10)$ as the tenth-smallest of those chosen numbers minus $9$. (This is guaranteed to be greater than or equal to $f(9)$).

  • $\begingroup$ To get the final answer we have to choose any 10 numbers from co domain and for a given selection there is only one arrangement that satisfies the strictly increasing condition . That's why the answer is just 29 choose 10. Is this reasoning correct ? $\endgroup$ – Sudhanshu Aug 14 '15 at 13:37
  • $\begingroup$ @Sudhanshu: I'm not sure what you mean. I added a section on how to get an appropriate function from a subset of $\{1,2,\ldots,29\}$. Does this answer your question? $\endgroup$ – Rory Daulton Aug 14 '15 at 17:48
  • $\begingroup$ I got it thanks! $\endgroup$ – Sudhanshu Aug 14 '15 at 18:01

The opposite of a nondecreasing function is not a decreasing function. For example, the function that maps $1 \mapsto 1, \;2 \mapsto 3, \;3 \mapsto 2$ is neither decreasing, nor nondecreasing.

But your idea can be adapted to calculate the number of nondecreasing functions. You just need to consider the number of ways to choose 10 numbers from 20 with repetitions.

  • $\begingroup$ This is unfortunate terminology. $\endgroup$ – Akiva Weinberger Aug 14 '15 at 11:10

Means Here function satisfy the following Condition.

$f(1),f(2),f(3),.......f(10)\in \left\{1,2,3,4,5,...,20\right\}$

$\; \bullet f(1)<f(2)<..........<f(10)\;,$ Total no. of possibilities $ = \displaystyle \binom{20}{10}$

$\;\bullet f(1)\leq f(2)<f(3)<.......<f(10)\;,$ Total no. of possibilities $\displaystyle \binom{20}{9}$

There are $9$ Such cases. So Total Possibilities for $\bf{2^{nd}}$ cases $ \displaystyle 9 \times \binom{20}{9}$

$\;\bullet\; f(1)\leq f(2)\leq f(3)<......,f(10)\;,$ Total cases $\displaystyle \binom{20}{8}$

These are $8$ such cases . So Total $\displaystyle 8\times \binom{20}{8}$

Similarly Calculate in that manner.

may be it helps to you.

Now We can add all possibilities , we get

$\displaystyle = \binom{20}{10}+9\times \binom{20}{9}+8\times \binom{20}{8}+........+1\times \binom{20}{1}$

$\displaystyle = \underbrace{\binom{20}{10}+\binom{20}{9}}+8\left[\underbrace{\binom{20}{9}+\binom{20}{8}}\right]+..........+\binom{20}{1}$

$\displaystyle = \binom{21}{10}+8\times \binom{21}{9}+.....+\binom{20}{1}$

Above we have uese the formula $\displaystyle \binom{n}{r}+\binom{n}{r-1} = \binom{n+1}{r}$

Now Adding in similar manner, We get final answer $\displaystyle = \binom{29}{10}$

  • $\begingroup$ The resultant is very difficult to compute by this method .. $\endgroup$ – Sudhanshu Aug 14 '15 at 10:54
  • $\begingroup$ Can we simplify it to a single term ? The given answer is 29 choose 10 $\endgroup$ – Sudhanshu Aug 14 '15 at 10:56
  • $\begingroup$ Your idea is correct, but your formula is wrong. For example, for the second case there are not $8$, but ${ 9 \choose 2} = 36$ possibilites. $\endgroup$ – Dominik Aug 14 '15 at 11:14
  • $\begingroup$ No Dominik , actually here i am calculating for $1\leq 2<3<4<......<10,$ then for increasing function, we get $f(1)\leq f(2)<f(3)<...<f(10),$ Now i have the position of $\leq $ in Rightward Direction, Thats why i count as $9$ $\endgroup$ – juantheron Aug 14 '15 at 11:25
  • $\begingroup$ My fault, i meant your third case, not the second. There you count the possibilites for $1 \le 2 \le 3 < 4 < \ldots < 9$ to $1 \le 2 < 3 < \ldots < 9 \le 10$, but you forget cases like $1 < 2 \le 3 \le 4 < \ldots < 9$. $\endgroup$ – Dominik Aug 14 '15 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.