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.


closed as off-topic by Wolfgang, Ilya Bogdanov, user1688, Alex Degtyarev, Jan-Christoph Schlage-Puchta Sep 19 '16 at 10:06

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Wolfgang, Ilya Bogdanov, Community, Alex Degtyarev
If this question can be reworded to fit the rules in the help center, please edit the question.


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.


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.)


Not the answer you're looking for? Browse other questions tagged or ask your own question.