The number of paths on a graph of a fixed length w/o repeatings

Consider a graph $G$ with the adjacency matrix $A$. I know that the number of paths of the length $n$ is the sum of elements $A^n$.

But what if we can't walk through a vertex more than one times?

-
It that would be as simple as some modified $A^n$, then you would solve Hamiltonian path problem in polynomial time. Of course, we don't know whether $P = NP$ or not, but I strongly suspect, that your formula to be easily provable, will have to include (somewhere, maybe indirectly) exponential number of operations, e.g. $2^n$ additions, multiplications, assignments, whatever. –  dtldarek Feb 10 '13 at 9:36
@dtldarek: Isn't $A^n$ exponential in $n$? –  Raskolnikov Feb 10 '13 at 9:52
@Raskolnikov In terms of number of operations, no. E.g. $a^{12} = a\cdot a \cdot a \cdot \ldots \cdot a$ which uses only linear number of multiplications. Moreover, if you rearrange it smartly (that is via Horner's scheme) you can make it even logarithimc in $n$, e.g. $a^{12} = ((a^2\cdot a)^2)^2$. –  dtldarek Feb 10 '13 at 10:52
@dtldarek: Yes, but that only computes how many paths of length $n$ there are. Searching those paths for Hamiltonian ones means searching through an exponentially growing number of paths, regardless of how fast that number can be computed. –  Raskolnikov Feb 10 '13 at 11:59
@Raskolnikov An oracle that calculates the number of paths of length $|V|$ that doesn't go twice through any vertex is enough to solve Hamiltonian path problem. Moreover, even if the original problem is of the form "is there a Hamiltonian path of length $k$", it is easy to compute the path itself – just remove any unnecessary edges until a single path remains. –  dtldarek Feb 10 '13 at 15:28

Let $A\otimes B$ be defined as the product of matrices where you removed the diagonal i.e.: $$A\otimes B=(A-diag(A))\times(B-diag(B))$$ Let $A_1=A$ and $A_n=A\otimes A_{n-1}$.
The number of paths of the length n without going through a vertex more than one times is equal to the sum of elements of $A_n$.