14
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What did you try so far? Did you find a pattern for $n = 1, 2, 3, 4, 5$? $\endgroup$ – Ronald Aug 21 '18 at 11:05
  • 1
    $\begingroup$ 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 $\endgroup$ – F.Carette Aug 21 '18 at 11:06
  • 1
    $\begingroup$ @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. $\endgroup$ – Arthur Aug 21 '18 at 11:27
  • 1
    $\begingroup$ @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 $\endgroup$ – F.Carette Aug 21 '18 at 11:37
  • 2
    $\begingroup$ 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. $\endgroup$ – Steve D Aug 21 '18 at 12:07
10
$\begingroup$

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).

enter image description here

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

[Green is where they overlap.]

The Catalan numbers count the number of paths below the diagonal. And the points you've plotted uniquely identify such a path.

$\endgroup$
  • $\begingroup$ Nice, thank You very much for the solution. $\endgroup$ – Jack Blackwell Aug 21 '18 at 13:47
  • 4
    $\begingroup$ 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$. $\endgroup$ – Travis Aug 21 '18 at 14:30

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.