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.

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}$

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$$