| Title: | Young Tableaux |
|---|---|
| Description: | Deals with Young tableaux (field of combinatorics). For standard Young tabeaux, performs enumeration, counting, random generation, the Robinson-Schensted correspondence, and conversion to and from paths on the Young lattice. Also performs enumeration and counting of semistandard Young tableaux, enumeration of skew semistandard Young tableaux, enumeration of Gelfand-Tsetlin patterns, and computation of Kostka numbers. |
| Authors: | Stéphane Laurent |
| Maintainer: | Stéphane Laurent <[email protected]> |
| License: | GPL-3 |
| Version: | 0.5.0 |
| Built: | 2024-11-22 02:50:15 UTC |
| Source: | https://github.com/stla/syt |
Enumeration of all semistandard skew tableaux with given shape and given maximum entry.
all_ssSkewTableaux(lambda, mu, n)all_ssSkewTableaux(lambda, mu, n)
lambda, mu
|
integer partitions defining the skew partition:
|
n |
a positive integer, the maximum entry of the skew tableaux |
The list of all semistandard skew tableaux whose shape is the skew
partition defined by lambda and mu and with maximum entry
n.
all_ssytx,
skewTableauxWithGivenShapeAndWeight.
ssstx <- all_ssSkewTableaux(c(4, 3, 1), c(2, 2), 2) lapply(ssstx, prettySkewTableau)ssstx <- all_ssSkewTableaux(c(4, 3, 1), c(2, 2), 2) lapply(ssstx, prettySkewTableau)
Generates all semistandard Young tableaux of a given shape and
filled with integers between 1 and a given n.
all_ssytx(lambda, n)all_ssytx(lambda, n)
lambda |
an integer partition, the shape |
n |
an integer, the maximum value of the entries (the minimum value
is |
List of all semistandard Young tableaux with shape lambda
and filled with integers between 1 and n.
ssytx_withGivenShapeAndWeight.
ssytx <- all_ssytx(c(2, 1), 3) lapply(ssytx, prettyTableau)ssytx <- all_ssytx(c(2, 1), 3) lapply(ssytx, prettyTableau)
Generates all standard Young tableaux of a given shape.
all_sytx(lambda)all_sytx(lambda)
lambda |
the shape, an integer partition |
A list of standard Young tableaux.
sytx <- all_sytx(c(5, 2)) lapply(sytx, prettyTableau)sytx <- all_sytx(c(5, 2)) lapply(sytx, prettyTableau)
Converts a ballot sequence to its corresponding standard Young tableau.
ballot2syt(a)ballot2syt(a)
a |
ballot sequence |
A standard Young tableau.
a <- c(1,1,2,3,2,1) ballot2syt(a)a <- c(1,1,2,3,2,1) ballot2syt(a)
Number of semistandard Young tableaux of a given shape and
filled with integers between 1 and a given n.
count_ssytx(lambda, n)count_ssytx(lambda, n)
lambda |
an integer partition, the shape |
n |
an integer, the maximum value of the entries (the minimum value
is |
The number of semistandard Young tableaux with shape lambda
and filled with integers between 1 and n.
count_ssytx(c(4, 3, 3, 2), 5)count_ssytx(c(4, 3, 3, 2), 5)
Number of standard Young tableaux of a given shape.
count_sytx(lambda)count_sytx(lambda)
lambda |
an integer partition, the shape |
An integer, the number of standard Young tableaux of shape lambda.
count_sytx(c(5, 4, 1)) length(all_sytx(c(5, 4, 1)))count_sytx(c(5, 4, 1)) length(all_sytx(c(5, 4, 1)))
Returns the dual (skew) tableau of a skew tableau.
dualSkewTableau(skewTableau)dualSkewTableau(skewTableau)
skewTableau |
a skew tableau |
A skew tableau.
tbl <- list(c(NA, NA, 1, 1), c(NA, 1), c(1, 2)) dtbl <- dualSkewTableau(tbl) prettySkewTableau(dtbl)tbl <- list(c(NA, NA, 1, 1), c(NA, 1), c(1, 2)) dtbl <- dualSkewTableau(tbl) prettySkewTableau(dtbl)
The dual standard Young tableau of a standard Young tableau.
dualsyt(syt)dualsyt(syt)
syt |
standard Young tableau |
A standard Young tableau.
syt <- list(c(1,2,6), c(3,5), 4) dualsyt(syt)syt <- list(c(1,2,6), c(3,5), 4) dualsyt(syt)
The dual tableau of a tableau (mirror image to the main diagonal).
dualTableau(tableau)dualTableau(tableau)
tableau |
a tableau |
A tableau.
tbl <- list(c("a", "s", "e", "f"), c("f", "o"), c("u")) dualTableau(tbl)tbl <- list(c("a", "s", "e", "f"), c("f", "o"), c("u")) dualTableau(tbl)
Returns the "first" standard Young tableau of a given shape.
firstsyt(lambda)firstsyt(lambda)
lambda |
the shape, an integer partition |
A standard Young tableau.
firstsyt(c(4, 2, 1))firstsyt(c(4, 2, 1))
Enumeration of Gelfand-Tsetlin patterns defined by a given integer partition and a given weight.
GelfandTsetlinPatterns(lambda, weight)GelfandTsetlinPatterns(lambda, weight)
lambda |
integer partition; up to trailing zeros, this will be the top diagonal of the generated Gelfand-Tsetlin patterns |
weight |
integer vector; the partial sums of this vector will be the diagonal sums of the generated Gelfand-Tsetlin patterns |
A list of Gelfand-Tsetlin patterns. A Gelfand-Tsetlin pattern is a
triangular array of non-negative integers, and it is represented by the
list of its rows. Hence the first element of this list is an integer, the
second element is an integer vector of length two, and so on. The length
of this list is the length of weight.
GTpatterns <- GelfandTsetlinPatterns(c(3, 1), c(1, 1, 1, 1)) lapply(GTpatterns, prettyGT)GTpatterns <- GelfandTsetlinPatterns(c(3, 1), c(1, 1, 1, 1)) lapply(GTpatterns, prettyGT)
Converts a growth process of integer partitions to its corresponding standard Young tableau.
gprocess2syt(path)gprocess2syt(path)
path |
a path of the Young graph from the root vertex, given as a list of integer partitions |
A standard Young tableau.
path <- list(1, 2, c(2,1), c(3,1), c(3,1,1)) gprocess2syt(path)path <- list(1, 2, c(2,1), c(3,1), c(3,1,1)) gprocess2syt(path)
Hook lengths of a given integer partition.
hooklengths(lambda)hooklengths(lambda)
lambda |
an integer partition |
The hook lengths of the partition, given in a list.
hooklengths(c(4, 2))hooklengths(c(4, 2))
Hooks of a given integer partition.
hooks(lambda)hooks(lambda)
lambda |
integer partition |
The hooks of the partition in a list.
hooks(c(4, 2))hooks(c(4, 2))
Check whether a skew tableau is a semistandard skew tableau.
isSemistandardSkewTableau(skewTableau)isSemistandardSkewTableau(skewTableau)
skewTableau |
a skew tableau |
A Boolean value.
tbl <- list(c(NA, NA, 1, 1), c(NA, 1), c(1, 2)) isSemistandardSkewTableau(tbl)tbl <- list(c(NA, NA, 1, 1), c(NA, 1), c(1, 2)) isSemistandardSkewTableau(tbl)
Check whether a tableau is a skew tableau.
isSkewTableau(tableau)isSkewTableau(tableau)
tableau |
a tableau |
A Boolean value.
tbl <- list(c(NA, NA, 1, 1), c(NA, 1), c(1, 2)) isSkewTableau(tbl)tbl <- list(c(NA, NA, 1, 1), c(NA, 1), c(1, 2)) isSkewTableau(tbl)
Checks whether a tableau is a semistandard Young tableau.
isSSYT(tableau)isSSYT(tableau)
tableau |
a tableau |
A Boolean value.
tbl <- list(c(1, 2, 6), c(5, 5), 7) isSSYT(tbl)tbl <- list(c(1, 2, 6), c(5, 5), 7) isSSYT(tbl)
Check whether a skew tableau is a standard skew tableau.
isStandardSkewTableau(skewTableau)isStandardSkewTableau(skewTableau)
skewTableau |
a skew tableau |
A Boolean value.
tbl <- list(c(NA, NA, 1, 1), c(NA, 1), c(1, 2)) isStandardSkewTableau(tbl)tbl <- list(c(NA, NA, 1, 1), c(NA, 1), c(1, 2)) isStandardSkewTableau(tbl)
Checks whether a tableau is a standard Young tableau.
isSYT(tableau)isSYT(tableau)
tableau |
a tableau |
A Boolean value.
tbl <- list(c(1, 2, 6), c(3, 5), 4) isSYT(tbl)tbl <- list(c(1, 2, 6), c(3, 5), 4) isSYT(tbl)
Computes a Kostka number.
KostkaNumber(lambda, mu)KostkaNumber(lambda, mu)
lambda |
an integer partition |
mu |
an integer vector whose sum equals the weight (i.e. the sum) of
|
The Kostka number is the number of semistandard
Young tableaux with shape and weight . It does
not depend on the order of the elements of (so one can always
take an integer partition for ). The weight is the
vector whose -th element is the number of occurrences of
in the tableau.
The Kostka number corresponding to lambda and mu.
KostkaNumbers, KostkaNumbersWithGivenMu,
KostkaNumbersWithGivenLambda,
skewKostkaNumbers.
KostkaNumber(c(3,2), c(1,1,1,2)) KostkaNumber(c(3,2), c(1,1,2,1)) KostkaNumber(c(3,2), c(1,2,1,1)) KostkaNumber(c(3,2), c(2,1,1,1)) lambda <- c(4, 3, 1) mu <- rep(1, sum(lambda)) KostkaNumber(lambda, mu) == count_sytx(lambda) # should be TRUEKostkaNumber(c(3,2), c(1,1,1,2)) KostkaNumber(c(3,2), c(1,1,2,1)) KostkaNumber(c(3,2), c(1,2,1,1)) KostkaNumber(c(3,2), c(2,1,1,1)) lambda <- c(4, 3, 1) mu <- rep(1, sum(lambda)) KostkaNumber(lambda, mu) == count_sytx(lambda) # should be TRUE
Computes the Kostka numbers for all integer partitions of a given weight.
KostkaNumbers(n)KostkaNumbers(n)
n |
positive integer, the weight of the partitions |
An integer matrix, whose row names and column names encode the
partitions and and whose entries are the
Kostka numbers .
KostkaNumbersWithGivenLambda,
KostkaNumbersWithGivenMu, skewKostkaNumbers.
KostkaNumbers(4)KostkaNumbers(4)
Lists all positive Kostka numbers with
a given partition .
KostkaNumbersWithGivenLambda(lambda, output = "vector")KostkaNumbersWithGivenLambda(lambda, output = "vector")
lambda |
integer partition |
output |
the format of the output, either |
If output="vector", this function returns a named vector.
This vector is made of the non-zero (i.e. positive) Kostka numbers
, which are integers, and its names encode the
partitions .
If output="list", this function returns a list of lists.
Each of these lists has two
elements. The first one is named mu and is an integer
partition, and the second one is named value and is a positive
integer, the Kostka number . It is faster to
compute the Kostka numbers with this function than computing the
individual Kostka numbers with the function KostkaNumber.
KostkaNumber, KostkaNumbers,
KostkaNumbersWithGivenMu.
KostkaNumbersWithGivenLambda(c(2, 1, 1))KostkaNumbersWithGivenLambda(c(2, 1, 1))
Lists all positive Kostka numbers with
a given partition .
KostkaNumbersWithGivenMu(mu, output = "vector")KostkaNumbersWithGivenMu(mu, output = "vector")
mu |
integer partition |
output |
the format of the output, either |
If output="vector", this function returns a named vector.
This vector is made of the positive Kostka numbers
and its names encode the partitions .
If output="list", this function returns a list of lists.
Each of these lists has two
elements. The first one is named lambda and is an integer
partition, and the second one is named value and is a positive
integer, the Kostka number . It is faster to
compute the Kostka numbers with this function than computing the
individual Kostka numbers with the function KostkaNumber.
KostkaNumber, KostkaNumbers,
KostkaNumbersWithGivenLambda.
KostkaNumbersWithGivenMu(c(2, 1, 1))KostkaNumbersWithGivenMu(c(2, 1, 1))
Converts a matrix to a standard Young tableau.
matrix2syt(M)matrix2syt(M)
M |
a matrix |
A standard Young tableau.
M <- rbind(c(1,2,6), c(3,5,0), c(4,0,0)) matrix2syt(M)M <- rbind(c(1,2,6), c(3,5,0), c(4,0,0)) matrix2syt(M)
Given a standard Young tableau, returns the "next" one having the same shape.
nextsyt(syt)nextsyt(syt)
syt |
a standard Young tableau |
A standard Young tableau of the same shape as syt, or
NULL if syt is the last standard Young tableau of this shape.
syt <- firstsyt(c(4, 2, 1)) nextsyt(syt)syt <- firstsyt(c(4, 2, 1)) nextsyt(syt)
Pretty form of a Gelfand-Tsetlin pattern.
prettyGT(GT)prettyGT(GT)
GT |
a Gelfand-Tsetlin pattern |
A 'noquote' character matrix.
Pretty form of a skew tableau.
prettySkewTableau(skewTableau)prettySkewTableau(skewTableau)
skewTableau |
a skew tableau |
A 'noquote' character matrix.
tbl <- list(c(NA, NA, 1, 1), c(NA, 1), c(1, 2)) prettySkewTableau(tbl)tbl <- list(c(NA, NA, 1, 1), c(NA, 1), c(1, 2)) prettySkewTableau(tbl)
Pretty form of a tableau.
prettyTableau(tableau)prettyTableau(tableau)
tableau |
a tableau |
A 'noquote' character matrix.
tbl <- list(c(0, 2, 1, 1), c(4, 1), c(1, 2)) prettyTableau(tbl)tbl <- list(c(0, 2, 1, 1), c(4, 1), c(1, 2)) prettyTableau(tbl)
Samples a path of the Young graph according to the Plancherel growth process.
rgprocess(n)rgprocess(n)
n |
the size of the path to be sampled |
The path as a list, starting from the root vertex 1.
gprocess2syt and syt2gprocess to convert
a Young path to a standard Young tableau and conversely.
rgprocess(7)rgprocess(7)
Pair of standard Young tableaux given from a permutation by the Robinson-Schensted correspondence.
RS(sigma)RS(sigma)
sigma |
a permutation given as a vector of integers |
A list of two standard Young tableaux.
RS(c(1, 3, 6, 4, 7, 5, 2))RS(c(1, 3, 6, 4, 7, 5, 2))
Uniform sampling of a standard Young tableau of a given shape.
rsyt(lambda)rsyt(lambda)
lambda |
shape, an integer partition |
A standard Young tableau of shape lambda.
rsyt(c(7, 3, 1))rsyt(c(7, 3, 1))
Enumeration of Gelfand-Tsetlin patterns defined by a given skew partition and a given weight.
skewGelfandTsetlinPatterns(lambda, mu, weight)skewGelfandTsetlinPatterns(lambda, mu, weight)
lambda, mu
|
integer partitions defining the skew partition:
|
weight |
integer vector; this vector will be the
differences of the row sums of the generated Gelfand-Tsetlin patterns;
consequently, there will be no generated Gelfand-Tsetlin pattern unless
the sum of |
A list of matrices with non-negative integer entries. The number
of columns of these matrices is the length of lambda and the
number of rows of these matrices is one plus the length of weight.
skewGelfandTsetlinPatterns(c(3, 1, 1), c(2), c(1, 1, 1))skewGelfandTsetlinPatterns(c(3, 1, 1), c(2), c(1, 1, 1))
Skew Kostka numbers associated to a given skew partition.
skewKostkaNumbers(lambda, mu, output = "vector")skewKostkaNumbers(lambda, mu, output = "vector")
lambda, mu
|
integer partitions defining the skew partition:
|
output |
the format of the output, either |
The skew Kostka number is the number of skew
semistandard Young tableaux with shape and weight
. The weight of a Young tableau is the
vector whose -th element is the number of occurrences of
in this tableau.
If output="vector", the function returns a named vector.
This vector is made of the positive skew Kostka numbers
and its names encode the partitions .
If ouput="list", the function returns a list. Each element of this
list is a named list with two elements: an integer partition
in the field named "nu", and the corresponding skew Kostka number
in the field named "value". Only the
non-null skew Kostka numbers are provided by this list.
KostkaNumber, KostkaNumbersWithGivenMu.
skewKostkaNumbers(c(4,2,2), c(2,2))skewKostkaNumbers(c(4,2,2), c(2,2))
Enumeration of all skew semistandard tableaux with a given
shape and a given weight. The weight of a tableau is the
vector whose -th element is the number of occurrences of
in this tableau.
skewTableauxWithGivenShapeAndWeight(lambda, mu, weight)skewTableauxWithGivenShapeAndWeight(lambda, mu, weight)
lambda, mu
|
integer partitions defining the skew partition:
|
weight |
integer vector, the weight |
List of all skew semistandard tableaux whose shape is the skew
partition defined by lambda and mu and whose weight is
weight.
ssstx <- skewTableauxWithGivenShapeAndWeight(c(3, 1, 1), c(2), c(1, 1, 1)) lapply(ssstx, prettySkewTableau)ssstx <- skewTableauxWithGivenShapeAndWeight(c(3, 1, 1), c(2), c(1, 1, 1)) lapply(ssstx, prettySkewTableau)
Enumeration of all semistandard Young tableaux with a given
shape and a given weight. The weight of a tableau is the
vector whose -th element is the number of occurrences of
in this tableau.
ssytx_withGivenShapeAndWeight(lambda, weight)ssytx_withGivenShapeAndWeight(lambda, weight)
lambda |
integer partition, the shape |
weight |
integer vector, the weight |
List of all semistandard Young tableaux with shape lambda
and weight weight.
ssytx <- ssytx_withGivenShapeAndWeight(c(4, 1), c(0, 2, 1, 1, 1)) lapply(ssytx, prettyTableau)ssytx <- ssytx_withGivenShapeAndWeight(c(4, 1), c(0, 2, 1, 1, 1)) lapply(ssytx, prettyTableau)
Converts a standard Young tableau to its corresponding ballot sequence.
syt2ballot(syt)syt2ballot(syt)
syt |
standard Young tableau |
A ballot sequence.
syt <- list(c(1,2,6), c(3,5), 4) syt2ballot(syt)syt <- list(c(1,2,6), c(3,5), 4) syt2ballot(syt)
Converts a standard Young tableau to its corresponding growth process of partitions.
syt2gprocess(syt)syt2gprocess(syt)
syt |
standard Young tableau |
A list of integer partitions, representing a path of the Young graph starting from the root vertex.
syt <- list(c(1,2,4), 3, 5) syt2gprocess(syt)syt <- list(c(1,2,4), 3, 5) syt2gprocess(syt)
Representation of a standard Young tableau as a sparse matrix.
syt2matrix(syt)syt2matrix(syt)
syt |
a standard Young tableau |
A sparse matrix.
This function is the same as tableau2matrix except that
in addition it checks that the given tableau is a standard Young tableau.
syt <- list(c(1, 2, 6), c(3, 5), 4) syt2matrix(syt)syt <- list(c(1, 2, 6), c(3, 5), 4) syt2matrix(syt)
Representation of a tableau as a sparse matrix; only for a tableau with numeric or logical entries.
tableau2matrix(tableau)tableau2matrix(tableau)
tableau |
a tableau with numeric or logical entries |
A sparse matrix.
syt <- list(c(1, 2, 6), c(3, 5), 4) tableau2matrix(syt)syt <- list(c(1, 2, 6), c(3, 5), 4) tableau2matrix(syt)
The shape of a tableau.
tableauShape(tableau)tableauShape(tableau)
tableau |
a tableau (list of vectors having the same mode) |
The shape of the tableau. This is an integer partition whose
i-th part is the number of boxes in the i-th row of
the tableau.
tableau <- list(c(2, 1, 3), c(5, 2)) tableauShape(tableau)tableau <- list(c(2, 1, 3), c(5, 2)) tableauShape(tableau)