Block walking

From Wikipedia, the free encyclopedia

In mathematics, block walking is a method useful in thinking about sums of combinations graphically as a 'walk' on Pascal's triangle.

1 An analogous problem
- 1.1 Brute force
- 1.2 A smarter approach
2 Back to the original problem
3 Some problems

[edit] An analogous problem

To understand block walking consider the following problem: Given a grid how many ways are there to go from (0,0) to (5,5) assuming that you can only travel along lattice points and you may only move a total of 5 units in each direction.

[edit] Brute force

To approach this problem you could simply start counting the number of total possible paths by brute force, so the number of ways to go from (0,0) to (1,1) is two, from (0,0) to (1,2) there are three ways and from (0,0) to (2,1) there are also three ways. To get consecutive points we could simply add terms previous to it to simplify the process.

[edit] A smarter approach

We understand that the answer is not identically infinity due to the fact that the total number of moves is restrained to five units, so we approach the problem combinatorially. Initially split up the moves into unit vectors, so we have five vectors of the type <1,0> and five vectors of the type <0,1>, to make things even more clear we make a substitution, we say that <0,1> = x and <1,0> = y. Now our problem has simplified down to finding the number of distinct arrangements of the word xxxxxyyyyy. This problem is interesting but fairly straightforward, so let's arrange 10 characters in every possible way, we get 10!, however this assumes that all the characters are distinct, do you see why? But we can easily fix that so we have $\frac{10!}{5!5!}$ .

[edit] Back to the original problem

Block walking is simply using the previous problem on Pascal's Triangle to simplify seemingly impossible sums. It works as follows, starting at (0,0) on Pascal's Triangle we try to get to some number say ${n \choose k}$ , using the previous example makes the problem easier to think about but basically we have to move n units down and k units across, because we can move both down and across at the same time the problem becomes even simpler than the previous example. We choose the k of the n downwards movements that are to be coupled with movements to the side, this is obviously ${n \choose k}$ .

[edit] Some problems

(1.) Find $\sum_{k=0}^n { n \choose k}^2\ = { 2n \choose n}$ ( Taken from "The Art of Problem Solving, Volume II" pg 231 by Richard Rusczyk and Sandor Lehoczky)

This problem melts away with a simple application of block walking, so, we know that in traveling to ${n \choose k}$ we have to travel through ${n \choose k}$ and as a result we are tempted to change $\sum_{k=0}^n { n \choose k}^2\ = \sum_{k=0}^n { n \choose k}{ n \choose k} = \sum_{k=0}^n { n \choose k}{ n \choose n-k}$ and because we can pass through the nth row at any position $0 \le k \le n$ we have that $\sum_{k=0}^n { n \choose k}{ n \choose n-k} = {2n \choose k }$ .