Q16
3 marks
Combinations & Selection
Lattice Path Counting
View
A good path is a sequence of points in the $XY$ plane such that in each step exactly one of the coordinates increases by 1 and the other stays the same. E.g., $$(0,0),(1,0),(2,0),(2,1),(3,1),(3,2),(3,3)$$ is a good path from the origin to $(3,3)$. It is a fact that there are exactly 924 good paths from the origin to $(6,6)$.
Find the number of good paths from $(0,0)$ to $(6,6)$ such that neither of the two points $(1,2)$ and $(3,4)$ occurs on the path, i.e., the path must miss both of the points $(1,2)$ and $(3,4)$. [3 points]