Partitions and Young tableaux

Partition(part::Vector{<:Integer}[, check::Bool=true]) <: AbstractVector{Int}

Represent integer partition in the non-increasing order.

part will be sorted, if necessary. Checks for validity of input can be skipped by calling the (inner) constructor with false as the second argument.

Functionally Partition is a thin wrapper over Vector{Int}.

Fieldnames:

• n::Int - the partitioned number
• part::Vector{Int} - a non-increasing sequence of summands of n.

Examples:

julia> p = Partition([4,2,1,1,1])
4₁2₁1₃

julia> p.n == sum(p.part)
true

size(p::Partition)

Return the size of the vector which represents the partition.

Examples:

julia> p = Partition([4,3,1]); size(p)
(3,)

getindex(p::Partition, i::Integer)

Return the i-th part (in decreasing order) of the partition.

setindex!(p::Partition, v::Integer, i::Integer)

Set the i-th part of partition p to v. setindex! will throw an error if the operation violates the non-increasing assumption.

AllParts(n::Int)

Return an iterator over all integer Partitions of n. Partitions are produced in ascending order according to RuleAsc (Algorithm 3.1) from

Jerome Kelleher and Barry O’Sullivan, Generating All Partitions: A Comparison Of Two Encodings ArXiv:0909.2331

See also Combinatorics.partitions(1:n).

Examples

julia> ap = AllParts(5);

julia> collect(ap)
7-element Array{AbstractAlgebra.Generic.Partition,1}:
 1₅
 2₁1₃
 3₁1₂
 2₂1₁
 4₁1₁
 3₁2₁
 5₁

_numpart(n::Integer)

Returns the number of all distinct integer partitions of n. The function uses Euler pentagonal number theorem for recursive formula. For more details see OEIS sequence A000041. Note that _numpart(0) = 1 by convention.

conj(part::Partition)

Returns the conjugated partition of part, i.e. the partition corresponding to the Young diagram of part reflected through the main diagonal.

Examples:

julia> p = Partition([4,2,1,1,1])
4₁2₁1₃

julia> conj(p)
5₁2₁1₂

conj(part::Partition, v::Vector)

Returns the conjugated partition of part together with permuted vector v.

YoungTableau(part::Partition[, fill::Vector{Int}=collect(1:sum(part))])  <: AbstractArray{Int, 2}

Returns the Young tableaux of partition part, filled linearly by fill vector. Note that fill vector is in row-major format.

Fields:

• part - the partition defining Young diagram
• fill - the row-major fill vector: the entries of the diagram.

Examples:

julia> p = Partition([4,3,1]); y = YoungTableau(p)
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘

julia> y.part
4₁3₁1₁

julia> y.fill
8-element Array{Int64,1}:
 1
 2
 3
 4
 5
 6
 7
 8

size(Y::YoungTableau)

Return size of the smallest array containing Y, i.e. the tuple of the number of rows and the number of columns of Y.

Examples:

julia> y = YoungTableau([4,3,1]); size(y)
(3, 4)

getindex(Y::YoungTableau, n::Integer)

Return the column-major linear index into the size(Y)-array. If a box is outside of the array return 0.

Examples:

julia> y = YoungTableau([4,3,1])
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘

julia> y[1]
1

julia> y[2]
5

julia> y[4]
2

julia> y[6]
0

conj(Y::YoungTableau)

Returns the conjugated tableau, i.e. the tableau reflected through the main diagonal.

Examples

julia> y = YoungTableau([4,3,1])
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘

julia> conj(y)
┌───┬───┬───┐
│ 1 │ 5 │ 8 │
├───┼───┼───┘
│ 2 │ 6 │
├───┼───┤
│ 3 │ 7 │
├───┼───┘
│ 4 │
└───┘

setyoungtabstyle(format::Symbol)

Select the style in which Young tableaux are displayed (in REPL or in general as string). This can be either

• :array - as matrices of integers, or
• :diagram - as filled Young diagrams (the default).

The difference is purely esthetical.

Examples:

julia> Generic.setyoungtabstyle(:array)
:array

julia> p = Partition([4,3,1]); YoungTableau(p)
 1  2  3  4
 5  6  7
 8

julia> Generic.setyoungtabstyle(:diagram)
:diagram

julia> YoungTableau(p)
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘

matrix_repr(Y::YoungTableau)

Construct sparse integer matrix representing the tableau.

Examples:

julia> y = YoungTableau([4,3,1]);

julia> matrix_repr(y)
3×4 SparseMatrixCSC{Int64,Int64} with 8 stored entries:
  [1, 1]  =  1
  [2, 1]  =  5
  [3, 1]  =  8
  [1, 2]  =  2
  [2, 2]  =  6
  [1, 3]  =  3
  [2, 3]  =  7
  [1, 4]  =  4

fill!(Y::YoungTableaux, V::Vector{<:Integer})

Replace the fill vector Y.fill by V. No check if the resulting tableau is standard (i.e. increasing along rows and columns) is performed.

Examples:

julia> y = YoungTableau([4,3,1])
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘

julia> fill!(y, [2:9...])
┌───┬───┬───┬───┐
│ 2 │ 3 │ 4 │ 5 │
├───┼───┼───┼───┘
│ 6 │ 7 │ 8 │
├───┼───┴───┘
│ 9 │
└───┘

character(lambda::Partition)

Return the $\lambda$-th irreducible character of permutation group on sum(lambda) symbols. The returned character function is of the following signature:

chi(p::perm[, check::Bool=true]) -> BigInt

The function checks (if p belongs to the appropriate group) can be switched off by calling chi(p, false). The values computed by $\chi$ are cached in look-up table.

