Partitions and Young tableaux

# Partitions and Young tableaux

AbstractAlgebra.jl provides basic support for computations with Young tableaux, skew diagrams and the characters of permutation groups (implemented src/generic/YoungTabs.jl). All functionality of permutations is accesible in the Generic submodule.

## Partitions

The basic underlying object for those concepts is Partition of a number $n$, i.e. a sequence of positive integers $n_1, \ldots, n_k$ which sum to $n$. Partitions in AbstractAlgebra.jl are represented internally by non-increasing Vectors of Ints. Partitions are printed using the standard notation, i.e. $9 = 4 + 2 + 1 + 1 + 1$ is shown as $4_1 2_1 1_3$ with the subscript indicating the count of a summand in the partition.

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

### Array interface

Partition is a concrete subtype of AbstractVector{Int} and implements the following standard Array interface:

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.

These functions work on the level of p.part vector. Additionally setindex! will try to prevent uses which result in non-valid (i.e. non-decreasing) partition vectors.

One can easily iterate over all partitions of $n$ using the AllParts type:

AllParts(n::Integer)

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{Int64},1}:
1₅
2₁1₃
3₁1₂
2₂1₁
4₁1₁
3₁2₁
5₁

The number of all partitions can be computed by the hidden function _numpart. Much faster implementation is available in Nemo.jl.

_numpart(n::Integer)

Return 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.

Since Partition is a subtype of AbstractVector generic functions which operate on vectors should work in general. However the meaning of conj has been changed to agree with the traditional understanding of conjugation of Partitions:

conj(part::Partition)

Return 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)

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

## Young Diagrams and Young Tableaux

Mathematicaly speaking Young diagram is a diagram which consists of rows of square boxes such that the number of boxes in each row is no less than the number of boxes in the previous row. For example partition $4_1 3_2 1$ represents the following diagram.

┌───┬───┬───┬───┐
│   │   │   │   │
├───┼───┼───┼───┘
│   │   │   │
├───┼───┼───┤
│   │   │   │
├───┼───┴───┘
│   │
└───┘

Young Tableau is formally a bijection between the set of boxes of a Young Diagram and the set $\{1, \ldots, n\}$. If a bijection is increasing along rows and columns of the diagram it is referred to as standard. For example

┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┘
│ 5 │ 6 │ 7 │
├───┼───┼───┤
│ 8 │ 9 │10 │
├───┼───┴───┘
│11 │
└───┘

is a standard Young tableau of $4_1 3_2 1$ where the bijection assigns consecutive natural numbers to consecutive (row-major) cells.

### Constructors

In AbstractAlgebra.jl Young tableau are implemented as essentially row-major sparse matrices, i.e. YoungTableau <: AbstractArray{Int,2} but only the defining Partition and the (row-major) fill-vector is stored.

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

Return 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

For convenience there exists an alternative constructor of YoungTableau, which accepts a vector of integers and constructs Partition internally.

YoungTableau(p::Vector{Integer}[, fill=collect(1:sum(p))])

### Array interface

To make YoungTableaux array-like we implement the following functions:

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

julia> y
5

julia> y
2

julia> y
0

Also the double-indexing corresponds to (row, column) access to an abstract array.

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

julia> y[1,2]
2

julia> y[2,3]
7

julia> y[3,2]
0

Functions defined for AbstractArray type based on those (e.g. length) should work. Again, as in the case of Partition the meaning of conj is altered to reflect the usual meaning for Young tableaux:

conj(Y::YoungTableau)

Return 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 │
└───┘

### Pretty-printing

Similarly to permutations we have two methods of displaying Young Diagrams:

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 │
└───┘

### Ulitility functions

matrix_repr(a::Perm)

Return the permutation matrix as a sparse matrix representing a via natural embedding of the permutation group into the general linear group over $\mathbb{Z}$.

Examples:

julia> p = Perm([2,3,1])
(1,2,3)

