# How many nondecreasing functions $f:\{1,2, \ldots, n\} \to \{1,2, \ldots, n\}$ with $f(i)\leq i$ are there?

As in title, how to determine the number of nondecreasing functions $f:\{1,2, \ldots, n\} \to \{1,2, \ldots, n\}$ such that $f(i)\leq i$, for all $i \in \{1,2, \ldots, n\}$?

I know that there is in general ${2n-1}\choose{n-1}$ nondecreasing functions.

I also have tried to solve the problem for small n's:

For n=1 we have one such function, for n=2 we have two such functions and for n=3 we have five such functions.

If we list all the possible values that functions can take for $n=3$, we see that there are as many functions as paths connecting all the columns's, for example f(1)=1, f(2)=2, f(3)=3. Starting with f(3)=3, at each step we can go "left" and "down" or remain "at the same level" but we cannot go "up", because then the function would be decreasing.

$f(1)=1$

$f(1)=2$ $f(2)=2$

$f(1)=3$ $f(2)=3$ $f(3)=3$

Having that said we can count how many nondecreasing sequences of the form $(a_1, a_2, \ldots, a_n)$ we have such that $a_i = f(i)$.

• What did you try so far? Did you find a pattern for $n = 1, 2, 3, 4, 5$? – Ronald Aug 21 '18 at 11:05
• Do you mean decreasing or strictly decreasing? As a constant function is (nonstrictly) decreasing, if you function can't be constant, the only possibility is the identity f(i)=i – F.Carette Aug 21 '18 at 11:06
• @F.Carette Nondecreasing is a word which never means what I think it ought to mean (to me it ought to mean that the function is not a decreasing function). It means "increasing (but not necessarily stricltly)". I think it was coined by someone who thought the word "increasing" ought to mean "strictly increasing", and then wanted a word for the non-strict meaning. – Arthur Aug 21 '18 at 11:27
• @JackBlackwell, both your exemple in comment and in question are wrong ($\exists i, f(i)>i$). Your function needs to satisfy $f(1)=1$ no matter $n$. Then $f(2) \in \{1,2\}$,etc... I managed to build every solution step by step for n=1,..5, but I can't find a pattern in the number of solutions. Your question seems way more interesting that I thought – F.Carette Aug 21 '18 at 11:37
• Aren't these just the Catalan numbers? This is just patha in a square lattice that don't go above the diagonal: if $f(i-1)=f(i)$, go right, otherwise go up. – Steve D Aug 21 '18 at 12:07

These are just the Catalan numbers. Plot points in the $n\times n$ grid, with coordinates $(i, f(i))$. Then connect the bottom-left corner to the upper-right corner by going through the points (and never going above the diagonal).
In this picture, the yellow line represents the function: $$f(1) = 1, f(2) = 1, f(3) = 2$$ and the blue line represents the function $$f(1) = 1, f(2) = 2, f(3) = 2$$
• Using the explicit expression $\frac{1}{n + 1} {{2 n} \choose n}$ for the $n$th Catalan number and the formula for the number of nondecreasing functions gives that the fraction of nondecreasing functions that satisfy the above condition is just $2 / (n + 1)$, $n > 0$. – Travis Aug 21 '18 at 14:30