Permutations, matrices, and generalized Young tableaux

DOI10.2140/pjm.1970.34.709zbMath0199.31901OpenAlexW2168316830WikidataQ106435008 ScholiaQ106435008MaRDI QIDQ2540557

Donald E. Knuth

Publication date: 1970

Published in: Pacific Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2140/pjm.1970.34.709

zbMATH Keywords

combinatorics

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Symmetric functions and generalizations (05E05) Orthogonal arrays, Latin squares, Room squares (05B15) Matrices of integers (15B36) Boolean and Hadamard matrices (15B34)

Related Items

Notes on Schubert, Grothendieck and key polynomials, Forbidden subsequences, Generalized Robinson-Schensted correspondence: A new algorithm, Recognizable subsets of the two letter plactic monoid, Duality of graded graphs, Word reading is a crystal morphism, Refined restricted involutions, Algorithms for constructing \((0,1)\)-matrices with prescribed row and column sum vectors, Crystal graphs for Lie superalgebras and Cauchy decomposition, An occurrence of the Robinson-Schensted correspondence, Variants of the RSK algorithm adapted to combinatorial Macdonald polynomials, Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes, Shifted tableaux, Schur q-functions, and a conjecture of R. Stanley, Initial algebras of Pfaffian rings, Permutation statistics and \((k,\ell)\)-hook Schur functions, Tableaux and matrix correspondences, Standard Young tableaux of height 4 and 5, Partially ordered sets associated with permutations, Shifted tableaux and the projective representations of symmetric groups, Counting permutations modulo pattern-replacement equivalences for three-letter patterns, A Pieri rule for skew shapes, An analog of Schensted's algorithm for shifted Young tableaux, A Polya interpretation of the Schur function, Sign under the domino Robinson-Schensted maps, Equivalence classes of permutations modulo replacements between 123 and two-integer patterns, Crystal \(B(\lambda)\) as a subset of crystal \(B(\infty)\) expressed as tableaux for \(A_n\) type, Kronecker products and the RSK correspondence., Gröbner bases of ideals cogenerated by Pfaffians, Type \(A\) molecules are Kazhdan-Lusztig, Littlewood identity and crystal bases, Monotonicity and unimodality of the pattern inventory, A generalization of the Littlewood-Richardson rule and the Robinson- Schensted-Knuth correspondence, On the equality of two plane partition correspondences, On the Kostka-Green-Foulkes polynomials and Clebsch-Gordan numbers, Polynomial ring generated by tableau shapes, On mixed insertion, symmetry, and shifted Young tableaux, Generalized Robinson-Schensted-Knuth correspondence, The Hillman-Grassl correspondence and the enumeration of reverse plane partitions, Tournaments and generalized Young tableaux, A plactic algebra of extremal weight crystals and the Cauchy identity for Schur operators, Symmetric functions and P-recursiveness, On the Lipschitz constant of the RSK correspondence, Enumeration of involutions by descents and symmetric matrices, Coinsertion and standard bitableaux, A symmetry property for \(q\)-weighted Robinson-Schensted and other branching insertion algorithms, The number of involutions with \(r\) fixed points and a long increasing subsequence, Generalized roinsertive correspondence between multitableaux and multimonomials, Enumerating \(r\)c-invariant permutations with no long decreasing subsequences, Geometric interpretation of Murphy bases and an application., Finite Gröbner-Shirshov bases for plactic algebras and biautomatic structures for plactic monoids., New approaches to plactic monoid via Gröbner-Shirshov bases., Generalized rodeletive correspondence between multitableaux and multimonomials, Algorithms for generating labelled graphs with given degree, Zonal polynomials and domino tableaux, Dual equivalence with applications, including a conjecture of Proctor, Classical partition functions and the \(U(n+1)\) Rogers-Selberg identity, Crystallizing the hypoplactic monoid: from quasi-Kashiwara operators to the Robinson-Schensted-Knuth-type correspondence for quasi-ribbon tableaux, On the Schur expansion of Hall-Littlewood and related polynomials via Yamanouchi words, Enumeration of generalized Young tableaux with bounded height, Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm, Gröbner bases and multiplicity of determinantal and Pfaffian ideals, Hall-Littlewood polynomials and fixed point enumeration, A Robinson-Schensted-type correspondence for a dual pair on spinors, Reflection and algorithm proofs of some more Lie group dual pair identities, Generalized coinsertion and standard multitableaux, Counting paths in Young's lattice, An extension of Schensted's theorem, Evacuation and a geometric construction for Fibonacci tableaux, The algebra of binary search trees, Rational tableaux and the tensor algebra of \(gl_ n\), Minimal permutations and 2-regular skew tableaux, Young diagrams, Schur functions, the Gale-Ryser theorem and a conjecture or Snapper, Demazure crystals of generalized Verma modules and a flagged RSK correspondence, Bijections between oscillating tableaux and (semi)standard tableaux via growth diagrams, Structure constants for \(K\)-theory of Grassmannians, revisited, On Schensted's construction and the multiplication of Schur functions, \(k\)-ribbon Fibonacci tableaux, A combinatorial proof of a Weyl type formula for hook Schur polynomials, An explicit construction of type A Demazure atoms, Percentage-avoiding, northwest shapes and peelable tableaux, Some aspects of sorting in two dimensions, Multicolored permutations, sequences, and tableaux, Identities for classical group characters of nearly rectangular shape, Enumeration of bilaterally symmetric 3-noncrossing partitions, On (0, 1)-matrices with prescribed row and column sum vectors, A characteristic property of labelings and linear extensions of posets of dimension 2, The longest almost-increasing subsequence, Crystal graphs for general linear Lie superalgebras and quasi-symmetric functions, Multiplying Schur \(Q\)-functions, Enumerative aspects of certain subclasses of perfect graphs, Hook flag characters and their combinatorics, A Schensted algorithm for rim hook tableaux, W-graphs of representations of symmetric groups, Hybrid tableaux and the Littlewood-Richardson rule, Robinson-Schensted algorithms for skew tableaux, Counting permutations with given cycle structure and descent set, Multivariate polynomials, standard tableaux, and representations of symmetric groups, The estimate of the number of permutationally-ordered sets, Shuffles of permutations and the Kronecker product, Asymptotics of maximal and typical dimensions of irreducible representations of a symmetric group, Limit shape for infinite rank limit of tensor power decomposition for Lie algebras of series so2n+1 ^*, ON THE IDEALS OF MINORS OF PLURI-CIRCULANT MATRICES, The Schensted Correspondence and Lexicographic Matchings on Multisubset Lattices, Acyclic Digraphs, Young Tableaux and Nilpotent Matrices, THE CHINESE MONOID, The Characters of the Infinite Symmetric Group and Probability Properties of the Robinson–Schensted–Knuth Algorithm, A bijective proof of a factorization theorem for (k,l)-hook schur functions, Dominance method for plane partitions. IV: Enumeration of flagged skew tableaux, Straightening Bases for Tensor Products, Interview with Bruce Sagan, Growth diagrams from polygons in the affine Grassmannian, Dual equivalence graphs and CAT(0) combinatorics, Unnamed Item, On the Littlewood-Richardson rule in terms of lattice path combinatorics, Schröder partitions, Schröder tableaux and weak poset patterns, Estimates in Shirshov height theorem, Unnamed Item, Super jeu de taquin and combinatorics of super tableaux of type A, Unnamed Item, Theory and Application of Plane Partitions: Part 1, Theory and Application of Plane Partitions. Part 2, Transition between characters of classical groups, decomposition of Gelfand-Tsetlin patterns and last passage percolation, Identities of tropical matrix semigroups and the plactic monoid of rank 4, The sum of all width-one matrices, A new approach to word standardization and some of its applications, The oriented swap process and last passage percolation, Rigged configuration descriptions of the crystals B(∞) and B(λ) for special linear Lie algebras, Finite basis problems for stalactic, taiga, sylvester and baxter monoids, Skew RSK dynamics: Greene invariants, affine crystals and applications toq-Whittaker polynomials, Box-ball systems and RSK tableaux, Muttalib-Borodin plane partitions and the hard edge of random matrix ensembles, A Maple package for combinatorial aspects of Bethe ansatz, Grothendieck-to-Lascoux expansions, Peaks of cylindric plane partitions, Non-intersecting path constructions for TASEP with inhomogeneous rates and the KPZ fixed point, Monk's rule for Demazure characters of the general linear group, RSK tableaux and the weak order on fully commutative permutations, Counting crucial permutations with respect to monotone patterns, Computing longest Lyndon subsequences and longest common Lyndon subsequences, Top-degree components of Grothendieck and Lascoux polynomials, Hasimoto frames and the Gibbs measure of the periodic nonlinear Schrödinger equation, Tropical representations and identities of the stylic monoid, Simple modules for quiver Hecke algebras and the Robinson–Schensted–Knuth correspondence, RSK tableaux and box-ball systems, Representations and identities of hypoplactic monoids with involution, The number of inversions of permutations with fixed shape, Permutations whose reverse shares the same recording tableau in the RS correspondence, On the action of the long cycle on the Kazhdan-Lusztig basis, Fused braids and centralisers of tensor representations of \(U_q(gl_{N})\), Chess tableaux, powers of two and affine Lie algebras, HALF-SPACE MACDONALD PROCESSES, Plactic key agreement (insecure?), Identities and bases in the Sylvester and Baxter monoids, Rogers-Ramanujan identities and the Robinson-Schensted-Knuth correspondence, The Preisach graph and longest increasing subsequences, Combinatorial approach to the representation of the Schur-Weyl duality in one-dimensional spin systems, Ribbon tableaux, Hall–Littlewood functions, quantum affine algebras, and unipotent varieties, Symmetric functions in noncommuting variables, Random Sampling of Plane Partitions, GRASSMANNIAN SEMIGROUPS AND THEIR REPRESENTATIONS, Inner tableau translation property of the weak order and related results, Large Parts of Random Plane Partitions: a Poisson Limit Theorem, Equivalence Classes for the μ-Coefficient of Kazhdan–Lusztig Polynomials inS_n, ROBINSON-SCHENSTED CORRESPONDENCE FOR THE G-VERTEX COLORED PARTITION ALGEBRA, Skew Schubert functions and the Pieri formula for flag manifolds, Gröbner–Shirshov bases and their calculation, A cyclage poset structure for Littlewood-Richardson tableaux, Multi-atoms and monotonicity of generalized Kostka polynomials, An inversion formula involving partitions, Restricted permutations, A Matrix-analog for Viennot's construction of the Robinson correspondence^†, Dominance method for plane partitions III-flagged skew plane partitions, On the Foundations of Combinatorial Theory: IX Combinatorial Methods in Invariant Theory, A Solomon descent theory for the wreath products $G\wr\mathfrak S_n$, Robinson–Schensted–Knuth Correspondence and Weak Polynomial Identities of M_1,1(E), Minuscule reverse plane partitions via quiver representations, Crystal Graphs and the Combinatorics of Young Tableaux, Inverses of words and the parabolic structure of the symmetric group, Complementary algorithms for tableaux, A generalization of the Kostka-Foulkes polynomials, The shifted plactic monoid, Tableau correspondences and representation theory, Unnamed Item, GENERALIZATION OF THE SCHENSTED ALGORITHM FOR RIM HOOK TABLEAUX, THE JEU DE TAQUIN ON THE SHIFTED RIM HOOK TABLEAUX, Virtual crystals and fermionic formulas of type 𝐷_{𝑛+1}⁽²⁾, 𝐴_{2𝑛}⁽²⁾, and 𝐶_{𝑛}⁽¹⁾, Generating functions for SU(2) plethysms with fixed exchange symmetry, Tropical representations and identities of plactic monoids, Queues, stores, and tableaux, SUPER RSK-ALGORITHMS AND SUPER PLACTIC MONOID, Enumeration of plane partitions, The conjugate trace and trace of a plane partition, Quantum field theory meets Hopf algebra, Effective scalar products of D-finite symmetric functions, Robinson–Schensted–Knuth correspondence in the representation theory of the general linear group over a non-archimedean local field, SOME PROPERTIES OF SCHENSTED ALGORITHM USING VIENNOT'S GEOMETRIC INTERPRETATION, Unnamed Item, Identities and bases in the hypoplactic monoid, A note on the Formanek Weingarten function, Coherence for plactic monoids via rewriting theory and crystal structures, Skew Howe duality and limit shapes of Young diagrams, Invariance of polymer partition functions under the geometric RSK correspondence, Tableau atoms and a new Macdonald positivity conjecture, Hall-Littlewood RSK field, \(P\)-partitions and the plactic congruence, Longest increasing subsequences in sliding windows, RSK in last passage percolation: a unified approach, Crystal monoids \& crystal bases: rewriting systems and biautomatic structures for plactic monoids of types \(A_{n}\), \(B_{n}\), \(C_{n}\), \(D_{n}\), and \(G_{2}\), Interpretation of a basic hypergeometric identity with Lie characters and Young tableaux, Schensted algorithms for dual graded graphs, An alternative presentation of the Schensted correspondence, Splitting the square of a Schur function into its symmetric and antisymmetric parts, The Robinson-Schensted correspondence for skew oscillating tableaux, The Euler-Mahonian distributions over the words, Eulerian calculus. III: The ubiquitous Cauchy formula, Plactification, Schur operators and Knuth correspondences, Crystal graphs and \(q\)-analogues of weight multiplicities for the root system \(A_ n\), Orthosymplectic Cauchy identities, Interlacing and scaling exponents for the geodesic watermelon in last passage percolation, The Selberg-Jack symmetric functions, The stylic monoid, Genomic tableaux, Noncommutative symmetric functions. IV: Quantum linear groups and Hecke algebras at \(q=0\), Quasisymmetric and noncommutative skew Pieri rules, Computing the longest common almost-increasing subsequence, Gröbner bases of powers of ideals of maximal minors, Irreducible representations of the plactic algebra of rank four, Computing longest (common) Lyndon subsequences, A \(q\)-Robinson-Schensted-Knuth algorithm and a \(q\)-polymer, An insertion algorithm on multiset partitions with applications to diagram algebras, Crystal algebra, Tableau algorithms defined naturally for pictures, The bijection between plane partitions and nonnegative matrices, Knuth's coherent presentations of plactic monoids of type A, New results on families of pattern-replacement equivalences, Spectral analysis of random-to-random Markov chains, Super RSK correspondence with symmetry, Promotion des morphismes d'ensembles ordonnes, Two-row \(W\)-graphs in affine type \(A\), Revisiting pattern avoidance and quasisymmetric functions, An insertion algorithm for diagram algebras, Limit theorems for longest monotone subsequences in random Mallows permutations, Plactic monoids: a braided approach, Plane overpartitions and cylindric partitions, Estimate of time needed for a coordinate of a Bernoulli scheme to fall into the first column of a Young tableau, The Ehrhart polynomial of the Birkhoff polytope, Monotonous subsequences and the descent process of invariant random permutations, Automedian sets of permutations: direct sum and shuffle, Computing a longest common almost-increasing subsequence of two sequences, Plactic algebras., Tropical plactic algebra, the cloaktic monoid, and semigroup representations, \(R\)-systems, Schubert polynomials, the Bruhat order, and the geometry of flag manifolds, Flag varieties and interpretations of Young tableau algorithms, Geometric combinatorics of Kalman algebras, Quantum spectrum testing, Iterating the RSK bijection, Rational semistandard tableaux and character formula for the Lie superalgebra \(\widehat{\mathfrak{gl}}_{\infty|\infty}\), The ABC of \(p\)-cells, Symmetrized models of last passage percolation and non-intersecting lattice paths, Dual equivalence graphs revisited and the explicit Schur expansion of a family of LLT polynomials, The Robinson-Schensted correspondence for skew oscillating semi-standard tableaux, A new link between the descent algebra of type B, domino tableaux and Chow's quasisymmetric functions, An analogue of the Robinson-Schensted-Knuth correspondence and non-symmetric Cauchy kernels for truncated staircases, Interpretations of some parameter dependent generalizations of classical matrix ensembles, Performance evaluation of demodulation with diversity -- a combinatorial approach. II: Bijective methods, Unipotent Hecke algebras of \(\text{GL}_n(\mathbb{F}_q)\)., Factorization of the Robinson-Schensted-Knuth correspondence, Noncommutative Schur functions and their applications. (Reprint), Action of the symmetric group on sets of skew-tableaux with prescribed matrix realization, Properties of four partial orders on standard Young tableaux, Generating functions for plane partitions of a given shape, A Nekrasov-Okounkov formula for Macdonald polynomials, On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients, Dual filtered graphs, Zigzag diagrams and Martin boundary, Bases for coordinate rings of conjugacy classes of nilpotent matrices, Bijection between indexed monomials and standard bitableaux, The geometric Burge correspondence and the partition function of polymer replicas, Toward a local characterization of crystals for the quantum queer superalgebra, Combinatorics of patience sorting monoids, Balanced tableaux, \(3d\) field theory, plane partitions and triple Macdonald polynomials, Greene-Kleitman invariants for Sulzgruber insertion, A combinatorial realization of Kirillov-Reshetikhin crystals for type E arising from translations, Chinese syzygies by insertions, Gröbner bases and Stanley decompositions of determinantal ideals, On-line scheduling with monotone subsequence constraints, On the number of faces of certain transportation polytopes, Noncommutative Schur functions and their applications, A combinatorial proof of a recursion for the \(q\)-Kostka polynomials, Four correspondences between graphs and generalized Young tableaux, Position sequences and a \(q\)-analogue for the modular hook length formula, Grammic monoids with three generators, Lengths of monotone subsequences in a Mallows permutation, Affine type A crystal structure on tensor products of rectangles, Demazure characters, and nilpotent varieties, The Burge correspondence and crystal graphs, From Hertzsprung's problem to pattern-rewriting systems, A new class of Wilf-equivalent permutations, Spin \(q\)-Whittaker polynomials and deformed quantum Toda