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.

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

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}$.


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.