View source for Pictures

A class of bijections (cf. [[Bijection|Bijection]]) between subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101301.png" />, namely skew diagrams. A skew diagram is a finite subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101302.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101303.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101304.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101305.png" />, where  "≤"  is the coordinatewise partial ordering of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101306.png" />; a typical skew diagram is the difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101307.png" /> of two Young diagrams (cf. [[Young diagram|Young diagram]]) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101308.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101309.png" />. The definition of pictures also uses another partial ordering  "≤"  on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013010.png" />, given by

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013011.png" /></td> </tr></table>

(sometimes the opposite ordering is used instead); a bijection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013012.png" /> between two skew diagrams is a picture if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013013.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013015.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013016.png" />. The set of all pictures has various symmetries, among which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013017.png" />.

When domain and image are fixed to certain shapes, pictures become equivalent to many other combinatorial concepts, such as permutations, (semi-) standard Young tableaux, skew tableaux, Littlewood–Richardson fillings, and matrices over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013018.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013019.png" /> with prescribed row and column sums. On the other hand, any picture gives rise to a semi-standard skew tableau by projecting its images onto their first coordinate. For any skew diagrams <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013021.png" />, the number of pictures <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013022.png" /> is equal to the [[Intertwining number|intertwining number]] of representations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013024.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013025.png" />, or of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013026.png" />, see [[#References|[a5]]]. In particular, the number of pictures from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013027.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013028.png" />, for Young diagrams <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013029.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013031.png" />, is the multiplicity of the [[Irreducible representation|irreducible representation]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013032.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013033.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013034.png" />; this is essentially the Littlewood–Richardson rule.

There is a natural bijection between pictures <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013035.png" />, for arbitrary skew shapes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013037.png" />, and pairs of pictures <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013039.png" />, for some Young diagram <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013040.png" />. This is a generalization of the [[Robinson–Schensted correspondence|Robinson–Schensted correspondence]], and it agrees with the intertwining number interpretation. It also gives a decomposition of skew Schur polynomials into ordinary Schur polynomials, generalizing the decomposition of the character of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013041.png" /> mentioned in [[Robinson–Schensted correspondence|Robinson–Schensted correspondence]], and thereby provides a proof of the Littlewood–Richardson rule; this is closely related to the reason that correspondence was originally introduced in [[#References|[a3]]]. Like the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013042.png" />-symbol in the ordinary Robinson–Schensted correspondence, the picture <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013043.png" /> can not only be computed from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013044.png" /> by an insertion procedure, but also by using the [[Jeu de taquin|jeu de taquin]] (see [[#References|[a4]]]), to gradually transform the domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013045.png" /> into a Young diagram <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013046.png" />. By the symmetry <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013047.png" />, the picture <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013048.png" /> can also be computed by the jeu de taquin at the image side, to transform the image <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013049.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013050.png" />. The steps of these two forms of the jeu de taquin commute with each other, and this provides a key to many properties of the Robinson–Schensted correspondence [[#References|[a2]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S. Fomin,   C. Greene,   "A Littlewood–Richardson miscellany"  ''European J. Combinatorics'' , '''14'''  (1993)  pp. 191–212</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M.A.A. van Leeuwen,   "Tableau algorithms defined naturally for pictures"  ''Discrete Math.'' , '''157'''  (1996)  pp. 321–362</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G. de B. Robinson,   "On the representations of the symmetric group"  ''Amer. J. Math.'' , '''60'''  (1938)  pp. 745–760</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  M.P. Schützenberger,   "La correspondance de Robinson"  D. Foata (ed.) , ''Combinatoire et Représentation du Groupe Symétrique'' , ''Lecture Notes in Mathematics'' , '''579''' , Springer  (1976)  pp. 59–113</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A.V. Zelevinsky,   "A generalisation of the Littlewood–Richardson rule and the Robinson–Schensted–Knuth correspondence"  ''J. Algebra'' , '''69'''  (1981)  pp. 82–94</TD></TR></table>