Combination with repeated floor operations same as the whole combination?

Question

This question involves both math and programming, but the main inquiry in nature is mathematical.

There is a LeetCode question called Unique Paths that asks the number of ways that one can reach the lower-right corner of a $m \times n$ grid if you start in the upper-left corner and want to reach the lower-right corner, only being able to move down or right at any step.

Visualization of the $3 \times 7$ case, for example:

One mathematical approach that was suggested is to compute $\begin{pmatrix}m + n - 2 \\ m - 1\end{pmatrix}$ as the question is equivalent to asking the number of ways to select $m - 1$ downwards moves from a total of $m + n - 2$ moves to reach the lower-right corner.

However, the programming solution that was proposed essentially computes the following:

$$ \left\lfloor \frac{\left\lfloor \frac{\left\lfloor \frac{\left\lfloor \frac{1 \cdot n}{1} \right\rfloor (n + 1)}{2} \right\rfloor (n + 2)}{3} \right\rfloor \cdots (n + m - 2)}{\vdots \atop m - 1} \right\rfloor $$

So, my question is how does the solution guarantee that the above is equivalent to $\left\lfloor \frac{(m + n - 2)!}{(m - 1)!(n - 1)!} \right\rfloor$ without any loss of data from the repeated application of the floor operator?

Edit:

The accepted answer from Sil helped me out the most intuitively. Though, the inductive proof of how each step results in a combination by Mike also helped very much.

Answer 1

The division is applied in cases where denominator already divides numerator, so there is no remainder. This is because $\binom{n+k-1}{k}=\frac{n(n+1)\cdots(n+k-1)}{1\cdot 2\cdots k}$ is an integer for all $k=1,2,\dots$ (see for example Division of Factorials [binomal coefficients are integers] or Proof that a Combination is an integer for some proofs of this fact). Hence the result of the division is an integer and there is nothing to round (floor function).

Using your notation, first it's clear that $1$ divides $n$ and so $\frac{1 \cdot n}{1}=n$ and $\lfloor n \rfloor=n$. Then $n(n+1)$ is a multiple of $2$ (one of two consecutive integers will be even), so $\frac{n(n+1)}{2}$ is an integer and so $\lfloor \frac{n(n+1)}{2} \rfloor= \frac{n(n+1)}{2}$. And so on... In $k$-th step you take the above binomial coefficient about which we already know is an integer, and so $1\cdot 2\cdots k$ divides $n(n+1)\cdots(n+k-1)$, hence $k$ divides $\frac{n(n+1)\cdots(n+k-1)}{1\cdot 2\cdots (k-1)}$ which we have from the previous step.

From more programming point of view, the step you refer to I believe is ans = ans * x / y;, which in C is evaluated as ans = (ans * x) / y;. The division operator here is an integer division so in principle it could also perform some rounding, but as explained above, ans * x is already a multiple of y so this is not an issue here.

Answer 2

Let us give names to the intermediate values of this calculation. Let $x_0=1$, and for each $i\in \{1,2,\dots,m-1\}$, let $$ x_{i+1}=\left\lfloor\frac{x_i\cdot (n+i)}{i+1}\right\rfloor $$ We will prove by induction on $i$ that $$x_i=\binom{n+i-1}{i},\qquad i\in \{0,1,\dots,m-1\}$$ In particular, the last value is $x_{m-1}=\binom{m+n-2}{m-1}$, so this would prove the algorithm is computing the correct value.

For the base case, we must prove $x_0=\binom{n-1}{0}$. Since $\binom{n-1}{0}=1$, this matches the definition of $x_0$.

For the inductive step, given $i\ge 0$, we assume $x_i=\binom{n+i-1}{i}$, and must prove $x_{i+1}=\binom{n+i}{i+1}$. \begin{align} x_{i+1} &= \left\lfloor\frac{x_i\cdot (n+i)}{i+1}\right\rfloor \\&= \left\lfloor\binom{n+i-1}{i}\cdot \frac{n+i}{i+1}\right\rfloor \tag{Inductive hypothesis} \\&= \left\lfloor\binom{n+i}{i+1}\right\rfloor \tag{Absorption identity} \\&= \binom{n+i}{i+1} \tag{Floor of integer is self} \end{align} The absorption identity I am using is $$ \binom{t}{k}=\binom{t-1}{k-1}\frac{t}{k},\qquad k\ge 1 $$ which is easy to prove by converting everything to factorials, i.e. using $\binom tk=t!/[k!\cdot (t-k)!]$.