Arranging +1's and -1's?

If you draw a 2D lattice path, it is easy to understand the sequence

you get

01 05 14 28 42 42

01 04 09 14 14 00

01 03 05 05 00 00

01 02 02 00 00 00

01 01 00 00 00 00

00 00 00 00 00 00

the sequence is 1,2,5,14,42, ......

which corresponds to C(2n,n)/(n+1)

ps:

----

It is getting much more difficult to submit an answer compared to working out one, and to edit an ans is pure hell !

pps:

------

Once you work out the totals through the lattice path, you can just treat it as an IQ test sequence, and arrive at some formula. That is what I did, as w/o referring to a source, it seemed simplest.

But this is serious stuff, a well known "Dyck path" and if you want complex and clever ways of arriving at the formula, see

http://en.wikipedia.org/wiki/Catalan_number

ppps:

--------

Surely to give a *proof* here is too lengthy and inconvenient, wiki is giving many such proofs, but you can note without proof that counting upsteps above the diagonal, there is,surprisingly, an equal # of paths with 0 up-steps, 1 up-step, ...... n up-steps. Since the total # of paths is C(2n,n), the favorable paths = C(2n,n)/(n+1)

If n=1, there is 1: 1 -1

If n=2, there are 2:

1 -1 1 -1

1 1 -1 -1

If n = 3, there are 5

1 1 1 -1 -1 -1

1 1 -1 1 -1 -1

1 1 -1 -1 1 -1

1 -1 1 1 -1 -1

1 -1 1 -1 1 -1

For n = 4, there are 14

1 1 1 1 -1 -1 -1 -1

1 1 1 -1 1 -1 -1 -1

1 1 1 -1 -1 1 -1 -1

1 1 1 -1 -1 -1 1 -1

1 1 -1 1 1 -1 -1 -1

1 1 -1 1 -1 1 -1 -1

1 1 -1 1 -1 -1 1 -1

1 1 -1 -1 1 1 -1 -1

1 1 -1 -1 1 -1 1 -1

1 -1 1 1 1 -1 -1 -1

1 -1 1 1 -1 1 -1 -1

1 -1 1 1 -1 -1 1 -1

1 -1 1 -1 1 1 -1 -1

1 -1 1 -1 1 -1 1 -1

Call f(n) the number for n 1's and -1's

Given the results for n, how do you get the number for n+1? There are two differnt ways you can generate the strings for n+2:

1. Put 1 -1 at the beginning. That gives you f(n) strings.

2. Put 1 at the beginning, and put the -1 anywhere else other than right after it. Unfortunately, it's difficult to count the number of different strings that generates, because there are duplicates fi the string ends in more than one -1. I'll keep working on that.

One way to character the problem is:

What is it the number of random walks of length 2n, starting at the origin, that never go negative.

Interesting problem!

Edit: I found the answer, but not the proof: "Consider all the binomial(2n,n) paths on squared paper that (i) start at (0, 0), (ii) end at (2n, 0) and (iii) at each step, either make a (+1,+1) step or a (+1,-1) step. Then the number of such paths that never go below the x-axis (Dyck paths) is C(n). [Chung-Feller]" at http://oeis.org/A000108 . That's why I calculated the first few values, so I could search the OEIS last night. But this description was a few lines down, and I didn't see it until today, even though I understood the problem as a random walk problem.

For any chosen n we have n +1's and n -1's, hence it is always possible to arrange them in such a manner if and only if in the arrangement, the number of +1's is greater than or equal to the number of -1's, otherwise we have a < 0 arrangement. Since we have n equally many +1's and -1's, there are n! possible arrangements. This is because we want to arrange n elements randomly, still knowing that the number of -1's cannot exceed that of +1's. If not provided the condition >= 0, the number of arrangements would have been (n + n)! = (2n)!.

Your answer is n!.

Looking back, I don't think my answer is correct. I misunderstood the question. But there are some things that must be mentioned further than what you have mentioned. For example, is order important?

draw out an n x n grid.

start in the top left corner. Evert time you get a +1 you move to the right. every time you have a -1 you move down.

you cannot move below the main diagonal or your sum is negative. The number of ways to get to any point = number of ways above + number of ways to the left.

1.1.1.1...1....1.....1

...1.2.3...4....5.....6

......2.5...9..14...20

.........5.14..28...48

.............14.42...90

...................42.132

.........................132

update:

Okay.... lets count the total number of paths removing the restriction that the partial sum must be >=0....

1...1...1...1...1

1...2...3...4...5

1...3...6.10.15

1...4.10.20.35

1...5.15.35.70

The value of m x n th cell is (m-1+n-1)C(n-1)

now, with our constraint... all paths are good except those that cross the main diagonal.

the number before the comma is the number of the good paths, the number after the comma is the number of bad paths

1,0....1,0....1,0....1,0...1,0

0,1....1,1....2,1....3,1...4,1

0,1....0,3....2,4....5,5...9,6

0,1....0,4....0,10..5,15.14,21

0.1....0,5....0,15..0,35.14,56

if n is our column number and m is our row number.... the number of bad paths if n=>m

(n+m-2)C(m-2)

and if n<m

(n+m-2)C(m-1)

the number of good paths =

(n+m-2)C(m-1) - (n+m-2)C(m-2)

and along the main diagonal

(2n-2)C(n-1) - (2n-2)C(n-2)

(2n-2)!/(n-1)!(n-1)! - (2n-2)!/(n-2)!(n)!

(2n-2)!/(n)!(n-1)! = (2n-2)C(n-1) / (n)