| dbo:abstract
|
- In mathematics, the Robinson–Schensted correspondence is a bijective correspondence between permutations and pairs of standard Young tableaux of the same shape. It has various descriptions, all of which are of algorithmic nature, it has many remarkable properties, and it has applications in combinatorics and other areas such as representation theory. The correspondence has been generalized in numerous ways, notably by Knuth to what is known as the Robinson–Schensted–Knuth correspondence, and a further generalization to pictures by Zelevinsky. The simplest description of the correspondence is using the Schensted algorithm (Schensted ), a procedure that constructs one tableau by successively inserting the values of the permutation according to a specific rule, while the other tableau records the evolution of the shape during construction. The correspondence had been described, in a rather different form, much earlier by Robinson (Robinson ), in an attempt to prove the Littlewood–Richardson rule. The correspondence is often referred to as the Robinson–Schensted algorithm, although the procedure used by Robinson is radically different from the Schensted algorithm, and almost entirely forgotten. Other methods of defining the correspondence include a nondeterministic algorithm in terms of jeu de taquin. The bijective nature of the correspondence relates it to the enumerative identity where denotes the set of partitions of n (or of Young diagrams with n squares), and tλ denotes the number of standard Young tableaux of shape λ. (en)
- En mathématiques, et notamment en combinatoire algébrique, la correspondance de Robinson-Schensted est une bijection entre permutations et paires de tableaux de Young standard de même forme. Cette bijection peut être décrite de diverses manières, toutes algorithmiques. Elle a de nombreuses propriétés remarquables, et des applications en combinatoire et dans d'autres domaines comme la représentation des groupes finis. La correspondance a été généralisée de plusieurs façons, notamment par Knuth en ce qui est connu maintenant comme la correspondance de Robinson-Schensted-Knuth, et plus généralement encore en des objets appelés figures par Zelevinsky. La description la plus simple de la correspondance est par l'algorithme de Schensted, une procédure qui construit un tableau par insertion successive des valeurs d'une permutation selon une règle précises, et un deuxième tableau qui enregistre l'évolution de la forme pendant la construction. La correspondance a été décrite, dans une forme différente, bien plus tôt par Gilbert de Beauregard Robinson dans , dans une tentative de preuve de la règle de Littlewood-Richardson. La correspondance est souvent appelée l'algorithme de Robinson-Schensted , alors que la procédure employée par Robinson est radicalement différente de celle de Schensted, et est presque totalement oubliée. Parmi les autres méthodes pour définir la correspondance, il y a un algorithme non déterministe basé sur le jeu de taquin de Schützenberger. La nature bijective de la correspondance se reflète dans des identités combinatoires comme : où la somme est sur les partitions de (ou des diagrammes de Young avec carrés), et est le nombre de tableaux de Young standard de forme . (fr)
- Алгоритм Робинсона — Шенстеда — комбинаторный алгоритм, впервые описанный в 1938, который устанавливает биективное соответствие между элементами симметрической группы и парами стандартных таблиц Юнга той же формы. Он может рассматриваться как простое конструктивное доказательство тождества где означает, что пробегает все разбиения и — количество стандартных диаграмм Юнга формы . Это достигается путём построения отображения из пар -таблиц в перестановки . (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 14302 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:author
| |
| dbp:authorlink
|
- Gilbert de Beauregard Robinson (en)
|
| dbp:first
| |
| dbp:id
| |
| dbp:last
|
- Robinson (en)
- van Leeuwen (en)
- Schensted (en)
|
| dbp:title
|
- Robinson–Schensted correspondence (en)
|
| dbp:wikiPageUsesTemplate
| |
| dbp:year
|
- 1938 (xsd:integer)
- 1961 (xsd:integer)
|
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Алгоритм Робинсона — Шенстеда — комбинаторный алгоритм, впервые описанный в 1938, который устанавливает биективное соответствие между элементами симметрической группы и парами стандартных таблиц Юнга той же формы. Он может рассматриваться как простое конструктивное доказательство тождества где означает, что пробегает все разбиения и — количество стандартных диаграмм Юнга формы . Это достигается путём построения отображения из пар -таблиц в перестановки . (ru)
- In mathematics, the Robinson–Schensted correspondence is a bijective correspondence between permutations and pairs of standard Young tableaux of the same shape. It has various descriptions, all of which are of algorithmic nature, it has many remarkable properties, and it has applications in combinatorics and other areas such as representation theory. The correspondence has been generalized in numerous ways, notably by Knuth to what is known as the Robinson–Schensted–Knuth correspondence, and a further generalization to pictures by Zelevinsky. (en)
- En mathématiques, et notamment en combinatoire algébrique, la correspondance de Robinson-Schensted est une bijection entre permutations et paires de tableaux de Young standard de même forme. Cette bijection peut être décrite de diverses manières, toutes algorithmiques. Elle a de nombreuses propriétés remarquables, et des applications en combinatoire et dans d'autres domaines comme la représentation des groupes finis. La correspondance a été généralisée de plusieurs façons, notamment par Knuth en ce qui est connu maintenant comme la correspondance de Robinson-Schensted-Knuth, et plus généralement encore en des objets appelés figures par Zelevinsky. (fr)
|
| rdfs:label
|
- Correspondance de Robinson-Schensted (fr)
- Robinson–Schensted correspondence (en)
- Алгоритм Робинсона — Шенстеда (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
