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_tableau — Functionyoung_tableau([::Type{T}], v::Vector{Vector{<:IntegerUnion}}; check::Bool = true) where T <: IntegerUnionReturn 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 |
+---+Operations
hook_length — Functionhook_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.
hook_lengths — Functionhook_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.
shape — Functionshape(tab::YoungTableau)Return the shape of the tableau tab, i.e. the partition given by the lengths of the rows of the tableau.
weight — Functionweight(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.
reading_word — Functionreading_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
3Semistandard tableaux
is_semistandard — Functionis_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.
semistandard_tableaux — Functionsemistandard_tableaux(shape::Partition{T}, max_val::T = sum(shape)) where T <: Integer
semistandard_tableaux(shape::Vector{T}, max_val::T = sum(shape)) where T <: IntegerReturn 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.
semistandard_tableaux(box_num::T, max_val::T = box_num) where T <: IntegerReturn an iterator over all semistandard Young tableaux consisting of box_num boxes and filling elements bounded by max_val.
semistandard_tableaux(s::Partition{T}, weight::Vector{T}) where T <: Integer
semistandard_tableaux(s::Vector{T}, weight::Vector{T}) where T <: IntegerReturn an iterator over all semistandard Young tableaux with shape s and given weight. This requires that sum(s) = sum(weight).
Standard tableaux
is_standard — Functionis_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.
standard_tableaux — Functionstandard_tableaux(s::Partition)
standard_tableaux(s::Vector{Integer})Return an iterator over all standard Young tableaux of a given shape s.
standard_tableaux(n::Integer)Return an iterator over all standard Young tableaux with n boxes.
number_of_standard_tableaux — Functionnumber_of_standard_tableaux(lambda::Partition)Return the number of standard Young tableaux of shape lambda.
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)$.
schensted — Functionschensted(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 |
+---+
bump! — Functionbump!(tab::YoungTableau, x::Int)Insert the integer x into the tableau tab according to the bumping algorithm by applying the Schensted insertion.
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.