[seqfan] Re: Permutations Of +- Integers

[franktaw at netscape.net]

It's a(1) = 1, a(2) = 1, and the rest zeros.

Consider the assignment of signs which minimizes the absolute value of 
the sum at each point (if two values with the same absolute value are 
possible, we don't care which is taken).  The absolute sum must then be 
0 <= |Q(m)| <= n; this can fail to duplicate only if it takes on all 
n+1 possible values.  But |Q(m)| = n with this assignment is possible 
only when Q(m-1) = 0 and r(m) = n.  If m != 1, this is a duplication of 
the value 0, so we must have r(1) = n.  Now the only ways to get |Q(m)| 
= n-1 is for r(2) = 1, or some r(m) = n-1 and Q(m-1) = 0; but the 
latter again duplicates the 0 sum.  Repeating this argument, we can't 
set r(2) = 1 to immediately get |Q(2)| = n-2, because 1 has already 
been used.  So the n-2 must follow a 0, and we have a duplication.

Franklin T. Adams-Watters


-----Original Message-----
From: Leroy Quet <q1qq2qqq3qqqq at yahoo.com>

This question is inspired by the game at:
http://gamesconceived.blogspot.com/2009/04/permutations-of-integers.html

Take the permutation, R= (r(1),r(2),r(3),...,r(n)), of (1,2,3,...,n). 
Then give
a sign (+ or -) to each integer of the permutation to get 
(q(1),q(2),q(3),...q(n)).
(In other words, each q(m) = + or - r(m).)
Let
Q(m) = sum{k=1 to m} q(k), for each m where 0 <= m <= n.
(Q(0) = 0.)

How many permutations R are such that, no matter how the signs are 
assigned to
the integers of the permutation, then no |Q(m)| equals any |Q(j)|, for 
each j
and m where 0 <= j < m <= n?

Is the sequence of the number of such permutations of (1,2,3,..,n) 
easily
derived, or even trivially derived?