<pre>
Let E(m,n) be this number, and let (x)C(y) = x====/(y! (x-y)!).  A model
====
for this problem is the following nxm grid:

     ^         B---+---+---+ ... +---+---+---+ (m,0)
     ||         ||   ||   ||   ||     ||   ||   ||   ||
     N         +---+---+---+ ... +---+---+---+ (m,1)
<--W + E-->    :   :   :   :     :   :   :   :
     S         +---+---+---+ ... +---+---+---+ (m,n-1)
     ||         ||   ||   ||   ||     ||   ||   ||   ||
     v         +---+---+---+ ... +---+---+---E (m,n)

where each + represents a traffic light.  We can consider each
traffic light to be a direction pointer, with an equal chance of
pointing either east or south.

IMHO, the best way to approach this problem is to ask:  what is the
probability that edge-light (x,y) will be the first red edge-light
that the pedestrian encounters?  This is easy to answer; since the
only way to reach (x,y) is by going south x times and east y times,
in any order, we see that there are (x+y)C(x) possible paths from
(0,0) to (x,y).  Since each of these has probability (1/2)^(x+y+1)
of occuring, we see that the the probability we are looking for is
(1/2)^(x+y+1)*(x+y)C(x).  Multiplying this by the expected number
of red lights that will be encountered from that point, (n-k+1)/2,
we see that

            m-1
           -----
           
E(m,n) =    >    ( 1/2 )^(n+k+1) ''' (n+k)C(n) ''' (m-k+1)/2
           /
           -----
            k=

            n-1
           -----
           
      +     >    ( 1/2 )^(m+k+1) ''' (m+k)C(m) ''' (n-k+1)/2 .
           /
           -----
            k=


Are we done?  No====  Putting on our Captain Clever Cap, we define
====

            n-1
           -----
           
f(m,n) =    >    ( 1/2 )^k ''' (m+k)C(m) ''' k
           /
           -----
            k=

and

            n-1
           -----
           
g(m,n) =    >    ( 1/2 )^k * (m+k)C(m) .
           /
           -----
            k=

Now, we know that

             n
           -----
           
f(m,n)/2 =  >    ( 1/2 )^k ''' (m+k-1)C(m) ''' (k-1)
           /
           -----
            k=1

and since f(m,n)/2 = f(m,n) - f(m,n)/2, we get that

            n-1
           -----
           
f(m,n)/2 =  >    ( 1/2 )^k ''' ( (m+k)C(m) ''' k - (m+k-1)C(m) * (k-1) )
           /
           -----
            k=1

- (1/2)^n ''' (m+n-1)C(m) ''' (n-1)

            n-2
           -----
           
 =          >    ( 1/2 )^(k+1) ''' (m+k)C(m) ''' (m+1)
           /
           -----
            k=

- (1/2)^n ''' (m+n-1)C(m) ''' (n-1)

= (m+1)/2 ''' (g(m,n) - (1/2)^(n-1)'''(m+n-1)C(m)) - (1/2)^n'''(m+n-1)C(m)'''(n-1)

therefore

f(m,n) = (m+1) ''' g(m,n) - (n+m) ''' (1/2)^(n-1) * (m+n-1)C(m) .


Now, E(m,n) = (n+1) ''' (1/2)^(m+2) ''' g(m,n) - (1/2)^(m+2) * f(m,n)

+ (m+1) ''' (1/2)^(n+2) ''' g(n,m) - (1/2)^(n+2) * f(n,m)

= (m+n) ''' (1/2)^(n+m+1) ''' (m+n)C(m) + (m-n) ''' (1/2)^(n+2) ''' g(n,m)

+ (n-m) ''' (1/2)^(m+2) ''' g(m,n) .


Setting m=n in this formula, we see that

           E(n,n) = n ''' (1/2)^(2n) ''' (2n)C(n),

and applying Stirling's theorem we get the beautiful asymptotic formula

                  E(n,n) ~ sqrt(n/pi).
</pre>
