Suppose we have an **unweighted directed graph** with vertices numbered as $1...n$

From each vertex $i$ there are edges to $i+1$, $i+2$ and $i+7$.

My task is to find a recurrence $f(i,j)$ to compute the number of paths from vertex $i$ to vertex $j$.

**My current toughs:**

For a base case, if $i \geq j$ then $f(i,j)=0$. For example, there is no path from $1$ to $1$, or from $2$ to $2$. And there is no path from $2$ to $1$.

For a general case, and when $i < j$, from $i$ there are edges to $i+1$, $i+2$ and $i+7$. So we can reach $j$ from $j-1$, $j-2$ and $j-7$. I think the recurrence depends on $f(j-1,j)$, $f(j-2,j)$ and $f(j-7,j)$.

Im doing well?, really i don''t find this intuitive at all.

Brian M. Scott 08/14/2015.

You’re on the right track.

Suppose that $i<j$. Each path from $i$ to $j$ must end with an edge from one of the vertices $j-7,j-2,j-1$ to $j$. Let $k$ be one of these vertices; there are $f(i,k)$ paths from $i$ to $k$, each of which extends to a path from $i$ to $j$ whose last edge is $\{k,j\}$. Thus, you can almost set

$$f(i,j)=f(i,j-7)+f(i,j-2)+f(i,j-1)\;.\tag{1}$$

There are a couple of potential problems here. First, one or more of $k\in\{j-7,j-2,j-1\}$ may be less than $i$. That’s not really a problem, since in that case we set $f(i,k)=0$, as you already did. Next, $j-7$, for instance, might be less than $1$. We can solve that by agreeing that $f(i,j)=0$ if $i$ or $j$ is out of the range from $1$ through $n$.

The last problem is what to do if one of the numbers $j-7,j-2,j-1$ equals $i$. In order for $(1)$ to give the right answer, we must have $f(i,i)=0$, as you have it in your question. However, this isn’t actually correct: there is *one* path from $i$ to $i$, of length $0$.

One way around this difficulty is to set $f(i,i)=1$ for $i=1,\ldots,n$ as an initial condition and then modify $(1)$ to read

$$f(i,j)=f(i,j-7)+f(i,j-2)+f(i,j-1)-\big[i\in\{j-7,j-2,j-1\}\big]\;,$$

where the last term is an Iverson bracket.

There are other ways to make the necessary adjustment, but the irregularity of the set $\{1,2,7\}$ makes all of them a bit messy.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

- Comparing the number of cuts and paths in graph
- Total number of linear paths from any vertex to any other in an undirected graph?
- number of paths between [i] and [j] on a directed unweighted cyclic graph?
- Directed Multigraph or Directed Simple Graph?
- Count ways to reach last layer
- Number of Paths in a Graph
- Disjoint paths in a directed graph
- Find lightest paths from $r$
- A procedure for sampling paths in a directed acyclic graph
- How do you correctly reason that this directed graph is acyclic?

- How to avoid mentioning the name of a character?
- Is there a proverb to expess "You are too late and it's your own fault."?
- A guy asked me to kill 15 trolls, how do I prove that I did it?
- Is this wolf DMPC overpowered or underpowered?
- Sum of the reciprocals of radicals
- How to make slimes a formidable enemy?
- Is it ethical to use knowledge in main job for side gig?
- Public API with authorization token -- is it possible to protect the demo token?
- Can you aim for something behind an invisible creature to avoid the disadvantage?
- Can area of rectangle be greater than the square of its diagonal?
- A dice game called "Greed"
- Did the Apollo astronauts ever take any medications while on their mission in order to calm their nerves?
- What are these stamps in my passport after I was advised to divert via the UK but didn't have a visa?
- Was there a diorama at the Chicago Museum of Science where children could play shooting at a Vietnamese village?
- Roads in Switzerland in December
- What circuit or operation corresponds to the tensor product?
- Isn't an isobar just an isotope?
- How should I deal with an employee who is stealing from the cash counter?
- Why is the EU concerned about the UK "unilaterally withdrawing" from a proposed Irish backstop?
- Is the normal force equal to weight if we take the rotation of Earth into account?
- How can I prevent a human sacrifice from dying before a ritual is complete?
- How can I tell the DM that I wasn't having fun and that I fault him for it?
- Quaternion square root
- Why is counting election totals more difficult than lottery administration?