Signature permutations

This article needs more work.

Please help by expanding it!

A signature permutation is an integer sequence which records in OEIS a particular bijection of an enumerable combinatorial structure. Formally, if $\scriptstyle S$ is the infinite, but enumerable set of a particular combinatorial structure, and $\scriptstyle b$ is a bijection on that set, i.e. $\scriptstyle b\,:\,S\,\rightarrow \,S\,$, then its associated signature permutation $\scriptstyle {\rm {SP}}_{b}\,$ is the function

${\rm {SP}}_{b}(n)={\rm {Grank}}(b\,({\rm {Gunrank}}(n)))\,$

where Grank and Gunrank are global ranking and unranking functions for the said combinatorial structures.

To be useful to the other users of the OEIS, the submitter should choose a ranking scheme (that is, the function Grank and its inverse Gunrank) so that they reflect the most natural, or at least a commonly agreed total ordering by which the set of such combinatorial structures can be unambiguously mapped to a set of natural numbers $\scriptstyle \mathbb {N} \,$ (with $0$ either included or not, depending on whether it makes sense with that particular combinatorial structure).

This mapping then works as a group isomorphism between the group of bijections acting on the said combinatorial structures, and a subgroup of $\scriptstyle S_{\infty }\,$, i.e. symmetric group of an (uncountably) infinite set, the latter group which consists of permutations of natural numbers.

Note that only if we allow arbitrary bijections between any two combinatorial structures (of the said enumerable set), then the isomorphism maps onto whole $\scriptstyle S_{\infty }\,$. However, usually we are interested about only such bijections that somehow "make sense" with chosen combinatorial structures, that is preserve some structural property of them, or at least their size, if nothing else. In that case, the corresponding permutations of natural numbers usually have specific restrictions on their cycle structure, for example, only finite cycles occur in them.

Signature permutations of Catalan bijections

In OEIS, the majority of submitted signature permutations for Catalan bijections are based on the standard ordering of Catalan structures. As we have chosen to concentrate only on those Catalan bijections that preserve the size of Catalan structures, it implies that the cycle structure of the corresponding signature permutations (i.e. permutations of non-negative integers) is constrained in such a way, that

• each cycle is finite
• and furthermore, no cycle crosses the boundaries set by the sequences A014137 and A014138.

The lexicographically first signature permutation in OEIS is A001477 which has a role of an identity permutation, while the lexicographically last signature permutation of Catalan bijections is A130918. To count the number of fixed points, distinct orbits and the maximum orbit size when the said Catalan bijection acts on the Catalan structure of size $n$, it is equal to count the number of fixed points, distinct cycles and the maximum cycle size in range [A014137(n-1)..A014138(n-1)] of the corresponding signature permutation. (Here we use the older indexing for A014138, which didn't include the initial 0, but started as A014138(0)=1, A014138(1)=3, etc.)

Signature permutations for bijections of compositions

Integer compositions (i.e. ordered integer partitions) can be mapped 1-to-1 to non-negative integers via binary run-length encoding (and then converting the produced binary number to decimal). (XXX -- Needs explanation!) The sequence A056539 is a signature permutation for involution that reverses the list of composants when the said mapping is used. Cf. A066099 for other orderings of compositions, from which one can create similar signature permutations.

Signature permutations for bijections of partitions

As far as I know, there are not that many natural bijective operations on partitions, apart from the trivial identity mapping and the self-inverse conjugation operation. The sequence A122111 is signature permutation for partition conjugation based on Marc LeBrun's original "crazy order" mapping and A129594 is based on mapping of partitions to natural numbers via compositions encoded as binary runs. By using other orderings of partitions one can create further signature permutations for partition conjugation.

Signature permutations for bijections on finitary permutations

There are several natural orderings for all finitary permutations (i.e. of all permutations of natural numbers {(0), 1, 2, 3, ... } with only finite number of elements moved). See e.g. A195663 and its compact representation A055089. For a simple (self-inverse) bijection of permutations, one can consider the taking of the inverse permutation. For a more complex example, there is for example the Foata-transform. Both of these bijections (the latter in a slightly modified form) are "telescoping" or "compacting" in a sense that they map each permutation to a permutation of the same "size", which thus allows to form a compact signature permutation. These are given respectively by the sequences A056019 and A065181-A065182.

Alternatively, finitary permutations can be ordered as in A060117 (which is slightly more efficient for computers) in which case the signature permutation for taking inverses is A060125, and A065183-A065184 are the signature permutations for a modified Foata transform.

Moreover, one could consider also a "cross-indexing maps" between different orderings as signature-permutations of some exotic bijections on finitary permutations as ordered by either ordering. See e.g. A060119-A060126.

Signature permutations for bijections on rational numbers

There are several orderings of rational numbers and any of them could be used as a map for constructing a signature permutation for a particular permutation of the rational numbers. The Stern-Brocot tree (either in its standard form, covering only strictly positive rationals, or the extended version, which covers the whole $\scriptstyle \mathbb {Q} \,$) gives one of the most elegant ways of mapping between the set of rational numbers and the set of natural numbers.

For example, A057114 and A057115 are signature permutations for bijections of which the other adds one to a rational number, and the other decrements it by one, while A065249 and A065250 are signature permutations for bijections of which the other divides a rational number by two, and the other multiplies it by two.

Signature permutations for bijections of CGT-trees

The games as studied by Combinatorial Game Theory can be conveniently presented as rooted trees where each vertex contains a left hand set of descendants and a right hand set of descendants (of further such trees), where either set can also be empty set. These trees are mapped bijectively to non-negative integers with a scheme explained in A106486. The sequence A106485 is a signature permutation for the bijection that reflects such trees (when mapped with such scheme), in such a way, that all left options are changed to right options, and vice versa, at every level of the tree, thus their combinatorial game theoretical value is negated. The sequence A057300 can be considered as a signature permutation of a "shallow" version of that bijection, which just swaps the left and right options at the top vertex of the game tree, but does not reflect the sub-trees themselves.

Authorship

The first version of this page was written by Antti Karttunen Jul 29, 2012.
Copy edited (presentation) by Alonso del Arte, Daniel Forgues, et al, Aug 07-, 2012.

Cite this page as

A. Karttunen & <any other authors>, <a href="http://oeis.org/wiki/Signature_permutations">Signature permutations</a>, OEIS Wiki.