This site is supported by donations to The OEIS Foundation.

# Compressed signature permutations

This article needs more **work**.

Please help by expanding it!

## Definition

*Compact (or compressed) signature permutation* is an integer sequence which
can be formed from a particular (ordinary) signature permutation recording a particular
bijection of combinatorial structures (with counting function
giving the number of structures of size ) as ordered by
the total order ,
provided that the following conditions hold:

- the set of combinatorial structures allows a natural embedding of smaller structures amongst one item (vertex, point, element, etc.) larger structures (e.g. the six permutations of three elements can be embedded into the set of 24 permutations of four elements by just adding a fixed fourth element to the end of each)

- for each set of size structures, the selected ordering orders the said structures by their size, and places all those structures that contain a structure of size embedded in such a manner,
**before**all other structures of size , in the**same order**as they occur in the previous subsequence of structures

- the bijection acting on those structures preserves their size and keeps each such embedded subset closed, and respects the original ordering of the smaller structures embedded in the larger structures.

If the above conditions hold, the signature permutation can be "compressed" by discarding from each subsequence of length the first integers, and then "normalizing" (XXX - Elaborate!) the remaining integers on such way that a bijection of natural numbers result. This procedure removes only redundant information, and from each compressed signature permutation, a corresponding ordinary, uncompressed permutation can be recovered.

Remark. The set of bijections which allow compact signature presentation form
a genuine subgroup of all bijections of the said combinatorial structures.
Provided the sequence enumerating such combinatorial structures is
genuinely monotone (growing), then the number of equivalence classes to
which any such (compacting/compressible/telescoping) bijection partitions
the said structures grows monotonically as well.

### Compressed signature permutations of Catalan bijections

For Catalan bijections the
criteria for compressibility is simple.
The bijection has a compressed signature permutation
(when using the standard ordering of Catalan structures)
if and only if it satisfies
**Failed to parse (syntax error): {\displaystyle (g~(cons~’(~)~s))~=~(cons~’(~)~(g~s))}**
.
Here it is assumed that bijection has been
defined to act on S-expressions. In terms of
totally balanced sequences, the operation **Failed to parse (syntax error): {\displaystyle (cons~’(~)~s)}**
corresponds to concatenating binary digits to
the front of binary representation.

For example, A038776 is a compressed signature permutation of Meeussen's depth-first->breadth-first bijection of planar binary trees, whose ordinary Catalan signature permutation is A057117.

### Compressed signature permutations of bijections on finitary permutations

For bijections of finitary permutations, when using reverse colexicographic order, the criteria for the existence of compact signature permutation is that bijection (acting on finitary permutations of any size ) satisfies the following condition .

For example, A056019 gives a compressed signature permutation for the operation of taking inverse of a finitary permutation. It satisfies the above condition because inverting a permutation doesn't affect its fixed elements.