How many monotone increasing functions are there? Let $f:[n]\to [k]$ such that $n,k\in \mathbb{N}$, where $[n]=\{1,2...,n\}$. A weak increasing monotone function satisfies $f(i)\le f(i+1)$ and a strong increasing monotone function satisfies $f(i) < f(i+1)$
a) how many strong increasing monotone functions are there?
b) how many weak increasing monotone functions are there?
c) how many functions are there that are non-monotone (weak) increasing or decreasing
d) how many functions satisfy $f(i) + i \le f(i+1)$
My attempt:
a) we need to choose $n$ different values for $f$ out of $k$ so the answer is $k \choose n$
b) we need to choose $n$ values for $f$ out of $k$ with possible repetitions so $n+k-1 \choose n$
c) all possible functions are $k^n$ and we subtract from that $2$$n+k-1 \choose n$ and add $k$ for the constant functions that we subtracted twice.
d) stuck with this one. Maybe I need to look at it as a recursion series $f(i+1)-f(i)\ge i$
 A: For part d), let us consider the function $g$ defined on $[n]$ such that
$g(n) = (k+1) - f(n),$ $g(n-1) = (k+1) - f(n-1) - (n-1),$ $g(n-2) = (k+1) - f(n-2) - (n-2) - (n-1), \dots$.
The function $g$ satisfies that $g(i+1) \geq g(i)$, thus for counting the number of $f$'s, you can determine the upper bound of $g(n)$ and reduce the problem to part b).
A: For anyone interested, I think I found a nice solution for part d, which I believe is just a bit inaccurate.
We can frame the questions with sticks and balls, where $f(1),...,f(n)$ are the sticks and we look at the gaps between them $x_0,x_1,...,x_{n-1},x_n$ ($x_0$ is the gap before $f(1)$ and $x_n$ is the gap after $f(n)$) in which we need to place place $k$ balls (possible numbers from $[k]$). The reason that $f(i)$ don't impact the number of possible placements $k$ is that the function in weak monotone increasing.
We have the following conditions on the gaps: $x_0\ge 0, x_n \ge 0$ and $x_i \ge i$ for all other $i$. And we need to solve the equation $x_0 + ... + x_n = k$ with these conditions. We can define $y_i = x_i - i$ for $i=1,...,n-1$ and $x_0=y_0, x_n=y_n$ and after substituting the $x_i$ in the equation above we get $\sum_{y=0}^{y=n}y_i=k-\frac{n(n-1)}{2}$ using the sum of an arithmetic series.
Now the answer is simply $n+ k-\frac{n(n-1)}{2} \choose k-\frac{n(n-1)}{2}$ ($n+1$ elements in the summation).
The only problem is that the general formula is $n+k-1 \choose k$ but I get that the difference between the expressions in the "choose" formula is $n+ k-\frac{n(n-1)}{2} - (k-\frac{n(n-1)}{2}) = n$ and not $n-1$. But I think the general idea is correct.
