Queries for Decorated permutations: search statistic / browse statistics / browse maps from / browse maps to
Definition & Example
-
A decorated permutation of size $n$ is a permutation of $\{1,\dots,n\}$ for which each fixed point is either decorated with a '$+$' or with a '$-$'.
-
We write a decorated permutation in one-line notation as $\tau = [\tau_1,\dots,\tau_n]$ where fixed points $\tau_i = i$ come in two colors '$+$' and '$-$'.
| the 16 Decorated permutations of size 3 | |||||||||||||||
| [+,+,+] | [-,+,+] | [+,-,+] | [+,+,-] | [-,-,+] | [-,+,-] | [+,-,-] | [-,-,-] | ||||||||
| [+,3,2] | [-,3,2] | [2,1,+] | [2,1,-] | [2,3,1] | [3,1,2] | [3,+,1] | [3,-,1] | ||||||||
- The number of decorated permutations of size $n$ is A000522 and given by $\sum_{k = 0}^n n!/k!\ $.
Properties
- Decorated permutations are in bijection with many other objects, such as total subset permutations, Grassmannian necklaces, positroid, Le-diagrams, and bounded affine permutations
- Every decorated permutation can be decomposed into a set of decorated fixed points and a derangement.
Additional information
- In [BS20, FHL20], the authors consider $k$-arrangements. These are permutations with fixed points being colored in $k$ colors. In particular, their notion of $2$-arrangements coincides with decorated permutations.
References
[BS20] N. Blitvić and E. Steingrímsson, Permutations, Moments, Measures, arXiv:2001.00280
[FHL20] Shishuo Fu, Guo-Niu Han, Zhicong Lin, k-arrangements, statistics and patterns arXiv:2005.06354
[La15] T. Lam, Totally Nonnegative Grassmannian and Grassmannian Polytopes. 1 June 2015. arxiv:1506.00603
[Po06] A. Postnikov, Total positivity, Grassmannians, and networks. 27 Sep 2006. arxiv:0609764
Sage examples
Technical information for database usage
- A decorated permutation is uniquely represented as a list.
- Decorated permutations are graded by their size.
- The database contains all decorated permutations of size at most 6.