How many convex functions are there in $[0,1]^2$?

Solution 1:

I am not sure that this is what you want, but here is my thinking about it:

If $n$ is the number of divisions of unity ($n=10$ in your drawing), and $x_i, i=1,2,\ldots n$ is the number of divisions traveled downwards by each segment of your curve (for the green curve $x_1,\ldots ,x_{10}$ would be $5,2,1,1,1,0,0,0,0,0$), then your problem could be formulated as the number of solutions of the following integer equation:

$x_1+x_2+\ldots+x_n=n$

subject to:

$x_1\ge x_2\ge\ldots\ge x_n\ge 0$

We can observe that each solution of this integer equation can be put in $1:1$ correspondence with a partition of $n$ (by ignoring the zeros). For the green line, this is:

$10=5+2+1+1+1$

So the number of convex functions equals $p(n)$, which is the number of partitions of $n$.

Unfortunately, $p(n)$ does not have a nice closed-form formula, but you can see the Wikipedia page Partition_(number_theory) for more details, recurrences, asymptotics, etc.

EDIT: To address OP's question about comparing $p(n)$ with the number of non-increasing functions:

If $q(n)$ is the number of non-increasing functions (not necessarily convex), then by reusing the previous notation, we get that $q(n)$ is the number of integer solutions of the following equation:

$x_1+x_2+\ldots+x_n=n$

subject to:

$x_1, x_2,\ldots, x_n\ge 0$

This is a classic Stars and bars problem (theorem two), whose solution is:

$q(n)= {n + n - 1 \choose n - 1}={2n-1\choose n-1}$

A quick check on Wolfram Alpha shows that $\frac{q(n)}{p(n)}\to\infty$, so $p(n)=o(q(n))$