0
$\begingroup$

I recently came across a coding problem in which the solution involves writing a program that can take in the starting position and destination square of a chess piece, and then output the number of possible combinations for reaching the destination. The piece can only move up or to the right by one square at a time; the squares are represented with numbers, where the first number represents the row and the second represents the column. So if you were to input '(1 1)(2 2)', you are asking the program to calculate the number of given legal ways the piece can travel from the 1st row/1st column square to the 2nd row/2nd column. The answer here is 2 because it can either move up then right, or right and then up.

The solution involved calculating the factorial of the difference between the start and end rows plus the difference between the start and end columns. So in the above example this would be the factorial of 2, or the factorial of (2-1)+(2-1), which is 2 * 1 or 2. Then, this number is divided by the factorial of the difference between the start and end rows, multiplied by the factorial of the difference between the start and end columns, which here would equal 1, since the factorial of (2-1) times the factorial of (2-1) is simply 1 * 1 or 1, which the first calculation of 2 is divided into.

Can someone explain to me in simple layman's terms why this division step is necessary? I understand the numerator represents all of the permutations and some of them are repeats (since the order doesn't matter, and we only need to count a specific set of moves once) and need to be cancelled out, but how does this work exactly?

I appreciate any help I can get.

$\endgroup$
2
$\begingroup$

If you move the $(a,b)$ to $(c,d)$ where $c \ge a$ and $d \ge b$.

In total, we know that you have to take $(c-a)+(d-b)$ steps of which $(c-a)$ of them are horizontal steps and clearly the rest are vertical moves.

That is out of $(c-a)+(d-b)$ steps, we have to select $c-a$ of them to be horizontal steps. Hence the number of possible moves are

$$\binom{(c-a)+(d-b)}{c-a}=\frac{(c-a+d-b)!}{(c-a)!(d-b)!}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.