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, 1, 1, 3, 10, 52, 459, 1271, 10094, 63133, 547565, 4431517, 42046100, 400782747, 8711476734

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_{n-1}(1) = 0.

Comments from Olivier Gérard, Jun 04 2024 (Start)

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, n-1, n-2, ..., 1 (End).

Links

Table of n, a(n) for n=1..16.

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)
print([a(n) for n in range(1, 10)]) # Michael S. Branicky, May 30 2024

Crossrefs

Cf. A001792, A131502.

Sequence in context: A363209 A052446 A362062 * A290489 A002873 A309910

Adjacent sequences: A373281 A373282 A373283 * A373285 A373286 A373287

Keyword

nonn,nice,hard,more

Author

Bryle Morga, May 30 2024

Extensions

a(12)-a(13) from Michael S. Branicky, May 30 2024

a(14)-a(16) from Bert Dobbelaere, Jun 09 2024

Status

approved