recurrence relation for the following? | Muzaffer Kal | 10/23/94 3:05 PM | hi, 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 ? thanks Muzaffer |

recurrence relation for the following? | Richard J. Yanco | 10/23/94 3:15 PM | >suppose there are n '-1' and n '+1'. What is This looks awfully like a homework problem. Rick |

recurrence relation for the following? | Dipankar Gupta | 10/27/94 3:46 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 the An elegant solution due to D. Andr{\'e} (1878) and the more general Regards, |

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 us Let w(n) be the number of unilateral walks of type n. Let us classify these +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 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. 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 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 Rob Johnson |