# counting monotonically increasing functions

How many monotonically increasing functions are there with domain $\mathbb Z_7$ and codomain $\mathbb Z_5$?
So, the domain is $\{0, 1, 2, 3, 4, 5, 6\}$ and the codomain $\{0, 1, 2, 3, 4\}$.
I found the total number of functions to be $405$ and know that it will be a recurrence relation, but I have had no luck deriving it.

• The total number of functions is $5^7$. But monotonically increasing is far smaller. Use Stars and Bars. – André Nicolas Nov 29 '15 at 22:36
• Would you be able to give me an example of how to apply Stars and Bars in this situation? – Hector Nov 30 '15 at 2:13

Such a function can be completely described once we know how many of $0,1,2,\dots,6$ are mapped to $0$, how many are mapped to $1$, how many are mapped to $2$, and so on. For if $x_0$ of them are mapped to $0$, it must be the first $x_0$ of $0,1,2,\dots$. And if $x_1$ of them are mapped to $1$, it must be the next $x_1$ of $0,1,2,\dots$, and so on.
Here is a quick shorthand description of such a function: $10402$. This says that $1$ object in $\mathbb{Z}_7$ is mapped to $0$, $0$ objects are mapped to $1$, $4$ objects are mapped to $2$, none are mapped to $3$, and $2$ are mapped to $4$. In function language, we have $f(0)=0$, $f(1)=f(2)=f(3)=f(4)=2$, and $f(5)=f(6)=4$.
So we want to count the number of solutions of the equation $x_0+x_1+x_2+x_3+x_4=7$ in non-negative integers. By Stars and Bars, this number is $\binom{7+5-1}{5-1}$.