Travelling on a 2D grid
In a 2D area person A can only move right or down. They cannot move up or left.
Using your knowledge of Pascal’s triangle and treating the space A moves in as a grid, determine a formula which will find, directly, the number of routes from A’s home to any node on such a grid. Explain your answer fully and include an example of the model in practice. Also, discuss any strengths and limitations of the use of this model when determining the number of routes, including any assumption(s) required and the effect of these assumptions.
2 Answers | Add Yours
Person A can only move right (east) or downwards (south) on a grid.
We can think of the number of ways A can do this by treating travel eastwards as moving down and right on the Pascal triangle and treating travel southwards as moving down and left on the Pascal triangle.
Recall that the Pascal triangle looks like this
1 2 1
1 3 3 1
1 4 6 4 1
where each 'node' is the sum of its 'parent nodes' (up one to the left and to the right). The formula for the node in the nth row (counting from zero) and x nodes across (again counting from zero) is given by
`p(n,x) = (n!)/(x!(n-x)!)`
For example, the node two along in the fourth row is then
`p(4,2) = (4!)/(2!2!) = (22.214.171.124)/((2.1)(2.1)) = (4.3)/(2.1) = 12/2 = 6`
So, thinking of movement eastwards as moving to the right in the Pascal's triangle and movement southwards by moving downwards, two units east and one unit south can be done in 3 ways: EES, ESE, SEE
1 1 1
1 1 1
1 2 2
3 3 3
A has moved a total of 3 units so that leads us to the 3rd row of Pascal's triangle (counting from zero) and 2 units east and 1 unit south - this is the 2nd node along from the left (counting from zero) and the 1st from the right.
Therefore the formula for the number of ways W of moving `n_e` units to the east and `n_s` units to the south is given by
`W(n_e,n_s) = ((n_e+n_s)!)/(n_e!n_s!)`
Strengths: this is a simple model that treats the area A can travel in as a grid. Because it is a simple model, the formula to calculate the number of ways is straightforward and can be derived from Pascal's triangle.
Limitations: i) as the number of units travelled becomes large, calculation of the number of ways becomes difficult for the calculator/computer as it requires a lot of memory (RAM). This is because the calculation involves large factorials (!). For a very large number of units, computation of the number of ways would be 'infeasible'.
ii) The assumption that the space A travels in is defined by a grid cuts the space into discrete nodes and doesn't treat it as continuous space. 'A' can only travel to certain points in the area. To overcome this, the grid could be made very fine to make it more continuous, but the more nodes, the more infeasible the calculation of the number of ways becomes because of the calculation of large factorials.
Hi, when you say this "We can think of the number of ways A can do this by treating travel eastwards as moving down and right on the Pascal triangle and treating travel southwards as moving down and left on the Pascal triangle." i do not understand why is "travel eastwards as moving down and right" for A????
Join to answer this question
Join a community of thousands of dedicated teachers and students.Join eNotes