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 consists of a permutation and a partition of the set such that the partition dominates the permutation in the sense that every cycle of is contained in one block of . We call the length of . Mathematically, another length function is more important. It is given by and we call this the adjusted length of . Note that this terminology is not used in the literature.
PartitionedPermutation
— TypePartitionedPermutation
The type of partitioned permutations. Field names 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 constructor of PartitionedPermutation
:
PartitionedPermutation(p::PermGroupElem, V::Vector{Int})
constructs the partitioned permutation where the partition is given by the vectorV
.
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
— Methodlength(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
— Methodadjusted_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 and one defines their product as if . Otherwise, one sets . Here, is the partition where every block consists of exactly one element, and denotes the join of the partitions and .
A major problem is the factorization of a partitioned permutation . This involves finding all pairs of partitioned permutations with .
*
— 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
— Methodenumerate_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
— Methodfactor(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.