Lattice Paths that Avoid a Point

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP

up vote
9
down vote

favorite

1

My house is located at $(0,0)$ and the supermarket is located at $(7,5)$. I can only move in the upwards or in rightward directions. How many different routes are there? Obviously, ${12}choose{7}$ $=$ ${12}choose{5}$ $=$ $792$. How many paths are there if I want to avoid the really busy intersection located at $(3,3)$?

I have three ideas, all of which lead to different answers:

1) My first idea was to label out the grid and write the number at each intersection that represents how many paths cross that point. This was equivalent to writing out pascals triangle in a tilted diagonal way, until I reached $(3,3)$ whereI had to write a $0$, but then I proceeded as you’d expect, the intersection’s number was equal to the one below it added to the one to the left of it. At $(7,5)$ I ended up getting $490$.

After this, I wanted a combinatorial way to confirm my answer, so I tried:

2)counting all the paths from $(0,0)$ to $(3,3)$ and subtracting those away from $792$. So here I would subtract ${6}choose{3}$ $=20$.

3)counting all the paths from $(3,3)$ to $(7,5)$ and subtracting those away from $792$. So here I would subtract ${6}choose{4}$ $=15$.

So my question is: which method of thinking is correct and why do the other two not lead to the correct answer (what do they over/under count)? I suspect that my first try was correct, and the answer is $490$, but I don’t see the algorithmic way of seeing it…

EDIT: Made a correction to my grid. I wrote a $34$ instead of a $36$ for the intersection at $(7,2)$. Woops!

share|cite|improve this question

  • 4

    I would have expected your supermarket to be at $(7,11)$… 😛
    – Asaf Karagila
    Dec 1 at 8:00

up vote
9
down vote

favorite

1

My house is located at $(0,0)$ and the supermarket is located at $(7,5)$. I can only move in the upwards or in rightward directions. How many different routes are there? Obviously, ${12}choose{7}$ $=$ ${12}choose{5}$ $=$ $792$. How many paths are there if I want to avoid the really busy intersection located at $(3,3)$?

I have three ideas, all of which lead to different answers:

1) My first idea was to label out the grid and write the number at each intersection that represents how many paths cross that point. This was equivalent to writing out pascals triangle in a tilted diagonal way, until I reached $(3,3)$ whereI had to write a $0$, but then I proceeded as you’d expect, the intersection’s number was equal to the one below it added to the one to the left of it. At $(7,5)$ I ended up getting $490$.

After this, I wanted a combinatorial way to confirm my answer, so I tried:

2)counting all the paths from $(0,0)$ to $(3,3)$ and subtracting those away from $792$. So here I would subtract ${6}choose{3}$ $=20$.

3)counting all the paths from $(3,3)$ to $(7,5)$ and subtracting those away from $792$. So here I would subtract ${6}choose{4}$ $=15$.

So my question is: which method of thinking is correct and why do the other two not lead to the correct answer (what do they over/under count)? I suspect that my first try was correct, and the answer is $490$, but I don’t see the algorithmic way of seeing it…

EDIT: Made a correction to my grid. I wrote a $34$ instead of a $36$ for the intersection at $(7,2)$. Woops!

share|cite|improve this question

  • 4

    I would have expected your supermarket to be at $(7,11)$… 😛
    – Asaf Karagila
    Dec 1 at 8:00

up vote
9
down vote

favorite

1

up vote
9
down vote

favorite

1
1

My house is located at $(0,0)$ and the supermarket is located at $(7,5)$. I can only move in the upwards or in rightward directions. How many different routes are there? Obviously, ${12}choose{7}$ $=$ ${12}choose{5}$ $=$ $792$. How many paths are there if I want to avoid the really busy intersection located at $(3,3)$?

I have three ideas, all of which lead to different answers:

1) My first idea was to label out the grid and write the number at each intersection that represents how many paths cross that point. This was equivalent to writing out pascals triangle in a tilted diagonal way, until I reached $(3,3)$ whereI had to write a $0$, but then I proceeded as you’d expect, the intersection’s number was equal to the one below it added to the one to the left of it. At $(7,5)$ I ended up getting $490$.

