Number of ways an ant can move from the origin to $(16,16)$ in an odd number of direction changes 
An ant is standing at the origin. It makes its way from $(0,0)$ moving one unit in the positive $x$ or $y$ direction at a time, so the ant changes directions an odd number of times. How many ways can this be done?

So far I've tried to map out a few ways, and see if I can make some formulas based on relating the number of $x$ movements and $y$ movements, but it isn't doing the best job of addressing all the ways this can be done.
Any ideas? Any and all help is appreciated.
 A: Suppose the number of turns $2k-1$ is given where $1\le k\le16$. Then the path can be fully specified by partitioning both dimensions into $k$ blocks – the pair of axis partitions $(a_1,\dots,a_k),(b_1,\dots,b_k)$ with $a_i,b_i>0$ corresponds to the two paths that alternate $a_i$ steps right and $b_i$ steps up, starting in either direction as desired. The number of such partitions is $\binom{15}{k-1}^2$, so the answer is
$$2\sum_{k=0}^{15}\binom{15}k^2=2\binom{30}{15}=310235040$$
A: 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 :

*

*All paths beginning at $(1,0)$ (after taking first step $R$) and ending at $(16,15)$, to finish with an $U$ step on $(16,16)$. Number of such paths is $\dbinom{30}{15}$

*All paths starting at $(0,1)$ and ending at $(15,16)$. By symmetry or direct counting, again this is $\dbinom{30}{15}$
Hence answer is $\; 2\times \dbinom{30}{15}$
