Does a closed form formula f(n) exist for the two rightmost columns? The two question marks are meant to be 0.
The diagram is a summary of the numerical results from original question: Permutations to satisfy a challenging restriction
The question and the main results from previous post are summarized below. Attempts to find a closed form solution were elusive. Many thanks for users LaBird and JLee for generating the data and some insights.
Question
Cards {1,2,3,….n} are stacked in that order from top. We then rearrange the cards.
Define distance between two cards to be the number of cards between them; cards whose index differs by 1 are neighbours and the distance between them is 0.
How many card rearrangements (permutations) satisfy the following?
I) The sum of distances between any card and its neighbour/s (call that sum $S_n$ for card $n$), is distinct for all $n$ cards.
II) $S_n$ is distinct for all $n$ and only take on values smaller than $n$.
$Example$
Say we have cards {1,2,3} stacked in that order from top. Rearrange cards into order (2,3,1} from top. Then:
Card 1 is distance 1 from its former neighbour card 2. $S_1$=1
Card 2 is distance 1 to card 1 but distance 0 to card 3. $S_2$=1+0=1
Card 3 is distance 0 from card 2. $S_3$=0
Hence this rearrangement does not satisfy the conditions in the question, as both $S_1$ and $S_2$ are 1.
Here is a summary of important results and insights.
The number of permutations satisfying either condition/s must be a multiple of 4 for any n. For any permutation that satisfies either condition, say $(X_1, X_2, X_3, \dots, X_{n-2}, X_{n-1}, X_n)$, then $(X_n, X_{n-1}, X_{n-2}, \dots, X_3, X_2, X_1)$, $(n+1-X_1, n+1-X_2, n+1-X_3, \dots, n+1-X_{n-2}, n+1-X_{n-1}, n+1-X_n)$ $(n+1-X_n, n+1-X_{n-1}, n+1-X_{n-2}, \dots, n+1-X_3, n+1-X_2, n+1-X_1)$
are all distinct solutions to that condition. This result was proven in LaBird’s contribution in previous post.To satisfy condition 2, n must be of form 4n or 4n+1. This explains some strange behavior of vanishing solutions for n=10 despite very large number of solutions for n=9. This is again proven in the previous post.
The total distance between any card and its neighbor/s can take on any integer value from 0 to 2n-5 under condition 1. Under condition 2 every value from 0 to n-1 must be taken exactly once.
Title Picture
The picture was generated by JLee’s C sharp program and checked by LaBird’s program (thanks so much!). The 3 rightmost columns describe the total number of permutations of n cards excluding the original permutation (n!-1) and the respective number of permutations satisfying conditions 1 and 2. The ‘pyramid’ in the middle partitions the permutations satisfying condition 1 by the index of the top card. We thought that might reveal some insights.
All contributions are welcome. Some other directions of attack thought as suitable include generation functions and permutation group theory.