After this, I wanted a combinatorial way to confirm my answer, so I tried:

2)counting all the paths from $(0,0)$ to $(3,3)$ and subtracting those away from $792$. So here I would subtract ${6}choose{3}$ $=20$.

3)counting all the paths from $(3,3)$ to $(7,5)$ and subtracting those away from $792$. So here I would subtract ${6}choose{4}$ $=15$.

So my question is: which method of thinking is correct and why do the other two not lead to the correct answer (what do they over/under count)? I suspect that my first try was correct, and the answer is $490$, but I don’t see the algorithmic way of seeing it…

EDIT: Made a correction to my grid. I wrote a $34$ instead of a $36$ for the intersection at $(7,2)$. Woops!

share|cite|improve this question

My house is located at $(0,0)$ and the supermarket is located at $(7,5)$. I can only move in the upwards or in rightward directions. How many different routes are there? Obviously, ${12}choose{7}$ $=$ ${12}choose{5}$ $=$ $792$. How many paths are there if I want to avoid the really busy intersection located at $(3,3)$?

I have three ideas, all of which lead to different answers:

1) My first idea was to label out the grid and write the number at each intersection that represents how many paths cross that point. This was equivalent to writing out pascals triangle in a tilted diagonal way, until I reached $(3,3)$ whereI had to write a $0$, but then I proceeded as you’d expect, the intersection’s number was equal to the one below it added to the one to the left of it. At $(7,5)$ I ended up getting $490$.

After this, I wanted a combinatorial way to confirm my answer, so I tried:

2)counting all the paths from $(0,0)$ to $(3,3)$ and subtracting those away from $792$. So here I would subtract ${6}choose{3}$ $=20$.

3)counting all the paths from $(3,3)$ to $(7,5)$ and subtracting those away from $792$. So here I would subtract ${6}choose{4}$ $=15$.

So my question is: which method of thinking is correct and why do the other two not lead to the correct answer (what do they over/under count)? I suspect that my first try was correct, and the answer is $490$, but I don’t see the algorithmic way of seeing it…

EDIT: Made a correction to my grid. I wrote a $34$ instead of a $36$ for the intersection at $(7,2)$. Woops!

combinatorics

share|cite|improve this question

share|cite|improve this question

share|cite|improve this question

share|cite|improve this question

edited Nov 30 at 21:21

asked Nov 30 at 20:57

ruferd

22318

22318

  • 4

    I would have expected your supermarket to be at $(7,11)$… 😛
    – Asaf Karagila
    Dec 1 at 8:00

  • 4

    I would have expected your supermarket to be at $(7,11)$… 😛
    – Asaf Karagila
    Dec 1 at 8:00

4

4

I would have expected your supermarket to be at $(7,11)$… 😛
– Asaf Karagila
Dec 1 at 8:00

I would have expected your supermarket to be at $(7,11)$… 😛
– Asaf Karagila
Dec 1 at 8:00

2 Answers
2

active

oldest

votes

up vote
14
down vote

accepted

You need to look at the complement, which is all the paths from $(0,0)$ to $(7,5)$ that pass through $(3,3)$.

As you noted, the number of paths from $(0,0)$ to $(3,3)$ is ${6choose3} = 20$, and the number of paths from $(3,3)$ to $(7,5)$ is ${6choose4} = 15$. So the number of paths from $(0,0)$ to $(7,5)$ that pass through $(3,3)$ is all combinations of the above paths, which means $20cdot15=300$ paths.

$792-300=492$, and so $492$ is the final answer.

share|cite|improve this answer

  • Ok, I see now…I wasn’t accounting for each new branch that I could take from $(3,3)$ to $(7,5)$ after I had already gone from $(0,0)$ to $(3,3)$. I guess I should have reflected on my results of option 2 and 3 and seen if I could use ${6}choose{4}$ and ${6}choose{3}$ in some way with 792 to get the answer. The only reasonable way would be to multiply them together and subtract, but this is the argument to back that idea up, thank you! And also, it appears that my grid in option 1 was off somehow! Woops!
    – ruferd
    Nov 30 at 21:15

