Graph Theory question about path counting. How many different (open) paths of length $k$; $(0 < k < 2n)$ are there in a complete bipartite graph $K_{n,n}$; $(n>2)$ ? We do not consider different those paths that have the same or reversed sequence of nodes.
 A: If $k$ is odd, the path visits $(k+1)/2$ nodes on each side. Without loss of generality we can consider the node on the left as the begining of the path and give it an orientation. The total number of paths is $\frac{n!}{(n-(k+1)/2)!} \frac{n!}{(n-(k+1)/2)!}$
since any possible ordering of $(k+1)/2$ nodes on the left side and $(k+1)/2$ nodes on the right side is valid.
If $k$ is even, the path visits $k/2$ node on one side and $k/2+1$ on the other. Consider first paths that start on the left. The total number of such oriented paths is $\frac{n!}{(n-k/2)!} \frac{n!}{(n-k/2-1)!}$
since any possible ordering of $k/2+1$ nodes on the left side and $k/2$ nodes on the right side is valid. Since we don't care about orientation, we are double counting each path so the total number of unoriented paths that start on the left is $\frac 1 2 \frac{n!}{(n-k/2)!} \frac{n!}{(n-k/2-1)!}$. The same holds for paths that start on the right so in total we have $\frac{n!}{(n-k/2)!} \frac{n!}{(n-k/2-1)!}$ paths.
The answer is therefore for all $k$, $$\frac{n!}{(n-\lceil(k+1)/2\rceil)!} \frac{n!}{(n-\lfloor(k+1)/2\rfloor)!}$$
A: If by "path" we mean a simple (non-self-intersecting) path, then it is relatively easy to count these within a complete bipartite graph $K_{n,n}$.
Let $A = \{a_1,\ldots,a_n\}$ and $B = \{b_1,\ldots,b_n\}$ be the two "parts" of the graph.  Then a path of length $k$ might begin either with a vertex of part $A$ or of part $B$.  If the path is of odd length, then it's reversal will be a path that starts in the opposite part (and we want to count these as a single path).
Odd length paths
Let $k = 2m-1$, and there will be $m$ vertices in part $A$ as well as in part $B$.  All possible sequences in $A$ and $B$ can arise (because the bipartite graph is complete).  So the counting if we start in part $A$ will be:
$$\frac{(n!)^2}{(n-m)!^2}$$
as every such path can be made from an arbitrary distinct $m$-sequence in $A$ interleaved with an arbitrary distinct $m$-sequence in $B$ (and it is unnecessary duplication to consider the paths starting in $B$).  Note that the $2m$ "fence posts" give rise to the $k = 2m-1$ edges that connect them.
Even length paths
Very similar, except that we will have an odd number of vertices, so the path will begin and end in the same "part" $A$ or $B$ of the graph, and we therefore count the two cases separately.  However the sequence in the "dominant" part can be reversed, with an equal number of the shorter distinct sequences in the "lesser" part, so we divide by two in each case.
The two halves of each case (starting in $A$, starting in $B$) make a symmetric whole, so again it suffices to count only the cases starting in $A$.  If $k=2m$, we then have $m+1$ vertices in $A$ to pick and $m$ vertices in $B$, so the count is:
$$ \frac{(n!)^2}{(n-m)!(n-m-1)!} $$
