I am trying to understand a publication on structural path analysis in economics. It uses some concepts from graph theory with which I am unfamiliar - but even so, I must be confused about the combinatorics, because the numbers don't add up:
The 1988 article describes an input-output matrix $\mathbf{A}$, where the columns and rows correspond sectors of an economy and the elements of the matrix $a_{ij}$ are trade volumes between sectors $i \rightarrow j$.
In the graph theory approach that is introduced, a vertex $i$ correspondes to an economic sector $i$ and the arc $i \rightarrow j$ corresponds to the trade volume between sectors. The authors then state:
For example, in an $n\times n$ input-output matrix, the number $P$ of all possible elementary paths between two vertices $j$ and $i$ is equal to
$$ P=1+(n-2)+(n-2)(n-3)+\ldots+(n-2)(n-3) \ldots 2 \times 1=(n-2) ! \sum \frac{1}{k !} $$
By elementary paths, the authors mean simple paths, where vertices are unique. (I am guessing they forgot to define the range for the index $k$ here.)
and consequently, the number $N$ of all elementary paths for all pairs of different vertices is equal to
$$ N=n!\sum_{k=1}^{n-2}\frac{1}{k} $$ In a simple $5x5$ input-output matrix, there are 600 pairs of different vertices and each pair is associated with ten elementary paths, thus yielding 6000 elementary paths.
Now for $n=5$, I get $N=200$, according to the above equation. According to the article, this should be 600?
Also, for a 5-element set of sectors of the economy $(a,b,c,d,e)$ the total number of combinations of vertices should be 25 ($(aa), (ab), (ba), \dots$)? What am I missing?
There is lots to be confused by here.
The formula $$N = n! \sum_{k=1}^{n-2} \frac1{k!}$$ should indeed give $N = 200$ and not $N = 6000$ when $n=5$. I think I can guess where the mistake is. The claim that there are $600$ pairs of different vertices would be correct if we had $n = 25$, rather than $n=5$, since $600 = 25 \cdot 24$. From there, saying that there are $P=10$ elementary paths joining each pair of vertices agrees with the earlier formula for $P$. If we correct the quantity $600$ to $5 \cdot 4 = 20$, then multiplying by $10$ gives $200$, agreeing with the formula as written above.
Separately, the formulas for $P$ and for $N$ are incorrect if summed for $1 \le k \le n-2$. (The formula for $P$ is merely ambiguous in the paper, since it does not include a range; the formula for $N$ is flat-out incorrect.) We should have $0 \le k \le n-2$, giving $$P = (n-2)! \sum_{k=0}^{n-2} \frac1{k!} \qquad \text{and} \qquad N = n! \sum_{k=0}^{n-2} \frac1{k!}.$$ The value of $k$ tells us how many vertices should be left out of the path. The $k=0$ term corresponds to the $(n-2)!$ paths between two fixed vertices that visit every other vertex; the $k=1$ term corresponds to the $(n-2)!$ paths between two fixed vertices that visit all but one vertex. So, the correct count when $n=5$ is that there are $5 \cdot 4 = 20$ pairs of different vertices, and between each pair of vertices there are $$P = 1 + 3 + 3\cdot 2 + 3 \cdot 2 \cdot 1 = 16$$ paths, for a total of $N = 320$ paths.
By way of illustration, here are the $16$ paths from $a$ to $b$ when the sectors are $\{a,b,c,d,e\}$:
\begin{array}{cccc} (a,b) & (a,c,b) & (a,c,d,b) & (a,c,d,e,b)\\ & (a,d,b) & (a,c,e,b) & (a,c,e,d,b) \\ & (a,e,b) & (a,d,c,b) & (a,d,c,e,b) \\ & & (a,d,e,b) & (a,d,e,c,b) \\ & & (a,e,c,b) & (a,e,c,d,b) \\ & & (a,e,d,b) & (a,e,d,c,b) \end{array}
Finally, there are only $20$ and not $25$ pairs, because we want the paths to start and end at different vertices: if the sectors are $\{a,b,c,d,e\}$ then we include pairs of endpoints like $(a,b)$ and $(b,a)$, but not $(a,a)$. If we want to count cycles, or paths that start and end at the same vertex, that's a different problem. We'd want to nail down some details before we count these: does the cycle of length $0$ that ends where it starts without going anywhere count? What about a cycle like $(a,b,a)$? Does $(a,b,c,a)$ count separately from $(b,c,a,b)$, even though they're going around the same circle in the same direction? Once we answer these questions, a similar counting strategy will work.