>suppose there are n '-1' and n '+1'. What is
>the recurrence relation for the permutations
>where all the subtotals beginning from the
>left is non-negative ?
Let us call an arrangement of n '+1's and n '-1's a walk of type n. Let us
also call a walk that has no negative partial sum a unilateral walk.
Let w(n) be the number of unilateral walks of type n. Let us classify these
walks by the type of their smallest initial subwalk. Those whose smallest
initial subwalk is of type k look like this:
+1<a unilateral walk of type k-1>-1<a unilateral walk of type n-k>
By considering all possible types of initial subwalk, we get the following
recusive relation:
w(n) = w(0)w(n-1) + w(1)w(n-2) + w(2)w(n-3) + ... + w(n-1)w(0) [1]
with the initial condition that w(0) = 1.
Now that we have the recursive relation, let's try to find a closed form.
The best way is to look at the generating function:
f(x) = w(0) + w(1)x + w(2)x^2 + w(3)x^3 + ... [2]
The recursive relation [1] gives f(x) = 1 + xf(x)^2. Solving this with the
quadratic formula gives f(x) = (1 - sqrt(1-4x))/(2x). We can use the binomial
theorem to get the power series for sqrt(1-4x), subtract that from 1, and
divide by 2x. This gives
f(x) = 1 + x + 2x^2 + 5x^3 + 14x^4 + ... + C(2n,n)/(n+1) x^n + ... [3]
And equating the coefficients of [2] and [3] we get w(n) = C(2n,n)/(n+1).
This is pretty interesting given that the total number of walks of type n is
C(2n,n). That means that given a random walk of type n, the probability of
getting a unilateral walk is 1/(n+1).
A Generalization
----------------
Let us generalize the idea of a unilateral walk to include walks where
the sum is a non-negative integer s, not necessarily 0. That is, a
sum of s+n '+1's and n '-1's where no partial sum is negative. Call
such a unilateral walk of length s+2n that sums to s, type (s,n).
Let w(s,n) be the number of unilateral walks of type (s,n). Let us
classify these walks by the first time the partial sum returns to 0.
When s > 0, a walk whose partial sum never returns to 0 looks like
+1<a walk of type (s-1,n)>
Thus, the number of walks whose partial sum never returns to 0 is
w(s-1,n).
When s = 0, the only walk whose sum never returns to 0 is the empty
walk. Thus, the number of walks whose partial sum never returns to 0
is 1 if n = 0, and 0 if n > 0. We can simplify formulas by defining
w(-1,n) = 1 if n = 0 [4a]
= 0 if n > 0 [4b]
A walk whose partial sum returns first to 0 at step 2k looks like
+1<a walk of type (0,k-1)>-1<a walk of type (s,n-k)>
Thus, the number of walks whose partial sum returns first to 0 at step
2k is w(0,k-1) w(s,n-k).
Putting all this together, we get the recursion
n
---
w(s,n) = w(s-1,n) + > w(0,k-1) w(s,n-k) [5]
---
k=1
Define the generating function for w by
oo
--- n
f(s,x) = > w(s,n) x [6]
---
n=0
Using [4] and [6], we get
f(-1,x) = 1 [7]
Combining [5] and [6], we have
f(s,x) = f(s-1,x) + x f(0,x) f(s,x) [8a]
f(s,x) (1 - x f(0,x)) = f(s-1,x) [8b]
Setting s = 0 in [8] and applying [7], we arrive at
2
x f(0,x) - f(0,x) + 1 = 0 [9]
Solve [9] for f(0,x):
1 - sqrt(1-4x)
f(0,x) = --------------
2x
oo
--- C(2n,n) n
= > ------- x [10]
--- n+1
n=0
Equating coefficients in [10], we get the earlier result
C(2n,n)
w(0,n) = ------- [11]
n+1
Equation [9] says that f(0,x) (1 - x f(0,x)) = 1. This and [8] lets
us solve for f(s,x) in terms of f(s-1,x) and f(0,x):
f(s-1,x)
f(s,x) = ------------
1 - x f(0,x)
= f(s-1,x) f(0,x) [12]
Recursion [12] leads to the conclusion that
s+1
f(s,x) = f(0,x) [13]
Equations [9] and [13] say that
x f(s+2,x) = f(s+1,x) - f(s,x) [14]
Applying [6], equation [14] becomes
oo oo
--- n+1 --- n
> w(s+2,n) x = > (w(s+1,n) - w(s,n)) x [15]
--- ---
n=0 n=0
Equation [15] leads to the following double recursion on w,
w(s+2,n-1) = w(s+1,n) - w(s,n) [16]
Since w(s,0) is the number of walks with s '+1's and 0 '-1's, we have
w(s,0) = 1 [17]
Recursion [16], along with boundary conditions [11] and [17], is
sufficient to compute w(s,n) for all s,n >= 0.
Theorem
-------
For s,n >= 0,
s+1
w(s,n) = ----- C(2n+s,n) [18]
n+s+1
Proof
-----
For s = 0, [18] becomes [11]. For n = 0, [18] becomes [17]. Now we
must show that [18] satisfies [16]:
w(s+2,n-1)
= w(s+1,n) - w(s,n)
s+2 s+1
= ----- C(2n+s+1,n) - ----- C(2n+s,n)
n+s+2 n+s+1
s+2 (2n+s+1)(2n+s)! s+1 (n+s+2)(2n+s)!
= ----- --------------- - ----- --------------
n+s+2 (n+s+1)! n! n+s+2 (n+s+1)! n!
(2n+s)!
= n(s+3) -----------
(n+s+2)! n!
s+3 (2n+s)!
= ----- ---------------
n+s+2 (n+s+1)! (n-1)!
s+3
= ----- C(2n+s,n-1)
n+s+2
QED
Since the total number of walks of type (s,n) is C(2n+s,n), the
probability of a unilateral walk of type (s,n) is (s+1)/(n+s+1).