In a city with orthogonal streets and regular city block, a party-goer leaves a bar and walks back home. His home is North East from the bar, blocks up, and blocks east. At each intersection, he decide to go either north or east randomly—but whatever’s left of his sobriety keeps from backtracking: he always moves closer to home. How many ways can the drunkard get get back home?
So if there’s only one city block to go around, we only have two possibilities:
Either we go north first, or we go east first. If we have two city blocks, then there’s three choices:
Then, if we have city blocks, we have 6 choices:
The number of path grows rapidly after this.
If you try to solve the problem by enumeration, you probably will end up with a recurrence such as
(ignoring minor parametrization variations depending on whether you count intersections or city block). Solving that recurrence directly is not easily done, but we can make connections with similar recurrences we know. It does look like
while not being exactly the same.
However, to solve this easily, we’ll have to do some lateral thinking. If rather than taking the problem recursively, as its initial formulation seems to suggest, we take it as an encoding approach to the problem, we can find a much simpler solution. If we encode one of the many paths as a series of one and zeros, then one specific path will be encoded with, say, 1s, encoding going north, and zeroes, encoding east. So the question now becomes, how many strings are there with ones and zeroes? Or… How many strings of length have ones? Simply
is the numbers of way of picking ones amongst objects.
However we have a minor adjustment to make to this formula to make it agree with the recurrence above, , because doesn’t count street segments, it counts intersections. Therefore, we have that
Here we have another example where lateral thinking helps. Rather than trying to solve the recurrence directly (with something like characteristic polynomials and whatever other tools you happen to know) we found a perfectly cromulent solution by restating the problem as an encoding problem.