up vote
4
down vote

Your idea to subtract the number of paths passing through $(3,3)$ from $792$ was a good idea, but you didn’t carry it out quite right. The number of paths that pass through $(3,3)$ is not $binom{6}{3}$ nor $binom{6}{4}$, but $binom{6}{3}binom{6}{4}$. This is because every path from $(0,0)$ to $(7,5)$ through $(3,3)$ consists of two “mini-paths,” one from $(0,0)$ to $(3,3)$ and one from $(3,3)$ to $(7,5)$. There are $binom{6}{3}$ ways to choose the first path and $binom{6}{4}$ ways to choose the second, resulting in $binom{6}{3}binom{6}{4}$ ways to choose the entire path, and $792-binom{6}{3}binom{6}{4}$ paths avoiding $(3,3)$.

share|cite|improve this answer

  • AH ok, thank you. a path from $(0,0)$ to $(3,3)$ would also have ${6}choose{4}$ ways to get to $(7,5)$, so I’d multiply, thanks, it is so obvious now!
    – ruferd
    Nov 30 at 21:11

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’,
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%2f3020627%2flattice-paths-that-avoid-a-point%23new-answer’, ‘question_page’);
}
);

Post as a guest

Required, but never shown

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
14
down vote

accepted

You need to look at the complement, which is all the paths from $(0,0)$ to $(7,5)$ that pass through $(3,3)$.

As you noted, the number of paths from $(0,0)$ to $(3,3)$ is ${6choose3} = 20$, and the number of paths from $(3,3)$ to $(7,5)$ is ${6choose4} = 15$. So the number of paths from $(0,0)$ to $(7,5)$ that pass through $(3,3)$ is all combinations of the above paths, which means $20cdot15=300$ paths.

$792-300=492$, and so $492$ is the final answer.

share|cite|improve this answer

  • Ok, I see now…I wasn’t accounting for each new branch that I could take from $(3,3)$ to $(7,5)$ after I had already gone from $(0,0)$ to $(3,3)$. I guess I should have reflected on my results of option 2 and 3 and seen if I could use ${6}choose{4}$ and ${6}choose{3}$ in some way with 792 to get the answer. The only reasonable way would be to multiply them together and subtract, but this is the argument to back that idea up, thank you! And also, it appears that my grid in option 1 was off somehow! Woops!
    – ruferd
    Nov 30 at 21:15

up vote
14
down vote

accepted

You need to look at the complement, which is all the paths from $(0,0)$ to $(7,5)$ that pass through $(3,3)$.

As you noted, the number of paths from $(0,0)$ to $(3,3)$ is ${6choose3} = 20$, and the number of paths from $(3,3)$ to $(7,5)$ is ${6choose4} = 15$. So the number of paths from $(0,0)$ to $(7,5)$ that pass through $(3,3)$ is all combinations of the above paths, which means $20cdot15=300$ paths.

$792-300=492$, and so $492$ is the final answer.

share|cite|improve this answer

  • Ok, I see now…I wasn’t accounting for each new branch that I could take from $(3,3)$ to $(7,5)$ after I had already gone from $(0,0)$ to $(3,3)$. I guess I should have reflected on my results of option 2 and 3 and seen if I could use ${6}choose{4}$ and ${6}choose{3}$ in some way with 792 to get the answer. The only reasonable way would be to multiply them together and subtract, but this is the argument to back that idea up, thank you! And also, it appears that my grid in option 1 was off somehow! Woops!
    – ruferd
    Nov 30 at 21:15

up vote
14
down vote

accepted

up vote
14
down vote

accepted

You need to look at the complement, which is all the paths from $(0,0)$ to $(7,5)$ that pass through $(3,3)$.

As you noted, the number of paths from $(0,0)$ to $(3,3)$ is ${6choose3} = 20$, and the number of paths from $(3,3)$ to $(7,5)$ is ${6choose4} = 15$. So the number of paths from $(0,0)$ to $(7,5)$ that pass through $(3,3)$ is all combinations of the above paths, which means $20cdot15=300$ paths.

