Generalize the number of total overall hops possible in a line network

Question

Suppose I have a network of computers arranged in a line, like in the image I made below.

I want to know the total number of hops possible.

For example, $A$ gets to $B$ in $1$ hop, to $C$ in $2$ and to $D$ in $3$.

$B$ and $C$ are a little different, they get to the others in $1$, $1$ and $2$ hops.

$D$ is like $A$.

In this case, with four computers, the total number of possible hops is 20. But how can I generalize the computation of this for $n$ computers in a line?

Answer 1

@Imray;

I am getting

for A -> B -> C -> D -> E

$$1+2+3+4=10$$

$$1+2+3 = 6$$

$$1+2=3$$

$$1=1$$

10 + 6 + 3 + 1 = 20 and now there is the reverse direction, 2 * 20 = 40

This pattern repeats itself so doing the summation:

$$2 \sum _{k=1}^{n-1} \left(\sum _{m=1}^k m\right)=\frac{1}{3} (n-1) n (n+1)$$

$$f(n)=\frac{1}{3} (n-1) n (n+1)$$

Answer 2

So after thinking about it a lot, and doing some of my own research, I discovered that the solution follows a pattern that has applications in other areas as well (e.g. Nuclear Shell Model)

What I did is I manually solved the problem with two nodes, three nodes, four nodes and five nodes and came up with total hop values of $8$, $20$, $40$, $70$ respectively. I then Googled this series and came up with some interesting results. You can Google it yourself if your interested - there are lots of interesting connections with Pascal's Triangle, Triangular Numbers, Cubic Series', and other fun unexpected stuff.

I then found this great blog post by Nadav where he generalizes the series in terms of $n$. He first determines that it's a cubic series by looking at the differences between consecutive values. So for example, for

2  8  20  40  70

the differences between them are

 6  12  20  30

and in turn, the differences between the differences are

   6  8  10

and again, the differences are

    2  2

The differences are the same! Since it took three steps, we know it's a cubic series.

Then he sets up a system of equations using the points $(1, 2)$, $(2, 8)$, $(3, 20)$, $(4, 40)$ etc

a + b + c + d = 2

8a + 4b + 2c + d = 8

27a + 9b + 3c + d = 20

64a + 16b + 4c + d = 40

and solves it to arrive at

$$\frac{n^3}{3} + n^2 + \frac{2n}{3}$$

So in other words, the $n^{th}$ terms of the series can be found using the formula above.

Back to my question, if I have four computers in my network, I want the fourth value in this series - so I input 3 into the formula since $0$ is the first in the series.

$$\frac{3^3}{3} + 3^2 + \frac{2(3)}{3} = 20$$

:-)

---

Or Simpler

Or to make it simpler for this problem, I modified the formula so you could use the exact number of nodes as $n$. For example, if you want to know how many hops there are with $n$ nodes, just use $n$ directly in:

$$\frac{n^3}{3} - \frac{1}{3}n$$

Answer 3

One way to think about your problem would be using a graph. I believe in your example you're counting twice the total sum of the edges in a weighted $K_{4}$ graph. Where the weight of edge $ij$ is $w_{ij}$=The hopping distance between $i$ and $j$. You could obtain your solution recursively. So if $f(n)$ is the sum in the weighted $K_{n}$ it follows that $$f(n+1)=f(n)+2\sum_{i=1}^{n} w_{i(n+1)}$$ Is the sum of the weighted $K_{n+1},$ Where $w_{i(n+1)}=(n+1)-i$.