Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Yuval Filmus May 31 '11 at 16:36
    
thanks @Yuval. I was just wondering about any previous results or trivial facts, before looking at the problem more seriously ;) –  A. De Luca May 31 '11 at 16:41

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
Nice proof, thank you very much! I guess that's a good reason why nobody ever wrote about doubly graceful permutations ;) –  A. De Luca May 31 '11 at 17:47

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.

share|improve this answer
    
Vote for Yuval's answer! He actually solves the problem instead of just idly speculating. –  Michael Lugo May 31 '11 at 17:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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