Improve this page

#Preliminaries

We use standard notation, \(\setN\) is the set of natural numbers \(\{0,1,2,\dotsc\}\) and \([n]\coloneqq \{1,2,\dotsc,n\}.\)

#Partitions

A partition is a weakly decreasing sequence of positive integers, referred to as parts. A partition \(\lambda\) can be described as \(1^{m_1},2^{m_2},\dotsc,k^{m_k}\) where \(m_i\) is the number of parts of \(\lambda\) equal to \(i.\) The type of \(\lambda\) is the vector \((m_1,\dotsc,m_k).\) For example, the partition \(444332111111\) can in a more compact form be described as \(1^6,2^1,3^2,4^3,\) and it has type \((6,1,2,3).\)

Partitions may be illustrated as Young diagrams.

Example

Consider \(\lambda=(7,5,5,4,3).\) There are two common ways to draw \(\lambda\) as a Young diagram: the English way — which is what is mainly used here — and the French way. The English way uses matrix coordinates while the French way uses Cartesian coordinates in the first quadrant. The lengths of the rows are determined by the parts of \(\lambda.\)

$\circ $               $ \circ $               $ \circ $               $ \circ$                                                                                          

There is a third way to describe a partition, using Frobenius coordinates. Let \(d\) be the number of boxes on the main diagonal in the Young diagram of \(\lambda.\) This is the Durfee size of \(\lambda.\) The Frobenius coordinates of \(\lambda\) are given by \((a_1,a_2,\dotsc,a_d|b_1,b_2,\dotsc,b_d)\) where \(a_i = \lambda_i-i\) is the number of boxes to the right of the diagonal in row \(i,\) and \(b_i = \lambda'_i-i\) is the number of boxes below the diagonal in column \(i.\) In the figure above, \(d=4\) and \(\lambda=(6,3,2,0|4,3,2,0).\)

The conjugate of a partition \(\lambda\) is denoted \(\lambda',\) and corresponds to transposing the (English) Young diagram. Thus, the conjugate of \((7,5,5,4,3)\) is \((5,5,5,4,3,1,1),\) which is simply the sizes of the columns.

#Compositions and weak compositions

A composition of \(n\) is a vector with positive integer entries summing to \(n.\) Hence, every partition is a composition. These are also sometimes called strong compositions. It is a classical exercise to show that there are \(2^{n-1}\) compositions of \(n.\)

Example (Compositions of 4).

The compositions of \(4\) are \[(4), (3,1), (1,3), (2,2), (2,1,1), (1,2,1), (1,1,2), (1,1,1,1).\]

A weak composition of \(n\) is a vector with non-negative integer entries summing to \(n.\) Weak compositions are often considered with a fixed length. For example, the weak compositions of \(3\) of length \(2\) are \[(3,0),\quad (2,1),\quad (1,2),\quad (0,3).\]

#Partial orderings on partitions

We write \(\lambda \supseteq \mu\) if \(\lambda_i \geq \mu_i\) for all \(i.\) The dominance order is defined as \[\lambda \trianglerighteq \mu \text{ whenever } \lambda_1+\dotsb + \lambda_i \geq \mu_1 + \dotsb + \mu_i \text{ for all $i$}.\] Dominance order is defined in the same manner for compositions and weak compositions.

#Skew shapes and ribbons

If \(\lambda \supseteq \mu,\) we let \(\lambda/\mu\) denote the set of boxes in the Young diagram of \(\lambda\) which do not appear in \(\mu.\) We say that \(\lambda/\mu\) is a skew shape.

A skew shape is a ribbon if it is connected and does not contain a \(2\times 2\)-arrangement of boxes. The following figure illustrates a \(12\)-ribbon, as it has \(12\) boxes.

              $ h$                                                                 $ t $              

Ribbons are sometimes called border strips or rim hooks. Ribbons play a special role in the definition of border-strip tableaux. The head of a ribbon is the rightmost box in the first row of the ribbon, while the tail is the leftmost box in the last row of the ribbon.

#Statistics on partitions

Define \(\partitionN(\lambda) \coloneqq \sum_i (i-1) \lambda_i = \sum_{i \geq 2} \binom{\lambda'_i}{2}\) and let \(z_\lambda \coloneqq \prod_j \left( m_j! j^{m_j} \right)\) where \(m_i\) is the number of parts of \(\lambda\) of size \(i.\)

Note that \(z_\lambda\) is the number of elements in \(\symS_n\) that fix \(g_\lambda\) under conjugation, where \(g_\lambda\) is some fixed permutation of type \(\lambda.\) That is, \[z_\lambda = |\{ \sigma \in \symS_n : \sigma g_\lambda \sigma^{-1} = g_\lambda \}|.\] The \(z_\lambda\) often shows up as a normalizing factor when dealing with power-sum symmetric functions, and in particular, in the Hall inner product.

#Hook lengths and cores

Given a box \((i,j)\) in the Ferrers diagram of \(\lambda,\) the hook length of the box is given by \(1 + (\lambda_i-j) + (\lambda'_j-i).\) For example, the hook length in the diagram below has been written in each box.

$11$ $ 10$ $ 9 $ $ 7 $ $ 5 $ $ 2 $ $ 1$ $ 8 $ $ 7 $ $ 6 $ $ 4 $ $ 2$     $ 7 $ $ 6 $ $ 5 $ $ 3 $ $ 1$     $ 5 $ $ 4 $ $ 3 $ $ 1$       $ 3 $ $ 2 $ $ 1$        

The content of a box \((i,j)\) is \(j-i,\) where \(j\) is the column index, and \(i\) is the row index.

A \(p\)-core is a partition for which none of the hook lengths are divisible by \(p.\) A closely related concept is the notion of partition quotients.

The hook formula states that \[|\SYT(\lambda)| = \frac{n!}{\prod_{\square \in \lambda} h(\square)},\] where \(h(\square)\) denotes the hook length of the box. There is a \(q\)-analog of this identity.

There is a more complicated formula for skew diagrams, due to H. Naruse [Nar14]. For a proof, see A. Morales–I. Pak–G. Panova [MPP18]. An extension to cylindric diagrams is conjectured in [ST21].

#Permutations and words

The set of permutations of \(n\) elements is denoted \(\symS_n.\)

#Descents and major index

Let \(\pi \in \symS_n,\) or more generally, a word of length \(n.\) The descent set \(\DES(\pi)\subseteq [n-1]\) is defined as \[\DES(\pi) \coloneqq \{i \in [n-1] : \pi_i \gt \pi_{i+1} \}.\] The set of inversions is the set of pairs, \[\INV(\pi) \coloneqq \{(i,j) : 1\leq i\lt j\leq n,\ \pi_i \gt \pi_{j} \}.\] We define the inversion number and major index on permutations and words by \[\inv(\pi) \coloneqq |\INV(\pi)| \text{ and } \maj(\pi) \coloneqq \sum_{i \in \DES(\pi)} i.\] For permutations, we also define charge as \[\charge(\pi) \coloneqq \maj(\rev(\pi^{-1})) \text{ and } \cocharge(\pi) \coloneqq \binom{n}{2} - \charge(\pi).\] The latter statistic is called cocharge.

Lemma

For every permutation \(\pi,\) \[\charge(\pi) = \inv\!\left(\mathrm{foata}(\rev(\pi^{-1}))\right),\] where \(\mathrm{foata}\) denotes the map sending major index to inversions [Foa68].

For charge on words and tableaux, and its role in Kostka–Foulkes polynomials, see the Kostka–Foulkes page.

The weight or type of a word \(w\) is the composition \(\alpha\) such that \(\alpha_i\) is the number of entries in \(w\) equal to \(i.\)

A word \(w_1,\dotsc,w_n\) is called Yamanouchi if the number of occurrences of \(i\) is at least as many as the number of occurrences of \(i+1\) in every prefix \(w_1,\dotsc,w_k.\) Such words are also known as ballot words; see A000085.

For reduced words and the Bruhat order, see the permutations page. For affine permutations and other generalizations, see the generalizations page.

#Tableaux

A tableau is a filling of the boxes determined by a partition, or sometimes a more general configuration of boxes.

The reading word of a tableau is the word obtained by concatenating the rows, starting from the bottom row in English notation.

The set of standard Young tableaux of shape \(\lambda,\) denoted \(\SYT(\lambda),\) is the set of bijective fillings \(\lambda \to [n],\) such that rows and columns are increasing with row and column index. The set of semistandard Young tableaux, \(\SSYT(\lambda),\) is defined as the set of fillings with entries in \(\setP,\) with weakly increasing rows and strictly increasing columns. We let \(\SSYT(\lambda,\mu)\) denote the finite set of semistandard Young tableaux of type \(\mu\) with shape \(\lambda,\) that is, there are \(\mu_i\) entries equal to \(i\) in each such tableau.

Example

Consider the following tableau \(T.\)

$1 $ $ 2 $ $ 5 $ $ 7$ $ 3 $ $ 4$     $ 6$      

The reading word of \(T\) is \(6341257,\) denoted \(\rw(T).\) Note that if \(T\) is a standard or semistandard Young tableau, then \(T\) is uniquely determined by its reading word.

Whenever \(T \in \SYT(\lambda),\) we define \(\charge(T)\) and \(\cocharge(T)\) as the charge and cocharge, respectively, of their reading words.

Given \(T \in \SYT(\lambda),\) the tableau descent set is \[\DES(T) \coloneqq \{i \in [n-1] : i+1 \text{ appears in a lower row than } i \}.\] The tableau major index is \(\maj(T) \coloneqq \sum_{i \in \DES(T)} i.\) Thus, \(\maj(T) = \maj(\rw(T)^{-1}).\)

#Semistandard tableaux as lattice paths

See the main section about the Lindström–Gessel–Viennot lemma applied to count semistandard Young tableaux using a determinant.

#SYT as Yamanouchi words

The set \(\SYT(\lambda)\) is in bijection with Yamanouchi words with weight \(\lambda.\) The bijection \(f(T)=w\) is given by \(w_i = j\) if \(i\) occurs in row \(j\) of \(T.\) This map can be quite useful at times, and is usually called the companion map. Note that \(\maj(T) = \binom{n}{2}-\maj(w).\)

There are 10 Yamanouchi words of length \(4,\) and these are in bijection with the 10 standard Young tableaux with \(4\) boxes.

Example

We have the following \(10\) Yamanouchi words: \[\mathtt{1111},\, \mathtt{1112},\, \mathtt{1121},\, \mathtt{1211},\, \mathtt{1122},\, \mathtt{1212},\, \mathtt{1123},\, \mathtt{1213},\, \mathtt{1231},\, \mathtt{1234}.\] The standard Young tableaux are

$1$ $2$ $3$ $4$ $1$ $2$ $3$ $4$     $1$ $2$ $4$ $3$     $1$ $3$ $4$ $2$     $1$ $2$ $3$ $4$ $1$ $3$ $2$ $4$ $1$ $2$ $3$   $4$   $1$ $3$ $2$   $4$   $1$ $4$ $2$   $3$   $1$ $2$ $3$ $4$

#SSYT as lattice points in a polytope

Semistandard Young tableaux are in bijection with Gelfand–Tsetlin patterns, which are lattice points in Gelfand–Tsetlin polytopes.

#The companion map

In [KM19, Def. 15], the authors describe a companion map, which interchanges the role of shape and weight of fillings.

Bibliography

  1. [Foa68]Dominique Foata. On the Netto inversion number of a sequence. Proceedings of the American Mathematical Society, 19(1):236–240, February 1968.
    .bib
    @article{Foata1968,
  title = {On the {N}etto inversion number of a sequence},
  volume = {19},
  ISSN = {1088-6826},
  url = {http://dx.doi.org/10.1090/S0002-9939-1968-0223256-9},
  DOI = {10.1090/s0002-9939-1968-0223256-9},
  number = {1},
  journal = {Proceedings of the American Mathematical Society},
  publisher = {American Mathematical Society (AMS)},
  author = {Foata,  Dominique},
  year = {1968},
  month = feb,
  pages = {236--240}
}
  2. [KM19]Ryan Kaliszewski and Jennifer Morse. Colorful combinatorics and Macdonald polynomials. European Journal of Combinatorics, 81:354–377, October 2019.
    .bib
    @article{KaliszewskiMorse2019,
  doi = {10.1016/j.ejc.2019.05.006},
  url2 = {https://doi.org/10.1016/j.ejc.2019.05.006},
  year = {2019},
  month = oct,
  publisher = {Elsevier {BV}},
  volume = {81},
  pages = {354--377},
  author = {Ryan Kaliszewski and Jennifer Morse},
  title = {Colorful combinatorics and {M}acdonald polynomials},
  journal = {European Journal of Combinatorics}
}
  3. [MPP18]Alejandro H. Morales, Igor Pak and Greta Panova. Hook formulas for skew shapes I. $q$-analogues and bijections. Journal of Combinatorial Theory, Series A, 154:350–405, February 2018.
    .bib
    @article{MoralesPakPanova2018,
  doi = {10.1016/j.jcta.2017.09.002},
  url2 = {https://doi.org/10.1016/j.jcta.2017.09.002},
  year  = {2018},
  month = feb,
  publisher = {Elsevier {BV}},
  volume = {154},
  pages = {350--405},
  author = {Alejandro H. Morales and Igor Pak and Greta Panova},
  title = {Hook formulas for skew shapes {I}.  $q$-analogues and bijections},
  journal = {Journal of Combinatorial Theory,  Series A}
}
  4. [Nar14]Hiroshi Naruse. Schubert calculus and hook formula. Online, 2014. Talk slides at 73rd Sem. Lothar. Combin., Strobl, Austria, 2014
    .bib
    @misc{Naruse2014slides,
  author = {Hiroshi Naruse},
  title = {Schubert calculus and hook formula},
  howpublished = {Online},
  year = {2014},
  note = {Talk slides at 73rd Sem. Lothar. Combin., Strobl, Austria, 2014},
  url = {https://www.emis.de/journals/SLC/wpapers/s73vortrag/naruse.pdf}
}
  5. [ST21]Takeshi Suzuki and Yoshitaka Toyosawa. On hook formulas for cylindric skew diagrams. arXiv:2106.09254, 2021.
    .bib
    @article{SuzukiToyosawa2021x,
Author = {Takeshi Suzuki and Yoshitaka Toyosawa},
Title = {On Hook Formulas for Cylindric Skew Diagrams},
Year = {2021},
Eprint = {2106.09254},
  url = {https://arxiv.org/abs/2106.09254},
journal = {arXiv e-prints}
}

I use cookies to detect website issues and track search terms.