# Tableaux

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 $\lambda$ of a non-negative integer $n$ (the total number of boxes of the diagram). The diagram is then said to be of shape $\lambda$. Conversely, one can associate to any partition $\lambda$ a Young diagram in the obvious way, so Young diagrams are just another way to look at partitions.

A Young tableau of shape $\lambda$ is a filling of the boxes of the Young diagram of $\lambda$ 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$.

In OSCAR, a tableau is internally stored as an array of arrays and is represented by the type YoungTableau{T} which is a subtype of AbstractVector{AbstractVector{T}}, where T is the integer type of the filling. As for partitions, one may increase performance by casting into smaller integer types, e.g. Int8.

young_tableauFunction
young_tableau([::Type{T}], v::Vector{Vector{<:IntegerUnion}}; check::Bool = true) where T <: IntegerUnion

Return the Young tableau given by v as an object of type YoungTableau{T}.

The element type T may be optionally specified, see also the examples below.

If check is true (default), it is checked whether v defines a tableau, that is, whether the structure of v defines a partition.

Examples

julia> young_tableau([[1, 2, 3], [4, 5], [6]])
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 |
+---+---+
| 6 |
+---+

julia> young_tableau(Int8, [[1, 2, 3], [4, 5], [6]]) # save the elements in 8-bit integers
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 |
+---+---+
| 6 |
+---+
source

## Operations

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

Return the hook length of the box with coordinates (i, j) in the Young tableau tab respectively the Young diagram of shape lambda.

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.

See also hook_lengths.

source
hook_lengthsFunction
hook_lengths(lambda::Partition)

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

See also hook_length.

source
shapeFunction
shape(tab::YoungTableau)

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

source
weightFunction
weight(tab::YoungTableau)

Return the weight of the tableau tab as an array whose i-th element gives the number of times the integer i appears in the tableau.

source
reading_wordFunction
reading_word(tab::YoungTableau)

Return the reading word of the tableau tab as an array, i.e. the word obtained by concatenating the fillings of the rows, starting from the bottom row.

Examples

julia> reading_word(young_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::YoungTableau)

Return true if the tableau tab is semistandard and false otherwise.

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

See also is_standard.

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

Return an iterator over all semistandard Young tableaux of given shape 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(box_num::T, max_val::T = box_num) where T <: Integer

Return an iterator over all semistandard Young tableaux consisting of box_num boxes and filling elements bounded by max_val.

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

Return an iterator over all semistandard Young tableaux with shape s and given weight. This requires that sum(s) = sum(weight).

source

## Standard tableaux

is_standardFunction
is_standard(tab::YoungTableau)

Return true if the tableau tab is standard and false otherwise.

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.

See also is_semistandard.

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

Return an iterator over all standard Young tableaux of a given shape s.

source
standard_tableaux(n::IntegerUnion)

Return an iterator over all standard Young tableaux with n boxes.

source

The number $f^\lambda$ of standard Young tableaux of shape $\lambda$ is computed using the hook length formula

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

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

schenstedFunction
schensted(sigma::Vector{<:IntegerUnion})
schensted(sigma::PermGroupElem)

Return the pair of standard Young tableaux (the insertion and the recording tableau) corresponding to the permutation sigma under the Robinson-Schensted correspondence.

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

source
bump!Function
bump!(tab::YoungTableau, x::Int)

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

source
bump!(tab::YoungTableau, x::Integer, Q::YoungTableau, y::Integer)

Insert the integer x into tab according to the bumping algorithm by applying the Schensted insertion and insert the integer y into Q at the same position as x in tab.

source