==> probability/lights.s <==
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=0
n-1
-----
\
+ > ( 1/2 )^(m+k+1) * (m+k)C(m) * (n-k+1)/2 .
/
-----
k=0
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=0
and
n-1
-----
\
g(m,n) = > ( 1/2 )^k * (m+k)C(m) .
/
-----
k=0
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=0
- (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).