julia> matrix_repr(p)
3×3 SparseArrays.SparseMatrixCSC{Int64,Int64} with 3 stored entries:
[3, 1]  =  1
[1, 2]  =  1
[2, 3]  =  1

julia> Array(ans)
3×3 Array{Int64,2}:
0  1  0
0  0  1
1  0  0
matrix_repr(Y::YoungTableau)

Construct sparse integer matrix representing the tableau.

Examples:

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

julia> matrix_repr(y)
3×4 SparseArrays.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 │
└───┘

## Characters of permutation groups

Irreducible characters (at least over field of characteristic $0$) of the full group of permutations $S_n$ correspond via Specht modules to partitions of $n$.

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 = SymmetricGroup(4)
Full symmetric group over 4 elements

julia> chi = character(Partition([3,1])); # character of the regular representation

julia> chi(G())
3

julia> chi(perm"(1,3)(2,4)")
-1
character(lambda::Partition, p::Perm, check::Bool=true) -> BigInt

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

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

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

The values computed by characters are cached in an internal dictionary Dict{Tuple{BitVector,Vector{Int}}, BigInt}. Note that all of the above functions return BigInts. If you are sure that the computations do not overflow, variants of the last two functions using Int are available:

character(::Type{Int}, lambda::Partition, p::Perm[, check::Bool=true])
character(::Type{Int}, lambda::Partition, mu::Partition[, check::Bool=true])

The dimension $\dim \lambda$ of the irreducible module corresponding to partition $\lambda$ can be computed using Hook length formula

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 right 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

Return 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

The character associated with Y.part can also be used to compute the dimension, but as it is expected the Murnaghan-Nakayama is much slower even though (due to caching) consecutive calls are fast:

julia> λ = Partition(collect(12:-1:1))
12₁11₁10₁9₁8₁7₁6₁5₁4₁3₁2₁1₁

julia> @time dim(YoungTableau(λ))
0.224430 seconds (155.77 k allocations: 7.990 MiB)
9079590132732747656880081324531330222983622187548672000

julia> @time dim(YoungTableau(λ))
0.000038 seconds (335 allocations: 10.734 KiB)
9079590132732747656880081324531330222983622187548672000

julia> G = SymmetricGroup(sum(λ))
Full symmetric group over 78 elements

julia> @time character(λ, G())
24.154105 seconds (58.13 M allocations: 3.909 GiB, 42.84% gc time)
9079590132732747656880081324531330222983622187548672000

julia> @time character(λ, G())
0.001439 seconds (195 allocations: 24.453 KiB)
9079590132732747656880081324531330222983622187548672000

### Low-level functions and characters

As mentioned above character functions use the Murnaghan-Nakayama rule for evaluation. The implementation follows

Dan Bernstein, The computational complexity of rules for the character table of $S_n$ Journal of Symbolic Computation, 37 (6), 2004, p. 727-748,

implementing the following functions. For precise definitions and meaning please consult the paper cited.

partitionseq(lambda::Partition)

Return 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)

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

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

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::Integer, charvals)

Return 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.

## Skew Diagrams

Skew diagrams are formally differences of two Young diagrams. Given $\lambda$ and $\mu$, two partitions of $n+m$ and $m$ (respectively). Suppose that each of cells of $\mu$ is a cell of $\lambda$ (i.e. parts of $\mu$ are no greater than the corresponding parts of $\lambda$). Then the skew diagram denoted by $\lambda/\mu$ is the set theoretic difference the of sets of boxes, i.e. is a diagram with exactly $n$ boxes:

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{Int64}:
⋅  ⋅  ⋅  1
⋅  1  1
⋅  1


SkewDiagram implements array interface with the following functions:

size(xi::SkewDiagram)

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

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

Check 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.

The support for skew diagrams is very rudimentary. The following functions are available:

isrimhook(xi::SkewDiagram)

Check 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])

Compute 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)

Return 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.