IMC 2018 · Day 2 · P8

Let $\Psi = \{ (u, v) \in \mathbb{Z}^3 : v \ge 0, u \ge 2v \}$.

Notice that the map $\pi : \Omega \to \Psi$, $\pi(x, y, z) = (x + y, z)$ is a bijection between the two sets; moreover $\pi$ projects all allowed paths of the frogs to paths inside the set $\Psi$, using only unit jump vectors. Hence, we are interested in the number of paths from $\pi(0,0,0) = (0,0)$ to $\pi(n,n,n) = (2n, n)$ in the set $\Psi$, using only jumps $(1, 0)$ and $(0, 1)$.

For every lattice point $(u, v) \in \Psi$, let $f(u, v)$ be the number of paths from $(0,0)$ to $(u,v)$ in $\Psi$ with $u + v$ jumps. Evidently we have $f(0,0) = 1$. Extend this definition to the points with $v = -1$ and $2v = u + 1$ by setting $$\tag{3} f(u, -1) = 0, \qquad f(2v - 1, v) = 0.$$ To any point $(u, v)$ of $\Psi$ other than the origin, the path can come either from $(u-1, v)$ or from $(u, v-1)$, so $$\tag{4} f(u, v) = f(u-1, v) + f(u, v-1) \quad \text{for } (u, v) \in \Psi \setminus \{(0,0)\}.$$ If we ignore the boundary condition (3), there is a wide family of functions that satisfy (4); namely, for every integer $c$, $(u, v) \mapsto \binom{u+v}{v+c}$ is such a function, with defining this binomial coefficient to be 0 if $v + c$ is negative or greater than $u + v$.

Along the line $2v = u + 1$ we have $\binom{u+v}{v} = \binom{3v-1}{v} = 2 \binom{3v-1}{v-1} = 2 \binom{u+v}{v-1}$. Hence, the function $$f^*(u, v) = \binom{u+v}{v} - 2 \binom{u+v}{v-1}$$ satisfies (3), (4) and $f(0,0) = 1$. These properties uniquely define the function $f$, so $f = f^*$.

In particular, the number of paths of the frog from $(0,0,0)$ to $(n,n,n)$ is $$f(\pi(n,n,n)) = f(2n, n) = \binom{3n}{n} - 2 \binom{3n}{n-1} = \frac{\binom{3n}{n}}{2n+1}.$$

Remark. There exist direct proofs for the formula $\binom{3n}{n} / (2n+1)$. For instance, we can replicate the well-known proof of the formula for the Catalan numbers using the Cycle Lemma of Dvoretzky and Motzkin (related to the petrol station replenishment problem). See https://en.wikipedia.org/wiki/Catalan_number#Sixth_proof