[seqfan] Re: Permutations Of +- Integers

[franktaw at netscape.net]

Sorry, there's a mistake here.  At the last step, we can to n-2 by 
getting to |Q(m-1)| = 1, and r(m) = n-1.  And in fact, the permutation 
4,1,2,3 gets Q values of 0,4,3,1,-2 when we do this.  Of course, this 
isn't a counterexample to the claim; we can instead get Q values 
0,4,3,1,4, which duplicates the 4.  I'm pretty sure the result is 
correct; I'll see if I can patch the proof.

Franklin T. Adams-Watters


-----Original Message-----
From: 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?


_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/