Partitions, Words, and Young Tableaux
- Introduction
- Partitions
NumberOfPartitions(n): RngIntElt → RngIntEltPartitions(n): RngIntElt → [ [ RngIntElt ] ]Partitions(n, k): RngIntElt, RngIntElt → [ [ RngIntElt ] ]RestrictedPartitions(n, M): RngIntElt, SetEnum → [ [ RngIntElt ] ]RestrictedPartitions(n, k, M): RngIntElt, RngIntElt, SetEnum → [ [ RngIntElt ] ]WeightedPartitions(n, w): RngIntElt, [ RngIntElt ] → [ [ RngIntElt ] ]WeightedRestrictedPartitions(n, S, w): RngIntElt, [ { RngIntElt }], [ RngIntElt ] → [ [ RngIntElt ] ]IsPartition(S): SeqEnum → BoolEltRandomPartition(n): RngIntElt → SeqEnumWeight(P): SeqEnum → RngIntEltIndexOfPartition(P): SeqEnum → RngIntElt- Example: Partitions and Conjugacy Classes
- Example: Changing Money with Restricted Partitions
- Words
- Ordered Monoids
OrderedMonoid(n): RngIntElt → MonOrdOrderedIntegerMonoid() → MonOrdId(O): MonOrd → MonOrdEltO ! 1: MonOrd, RngInt → MonOrdEltO . i: MonOrd, RngIntElt → MonOrdEltO ! [w₁, ..., wₙ]: MonOrd, [MonOrdElt] → MonOrdEltO ! [i₁, ..., iₙ]: MonOrd, [RngIntElt] → MonOrdEltw1 eq w2: MonOrdElt, MonOrdElt → BoolEltw1 * w2: MonOrdElt, MonOrdElt → MonOrdEltIsKnuthEquivalent(w1, w2): MonOrdElt, MonOrdElt → BoolEltw[i]: MonOrdElt, RngIntElt → RngEltElementToSequence(w): MonOrdElt → SeqEnumEltseq(w): MonOrdElt → SeqEnumLength(w): MonOrdElt → RngIntElt# w: MonOrdElt → RngIntEltContent(w): MonOrdElt → SeqEnum[RngIntElt]IsReverseLatticeWord(w): MonOrdElt → BoolEltMaximalIncreasingSequence(w): MonOrdElt → RngIntEltMaximalIncreasingSequences(w, k): SeqEnum, RngIntElt → RngIntElt- Example: Ordered Monoid over the Integers
- Example: Finitely Generated Ordered Monoid
- Example: Longest Increasing Subsequences
- Plactic Monoids
PlacticMonoid(O): MonOrd → MonOrdPlacticIntegerMonoid() → MonOrdOrderedMonoid(P): MonPlc → MonOrdId(P): MonPlc → MonPlcEltP ! 1: MonPlc, RngIntElt → MonPlcEltP . i: MonPlc, RngIntElt → MonPlcEltP ! [u₁, ..., uₙ]: MonPlc, [MonPlcElt] → MonPlcEltP ! [i₁, ..., iₙ]: MonPlc, [RngIntElt] → MonPlcEltP ! w: MonPlc, MonOrdElt → MonPlcEltP ! [w₁, ..., wₙ]: MonPlc, [MonOrdElt] → MonPlcEltP ! t: MonPlc, Tbl → MonPlcEltu1 eq u2: MonPlcElt, MonPlcElt → BoolEltu1 * u2: MonPlcElt, MonPlcElt → MonPlcEltLength(u): MonPlcElt → RngIntElt# u: MonPlcElt → RngIntEltContent(u): MonPlcElt → SeqEnum[RngIntElt]- Example: Ordered and Plactic Integer Monoids
- Example: Invariants under Knuth Equivalence
- Tableaux
- Tableau Monoids
- Creation of Tableaux
Tableau(Q): SeqEnum[SeqEnum[RngIntElt]] → TblTableau(Q): SeqEnum[MonOrdElt] → TblTableau(S, Q): SeqEnum[RngIntElt], SeqEnum[SeqEnum[RngIntElt]] → TblTableau(S, Q): SeqEnum[RngIntElt], SeqEnum[MonOrdElt] → TblWordToTableau(w): MonOrdElt → TblWordToTableau(u): MonPlcElt → TblM ! w: MonTbl, MonOrdElt → TblM ! u: MonTbl, MonPlcElt → TblM ! [i₁, ..., iₙ]: MonPlc, [MonPlcElt] → MonPlcEltM ! Q: MonPlc, SeqEnum → MonPlcEltM ! Q: MonPlc, SeqEnum → MonPlcElt- Example: Creating Tableaux over the Integers
- Example: Skew Tableau over Finitely Many Labels
- Example: Maps between Ordered, Plactic, and Tableau Monoids
- Enumeration of Tableaux
StandardTableaux(P): SeqEnum[RngIntElt] → SetEnumStandardTableaux(M, P): MonTbl, SeqEnum[RngIntElt] → SetEnumStandardTableauxOfWeight(n): RngIntElt → SetEnumStandardTableauxOfWeight(M, n): MonTbl, RngIntElt → SetEnumTableauxOfShape(S, m): SeqEnum[RngIntElt], RngIntElt → SetEnumTableauxOfShape(M, S, m): MonTbl, SeqEnum[RngIntElt], RngIntElt → SetEnumTableauxOnShapeWithContent(S, C): SeqEnum[RngIntElt], SeqEnum[RngIntElt] → SetEnumTableauxOnShapeWithContent(M, S, C): MonTbl, SeqEnum[RngIntElt], SeqEnum[RngIntElt] → SetEnumTableauxWithContent(C): SeqEnum[RngIntElt] → SetEnumTableauxWithContent(M, C): MonTbl, SeqEnum[RngIntElt] → SetEnum- Example: Standard Tableaux of a Given Shape
- Example: Tableaux with a Given Shape and Content
- Random Tableaux
RandomHookWalk(P, i, j): SeqEnum[RngIntElt], RngIntElt, RngIntElt → RngIntElt, RngIntEltRandomHookWalk(t, i, j): Tbl, RngIntElt, RngIntElt → RngIntElt, RngIntEltRandomTableau(S): SeqEnum[RngIntElt] → TblRandomTableau(M, S): MonTbl, SeqEnum[RngIntElt] → TblRandomTableau(n): RngIntElt → TblRandomTableau(M, n): MonTbl, RngIntElt → Tbl- Example: Random Tableaux
- Basic Access Functions
Shape(t): Tbl → SeqEnum[RngIntElt]OuterShape(t): Tbl → SeqEnumSkewShape(t): Tbl → SeqEnum[RngIntElt]InnerShape(t): Tbl → SeqEnum[RngIntElt]PartitionCovers(P1, P2): SeqEnum, SeqEnum → BoolEltConjugatePartition(P): SeqEnum → SeqEnumWeight(t): Tbl → RngIntEltSkewWeight(t): Tbl → RngIntEltNumberOfRows(t): Tbl → RngIntEltNumberOfSkewRows(t): Tbl → RngIntEltRow(t, i): Tbl, RngIntElt → MonOrdEltRows(t): Tbl → SeqEnum[MonOrdElt]Column(t, j): Tbl, RngIntElt → MonOrdEltColumns(t): Tbl → SeqEnum[MonOrdElt]RowSkewLength(t, i): Tbl, RngIntElt → RngIntEltColumnSkewLength(t, j): Tbl, RngIntElt → RngIntEltFirstIndexOfRow(t, i): Tbl, RngIntElt → RngIntEltLastIndexOfRow(t, i): Tbl, RngIntElt → RngIntEltRowLength(t, i): Tbl, RngIntElt → RngIntEltFirstIndexOfColumn(t, j): Tbl, RngIntElt → RngIntEltLastIndexOfColumn(t, j): Tbl, RngIntElt → RngIntEltColumnLength(t, j): Tbl, RngIntElt → RnfIntElt- Example: Properties of a Skew Tableau
- Properties
- Operations
t1 eq t2: MonPlcElt, MonPlcElt → BoolEltt1 * t2: Tbl, Tbl → TblDiagonalSum(t1, t2): Tbl, Tbl → TblConjugate(t): Tbl → TblJeuDeTaquin(~t, i, j): Tbl, RngIntElt, RngIntEltJeuDeTaquin(t, i, j): Tbl, RngIntElt, RngIntElt → TblJeuDeTaquin(~t): TblJeuDeTaquin(t): Tbl → TblRectify(~t): TblRectify(t): Tbl → TblInverseJeuDeTaquin(~t, i, j): Tbl, RngIntElt, RngIntEltInverseJeuDeTaquin(t, i, j): Tbl, RngIntElt, RngIntElt → TblRowInsert(~t, w): Tbl, MonOrdEltRowInsert(t, w): Tbl, MonOrdElt → TblRowInsert(~t, u): Tbl, MonPlcEltRowInsert(t, u): Tbl, MonPlcElt → TblRowInsert(~t, x): Tbl, RngIntEltRowInsert(t, x): Tbl, RngIntElt → TblInverseRowInsert(~t, i, j): Tbl, RngIntElt, RngIntEltInverseRowInsert(t, i, j): Tbl, RngIntElt, RngIntElt → Tbl, MonOrdElt- Example: Jeu de Taquin
- Example: Two Ways of Multiplying Tableaux
- The Robinson-Schensted-Knuth Correspondence
LexicographicalOrdering(~w1, ~w2): MonOrdElt, MonOrdEltLexicographicalOrdering(w1, w2): MonOrdElt, MonOrdElt → MonOrdElt, MonOrdEltIsLexicographicallyOrdered(w1, w2): MonOrdElt, MonOrdElt → booleanRSKCorrespondence(w): SeqEnum[RngIntElt] → Tbl, TblInverseRSKCorrespondenceSingleWord(t1, t2): Tbl, Tbl → MonOrdEltRSKCorrespondence(w1, w2): SeqEnum[RngIntElt], SeqEnum[RngIntElt] → Tbl, TblInverseRSKCorrespondenceDoubleWord(t1, t2): Tbl, Tbl → MonOrdElt, MonOrdEltRSKCorrespondence(M): Mtrx → Tbl, TblInverseRSKCorrespondenceMatrix(t1, t2): Tbl, Tbl → Mat- Example: RSK Correspondence for a Single Word
- Example: RSK Correspondence for Two Words
- Example: RSK Correspondence for Matrices
- Example: RSK Correspondence and Inverse Permutations
- Counting Tableaux
- Bibliography