Tableaux

TableauType
Tableau{T} <: AbstractVector{AbstractVector{T}}

A Young diagram is a diagram of finitely many empty "boxes" arranged in left-justified rows, with the row lengths in non-increasing order. The box in row i and and column j has the coordinates (i,j). Listing the number of boxes in each row gives a partition $λ$ of a non-negative integer n (the total number of boxes of the diagram). The diagram is then said to be of shape $λ$. Conversely, one can associate to any partition $λ$ a Young diagram in the obvious way, so Young diagrams are just another way to look at partitions.

A Young tableau of shape $λ$ is a filling of the boxes of the Young diagram of $λ$ with elements from some set. After relabeling we can (and will) assume that we fill from a set of integers from $1$ up to some number, which in applications is often equal to n. We encode a tableau as an array of arrays and we have implemented an own type Tableau{T} as subtype of AbstractVector{AbstractVector{T}} to work with tableaux. As for partitions, you may increase performance by casting into smaller integer types, e.g.

For efficiency, we do not check whether the given array is really a tableau, i.e. whether the structure of the array defines a partition.

Examples

julia> tab=Tableau([[1,2,3],[4,5],[6]])
[[1, 2, 3], [4, 5], [6]]

julia> tab=Tableau(Vector{Int8}[[2,1], [], [3,2,1]]) #Using 8 bit integers
Vector{Int8}[[2, 1], [], [3, 2, 1]]

References

1. Wikipedia, Young tableau.
source

Operations

hook_lengthFunction
hook_length(lambda::Partition, i::Integer, j::Integer)

Consider the Young diagram of a partition $λ$. The hook length of a box, is the number of boxes to the right in the same row + the number of boxes below in the same column + 1. The function returns the hook length of the box with coordinates (i,j). The functions assumes that the box exists.

source
hook_length(tab::Tableau, i::Integer, j::Integer)

Shortcut for hook_length(shape(tab), i, j).

source
hook_lengthsFunction
hook_lengths(lambda::Partition)

Return the tableau of shape $λ$ in which the entry at position (i,j) is equal to the hook length of the corresponding box.

source
shapeFunction
shape(tab::Tableau{T})

Return the shape of a tableau, i.e. the partition given by the lengths of the rows of the tableau.

source
weightFunction
weight(tab::Tableau)

The weight of a tableau is the number of times each number appears in the tableau. The return value is an array whose i-th element gives the number of times the integer i appears in the tableau.

source
reading_wordFunction
reading_word(tab::Tableau)

The reading word of a tableau is the word obtained by concatenating the fillings of the rows, starting from the bottom row. The word is here returned as an array.

Examples

julia> reading_word(Tableau([ [1,2,3] , [4,5] , [6] ]))
6-element Vector{Int64}:
6
4
5
1
2
3
source

Semistandard tableaux

is_semistandardFunction
is_semistandard(tab::Tableau)

A tableau is called semistandard if the entries weakly increase along each row and strictly increase down each column.

source
semistandard_tableauxFunction
semistandard_tableaux(shape::Partition{T}, max_val::T=sum(shape)) where T<:Integer

Return a list of all semistandard tableaux of given shape and filling elements bounded by max_val. By default, max_val is equal to the sum of the shape partition (the number of boxes in the Young diagram). The list of tableaux is in lexicographic order from left to right and top to bottom.

source
semistandard_tableaux(shape::Partition{T}, max_val::T=sum(shape)) where T<:Integer

Shortcut for semistandard_tableaux(Partition(shape), max_val).

source
semistandard_tableaux(box_num::T, max_val::T=box_num) where T<:Integer

Return a list of all semistandard tableaux consisting of box_num boxes and filling elements bounded by max_val.

source
semistandard_tableaux(s::Vector{T}, weight::Vector{T}) where T<:Integer

Return a list of all semistandard tableaux with shape s and given weight. This requires that sum(s) = sum(weight).

source

Standard tableaux

is_standardFunction
is_standard(tab::Tableau)

A tableau is called standard if it is semistandard and the entries are in bijection with $1,…,n$, where $n$ is the number of boxes.

source
standard_tableauxFunction
standard_tableaux(s::Partition)
standard_tableaux(s::Vector{Integer})

Return a list of all standard tableaux of a given shape.

source
standard_tableaux(n::Integer)

Return a list of all standard tableaux with n boxes.

source
num_standard_tableauxFunction
num_standard_tableaux(lambda::Partition)

Return the number $f^λ$ of standard tableaux of shape $λ$ using the hook length formula

$$$f^λ = \frac{n!}{\prod_{i,j} h_λ(i,j)},$$$

where the product is taken over all boxes in the Young diagram of $λ$ and $h_λ$ denotes the hook length of the box (i,j).

References

1. Wikipedia, Hook length formula.
source
schenstedFunction
schensted(sigma::Vector{Integer})
schensted(sigma::Perm{T})

The Robinson–Schensted correspondence is a bijection between permutations and pairs of standard Young tableaux of the same shape. For a permutation sigma (given as an array), this function performs the Schnested algorithm and returns the corresponding pair of standard tableaux (the insertion and recording tableaux).

Examples

julia> P,Q = schensted([3,1,6,2,5,4]);

julia> P
[[1, 2, 4], [3, 5], [6]]

julia> Q
[[1, 3, 5], [2, 4], [6]]

References

1. Wikipedia, Robinson–Schensted correspondence
source
bump!Function
bump!(tab::Tableau, x::Int)

Inserts the integer x into the tableau tab according to the bumping algorithm by applying the Schensted insertion.

References

1. Wolfram MathWorld, Bumping Algorithm
source
bump!(tab::Tableau, x::Integer, Q::Tableau, y::Integer)

Inserts x into tab according to the bumping algorithm by applying the Schensted insertion. Traces the change with Q by inserting y at the same position in Q as x in tab.

source