<>
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 number of decorated permutations of size $n$ is [A000522](http://oeis.org/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](https://arxiv.org/abs/2001.00280)
[FHL20] Shishuo Fu, Guo-Niu Han, Zhicong Lin, k-arrangements, statistics and patterns [arXiv:2005.06354](https://arxiv.org/abs/2005.06354)
[La15] T. Lam, *Totally Nonnegative Grassmannian and Grassmannian Polytopes*. 1 June 2015. [arxiv:1506.00603](https://arxiv.org/abs/1506.00603)
[Po06] A. Postnikov, *Total positivity, Grassmannians, and networks.* 27 Sep 2006. [arxiv:0609764](https://arxiv.org/abs/math/0609764)
Sage examples
=============
{{{#!sagecell
def statistic(pi):
return sum(1 for a in pi if a < 0)
def DecoratedPermutations(n):
for sigma in Permutations(n):
F = sigma.fixed_points()
for X in Subsets(F):
tau = list(sigma)
for i in X:
tau[i-1] = -tau[i-1]
yield SignedPermutations(n)(tau)
def element_repr(pi):
pi = list(pi)
for i,a in enumerate(pi):
if a == i+1:
pi[i] = 0
elif -a == i+1:
pi[i] = -1
return str(pi).replace(" ","").replace("0","+").replace("-1","-")
for n in [1..4]:
for pi in DecoratedPermutations(n):
print(element_repr(pi))
}}}
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.