I think your generating function may be wrong. In particular when $n=4$, I think it gives $20$ when I can count $21$ cases
I think if $b_{n,k}$ is the number of choices when you have $n$ soldiers and the first group has $k$ individuals then you can consider adding an additional soldier at the beginning so you can say $$b_{n+1,k+1}=\frac{k+1}{k}b_{n,k}$$ for $k\ge 1$ while $$b_{n+1,1}=\sum\limits_{k=1}^n b_{n,k}$$ which leads to results like
- $b_{n,k} = k\, b_{n+1-k,1}$
- $b_{n+1,1} = b_{n,1}+ \sum\limits_{m=1}^n b_{m,1}$
- $b_{n+1,1}=3b_{n,1}-b_{n-1,1}$
- sine the number you want $a_n = b_{n+1,1}$: $$a_{n,1}=3a_{n-1,1}-a_{n-2,1}$$
Since the numbers are $1,3,8,21,\ldots$ when $n=1,2,3,4,\ldots$, this leads to a generating function of the form $\dfrac{x}{1-3x+x^2}$ if you think the answer is $0$ when $n=0$, or of the form $\dfrac{1-2x+x^2}{1-3x+x^2}$ if you think the answer is $1$ when $n=0$.
This is a second order recurrence and can be solved related to $\frac{3 \pm \sqrt 5}2$ but can also be written by saying the coefficient of $x^n$ is $\text{Fib}(2n)$.
First of all, there should be $n$ right moves, not $n-1$. The confusion arises because there are two ways to move on an $m\times n$ grid of squares; you can either move on the squares themselves, or along the vertices. Since the correct answer is $\binom{m+n}m$, the correct interpretation must be the vertices, so there are $n$ right moves. Similarly, each right move can occur at one of $m+1$ possible heights, not $m$.
This transforms your answer into
$$
\frac{(m+1)^n}{n!},
$$
but this is still incorrect, for a more subtle reason. The problem is that there are sometimes fewer than $n!$ unique rearrangements of a given placement of the $n$ horizontal edges. If you have multiple edges at the same height, then some of the $n!$ permutations are redundant, meaning you cannot divide by $n!$.
Maybe it would help to look at a small case, say $m=1$ and $n=2$. There are $(m+1)^n=4$ ways to distribute the two horizontal edges. You can do
high, high,
low, low,
high, low, and
low, high.
The last two methods, (high, low) and (low, high), are permuted versions of each other, and form a class of size $2!$. That is OK. However, when you permute (high, high), the result is still (high, high), even if the permutation is nontrivial. Therefore, the group associated with (high, high) only has size one, not $2!$. Since the groups are not uniformly sized at $2!$, you cannot count their number by dividing by $2!$.
Best Answer
Denoting a right step by $R$ and an upward step by $U$, odd number of direction changes means, if the very first step is $R$, the very last step is $U$ and vice-versa.
If we ignore the very first and very last steps, our desired paths fall in two categories :
Hence answer is $\; 2\times \dbinom{30}{15}$