Question 73
Let be given four positive integers $m, n, p, q$, with $p \lt m$ and $q \lt n$. Take the four points $A(0; 0)$, $B(p; 0)$, $C(m; q)$ and $D(m; n)$ in the coordinate plane.
Consider the paths $f$ from $A$ to $D$ and the paths $g$ from $B$ to $C$ such that when going along $f$ or $g$, one goes only in the positive directions of the axes of coordinates and one can only change directions (from the positive direction of one axe of coordinate into the positive direction of the other axe of coordinate) at the points with integral coordinates.
Let $S$ be the number of couples $(f, g)$ such that $f$ and $g$ have no common point. Prove that
$$
S = C_{m+n}^{p} \cdot C_{m+q-p}^{q} - C_{m+q}^{p} \cdot C_{m+n-p}^{q}.
$$
Consider the paths $f$ from $A$ to $D$ and the paths $g$ from $B$ to $C$ such that when going along $f$ or $g$, one goes only in the positive directions of the axes of coordinates and one can only change directions (from the positive direction of one axe of coordinate into the positive direction of the other axe of coordinate) at the points with integral coordinates.
Let $S$ be the number of couples $(f, g)$ such that $f$ and $g$ have no common point. Prove that
$$
S = C_{m+n}^{p} \cdot C_{m+q-p}^{q} - C_{m+q}^{p} \cdot C_{m+n-p}^{q}.
$$