Loading the lesson
Loading the lesson
Search AllRounder.ai
Search the courses, subjects, tracks, games and features, or jump straight to a page.
Search the courses, subjects, tracks, games and features, or jump straight to a page.
Learn it your way
A short class with Sarah and her students. The other ways are under More.
Sign up free to listen. Transcripts are free to read.
Today we’re going to explore grid paths. Imagine we have a grid starting at the bottom left corner (0, 0) and want to reach the top right corner, like (5, 10). How do you think we could determine the number of different paths?
Are there specific rules for how we can move on the grid?
Yes! You can only move right or up. So, if you think about it, to get from (0, 0) to (5, 10), how many steps would you need to take?
I think we need 15 steps total, 5 right and 10 up!
Correct! We denote this as '5 right and 10 up'. Now, can anyone tell me how we might count those different paths?
Maybe we can count the different ways to arrange those steps?
Exactly! This can be calculated using combinations, specifically '15 choose 5'. Good job!
Now that we know how many steps we need, let's talk about how to compute '15 choose 5'. What do you think that means?
Does it have something to do with factorials?
Yes! It's calculated as 15 factorial over the product of 10 and 5 factorial. Who can give me the numbers for this?
I think '15 factorial' is 1,307,674,368,000.
Great start! But can you calculate the combinations so we can find the final answer?
So, the answer is 3003 paths!
Yes! There are 3003 unique paths from (0, 0) to (5, 10). Fantastic job!
What if there are some intersections that we can't cross? For example, how would it change if (2, 4) is blocked?
Wouldn’t we just remove paths that go through that point?
Exactly! First, we find the number of paths that go through (2, 4) and then subtract those from our total.
So, do we count paths to (2, 4) and then from (2, 4) to (5, 10) separately?
Spot on! Then we multiply the two results. If there are 15 paths to (2, 4) and 84 from (2, 4) to (5, 10), what’s that total?
That would be 1260 paths that go through (2, 4).
And subtracting this from 3003 gives us the valid paths, which is 1743. Excellent thinking!
Now imagine we had two blocked points. Let’s consider (2, 4) and (4, 4). How would we approach this?
Would we need to subtract paths through both points?
Correct! But be careful, we might double count paths that go through both. What can we do about this?
I think we need to add back those double-counted paths?
Exactly! This technique is called the inclusion-exclusion principle. It helps us accurately count without overcounting. Great job!
The different sequences of moves possible from start to end.
'n choose k', a method to calculate the number of ways to choose items.
Intersections that inhibit certain possible routes.
A technique to accurately count valid outcomes in complex scenarios.
To go from left to top with ease, count the rights and ups, if you please.
Once upon a grid, there lived a traveler who could only move right or up. To reach the castle, he had to count his steps wisely, avoiding any blocked paths.
R for right, U for up - remember the path is a cup of luck!
C-U-B-E: Combinations, Up moves, Blocked paths, and Exclusions.
Term
What are grid paths?
Click to flip
Term
What is a blocked intersection?
Click to flip
A route from the bottom left corner of a grid to the top right, consisting only of moves up or right.
A selection of items from a larger set, where order does not matter, denote as 'n choose k'.
A point on the grid that cannot be traversed in the path from start to finish.
A combinatorial method to calculate the size of unions of multiple sets, accounting for overlaps.
This section introduces the concept of grid paths, focusing on how to calculate the number of unique paths from the bottom left to the top right corner of a grid.
The section explains the problem of counting grid paths, detailing how to calculate the total number of unique paths by applying combinatorial principles. It also addresses the impact of blocked intersections on valid paths and introduces concepts of inclusion-exclusion.
The topic of grid paths involves finding the number of different routes from the bottom left corner to the top right corner of a rectangular grid, where movement is restricted to the right and upward directions. For instance, if we define the starting point as (0, 0) and the ending point as (5, 10), we explore how many unique sequences of movements can take one from (0, 0) to (5, 10).
To calculate the number of different paths, we consider the total steps needed: for our example, we require 15 steps (5 right moves and 10 up moves). The total number of unique paths corresponds to selecting 5 moves to be right (or 10 moves to be up) from these 15 total movements, which can be expressed mathematically using combinations. Specifically, this is represented as '15 choose 5', allowing us to calculate the total combinations.
The presence of blocked paths introduces additional complexity, as certain intersections may not be traversable. If any path crosses a blocked point, it no longer counts as valid. The process to ascertain valid paths in this case is to subtract the number of invalid paths from the total calculated paths, which is where combinatorial methods are applied in conjunction with the principle of inclusion-exclusion to ensure accurate counting. Thus, the counting of paths, accounting for intersections and blockages, constitutes a vital area of combinatorial study.