>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).