Let $A = {1, 2, ..., 2014}$. Find the number of functions $f: A \rightarrow A$ satisfied the following properties.
There exists $k \in A$ such that $f$ is non-decreasing function on $\{1, 2, ..., k\}$ and $f$ is non-increasing function on $\{k, k+1,..., 2014\}$.
$|f(n+1)-f(n)| \leq 1 \;\;\forall n= 1, 2, ..., 2013$.
$f(1) = f(2014) = 1$.
My attempt :
Let $f$ be function such that f(k) is the maximum value.
$f(1) \leq f(2) \leq ... \leq f(k)$.
$f(k) \geq f(k+1) \geq ... \geq f(2014)$.
Let $f(k) = l$
so $1 \leq f(i) \leq l \;\;\forall i= 2, 3, ..., k-1$.
$l \leq f(i) \leq l \;\;\forall i= k+1, k+2, ..., 2013$.
Please suggest how to proceed.
$f$ must step up to a maximum, stay at that maximum (perhaps just for one point), then decrease back to $1$. Let the maximum value be $m$, then define $p$ as the first $n$ where $f(n)=m$ and $q$ as the last $n$ where $f(n)=m.$ We have $m-1 \le p \le q \le 2015-m$. The number of functions for a given $m,p,q$ can be counted by finding the number of ways to choose $m-1$ places for the function to step up out of $p-1$ places and similarly $m-1$ places for the function to step down. Now sum over $m,p,q$
Added: a much better approach. Based on the above, there must be an even number of steps up and down. The first half must be up and the last half must be down. There are $2013$ intervals between numbers. Compute the number of ways to pick an even number of them to be steps. Once you choose which gaps to have steps, the function is determined.