# Partitioned Permutations

Partitioned Permutations are used in the context of Free Probability Theory to model higher order freeness and higher order free cumulants, see e.g. [CMS07].

We provide basic functions for working with partitioned permutations. The focus is on factorizing partitioned permutations.

# Basics

Formally, a partitioned permutation $(V, \pi)$ consists of a permutation $\pi$ and a partition $V$ of the set $\{1, ..., n\}$ such that the partition dominates the permutation in the sense that every cycle of $\pi$ is contained in one block of $V$. We call $n$ the length of $(V, \pi)$. Mathematically, another length function is more important. It is given by $|(V, \pi)| := n - ( 2 \cdot \text{number of blocks of } V - \text{number of cycles of } \pi),$ and we call this the adjusted length of $(V, \pi)$. Note that this terminology is not used in the literature.

`PartitionedPermutation`

— Type`PartitionedPermutation`

The type of partitioned permutations. Fieldnames are

- p::PermGroupElem - a permutation
- V::SetPartition - a partition

If the permutation has length `n`

, then the partition must have `n`

upper points and 0 lower points. Further, if `W`

is the partition given by the cycles of `p`

, then `W`

must be dominated by `V`

in the sense that every block of `W`

is contained in one block of `V`

. There is one inner constructer of PartitionedPermutation:

- PartitionedPermutation(p::PermGroupElem, V::Vector{Int}) constructs the partitioned permutation where the partition is given by the vector V.

If the optional flag `check`

is set to `false`

, then the constructor skips the validation of the requirements mentioned above.

**Examples**

```
julia> PartitionedPermutation(perm(symmetric_group(3), [2, 1, 3]), [1, 1, 2])
PartitionedPermutation((1,2), SetPartition([1, 1, 2], Int64[]))
```

This function is part of the experimental code in Oscar. Please read here for more details.

`length`

— Method`length(pp::PartitionedPermutation)`

Return the length of a partitioned permutation, i.e. the size of the underlying set.

**Examples**

```
julia> length(partitioned_permutation(perm(symmetric_group(2), [2, 1]), [1, 1]))
2
```

This function is part of the experimental code in Oscar. Please read here for more details.

`adjusted_length`

— Method`adjusted_length(pp::PartitionedPermutation)`

Return the adjusted length of a partitioned permutation as described in [CMS07] as `|(V, pi)|`

for a partition `V`

and a permutation `pi`

.

**Examples**

```
julia> adjusted_length(partitioned_permutation(perm(symmetric_group(2), [2, 1]), [1, 1]))
1
```

This function is part of the experimental code in Oscar. Please read here for more details.

# Products of Partitioned Permutations

For two partitioned permutations $(V, \pi)$ and $(W, \sigma)$ one defines their product as $(V, \pi) \cdot (W, \sigma) = (V \vee W, \pi \sigma)$ if $|(V, \pi)| + |(W, \sigma)| = |(V \vee W, \pi \sigma)|$. Otherwise, one sets $(V, \pi) \cdot (W, \sigma) = (O, \mathrm{id})$. Here, $O$ is the partition where every block consists of exactly one element, and $V \vee W$ denotes the join of the partitions $V$ and $W$.

A major problem is the factorization of a partitioned permutation $(V, \pi)$. This involves finding all pairs $(W_1, \sigma_1), (W_2, \sigma_2)$ of partitioned permutations with $(V, \pi) = (W_1, \sigma_1) \cdot (W_2, \sigma_2)$.

`*`

— Method`*(pp_1::PartitionedPermutation, pp_2::PartitionedPermutation)`

Return the product of two partitioned permutations as described in [CMS07].

**Examples**

```
julia> x = partitioned_permutation(perm(symmetric_group(3), [1, 2, 3]), [1, 2, 3])
PartitionedPermutation((), SetPartition([1, 2, 3], Int64[]))
julia> y = partitioned_permutation(perm(symmetric_group(3), [2, 1, 3]), [1, 1, 3])
PartitionedPermutation((1,2), SetPartition([1, 1, 2], Int64[]))
julia> x*y
PartitionedPermutation((1,2), SetPartition([1, 1, 2], Int64[]))
```

This function is part of the experimental code in Oscar. Please read here for more details.

`enumerate_partitioned_permutations`

— Method`enumerate_partitioned_permutations(n::Int)`

Return and calculate all `PartitionedPermutation`

objects of length `n`

**Examples**

```
julia> length(enumerate_partitioned_permutations(6))
4051
```

This function is part of the experimental code in Oscar. Please read here for more details.

`factor`

— Method`factor(pp::PartitionedPermutation)`

Return the factorization of `pp`

in form of a set of 2-tuples.

**Examples**

```
julia> length(factor(partitioned_permutation(perm(symmetric_group(3), [2, 1, 3]), [1, 1, 2])))
2
```

This function is part of the experimental code in Oscar. Please read here for more details.