Let $I_j={\{1,2,\ldots,j}\}$ for $j \in \mathbb{N}$. For $m,n \in \mathbb{N}$, how many non-decreasing functions $f:I_m \to I_n$ exist?
[Math] Number of non-decreasing functions between two finite sets
combinatorics
combinatorics
Let $I_j={\{1,2,\ldots,j}\}$ for $j \in \mathbb{N}$. For $m,n \in \mathbb{N}$, how many non-decreasing functions $f:I_m \to I_n$ exist?
Best Answer
There are $\displaystyle \binom{m+n-1}{m}$ such functions.
One of many ways to see this: I start with two counters, $a$ and $b$, both equal to $1$. I take $m+n-1$ steps. At every step, I either increase $b$, or I output $f(a) = b$ and then increase $a$. Exactly $m$ steps have to be output steps (since I need to define $f$ on all of $I_m$); the other $n-1$ are steps where I increase $b$ (so that $b$ starts with value $1$ and ends at value $n$). Note that some of the increasing steps may take place before any output steps or after all output steps; that's fine (and corresponds to the cases where $f(1)>1$ and $f(m)<n$ respectively). Every non-decreasing $f:I_m\rightarrow I_n$ corresponds to a unique such process, and every such process yields a unique such function.
So it suffices to count the number of such processes, of which there are $\displaystyle\binom{m+n-1}{m}$, since such a process is exactly given by the choice of which $m$ of its steps are output steps.
You might also try to reduce this problem to a balls-in-boxes / stars-and-bars counting problem -- think about nested boxes of balls.