Proving that if $a+b = c+d$ and $a!b! = c!d!$ then either $a = c$ and $b = d$ or $a = d$ and $b = c$

Question

I recently have been thinking about how many ways it is possible to get from one square to another on a square grid using the fewest possible number of orthogonal steps. (i.e., using the fewest number of the xiangqi general's move, how many paths are there?) For example, to do an up-right diagonal, you can go up then right or right then up, so for this path, the answer is 2. For a knight's move, there are 3 ways: UUR, URU, and RUU. We can obviously consider paths rotated multiples of 45 degrees, so I will assume the path goes up and right, and it goes more up than right.

I was thinking that for each move a certain number of steps away from the starting point, each point might have a different number of ways of getting there. For a point (a,b) each path can be described by a permutation of the multiset that contains a U steps and b R steps. Therefore, the number of paths of (a, b) is the multinomial coefficient: $${a+b \choose a, b} = \frac {(a + b)!} {a!b!}$$ If (a, b) and (c, d) are the same number of steps away from the starting point, then $a+b = c+d$. So, if we are saying that (a, b) and (c,d) have the same number of paths to them, then the above is also equal to: $${c+d \choose c, d} = \frac {(c + d)!} {c!d!} = \frac {(a + b)!} {c!d!}$$ So, we are only a little algebra away from: $$a!b! = c!d!$$ The whole aim was to show that the number of paths is unique for this distance away from the origin. So I want to prove (or disprove) that (a,b) must be the same point as (c, d) ignoring rotations, which amounts to the question I asked. It seems pretty intuitive that it could be true, but I'm not sure what direction to go to prove it and can't find anything online.

Answer 1

Here's the thing:

If $j < k; m \ge 0$ then $\frac {(j+m)!}{j!} < \frac {(k + m)!}{k!}$ and if $m < \min (j,k)$ then $\frac {j!}{(j-m)!} < \frac {k!}{(k-m)!}$.

This is clear as $\frac {(j+m)!}{j!}=\prod_{i=1}^m (j+i)< \prod_{i=1}^m (k + i) = \frac {(k + m)!}{k!}$ and $\frac {j!}{(j-m)!}=\prod_{i=1}^m (j-m+i)! < \prod_{i-1}^m (k-m+i)! = \frac {k!}{(k-m)!}$.

So $\frac {(j+m)!}{j!} = \frac {(k + m)!}{k!}$ or $\frac {j!}{(j-m)!}= \frac {k!}{(k-m)!}$ $\implies j = k$.

Which means $(j\pm m)!k! = j!(k\pm m)!\implies k = j$ (assuming, of course, that $m \ne 0$.

.....

Now if $a + b = c + d$ and if we let $m= c-a = b-d$ then we have:

$a!b! = c!d! \implies a!(d+m)! = (a+m)!d!\implies (c-m)!b! = c!(d-m)!$.

If $m \ne 0$ then $a=d$ and $b = c$.

If $m = 0$ then $a = c$ and $b=d$.

Answer 2

Without loss of generality, $a\le b$ and $c\le d$. Write $n=a+b=c+d$ so you want

$$ \binom{n}{a}=\binom{n}{c} \implies a=c. $$

Writing $n=2k$ or $n=2k+1$ now, we can go a step further and try showing

$$ \binom{n}{0},\binom{n}{1},\binom{n}{2},\cdots,\binom{n}{k} $$

is a strictly increasing sequence (note $0\le a,c\le k$). For this, suppose $\ell<k$ and write

$$ \binom{n}{\ell}<\binom{n}{\ell+1}.$$

Use the formula for binomial coefficients to rearrange this into an equivalent form. Note there should be cancellation, and also that $\ell<k \implies 2\ell+1<n$.