Tableaux

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.

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.

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

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

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.

shape(tab::Tableau{T})

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

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.

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

is_semistandard(tab::Tableau)

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

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.

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

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

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.

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

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.

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

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

standard_tableaux(n::Integer)

Return a list of all standard tableaux with n boxes.

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.

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

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

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.