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?
Best Answer
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)$).