Using factorials to calculate # of chess combinations
$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.
combinatorics permutations combinatorial-game-theory chessboard
asked Dec 20 '18 at 7:39
Eric R.Eric R.
11
$endgroup$
add a comment |
$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.
combinatorics permutations combinatorial-game-theory chessboard
asked Dec 20 '18 at 7:39
Eric R.Eric R.
11
$endgroup$
add a comment |
$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.
combinatorics permutations combinatorial-game-theory chessboard
asked Dec 20 '18 at 7:39
Eric R.Eric R.
11
$endgroup$
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.
combinatorics permutations combinatorial-game-theory chessboard
combinatorics permutations combinatorial-game-theory chessboard
asked Dec 20 '18 at 7:39
Eric R.Eric R.
11
asked Dec 20 '18 at 7:39
Eric R.Eric R.
11
asked Dec 20 '18 at 7:39
Eric R.Eric R.
11
asked Dec 20 '18 at 7:39
Eric R.Eric R.
11
asked Dec 20 '18 at 7:39
Eric R.Eric R.
11
11
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$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)!}$$
answered Dec 20 '18 at 8:17
Siong Thye GohSiong Thye Goh
102k1466118
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047265%2fusing-factorials-to-calculate-of-chess-combinations%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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)!}$$
answered Dec 20 '18 at 8:17
Siong Thye GohSiong Thye Goh
102k1466118
$endgroup$
add a comment |
$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)!}$$
answered Dec 20 '18 at 8:17
Siong Thye GohSiong Thye Goh
102k1466118
$endgroup$
add a comment |
$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)!}$$
answered Dec 20 '18 at 8:17
Siong Thye GohSiong Thye Goh
102k1466118
$endgroup$
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)!}$$
answered Dec 20 '18 at 8:17
Siong Thye GohSiong Thye Goh
102k1466118
answered Dec 20 '18 at 8:17
Siong Thye GohSiong Thye Goh
102k1466118
answered Dec 20 '18 at 8:17
Siong Thye GohSiong Thye Goh
102k1466118
answered Dec 20 '18 at 8:17
Siong Thye GohSiong Thye Goh
102k1466118
102k1466118
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047265%2fusing-factorials-to-calculate-of-chess-combinations%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
