In combinatorial mathematics, block walking is a method useful in thinking about sums of combinations graphically as "walks" on Pascal's triangle. As the name suggests, block walking problems involve counting the number of ways an individual can walk from one corner A of a city block to another corner B of another city block given restrictions on the number of blocks the person may walk, the directions the person may travel, the distance from A to B, et cetera.
Contents
An example block walking problem
Suppose such an individual, say "Fred", must walk exactly k blocks to get to a point B that is exactly k blocks from A. It is convenient to regard Fred's starting point A as the origin,
Solution by brute force
A "brute force" solution to this problem may be obtained by systematically counting the number of ways Fred can reach each point
without backtracking (i.e. only traveling North or East from one point to another) until a pattern is observed. For example, the number of ways Fred could go from
Combinatorial solution
Since the problem involves counting a finite, discrete number of paths between lattice points, it is reasonable to assume a combinatorial solution exists to the problem. Towards this end, we note that for Fred to still be on a path that will take him from A to B over
which is equivalent to finding the number of ways to choose