Counting lattice paths which use fixed steps but can end in different places
$begingroup$
Consider a lattice path where one starts at $(0,0)$ and can move only right or up in integer steps. The total number of steps made is $4$, but the maximum steps in one direction $3$. How many paths exist?
I have two different ideas but I'm not sure which (if either) is correct. The first:
$$frac{n!}{n-k!}=frac{6!}{2!}$$ where $n$ is the number of different movement options ($3$ up and $3$ right) and $k$ is the number of spaces ($4$). From here there are three different scenarios:
$$(right, up): (3,1),(2,2),(1,3).$$
Considering each of these, the number of paths is given by: $$frac{6!}{2!}sum_{i=1}^{3}frac{1}{i!(k-i)!}=frac{6!}{2!}(frac{1}{3}+frac{1}{4})=frac{6!cdot7}{2!cdot12}=frac{7!}{4!}=210$$
which seems very high. Alternatively:
$$sum_{i=1}^{3}frac{4!}{i!(k-i)!}=14$$ which considers 4 different arrangements of each scenario (I think).
I think the second method is correct, but I don't really understand where my thinking fails in the first method. If anyone could provide intuition as to why it is wrong, that would be great.
combinatorics combinations integer-lattices
asked Dec 20 '18 at 10:48
cluelessatthiscluelessatthis
394313
$endgroup$
|
show 1 more comment
$begingroup$
Consider a lattice path where one starts at $(0,0)$ and can move only right or up in integer steps. The total number of steps made is $4$, but the maximum steps in one direction $3$. How many paths exist?
I have two different ideas but I'm not sure which (if either) is correct. The first:
$$frac{n!}{n-k!}=frac{6!}{2!}$$ where $n$ is the number of different movement options ($3$ up and $3$ right) and $k$ is the number of spaces ($4$). From here there are three different scenarios:
$$(right, up): (3,1),(2,2),(1,3).$$
Considering each of these, the number of paths is given by: $$frac{6!}{2!}sum_{i=1}^{3}frac{1}{i!(k-i)!}=frac{6!}{2!}(frac{1}{3}+frac{1}{4})=frac{6!cdot7}{2!cdot12}=frac{7!}{4!}=210$$
which seems very high. Alternatively:
$$sum_{i=1}^{3}frac{4!}{i!(k-i)!}=14$$ which considers 4 different arrangements of each scenario (I think).
I think the second method is correct, but I don't really understand where my thinking fails in the first method. If anyone could provide intuition as to why it is wrong, that would be great.
combinatorics combinations integer-lattices
asked Dec 20 '18 at 10:48
cluelessatthiscluelessatthis
394313
$endgroup$
$begingroup$
It is unclear what you mean by "move" and what "maximum number of moves in one direction" means. Maybe be more precise and/or provide some examples of allowed and not allowed paths.
$endgroup$
– Christoph
Dec 20 '18 at 11:00
$begingroup$
Sorry for being unclear. I'm trying to refer to a North-East lattice path with steps $S={ (0,1),(1,0) }$.
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:02
$begingroup$
That I got. But what are moves?
$endgroup$
– Christoph
Dec 20 '18 at 11:03
$begingroup$
By moves I mean steps - I'll edit the question. Sorry for confusion
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:03
$begingroup$
Assuming I go from $(0,0)$ to $(0,1)$ and then to $(0,3)$. Is this one step/move since the direction didn't change? Do you mean "maximum consecutive steps in one direction" or "maximum total steps in one direction"?
$endgroup$
– Christoph
Dec 20 '18 at 11:05
|
show 1 more comment
$begingroup$
Consider a lattice path where one starts at $(0,0)$ and can move only right or up in integer steps. The total number of steps made is $4$, but the maximum steps in one direction $3$. How many paths exist?
I have two different ideas but I'm not sure which (if either) is correct. The first:
$$frac{n!}{n-k!}=frac{6!}{2!}$$ where $n$ is the number of different movement options ($3$ up and $3$ right) and $k$ is the number of spaces ($4$). From here there are three different scenarios:
$$(right, up): (3,1),(2,2),(1,3).$$
Considering each of these, the number of paths is given by: $$frac{6!}{2!}sum_{i=1}^{3}frac{1}{i!(k-i)!}=frac{6!}{2!}(frac{1}{3}+frac{1}{4})=frac{6!cdot7}{2!cdot12}=frac{7!}{4!}=210$$
which seems very high. Alternatively:
$$sum_{i=1}^{3}frac{4!}{i!(k-i)!}=14$$ which considers 4 different arrangements of each scenario (I think).
I think the second method is correct, but I don't really understand where my thinking fails in the first method. If anyone could provide intuition as to why it is wrong, that would be great.
combinatorics combinations integer-lattices
asked Dec 20 '18 at 10:48
cluelessatthiscluelessatthis
394313
$endgroup$
Consider a lattice path where one starts at $(0,0)$ and can move only right or up in integer steps. The total number of steps made is $4$, but the maximum steps in one direction $3$. How many paths exist?
I have two different ideas but I'm not sure which (if either) is correct. The first:
$$frac{n!}{n-k!}=frac{6!}{2!}$$ where $n$ is the number of different movement options ($3$ up and $3$ right) and $k$ is the number of spaces ($4$). From here there are three different scenarios:
$$(right, up): (3,1),(2,2),(1,3).$$
Considering each of these, the number of paths is given by: $$frac{6!}{2!}sum_{i=1}^{3}frac{1}{i!(k-i)!}=frac{6!}{2!}(frac{1}{3}+frac{1}{4})=frac{6!cdot7}{2!cdot12}=frac{7!}{4!}=210$$
which seems very high. Alternatively:
$$sum_{i=1}^{3}frac{4!}{i!(k-i)!}=14$$ which considers 4 different arrangements of each scenario (I think).
I think the second method is correct, but I don't really understand where my thinking fails in the first method. If anyone could provide intuition as to why it is wrong, that would be great.
combinatorics combinations integer-lattices
combinatorics combinations integer-lattices
asked Dec 20 '18 at 10:48
cluelessatthiscluelessatthis
394313
asked Dec 20 '18 at 10:48
cluelessatthiscluelessatthis
394313
edited Dec 20 '18 at 11:04
cluelessatthis
asked Dec 20 '18 at 10:48
cluelessatthiscluelessatthis
394313
asked Dec 20 '18 at 10:48
cluelessatthiscluelessatthis
394313
asked Dec 20 '18 at 10:48
cluelessatthiscluelessatthis
394313
394313
$begingroup$
It is unclear what you mean by "move" and what "maximum number of moves in one direction" means. Maybe be more precise and/or provide some examples of allowed and not allowed paths.
$endgroup$
– Christoph
Dec 20 '18 at 11:00
$begingroup$
Sorry for being unclear. I'm trying to refer to a North-East lattice path with steps $S={ (0,1),(1,0) }$.
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:02
$begingroup$
That I got. But what are moves?
$endgroup$
– Christoph
Dec 20 '18 at 11:03
$begingroup$
By moves I mean steps - I'll edit the question. Sorry for confusion
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:03
$begingroup$
Assuming I go from $(0,0)$ to $(0,1)$ and then to $(0,3)$. Is this one step/move since the direction didn't change? Do you mean "maximum consecutive steps in one direction" or "maximum total steps in one direction"?
$endgroup$
– Christoph
Dec 20 '18 at 11:05
|
show 1 more comment
$begingroup$
It is unclear what you mean by "move" and what "maximum number of moves in one direction" means. Maybe be more precise and/or provide some examples of allowed and not allowed paths.
$endgroup$
– Christoph
Dec 20 '18 at 11:00
$begingroup$
Sorry for being unclear. I'm trying to refer to a North-East lattice path with steps $S={ (0,1),(1,0) }$.
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:02
$begingroup$
That I got. But what are moves?
$endgroup$
– Christoph
Dec 20 '18 at 11:03
$begingroup$
By moves I mean steps - I'll edit the question. Sorry for confusion
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:03
$begingroup$
Assuming I go from $(0,0)$ to $(0,1)$ and then to $(0,3)$. Is this one step/move since the direction didn't change? Do you mean "maximum consecutive steps in one direction" or "maximum total steps in one direction"?
$endgroup$
– Christoph
Dec 20 '18 at 11:05
$begingroup$
It is unclear what you mean by "move" and what "maximum number of moves in one direction" means. Maybe be more precise and/or provide some examples of allowed and not allowed paths.
$endgroup$
– Christoph
Dec 20 '18 at 11:00
$begingroup$
It is unclear what you mean by "move" and what "maximum number of moves in one direction" means. Maybe be more precise and/or provide some examples of allowed and not allowed paths.
$endgroup$
– Christoph
Dec 20 '18 at 11:00
$begingroup$
Sorry for being unclear. I'm trying to refer to a North-East lattice path with steps $S={ (0,1),(1,0) }$.
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:02
$begingroup$
Sorry for being unclear. I'm trying to refer to a North-East lattice path with steps $S={ (0,1),(1,0) }$.
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:02
$begingroup$
That I got. But what are moves?
$endgroup$
– Christoph
Dec 20 '18 at 11:03
$begingroup$
That I got. But what are moves?
$endgroup$
– Christoph
Dec 20 '18 at 11:03
$begingroup$
By moves I mean steps - I'll edit the question. Sorry for confusion
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:03
$begingroup$
By moves I mean steps - I'll edit the question. Sorry for confusion
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:03
$begingroup$
Assuming I go from $(0,0)$ to $(0,1)$ and then to $(0,3)$. Is this one step/move since the direction didn't change? Do you mean "maximum consecutive steps in one direction" or "maximum total steps in one direction"?
$endgroup$
– Christoph
Dec 20 '18 at 11:05
$begingroup$
Assuming I go from $(0,0)$ to $(0,1)$ and then to $(0,3)$. Is this one step/move since the direction didn't change? Do you mean "maximum consecutive steps in one direction" or "maximum total steps in one direction"?
$endgroup$
– Christoph
Dec 20 '18 at 11:05
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
If you start with $(0,0)$ and in each step add $(1,0)$ or $(0,1)$, going $4$ steps in total, there are $2^4=16$ possible paths. If you forbid path's where the $x$ or $y$ coordinate ends up above $3$, you have to subtract the two paths going either all 4 steps up or all 4 steps right. In total you have $16-2=14$ paths satisfying your condition.
In general, the number of paths ending in $(x,y)$ is given by $binom{x+y}{x} = binom{x+y}{y}$ since you are going $x+y$ steps and have to choose which of them are up and which are right. So the $16$ pathes split as
$$
binom{0+4}{0} + binom{1+3}{1} + binom{2+2}{2} + binom{3+1}{3} + binom{4+0}{4} =1+4+6+4+1.
$$
So if you want to make $n$ steps in total, only allowing at most $kle n$ in each direction you get
$$
sum_{i=n-k}^{k} binom{n}{i}.
$$
answered Dec 20 '18 at 11:08
ChristophChristoph
12.3k1642
$endgroup$
$begingroup$
How does this generalise? Say we have $4$ steps and stop $x$ or $y$ going above $2$, preventing $(3,1),(4,0),(1,3),(0,4)$. We end up with a $2times2$ North-East lattice for which there are 6 paths, but $2^{4}-4neq6$
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:26
1
$begingroup$
I updated my answer.
$endgroup$
– Christoph
Dec 20 '18 at 11:33
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%2f3047407%2fcounting-lattice-paths-which-use-fixed-steps-but-can-end-in-different-places%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 start with $(0,0)$ and in each step add $(1,0)$ or $(0,1)$, going $4$ steps in total, there are $2^4=16$ possible paths. If you forbid path's where the $x$ or $y$ coordinate ends up above $3$, you have to subtract the two paths going either all 4 steps up or all 4 steps right. In total you have $16-2=14$ paths satisfying your condition.
In general, the number of paths ending in $(x,y)$ is given by $binom{x+y}{x} = binom{x+y}{y}$ since you are going $x+y$ steps and have to choose which of them are up and which are right. So the $16$ pathes split as
$$
binom{0+4}{0} + binom{1+3}{1} + binom{2+2}{2} + binom{3+1}{3} + binom{4+0}{4} =1+4+6+4+1.
$$
So if you want to make $n$ steps in total, only allowing at most $kle n$ in each direction you get
$$
sum_{i=n-k}^{k} binom{n}{i}.
$$
answered Dec 20 '18 at 11:08
ChristophChristoph
12.3k1642
$endgroup$
$begingroup$
How does this generalise? Say we have $4$ steps and stop $x$ or $y$ going above $2$, preventing $(3,1),(4,0),(1,3),(0,4)$. We end up with a $2times2$ North-East lattice for which there are 6 paths, but $2^{4}-4neq6$
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:26
1
$begingroup$
I updated my answer.
$endgroup$
– Christoph
Dec 20 '18 at 11:33
add a comment |
$begingroup$
If you start with $(0,0)$ and in each step add $(1,0)$ or $(0,1)$, going $4$ steps in total, there are $2^4=16$ possible paths. If you forbid path's where the $x$ or $y$ coordinate ends up above $3$, you have to subtract the two paths going either all 4 steps up or all 4 steps right. In total you have $16-2=14$ paths satisfying your condition.
In general, the number of paths ending in $(x,y)$ is given by $binom{x+y}{x} = binom{x+y}{y}$ since you are going $x+y$ steps and have to choose which of them are up and which are right. So the $16$ pathes split as
$$
binom{0+4}{0} + binom{1+3}{1} + binom{2+2}{2} + binom{3+1}{3} + binom{4+0}{4} =1+4+6+4+1.
$$
So if you want to make $n$ steps in total, only allowing at most $kle n$ in each direction you get
$$
sum_{i=n-k}^{k} binom{n}{i}.
$$
answered Dec 20 '18 at 11:08
ChristophChristoph
12.3k1642
$endgroup$
$begingroup$
How does this generalise? Say we have $4$ steps and stop $x$ or $y$ going above $2$, preventing $(3,1),(4,0),(1,3),(0,4)$. We end up with a $2times2$ North-East lattice for which there are 6 paths, but $2^{4}-4neq6$
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:26
1
$begingroup$
I updated my answer.
$endgroup$
– Christoph
Dec 20 '18 at 11:33
add a comment |
$begingroup$
If you start with $(0,0)$ and in each step add $(1,0)$ or $(0,1)$, going $4$ steps in total, there are $2^4=16$ possible paths. If you forbid path's where the $x$ or $y$ coordinate ends up above $3$, you have to subtract the two paths going either all 4 steps up or all 4 steps right. In total you have $16-2=14$ paths satisfying your condition.
In general, the number of paths ending in $(x,y)$ is given by $binom{x+y}{x} = binom{x+y}{y}$ since you are going $x+y$ steps and have to choose which of them are up and which are right. So the $16$ pathes split as
$$
binom{0+4}{0} + binom{1+3}{1} + binom{2+2}{2} + binom{3+1}{3} + binom{4+0}{4} =1+4+6+4+1.
$$
So if you want to make $n$ steps in total, only allowing at most $kle n$ in each direction you get
$$
sum_{i=n-k}^{k} binom{n}{i}.
$$
answered Dec 20 '18 at 11:08
ChristophChristoph
12.3k1642
$endgroup$
If you start with $(0,0)$ and in each step add $(1,0)$ or $(0,1)$, going $4$ steps in total, there are $2^4=16$ possible paths. If you forbid path's where the $x$ or $y$ coordinate ends up above $3$, you have to subtract the two paths going either all 4 steps up or all 4 steps right. In total you have $16-2=14$ paths satisfying your condition.
In general, the number of paths ending in $(x,y)$ is given by $binom{x+y}{x} = binom{x+y}{y}$ since you are going $x+y$ steps and have to choose which of them are up and which are right. So the $16$ pathes split as
$$
binom{0+4}{0} + binom{1+3}{1} + binom{2+2}{2} + binom{3+1}{3} + binom{4+0}{4} =1+4+6+4+1.
$$
So if you want to make $n$ steps in total, only allowing at most $kle n$ in each direction you get
$$
sum_{i=n-k}^{k} binom{n}{i}.
$$
answered Dec 20 '18 at 11:08
ChristophChristoph
12.3k1642
edited Dec 20 '18 at 11:33
answered Dec 20 '18 at 11:08
ChristophChristoph
12.3k1642
answered Dec 20 '18 at 11:08
ChristophChristoph
12.3k1642
answered Dec 20 '18 at 11:08
ChristophChristoph
12.3k1642
12.3k1642
$begingroup$
How does this generalise? Say we have $4$ steps and stop $x$ or $y$ going above $2$, preventing $(3,1),(4,0),(1,3),(0,4)$. We end up with a $2times2$ North-East lattice for which there are 6 paths, but $2^{4}-4neq6$
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:26
1
$begingroup$
I updated my answer.
$endgroup$
– Christoph
Dec 20 '18 at 11:33
add a comment |
$begingroup$
How does this generalise? Say we have $4$ steps and stop $x$ or $y$ going above $2$, preventing $(3,1),(4,0),(1,3),(0,4)$. We end up with a $2times2$ North-East lattice for which there are 6 paths, but $2^{4}-4neq6$
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:26
1
$begingroup$
I updated my answer.
$endgroup$
– Christoph
Dec 20 '18 at 11:33
$begingroup$
How does this generalise? Say we have $4$ steps and stop $x$ or $y$ going above $2$, preventing $(3,1),(4,0),(1,3),(0,4)$. We end up with a $2times2$ North-East lattice for which there are 6 paths, but $2^{4}-4neq6$
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:26
$begingroup$
How does this generalise? Say we have $4$ steps and stop $x$ or $y$ going above $2$, preventing $(3,1),(4,0),(1,3),(0,4)$. We end up with a $2times2$ North-East lattice for which there are 6 paths, but $2^{4}-4neq6$
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:26
1
1
$begingroup$
I updated my answer.
$endgroup$
– Christoph
Dec 20 '18 at 11:33
$begingroup$
I updated my answer.
$endgroup$
– Christoph
Dec 20 '18 at 11:33
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%2f3047407%2fcounting-lattice-paths-which-use-fixed-steps-but-can-end-in-different-places%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
$begingroup$
It is unclear what you mean by "move" and what "maximum number of moves in one direction" means. Maybe be more precise and/or provide some examples of allowed and not allowed paths.
$endgroup$
– Christoph
Dec 20 '18 at 11:00
$begingroup$
Sorry for being unclear. I'm trying to refer to a North-East lattice path with steps $S={ (0,1),(1,0) }$.
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:02
$begingroup$
That I got. But what are moves?
$endgroup$
– Christoph
Dec 20 '18 at 11:03
$begingroup$
By moves I mean steps - I'll edit the question. Sorry for confusion
$endgroup$
– cluelessatthis
Dec 20 '18 at 11:03
$begingroup$
Assuming I go from $(0,0)$ to $(0,1)$ and then to $(0,3)$. Is this one step/move since the direction didn't change? Do you mean "maximum consecutive steps in one direction" or "maximum total steps in one direction"?
$endgroup$
– Christoph
Dec 20 '18 at 11:05