recurrence relation for the following?

[Muzaffer Kal]

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

[Richard J. Yanco]

>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

[Dipankar Gupta]

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
partial 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-4
and 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
--------------------------------------------------------------

[Robert Johnson]

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

Rob Johnson
Apple Computer, Inc.