$792-300=492$, and so $492$ is the final answer.

share|cite|improve this answer

You need to look at the complement, which is all the paths from $(0,0)$ to $(7,5)$ that pass through $(3,3)$.

As you noted, the number of paths from $(0,0)$ to $(3,3)$ is ${6choose3} = 20$, and the number of paths from $(3,3)$ to $(7,5)$ is ${6choose4} = 15$. So the number of paths from $(0,0)$ to $(7,5)$ that pass through $(3,3)$ is all combinations of the above paths, which means $20cdot15=300$ paths.

$792-300=492$, and so $492$ is the final answer.

share|cite|improve this answer

share|cite|improve this answer

share|cite|improve this answer

answered Nov 30 at 21:05

AlephZero

25816

25816

  • Ok, I see now…I wasn’t accounting for each new branch that I could take from $(3,3)$ to $(7,5)$ after I had already gone from $(0,0)$ to $(3,3)$. I guess I should have reflected on my results of option 2 and 3 and seen if I could use ${6}choose{4}$ and ${6}choose{3}$ in some way with 792 to get the answer. The only reasonable way would be to multiply them together and subtract, but this is the argument to back that idea up, thank you! And also, it appears that my grid in option 1 was off somehow! Woops!
    – ruferd
    Nov 30 at 21:15

  • Ok, I see now…I wasn’t accounting for each new branch that I could take from $(3,3)$ to $(7,5)$ after I had already gone from $(0,0)$ to $(3,3)$. I guess I should have reflected on my results of option 2 and 3 and seen if I could use ${6}choose{4}$ and ${6}choose{3}$ in some way with 792 to get the answer. The only reasonable way would be to multiply them together and subtract, but this is the argument to back that idea up, thank you! And also, it appears that my grid in option 1 was off somehow! Woops!
    – ruferd
    Nov 30 at 21:15

Ok, I see now…I wasn’t accounting for each new branch that I could take from $(3,3)$ to $(7,5)$ after I had already gone from $(0,0)$ to $(3,3)$. I guess I should have reflected on my results of option 2 and 3 and seen if I could use ${6}choose{4}$ and ${6}choose{3}$ in some way with 792 to get the answer. The only reasonable way would be to multiply them together and subtract, but this is the argument to back that idea up, thank you! And also, it appears that my grid in option 1 was off somehow! Woops!
– ruferd
Nov 30 at 21:15

Ok, I see now…I wasn’t accounting for each new branch that I could take from $(3,3)$ to $(7,5)$ after I had already gone from $(0,0)$ to $(3,3)$. I guess I should have reflected on my results of option 2 and 3 and seen if I could use ${6}choose{4}$ and ${6}choose{3}$ in some way with 792 to get the answer. The only reasonable way would be to multiply them together and subtract, but this is the argument to back that idea up, thank you! And also, it appears that my grid in option 1 was off somehow! Woops!
– ruferd
Nov 30 at 21:15

up vote
4
down vote

Your idea to subtract the number of paths passing through $(3,3)$ from $792$ was a good idea, but you didn’t carry it out quite right. The number of paths that pass through $(3,3)$ is not $binom{6}{3}$ nor $binom{6}{4}$, but $binom{6}{3}binom{6}{4}$. This is because every path from $(0,0)$ to $(7,5)$ through $(3,3)$ consists of two “mini-paths,” one from $(0,0)$ to $(3,3)$ and one from $(3,3)$ to $(7,5)$. There are $binom{6}{3}$ ways to choose the first path and $binom{6}{4}$ ways to choose the second, resulting in $binom{6}{3}binom{6}{4}$ ways to choose the entire path, and $792-binom{6}{3}binom{6}{4}$ paths avoiding $(3,3)$.

share|cite|improve this answer

  • AH ok, thank you. a path from $(0,0)$ to $(3,3)$ would also have ${6}choose{4}$ ways to get to $(7,5)$, so I’d multiply, thanks, it is so obvious now!
    – ruferd
    Nov 30 at 21:11

up vote
4
down vote

