8
$\begingroup$

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?

  • 0
    tha$n$ks @Yuval. I was just wondering about any previous results or trivial facts, before looking at the problem more seriously ;)2011-05-31

2 Answers 2

7

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.

  • 0
    Nice proof, thank you very much! I guess that's a good reason why nobody ever wrote about doubly graceful permutations ;)2011-05-31
5

The number of graceful permutations of $n$ is $\Omega(2.37^n)$, according to this note by Adamaszek; the speculation appears to be that the number of graceful permutations of $n$ actually grows exponentially, although it's hard to really be convinced of this by the data (say, from OEIS) alone.

If this is true, then the "probability" that a randomly chosen permutation is graceful is on the order of $f(n)/n!$, where $\lim_{n \to \infty} f(n)^{1/n} = c$ for some constant $c > 2.37$. (Adamaszek seems to believe this constant exists and is between 3 and 4.5.) Among the $f(n)$ graceful permutations of $n$, consider the corresponding permutations $\tau$. Assuming these $\tau$ are in some sense "random", you expect to find $f(n)^2/n!$ graceful permutations among them; this goes to zero very quickly as $n \to \infty$. Therefore one expects any doubly graceful permutations to be small.

Of course this is all heuristic, but it would seem to point towards nonexistence.

  • 0
    Vote for Yuval's answer! He actually solves the problem instead of just idly speculating.2011-05-31