Counting lattice paths which use fixed steps but can end in different places












0












$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.










share|cite|improve this question











$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


















0












$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.










share|cite|improve this question











$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
















0












0








0





$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.










share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 20 '18 at 11:04







cluelessatthis

















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




















  • $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












1 Answer
1






active

oldest

votes


















0












$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}.
$$






share|cite|improve this answer











$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











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
});


}
});














draft saved

draft discarded


















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









0












$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}.
$$






share|cite|improve this answer











$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
















0












$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}.
$$






share|cite|improve this answer











$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














0












0








0





$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}.
$$






share|cite|improve this answer











$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}.
$$







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Dec 20 '18 at 11:33

























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


















  • $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


















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

Ellipse (mathématiques)

Quarter-circle Tiles

Mont Emei