Commuting in Manhattan

Computer Science Level 5

A man walks n n blocks north and n n blocks west of his residence to get to work. As they are installing a sewage pipe diagonally across town, he can touch, but cannot cross over, the main diagonal line.

The above figure shows 84 84 possible paths he could take for n = 5 n=5 .

How many possible routes can he take if n = 28 n=28 ?


The answer is 527495903500720.

Beakal Tiliksew by Beakal Tiliksew , 24, Ethiopia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Thaddeus Abiy
Jul 29, 2015

This is twice the 28 28 th Catalan number 2 C 28 2C_{28} . 

1
2
3
 
from operator import mul   
from fractions import Fraction
print 2*(int( reduce(mul, (Fraction(2*28-i, i+1) for i in range(28)), 1) )/(28+1))

3 Helpful 0 Interesting 0 Brilliant 0 Confused
Arulx Z
Aug 6, 2015

Since I'm a beginner to the world of combinatorics, I used constructive counting approach.

I divided the grid into two halves (diagonally) then calculated the paths. When you do that, an obvious pattern emerges. Here is my code - 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
List<Double> n = new ArrayList<>();
for(double i = 1; i <= 28; i++)
    n.add(i);
while (n.size() != 1) {
    n.remove(0);
    for(int i = 0; i < n.size() - 1; i++){
        n.add(i + 1, n.get(i) + n.get(i + 1));
        n.remove(i + 2);
    }
}
System.out.println(n.get(0) * 2);

2 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...