Set theory combinatronics, number of walk function

Question

I am taking a coursera course on discrete math and I have this question that I have hard time figuring out, on how to proceed, any explanation to solution would be highly appreciated.

$$\textrm{A function} \quad \{0,\dots,n\} \rightarrow {Z} \quad \textrm{is a walk function if consecutive values differ by exactly 1, i.e.,} \left |f(i)=(i-1) \right |=1 \quad \textrm{for all} \quad 1=1\dots, n \quad \textrm{ How many walk functions are there from } \{0,\dots,6\} \quad \textrm {to} \quad \mathbb{Z} \quad \textrm{with} \quad f(0)=f(6)=0?$$

Thanks.

Answer 1

To reiterate what has been said in the comments above, a function $f$ from $\{0,1,2,\dots,n\}\to\Bbb Z$ is called a "walk function" (or equivalently a walk sequence) iff $|f(i)-f(i-1)|=1$ for all $i\in\{1,2,3\dots,n\}$. The intuitive interpretation is that you have a person who every second moves exactly one unit away from where he just was in any direction possible. In our case here, we are working in the one-dimensional case (only forwards or backwards) but as problems become more complicated we may open ourselves up to more possible directions of movement.

You will eventually revisit these types of functions when you study random walks.

For now, as per the instructions of the problem we limit our focus specifically to those walk functions from $\{0,1,2,\dots,6\}\to\Bbb Z$ satisfying $f(0)=f(6)=0$, that is to say, those walks where our person takes a total of six steps and ends where he began.

An example of a walk sequence satisfying those conditions might be: $$\begin{cases}f(0)=0\\f(1)=-1\\f(2)=0\\f(3)=1\\f(4)=2\\f(5)=1\\f(6)=0\end{cases}$$

Notice that the above example could have been described a different way... instead of describing it in terms of the position of our person at each time, we could have described it as the direction that our person walked each time he took a step. Using $+$ to denote forward movement and $-$ to denote backward movement, the above example could have instead been notated as:

$$-+++--$$

Notice, that every walk function from $\{0,1,2,\dots,6\}\to\Bbb Z$ satisfying $f(0)=f(6)=0$ could be described uniquely instead as a length $6$ sequence of exactly three $+$'s and three $-$'s and vice versa. That is to say, there exists a bijection between the sets of objects described by the two problems.

We ought to be more rigorous in proving that there is indeed a bijection between the two sets, but if it is obvious or a well known example then it is common to skip this step, only providing clarification upon request.

Explicitly, going from a walk function to a sequence of $+$'s and $-$'s, set the $k$'th entry in the sequence as a $+$ if $f(k)-f(k-1)=1$ and set the $k$'th entry in the sequence as a $-$ if $f(k)-f(k-1)=-1$. We should then take the time to show that this process will never have two different walk functions mapping to the same sequence, and further every sequence is mapped to by some walk function. It is worth taking the time to work through such a proof at least a few times.

One of the most important counting principles you will ever learn is that if there is a bijection between two sets, then they must be of the same size. That is to say, if we have our first problem and it sounds strange or difficult to approach, but we can in a convenient way explain exactly why there are the same number of solutions to the first problem as there are for a second related problem, then we may simply solve the second problem and know that the answer to the first problem will be the same.

Here, we were able to spot the convenient bijection between our original problem of counting how many walk functions there are with those limitations, to the problem of counting how many sequences of $+$'s and $-$'s there are, so we instead solve that.

---

So, the question becomes "How many length 6 sequences of $+$'s and $-$'s exist with exactly three $+$'s and exactly three $-$'s?"

This is going to be a direct application of binomial coefficients.

---

As you go on to try to generalize the formula you found to other or larger numbers, you should notice that there are no walk functions from $\{0,1,2,\dots,n\}\to\Bbb Z$ where $f(0)=f(n)=0$ in the case that $n$ is odd. That is perfectly fine, and you can include that in your final formula by using piece-wise defined function notation. Letting $F(n)$ denote the number of walk functions from $\{0,1,2,\dots,n\}\to\Bbb Z$ where $f(0)=f(n)=0$, you will have

$$F(n)=\begin{cases}0&\text{if}~n~\text{is odd}\\&\text{if}~n~\text{is even}\end{cases}$$

where I intentionally left the expression for when $n$ is even blank for you to fill in yourself.

Answer 2

Sometimes it is useful to have in mind an equivalent problem. In this case, let's suppose you're standing on a step of some long stairs and you ask yourself: In how many ways can I go up and down the stairs taking only one step at a time so that after six movements I end up exactly where I am now? Then you realize that for every step you take upwards you have to take another downwards and hence there are in total three of each. Now suppose $1$ means take a step upward, while $0$ means go down one step, then solving your problem ammounts to finding the number of binary chains of the type $101100$, $001101$, etc.