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

AbstractAlgebra.Generic.PartitionType
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
source

Array interface

Partition is a concrete (immutable) subtype of AbstractVector{Integer} and implements the standard Array interface.

Base.sizeMethod
size(p::Partition)

Return the size of the vector which represents the partition.

Examples

julia> p = Partition([4,3,1]); size(p)
(3,)
source
Base.getindexMethod
getindex(p::Partition, i::Integer)

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

source

These functions work on the level of p.part vector.

One can easily iterate over all partitions of $n$ using the Generic.partitions function.

AbstractAlgebra.Generic.partitionsFunction
partitions(n::Integer)

Return the vector of all permutations of n. For an unsafe generator version see partitions!.

Examples

julia> Generic.partitions(5)
7-element Vector{AbstractAlgebra.Generic.Partition{Int64}}:
 1₅
 2₁1₃
 3₁1₂
 2₂1₁
 4₁1₁
 3₁2₁
 5₁
source

You may also have a look at JuLie.jl package for more utilities related to partitions.

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

AbstractAlgebra.Generic._numpartFunction
_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.

source

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:

Base.conjMethod
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₂
source
Base.conjMethod
conj(part::Partition, v::Vector)

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

source

Young Diagrams and Young Tableaux

Mathematically 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 <: AbstractMatrix{Int} but only the defining Partition and the (row-major) fill-vector is stored.

AbstractAlgebra.Generic.YoungTableauType
YoungTableau(part::Partition[, fill::Vector{Int}=collect(1:sum(part))])  <: AbstractMatrix{Int}

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 Vector{Int64}:
 1
 2
 3
 4
 5
 6
 7
 8
source

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:

Base.sizeMethod
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)
source
Base.getindexMethod
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
source

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:

Base.conjMethod
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 │
└───┘
source

Pretty-printing

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

AbstractAlgebra.Generic.setyoungtabstyleFunction
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 │
└───┘
source

Ulitility functions

AbstractAlgebra.Generic.matrix_reprMethod
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:
 ⋅  1  ⋅
 ⋅  ⋅  1
 1  ⋅  ⋅

julia> Array(ans)
3×3 Matrix{Int64}:
 0  1  0
 0  0  1
 1  0  0
source
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  2  3  4
 5  6  7  ⋅
 8  ⋅  ⋅  ⋅
source
Base.fill!Method
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 │
└───┘
source

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

AbstractAlgebra.Generic.characterMethod
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(one(G))
3

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

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

source
AbstractAlgebra.Generic.characterMethod
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.

source

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

AbstractAlgebra.Generic.rowlengthFunction
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
source
AbstractAlgebra.Generic.collengthFunction
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
source
AbstractAlgebra.Generic.hooklengthFunction
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
source
AbstractAlgebra.Generic.dimMethod
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
source

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(λ, one(G))
  0.000046 seconds (115 allocations: 16.391 KiB)
9079590132732747656880081324531330222983622187548672000

julia> @time character(λ, one(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.

AbstractAlgebra.Generic.partitionseqFunction
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.

source
partitionseq(seq::BitVector)

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

source
AbstractAlgebra.Generic.is_rimhookMethod
is_rimhook(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.

source
AbstractAlgebra.Generic.MN1innerFunction
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.
source

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:

AbstractAlgebra.Generic.SkewDiagramType
SkewDiagram(lambda::Partition, mu::Partition) <: AbstractMatrix{Int}

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
source

SkewDiagram implements array interface with the following functions:

Base.sizeMethod
size(xi::SkewDiagram)

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

source
Base.inMethod
in(t::Tuple{Integer,Integer}, xi::SkewDiagram)

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

source
Base.getindexMethod
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.

source

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

AbstractAlgebra.Generic.leglengthFunction
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.

source
AbstractAlgebra.Generic.matrix_reprMethod
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.

source