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

Author

Bryle Morga, May 30 2024

Keywords

• nonn
• nice
• hard
• more

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.

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).

Examples

			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
		

Crossrefs

Cf. A001792, A131502.

Programs

Mathematica

Block[{fn, cperm, rs}, fn = Function[ls, First @ NestWhile[ MapThread[If[#2 < #1, #1 + #2, #2 - #1] &, {Most@#, Rest@#}] &, ls, Length@# > 1 &]]; cperm = Function[n, Total[ ParallelMap[ Boole[fn@# == 0] &, Permutations @ Range @ n]]]; rs = Table[cperm @ n, {n, 10}]; rs] (* Mikk Heidemaa, Mar 14 2025. Based on the Python code below *)

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]Michael S. Branicky, 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