Counting paths on a graph that don't visit the same node twice I am aware of the method for calculating the number of paths between each node in a graph G using the adjacency matrix of G.
Let $A$ be the adjacency matrix of G, then we can calculate the number of paths between each pair of nodes of length n, by raising $A$ to the $n$-th power. i.e $a^n_{i,j}$ (the $(i,j)$-th entry of $A^n$) gives the number of paths from node $i$ to node $j$ that takes $n$ steps.
Is there some similar method we can use to subtract away the paths that go through the same node twice?
 A: No, there cannot be an equally simple method such as taking the powers of the adjacency matrix. Imagine that there were a polynomial method to count the number of simple paths from $v$ to $w$ of length $k$ in $G$. Then by applying this method on each adjacent pair $\{v,w\}$ with paths of length $|V|$, we would know if $G$ contains a Hamiltonian cycle.
So unless P=NP, even knowing if there is at least one simple path from $v$ to $w$ with length $k$, will require hard (=non-polynomial) computations, let alone counting them all. This could also be seen from the fact that finding the longest simple path in a graph is also a known NP-hard problem.
A: The last section "An algorithm for finding all simple paths and all simple cycles" of Self-Avoiding Paths and the Adjacency Matrix of a Graph gives something close to the posted question. It's similar to the usual $A^n$ trick in that it requires repeated multiplication of $A$ ($A-diag(A)$ if there are nodes connected to themselves), with the additional steps of setting diagonal entries of the intermediate matrices to 0, and an additional check (see step 7 below).
It's quite a bit different than the usual method, as each entry in A is given by a variable representing the edge weight instead of some numeric value.  If G is the following graph:
.
Then the corresponding adjacency matrix A is given by:
\begin{bmatrix}
    0 & x_{1} & 0 &  0 \\
    x_{2} & 0 & x_{3}  & 0 \\
    x_{4} & 0 & 0   & x_{5} \\
    x_{6} & 0 & x_{7}  & x_{8} \\
\end{bmatrix}
Multiplication of variables corresponds to concatenation, addition corresponds to the seperation of different path instances. For example, $(x_1x_2)(x_3+x_4) = x_1x_2x_3 + x_1x_2x_4$.
Note that you cannot replace the variables with their actual value (until the algorithm is finished) as order will be lost and the actual paths in each cell will be replaced by a single number. Once the algorithm is complete replacing each $x$ with 1, the $(i,j)$ entry of $C_k$ corresponds to the number of simple paths from $i$ to $j$ of length k.
ALGORITHM. Let k be given, where $k \geq 1$. Then the following algorithm
yields all simple paths all simple cycles of length q for $q = 1, ... , k$.

*

*Let $D_1 = (A)_{i,i}=diag(A)$. Let $C_1 = A - D_1$. i.e. $D$ is the diagonal of $A$, and $C$ is the off diagonal entries of A.

*Let $q=1$

*Is $q = k$?

*If yes, $(C_t)_{i,j}$ represents all simple paths of length starting
from the ith node and ending at the jth node.
$D_t$ represents all simple
cycles of length t starting from and ending at the ith node, t = 1, ...,k
and the algorithm is finished.

*If no, calculate $C_1C_q$, and $C_qC_1$.

*Let $D_{q+1} = diag(C_qC_1) = diag(C_1C_q)$

*Define the matrix $C_{q+1}$ by $(C_{q+1})_{i,i} = 0$ and for $i \neq j$, $(C_{q+1})_{i,j}$ equal to the terms that occur in both $(C_1C_q)_{i,j}$, and $(C_qC_1)_{i,j}$

*Let q=q+1

*Go back to step 4

Step 7 needs a bit of explanation. I didn't quite get as it is phrased a bit confusingly in the paper. From construction we know $C_q$ has no repeated nodes, however $C_1C_q$ may in any given entry. If it does it will not appear in $C_qC_1$, hence the check. See the paper for a full proof by induction.
