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 $g$ of combinatorial structures $S$ (with counting function $C(n)$ giving the number of structures of size $n$) as ordered by the total order $\scriptstyle O$, provided that the following conditions hold:

• the set of combinatorial structures $S$ 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 $n+1$ size structures, the selected ordering $\scriptstyle O$ orders the said structures by their size, and places all those structures that contain a structure of size $n$ embedded in such a manner, before all other structures of size $n+1$, in the same order as they occur in the previous subsequence of $n$ structures

• the bijection $g$ 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 $C(n+1)$ the first $C(n)$ 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 $g$ 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 $g$ 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 $10$ 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 $g$ (acting on finitary permutations $p$ of any size $n$) satisfies the following condition $(g~(append~a~fixed~element~n+1~to~the~end~of~p))~=~(append~a~fixed~element~n+1~to~the~end~of~(g~p))$.

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.