

A373284


Number of permutations of {1, 2, 3, ..., n} that result in a final value of 0 by repeatedly iterating the process of "subtracting if the next item is greater or equal, otherwise adding" until there's only one number left.


0



0, 0, 1, 1, 3, 10, 52, 459, 1271, 10094, 63133, 547565, 4431517, 42046100, 400782747, 8711476734
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

Let x_0 be a permutation on {1, 2, 3, ..., n}. Let x_k(i) be a function defined when 0 < i <= n  k that is constructed as follows:
If x_k(i + 1) >= x_k(i), then x_{k+1}(i) = x_k(i + 1)  x_k(i).
Otherwise, x_{k+1}(i) = x_k(i + 1) + x_k(i).
a(n) is the number of permutations x_0 that satisfy x_{n1}(1) = 0.
The sequence of number of different values is:
1, 2, 4, 9, 32, 75, 179, 230, 933
The sequence of maxima of this process is A001792:
1, 3, 8, 20, 48, 112, 256, 576, 1280
Indeed, the maxima is attained only once and always for the last permutation in lexicographic order : n, n1, n2, ..., 1 (End).


LINKS



EXAMPLE

For n=5, one of the a(5) = 3 solutions is (1, 4, 5, 2, 3), whose trajectory to 0 is
1 4 5 2 3
3 1 7 1
4 6 8
2 2
0


PROG

(Python)
from itertools import permutations
def f(t):
if len(t) == 1: return t[0]
return f([t[i]+t[i+1] if t[i+1]<t[i] else t[i+1]t[i] for i in range(len(t)1)])
def a(n): return sum(1 for p in permutations(range(1, n+1)) if f(p) == 0)


CROSSREFS



KEYWORD

nonn,nice,hard,more


AUTHOR



EXTENSIONS



STATUS

approved



