I like solving algorithmic problems on combinatorics. Unfortunately it's not always the case that I can solve them myself. So here's the problem.
How many permutations of $1, \dots, n$ exist for which the differences between neighboring elements constitute a permutation of $1, \dots, n-1$?
For example, $(3,1,2)$ has neighbor-differences $(2,1)$ and that's a permutation of $1,2$.
I just don't see how to tackle this. $n$ can be as large as 30 so brute force solution considering all possible $n!$ permutations is not feasible.
I'm currently trying to find some recurrence relation but haven't find it yet. My idea is to consider positions of 1 in a permutation. Then we can subtract one from the remaining elements and consider them as permutation of $1, \dots, n$. But I don't see how to add differences here.