Suppose there is a simple NFA, with 3 states (p,r,q) where p is the start and r is the final.
Such that
$\delta$ = (p,a,q), (p,b,q),
(p,a,r), (p,b,r),
(q,a,p), (q,b,p),
(q,a,r), (q,b,r),
(r,a,p), (r,b,p),
(r,a,q), (r,b,q)
Is there a formula that can calculate the number of paths for a particular string?
I have tried just tracing for a small string such as "aaa", but when it gets larger, it becomes difficult.
For a string $w$ of length $n$ in the language, consider the states through which the NFA will be in when processing $w$. Each such path must start in state $p$ and end in the accepting state $r$, and may not have adjacent instances of the same state. Thus $w$ will give rise to all possible sequences $\langle\,s_1, s_2, \dotsc s_{n+1}\,\rangle$ where $s_i \in \{p,q,r\}$, $s_1=p, s_{n+1}=r$ and $s_i\ne s_{i+1}$ for all $1\le i\le n$.
Now suppose we look at the number of paths of length $n$ regardless of whether they end in $r$. Let the triple $(P,Q,R)$ count the number of length-$n$ paths that end in states $p,q,r$, respectively. The length-$0$ path, $\langle\,p\,\rangle$ will have count tuple $(1,0,0)$. The length-$1$ paths, $\langle\,p,q\,\rangle, \langle\,p,r\,\rangle$ will give the tuple $(0,1,1)$, since the two paths end once at $q$ and once at $r$.
Now comes the cute part: the length-$n$ count, $(P,Q,R)$ must come from the length-($n-1$) count $(P',Q',R')$ where $P=Q'+R', Q=P'+R', R=P'+Q'$, so, for example, the first few count tuples must be
$$\begin{align} n=0: &\quad (1,0,0)\\ n=1: &\quad (0,1,1)\\ n=2: &\quad (2,1,1)\\ n=3: &\quad (2,3,3)\\ n=4: &\quad (6,5,5)\\ \end{align}$$
Since we're interested in the counts for strings in the language, we're only interested in the last count element and we find that $r(n)$ is the sequence $$ r(0) = 0\quad r(1)=1\quad r(2)=1\quad r(3)=3\quad r(4)=5\quad r(5)=11 $$ and after a bit of looking we may spot the recurrence $r(n)=2r(n-1)+(-1)^{n+1}$, which has the nice closed form $$ r(n) =\frac{1}{3}\left(2^n-(-1)^n\right) $$ which is the answer we sought: the number of paths through the NFA for any accepted word of length $n$.