Numbers of undirected paths in the complete tripartite graph K_{n,n,n}.
=======================================================================

Label the three sets of vertices A, B and C.
Only paths with at least one edge are included.

Assume the path starts with a vertex of A:
  Between vertices of A the path will contain segments of BC vertices (alternating beween the two).
  The path may either end with a vertex of A or a segment of BC vertices.
  Let k > 1 be the number of segments of BC vertices. The number of A vertices will be k or k + 1.
  Let i >= 0 be the number of BC segments of odd length that start with a vertex of B.
  Let j >= 0 be the number of BC segments of odd length that start with a vertex of C.
  Let p be the number of additional pairs of vertices of B and C.
  We require p >= k-i-j to give at least one pair to any even length BC segment.
  Any remaining pairs can be placed in any of the k segments of BC vertices

Putting it together:
   binomial(n, k)        is the number of ways to pick the k vertices of A that will preceed BC segments
 * (1 + n - k)           is the choice of no A vertex at end or number of ways to pick final A vertex
 * binomial(n, i + p)    is the number of ways to pick the i+p vertices of B
 * binomial(n, j + p)    is the number of ways to pick the j+p vertices of C
 * k!                    is the number of ways of ordering the first k A vertices
 * (i + p)!              is the number of ways of ordering the B vertices
 * (j + p)!              is the number of ways of ordering the C vertices
 * binomial(k, i)        is the number of ways to associate initial B vertices of odd length BC segments with the A vertices they follow
 * binomial(k - i, j)    is the number of ways to associate initial C vertices of odd length BC segments with the A vertices they follow
 * 2^(k-i-j)             is the number of ways of selecting which of the even length BC segments start with B or C
 * binomial(p+i+j-1,k-1) is the number of ways of distributing the remaining p-(k-i-j) ordered pairs of BC vertices into the k BC segements.   

The above determines the number of directed paths starting with a vertex of A.
To get the number of undirected paths starting with a vertex from any of A,B or C multiply by 3/2.

Formula for number of undirected paths in the complete tripartite graph of order n:
a(n) =  (3/2) * Sum_{k=1..n} Sum_{i=0..k} Sum_{j=0..k-i} Sum_{p=k-i-j..n}
             binomial(n, k)*(1+n-k)*binomial(n, i+p)*binomial(n, j+p)*binomial(k, i)*binomial(k-i, j)*k!*(i+p)!*(j+p)!*2^(k-i-j)*binomial(p+i+j-1, k-1).