Your idea to subtract the number of paths passing through $(3,3)$ from $792$ was a good idea, but you didn’t carry it out quite right. The number of paths that pass through $(3,3)$ is not $binom{6}{3}$ nor $binom{6}{4}$, but $binom{6}{3}binom{6}{4}$. This is because every path from $(0,0)$ to $(7,5)$ through $(3,3)$ consists of two “mini-paths,” one from $(0,0)$ to $(3,3)$ and one from $(3,3)$ to $(7,5)$. There are $binom{6}{3}$ ways to choose the first path and $binom{6}{4}$ ways to choose the second, resulting in $binom{6}{3}binom{6}{4}$ ways to choose the entire path, and $792-binom{6}{3}binom{6}{4}$ paths avoiding $(3,3)$.

share|cite|improve this answer

  • AH ok, thank you. a path from $(0,0)$ to $(3,3)$ would also have ${6}choose{4}$ ways to get to $(7,5)$, so I’d multiply, thanks, it is so obvious now!
    – ruferd
    Nov 30 at 21:11

up vote
4
down vote

up vote
4
down vote

Your idea to subtract the number of paths passing through $(3,3)$ from $792$ was a good idea, but you didn’t carry it out quite right. The number of paths that pass through $(3,3)$ is not $binom{6}{3}$ nor $binom{6}{4}$, but $binom{6}{3}binom{6}{4}$. This is because every path from $(0,0)$ to $(7,5)$ through $(3,3)$ consists of two “mini-paths,” one from $(0,0)$ to $(3,3)$ and one from $(3,3)$ to $(7,5)$. There are $binom{6}{3}$ ways to choose the first path and $binom{6}{4}$ ways to choose the second, resulting in $binom{6}{3}binom{6}{4}$ ways to choose the entire path, and $792-binom{6}{3}binom{6}{4}$ paths avoiding $(3,3)$.

share|cite|improve this answer

Your idea to subtract the number of paths passing through $(3,3)$ from $792$ was a good idea, but you didn’t carry it out quite right. The number of paths that pass through $(3,3)$ is not $binom{6}{3}$ nor $binom{6}{4}$, but $binom{6}{3}binom{6}{4}$. This is because every path from $(0,0)$ to $(7,5)$ through $(3,3)$ consists of two “mini-paths,” one from $(0,0)$ to $(3,3)$ and one from $(3,3)$ to $(7,5)$. There are $binom{6}{3}$ ways to choose the first path and $binom{6}{4}$ ways to choose the second, resulting in $binom{6}{3}binom{6}{4}$ ways to choose the entire path, and $792-binom{6}{3}binom{6}{4}$ paths avoiding $(3,3)$.

share|cite|improve this answer

share|cite|improve this answer

share|cite|improve this answer

answered Nov 30 at 21:09

Frpzzd

20.7k638104

20.7k638104

  • AH ok, thank you. a path from $(0,0)$ to $(3,3)$ would also have ${6}choose{4}$ ways to get to $(7,5)$, so I’d multiply, thanks, it is so obvious now!
    – ruferd
    Nov 30 at 21:11

  • AH ok, thank you. a path from $(0,0)$ to $(3,3)$ would also have ${6}choose{4}$ ways to get to $(7,5)$, so I’d multiply, thanks, it is so obvious now!
    – ruferd
    Nov 30 at 21:11

AH ok, thank you. a path from $(0,0)$ to $(3,3)$ would also have ${6}choose{4}$ ways to get to $(7,5)$, so I’d multiply, thanks, it is so obvious now!
– ruferd
Nov 30 at 21:11

AH ok, thank you. a path from $(0,0)$ to $(3,3)$ would also have ${6}choose{4}$ ways to get to $(7,5)$, so I’d multiply, thanks, it is so obvious now!
– ruferd
Nov 30 at 21:11

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.

Some of your past answers have not been well-received, and you’re in danger of being blocked from answering.

Please pay close attention to the following guidance:

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

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%2f3020627%2flattice-paths-that-avoid-a-point%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

Related Post

Leave a Reply

Your email address will not be published. Required fields are marked *