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?

$\endgroup$
  • $\begingroup$ You can try to characterize all the graceful permutations and their "graces", and then deduce your required theorem. The easiest way would be to list them and see if you can find some pattern. $\endgroup$ – Yuval Filmus May 31 '11 at 16:36
  • $\begingroup$ thanks @Yuval. I was just wondering about any previous results or trivial facts, before looking at the problem more seriously ;) $\endgroup$ – A. De Luca May 31 '11 at 16:41
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice proof, thank you very much! I guess that's a good reason why nobody ever wrote about doubly graceful permutations ;) $\endgroup$ – A. De Luca May 31 '11 at 17:47
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Vote for Yuval's answer! He actually solves the problem instead of just idly speculating. $\endgroup$ – Michael Lugo May 31 '11 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.