0
$\begingroup$

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.

$\endgroup$

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.

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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