On doubly graceful permutations A permutation $\sigma\in\mathfrak S_n$ is _graceful_ if $$\\{|\sigma(i+1)-\sigma(i)| \text{ with } 1\leq i\leq n\\}=\\{1,2,\ldots,n-1\\}$$ (terminology coming from a more general definition in graph theory). From the definition, it follows that if $\sigma$ is graceful and we set $\tau(i)=|\sigma(i+1)-\sigma(i)|$ for $i=1,\ldots,n-1$, then $\tau$ is a permutation (in $\mathfrak S_{n-1}$). This made me wonder about those $\sigma$'s such that $\tau$ is again graceful – I would call them doubly graceful. For instance, this is clearly the case for $\sigma=[1,3,2]$. I ran tests showing there are no doubly graceful permutations for $n=4$ to 9. I could not find anything in the literature and I'm no expert of permutations nor graphs, so... **Question 1:** Are there any doubly graceful permutations for $n>3$? (I hope this is not too trivial) **Question 2:** Has anybody considered this before?

Consider how a graceful permutation in $S_n$ looks. The difference $n-1$ can only be realized by $1,n$ (or its reflection). The difference $n-2$ is then realized either by $n-1,1,n$ or by $1,n,2$. In order to realize $n-3$, we need to extend this to either $2,n-1,1,n$ or $n-1,1,n,3$ or $1,n,2,n-1$ or $n-2,1,n,2$.

Consider now the difference sequence: it is either $n-3,n-2,n-1$ or $n-2,n-1,n-3$ or $n-1,n-2,n-3$ or $n-3,n-1,n-2$. The first and third options have double difference sequence $1,1$, so the corresponding permutation cannot be double graceful. The second and fourth option have $n-1$ next to $n-2$ and $n-3$, so for that permutation to be graceful, either $n-2=1$ or $n-3=1$, i.e. either $n=3$ or $n=4$. The case $n=4$ can be ruled out by brute force.