Let $f(n)$ be the number of integer sequences with length of n which start with $0$, end with $0$ and every two adjacent numbers in the sequence has the difference of $1$ (i.e. for every $1\leq i \leq n-1$, $|a(i)-a(i+1)|=1$, numbers can be also negative).
(a) find the formula for $f(n)$
(b) find $g(n)$ under the same conditions but with the new condition $|a(i)-a(i+1)|\leq1$ for every $i$. (Replacing the last condition of f(n))
Thanks a lot if someone can help me!
a) $f(n)$ is equal to the number of sequences of $(n-1)$ finite differences $(a_{p+1}-a_p)$ all of which must be either $=1$ or $-1$
The $(n-1)$ numbers must sum to $0$
There must be the same number of $-1$ as$+1$
This can only happen if $(n-1)$ is even
So $f(n) =0$ for even $n$
for odd $n=2k+1$ you must have $k$ plus ones and $k$ minus ones in the sequence $2k$ of finite differences
There are $\binom{2k}k$ ways to choose where the negatives will be in the sequence
So $$f(n)= \binom{n-1}{\frac{n-1}2}$$
for odd $n$
b) I think that $f(n)$ is infinite for $n>2$
****** EDIT ***
I provide my best answer for b) on the understanding that we have an integer sequence.
Let $g(n) $represent the number of sequences for which the finite differences are in the set $\{-1,0,1\}$
Each sequence of first differences must consist of ... - $m$ positive ones - $m$ negative ones - $(n-1)-2m$ zeros
for some $m$ in the range from zero to $ \lfloor \frac {n-1}2 \rfloor $
there are $\binom{n-1}{n-1-2m}=\binom{n-1}{2m}$ ways to place the zeros
then $\binom{2m}m$ ways to arrange the positive and negative ones
So $$ g(n) =\sum_{m=0}^{ \lfloor \frac {n-1}2 \rfloor} \binom{n-1}{2m} \binom{2m}m$$