A permutation of has bounded displacement if some nonnegative integer satisfies
The same bound works at every position; each individual difference being finite would impose no restriction. Displacement zero gives the identity permutation.
For displacement at most one, every permutation is a collection of disjoint adjacent transpositions and fixed points. To prove this, inspect the smallest position not yet fixed or paired. Its image must be , and the only still available possible preimage of is . Thus these two positions are exchanged; continue inductively. Conversely, any such disjoint collection satisfies the bound. Independently choosing whether to exchange each pair gives an uncountable set of examples.
The inverse function has the same displacement bound: if , then . If two permutations have bounds , their function composition has bound by the triangle inequality. Thus bounded-displacement permutations form a group under function composition.

Articles by others on the same topic (0)

There are currently no matching articles.