What is the number of the ways of travelling through a path graph to reach a node from another? [closed]

Question

For the sake of simplicity, let's take a path graph of length 3, $P_3$ and say we want to get from one of its ending points to another. So, we have the vertices $v_1, v_2, v_3$ and thus two edges. The distance between $v_1$ and $v_3$ is 2, therefore we have to steps to take in order to get from $v_1$ to $v_3$. The number of the ways I can take before getting to $v_3$ is 2. Call this number $\mathcal N$. These two scenarios are as following.

1. $v_1 \rightarrow v_2 \rightarrow v_1$
2. $v_1 \rightarrow v_2 \rightarrow v_3$

Hopefully, you've got the idea. But to make sure, I'm going to calculate the $\mathcal N$ for $P_5$. As you can see, I've got 4 steps to take.

1. $v_1 \rightarrow v_2 \rightarrow v_1 \rightarrow v_2 \rightarrow v_1$
2. $v_1 \rightarrow v_2 \rightarrow v_1 \rightarrow v_2 \rightarrow v_3$
3. $v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_2 \rightarrow v_3$
4. $v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_2 \rightarrow v_1$
5. $v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4 \rightarrow v_3$
6. $v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4 \rightarrow v_5$

So here, $\mathcal N = 6$.

Here is my question: I have raised this question myself and found a solution of my own which seems correct from professors' review:

What is the $\mathcal N$ of any $P_n$?

This question has the answer when you take the ending vertices as the starting and the destination ones. But once you get this formula, you can easily find out a way to calculate the $\mathcal N$ when you choose arbitrary nodes for starting and destination vertices other than $v_1$ and $v_n$.

And here is my problem: I cannot find a reference to this kind of questions in order to further my studies and do more research. Any books or articles related to such studies will be much appreciated.

Answer 1

The basis for this kind of combinatorics is the following observation: If you take the adjacency matrix of a directed graph $$A_{ij} := \#\text{edges } v_i \leftarrow v_j$$ then $(A^l)_{ij}$ is the number of directed paths from $v_j$ to $v_i$ of length $l$ (with loops allowed). With this insight a lot of path-counting combinatorics becomes linear algebra.

In you case $A = \begin{pmatrix} 0 & 1 & & & \\ 1 & 0 & 1 & & \\ & \ddots & \ddots & \ddots & \\ & & 1 & 0 & 1 \\ &&& 1 & 0 \end{pmatrix}$ so can compute $\mathcal{N}$ by diagonalising $A$ for example.

Answer 2

In this particular case there is a simple approach. Take the infinite path with the integers as its vertex set. The number of walks of length $k$ starting at $0$ is $2^k$; the number of walks of length $k$ that start at zero and do not go below $0$ can be computed by the reflection principle. (Google on "reflection principle random walk" unless you're interested in Brownian motion.)