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
source

Array interface

Partition is a concrete subtype of AbstractVector{Int} and implements the following 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 decreasing order) of the partition.

source
Base.setindex!Method.
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.

source

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::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₁
source

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

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

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)

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

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

source

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}

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

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

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

Ulitility functions

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

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 = 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
source
character(lambda::Partition, p::perm, check::Bool=true) -> BigInt

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

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

Returns 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

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

The 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 = PermutationGroup(sum(λ))
Permutation 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)

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.

source
partitionseq(seq::BitVector)

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

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

source
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.
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:

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
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{T,T}, xi::SkewDiagram) where T<:Integer

Checks 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:

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.

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

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

source