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.

Let $J$ be a permutation of the first $N$ integers (1, 2, ..., $N$), so that the permuted sequence reads $(J(1),J(2),...,J(N))$. The function $J$ must of course be a bijection. Additionally, suppose that $J$ is its own inverse: $J(J(i))=i$, and that $J$ has, at most, one fixed point. That is, there is either none or one value of $i$ such that $J(i)=i$. It isn't hard to see that there is a single fixed point if and only if $N$ is odd, and there is none if $N$ is even.

A permutation $J$ with the above properties establishes a pairing of the integers from 1 to $N$, where $i$ is paired with $J(i)$ (except if $N$ is odd, in which case the fixed point is not paired).

Is there a name for this type of permutation?

share|improve this question
    
Since "pairing" could also apply to any permutation which is the product of disjoint swaps, but where the number of fixed points is not 0 or 1, perhaps "complete pairing" would be better? Or even "matching", since the swaps define a bipartite graph that is as close to a matching as possible? –  András Salamon Apr 25 '13 at 22:52
    
@AndrásSalamon I like all the terms you suggest. "Matching" is particularly good. But it would be nice if there was already an established name in the literature. –  becko Apr 25 '13 at 23:59
add comment

1 Answer

I would call this a fixed-point free involution, respectively involution with one fixed point.

After some searching I found the term "maximum matching of the complete graph on $N$ points" that unambiguously describes the set of edges that bijectively corresponds to a permutation of this type (you could also say "maximal" instead of "maximum", as this is the same thing for a complete graph). This avoids the even/odd dichotomy, but has the drawback of only somewhat indirectly describing a set of permutations.

share|improve this answer
    
-1 That's two names, one for $N$ even (fixed-point free involution) and one for $N$ odd (involution with one fixe poitn). I think "pairing" is more appropriate and descriptive, but I suppose no one uses it. –  becko Apr 25 '13 at 22:03
    
The term "pairing" has a connotation with bilinear forms, which is why I would not advise using it. –  Marc van Leeuwen Apr 26 '13 at 9:32
add comment

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.