The computation follows the Murnaghan-Nakayama formula: $\chi_\lambda(\sigma) = \sum_{\text{rimhook }\xi\subset \lambda}(-1)^{ll(\lambda\backslash\xi)} \chi_{\lambda \backslash\xi}(\tilde\sigma)$ where $\lambda\backslash\xi$ denotes the skew diagram of $\lambda$ with $\xi$ removed, $ll$ denotes the leg-length (i.e. number of rows - 1) and $\tilde\sigma$ is permutation obtained from $\sigma$ by the removal of the longest cycle.

For more details see e.g. Chapter 2.8 of Group Theory and Physics by S.Sternberg.

Examples

julia> G = PermutationGroup(4)
Permutation group over 4 elements

julia> chi = character(Partition([3,1])) # character of the regular representation
(::char) (generic function with 2 methods)

julia> chi(G())
3

julia> chi(perm"(1,3)(2,4)")
-1

character(lambda::Partition, p::perm, check::Bool=true) -> BigInt

Returns the value of lambda-th irreducible character of the permutation group on permutation p.

character(lambda::Partition, mu::Partition) -> BigInt

Returns the value of lambda-th irreducible character on the conjugacy class represented by partition mu.

rowlength(Y::YoungTableau, i, j)

Return the row length of Y at box (i,j), i.e. the number of boxes in the i-th row of the diagram of Y located to the right of the (i,j)-th box.

Examples

julia> y = YoungTableau([4,3,1])
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘

julia> Generic.rowlength(y, 1,2)
2

julia> Generic.rowlength(y, 2,3)
0

julia> Generic.rowlength(y, 3,3)
0

collength(Y::YoungTableau, i, j)

Return the column length of Y at box (i,j), i.e. the number of boxes in the j-th column of the diagram of Y located below of the (i,j)-th box.

Examples

julia> y = YoungTableau([4,3,1])
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘

julia> Generic.collength(y, 1,1)
2

julia> Generic.collength(y, 1,3)
1

julia> Generic.collength(y, 2,4)
0

hooklength(Y::YoungTableau, i, j)

Return the hook-length of an element in Y at position (i,j), i.e the number of cells in the i-th row to the rigth of (i,j)-th box, plus the number of cells in the j-th column below the (i,j)-th box, plus 1.

Return 0 for (i,j) not in the tableau Y.

Examples

julia> y = YoungTableau([4,3,1])
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┴───┘
│ 8 │
└───┘

julia> hooklength(y, 1,1)
6

julia> hooklength(y, 1,3)
3

julia> hooklength(y, 2,4)
0

dim(Y::YoungTableau) -> BigInt

Returns the dimension (using hook-length formula) of the irreducible representation of permutation group $S_n$ associated the partition Y.part.

Since the computation overflows easily BigInt is returned. You may perform the computation of the dimension in different type by calling dim(Int, Y).

Examples

julia> dim(YoungTableau([4,3,1]))
70

julia> dim(YoungTableau([3,1])) # the regular representation of S_4
3

partitionseq(lambda::Partition)

Returns a sequence (as BitVector) of falses and trues constructed from lambda: tracing the lower contour of the Young Diagram associated to lambda from left to right a true is inserted for every horizontal and false for every vertical step. The sequence always starts with true and ends with false.

partitionseq(seq::BitVector)

Returns the essential part of the sequence seq, i.e. a subsequence starting at first true and ending at last false.

isrimhook(R::BitVector, idx::Int, len::Int)

R[idx:idx+len] forms a rim hook in the Young Diagram of partition corresponding to R iff R[idx] == true and R[idx+len] == false.

MN1inner(R::BitVector, mu::Partition, t::Int, [charvals])

Returns the value of $\lambda$-th irreducible character on conjugacy class of permutations represented by partition mu, where R is the (binary) partition sequence representing $\lambda$. Values already computed are stored in charvals::Dict{Tuple{BitVector,Vector{Int}}, Int}. This is an implementation (with slight modifications) of the Murnaghan-Nakayama formula as described in

Dan Bernstein,
"The computational complexity of rules for the character table of Sn"
_Journal of Symbolic Computation_, 37(6), 2004, p. 727-748.

SkewDiagram(lambda::Partition, mu::Partition) <: AbstractArray{Int, 2}

Implements a skew diagram, i.e. a difference of two Young diagrams represented by partitions lambda and mu. (below dots symbolise the removed entries)

Examples

julia> l = Partition([4,3,2])
4₁3₁2₁

julia> m = Partition([3,1,1])
3₁1₂

julia> xi = SkewDiagram(l,m)
3×4 AbstractAlgebra.Generic.SkewDiagram:
 ⋅  ⋅  ⋅  1
 ⋅  1  1
 ⋅  1

size(xi::SkewDiagram)

Return the size of array where xi is minimally contained. See size(Y::YoungTableau) for more details.

in(t::Tuple{T,T}, xi::SkewDiagram) where T<:Integer

Checks if box at position (i,j) belongs to the skew diagram xi.

getindex(xi::SkewDiagram, n::Integer)

Return 1 if linear index n corresponds to (column-major) entry in xi.lam which is not contained in xi.mu. Otherwise return 0.

isrimhook(xi::SkewDiagram)

Checks if xi represents a rim-hook diagram, i.e. its diagram is edge-connected and contains no $2\times 2$ squares.

leglength(xi::SkewDiagram[, check::Bool=true])

Computes the leglength of a rim-hook xi, i.e. the number of rows with non-zero entries minus one. If check is false function will not check whether xi is actually a rim-hook.

matrix_repr(xi::SkewDiagram)

Returns a sparse representation of the diagram xi, i.e. a sparse array A where A[i,j] == 1 if and only if (i,j) is in xi.lam but not in xi.mu.