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.
[Math] counting monotonically increasing functions
combinatoricsfunctions
Best Answer
None of the functions can be strictly increasing, so we count what I would rather call the monotonically non-decreasing functions.
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}$.