## recurrence relation for the following?

Showing 1-4 of 4 messages
 recurrence relation for the following? Muzaffer Kal 10/23/94 2:58 PM hi,suppose there are n '-1' and n '+1'. What isthe recurrence relation for the permutationswhere all the subtotals beginning from theleft is non-negative ?thanksMuzaffer recurrence relation for the following? Richard J. Yanco 10/23/94 3:10 PM >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 ?This looks awfully like a homework problem.Rick recurrence relation for the following? Dipankar Gupta 10/27/94 3:36 AM MK> suppose there are n '-1' and n '+1'. What is MK> the recurrence relation for the permutations MK> where all the subtotals beginning from the MK> left is non-negative ?Hint: Split the sequence at the first point (from the left) where thepartial sum goes to 0 to obtain a recurrence.An elegant solution due to D. Andr{\'e} (1878) and the more general``ballot'' problem are discussed in the solution to problem 2.2.1-4and the sections 2.3.4.4 and 2.3.4.6 in Knuth vol I. Unfortunately,this appears to have been omitted from the concrete maths book.Regards,--Dipankar--------------------------------------------------------------  Dipankar Gupta, Hewlett-Packard Laboratories, Bristol UK-------------------------------------------------------------- recurrence relation for the following? Robert Johnson 11/5/94 5:48 AM >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 usalso 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 thesewalks by the type of their smallest initial subwalk.  Those whose smallestinitial subwalk is of type k look like this:   +1-1By considering all possible types of initial subwalk, we get the followingrecusive 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 thequadratic formula gives f(x) = (1 - sqrt(1-4x))/(2x).  We can use the binomialtheorem to get the power series for sqrt(1-4x), subtract that from 1, anddivide 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 isC(2n,n).  That means that given a random walk of type n, the probability ofgetting a unilateral walk is 1/(n+1).Rob JohnsonApple Computer, Inc.