Stanley’s theory of P-partitions and the Hook Formula

Wildon's Weblog 2020-03-22

The aim of this post is to introduce Stanley’s theory of labelled $\mathcal{P}_\preceq$ -partitions and, as an application, give a short motivated proof of the Hook Formula for the number of standard Young tableaux of a given shape. In fact we prove the stronger $q$ -analogue, in which hook lengths are replaced with quantum integers. All the ideas may be found in Chapter 7 of Stanley’s book Enumerative Combinatorics II so, in a particularly strong sense, no originality is claimed.

The division into four parts below and the recaps at the start of each part have the aim of reducing notational overload (the main difficulty in the early parts), while also giving convenient places to take a break.

Part 1: Background on arithmetic partitions

Recall that an arithmetic partition of size $n$ is a weakly decreasing sequence of natural numbers whose sum is $n$ . For example, there are $7$ partitions of $5$ with at most three parts, namely

$(7), (6,1), (5,1,1), (4,2,1), (3,3,1), (3,2,2),$

as represented by the Young diagrams shown below.

Since the Young diagram of a partition into at most $3$ parts is uniquely determined by its number of columns of lengths $1$ , $2$ and $3$ , such partitions are enumerated by the generating function

$\frac{1}{(1-q)(1-q^2)(1-q^3)} = 1 \!+\! q \!+ \!2q^2 \!+\! 3q^3 \!+\! 4q^4 \!+\! 5q^5 \!+\! 7q^6 \!+\! 8q^7 \!+\! \cdots$

For example $(4,2,1)$ contributes to the coefficient of $q^7$ , obtained when we expand the geometric series by choosing $q^{1 \times 2}$ from

$1/(1-q) = 1 + q + q^2 + \cdots,$

then $q^{2 \times 1}$ from

$1/(1-q^2) = 1+q^2 + q^4 + \cdots$

and finally $q^{3 \times 1}$ from

$1/(1-q^3) = 1+q^3+q^6 + \cdots .$

Now suppose that we are only interested in partitions where the first part is strictly bigger than the second. Then the Young diagram must have a column of size $1$ , and so we replace $1/(1-q)$ in the generating function with $q/(1-q)$ . Since the coefficient of $q^6$ above is $5$ , it follows (without direct enumeration) that there are $5$ such partitions. What if the second part must also be strictly bigger than the third? Then the Young diagram must have a column of size $2$ , and so we also replace $1/(1-q^2)$ with $q^2/(1-q^2)$ . (I like to see this by mentally removing the first row: the remaining diagram then has a column of size $1$ , by the case just seen.) By a routine generalization we get the following result: partitions with at most $k$ parts such that the $j$ th largest part is strictly more than the $(j+1)$ th largest part for all $j \in J \subseteq \{1,\ldots, k-1\}$ are enumerated by

$\displaystyle \frac{q^{\sum_{j \in J} j}}{(1-q)(1-q^2) \ldots (1-q^k)}.$

Part 2: $\mathcal{P}_\preceq$ -partitions

Let $\mathcal{P}$ be a poset with partial order $\preceq$ . A $\mathcal{P}_\preceq$ -partition is an order-preserving function $p : \mathcal{P} \rightarrow \mathbb{N}_0$ .

For example, if $\mathcal{P} = \{1,\ldots, k\}$ with the usual order then $\bigl( p(1), \ldots, p(k)\bigr)$ is the sequence of values of a $\mathcal{P}$ -partition if and only if $p(1) \le \ldots \le p(k)$ . Thus, by removing any initial zeros and reversing the sequence, $\mathcal{P}$ -partitions are in bijection with arithmetic partitions having at most $k$ parts.

I should mention that it is more usual to write $\mathcal{P}$ rather than $\mathcal{P}_\preceq$ . More importantly, Stanley’s original definition has ‘order-preserving’ rather than ‘order-reversing’. This fits better with arithmetic partitions, and plane-partitions, but since our intended application is to reverse plane-partitions and semistandard Young tableaux, the definition as given (and used for instance in Stembridge’s generalization) is most convenient.

Reversed plane partitions

Formally the Young diagram of the partition $(4,2,1)$ is the set

$[(4,2,1)] = \{(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(3,1)\}$

of boxes. We partially order the boxes by (the transitive closure of) $(a,b) \preceq (a+1,b)$ and $(a,b) \preceq (a,b+1)$ . This is shown diagramatically below.

For this partial order, $\mathcal{P}_\preceq$ -partitions correspond to assignments of non-negative integers to $[(4,2,1)]$ such that that the rows and columns are weakly increasing when read left to right and top to bottom. For example, three of the $72$ $\mathcal{P}_\preceq$ -partitions of size $6$ are shown below

Such assignments are known as reverse plane partitions. The proof of the Hook Formula given below depends on finding the generating function for reverse plane partitions in two different ways: first using the general theory of $\mathcal{P}$ -partitions, and then in a more direct way, for instance using the Hillman–Grassl bijection.

Enumerating $\mathrm{RPP}(2,1)$

As a warm-up, we replace $(4,2,1)$ with the smaller partition $(2,1)$ , so now $\mathcal{P}_\preceq = \{(1,1),(1,2),(2,1)\}$ , ordered by $(1,1) \preceq (1,2)$ , $(1,1) \preceq (2,1)$ . Comparing $p(1,2)$ and $p(2,1)$ , we divide the $\mathcal{P}_\preceq$ -partitions into two disjoint classes: those with $p(1,2) \le p(2,1)$ , and those with $p(1,2) > p(2,1)$ . The first class satisfy

$p(1,1) \le p(1,2) \le p(2,1)$

and so are in bijection with arithmetic partitions with at most $3$ parts. The second class satisfy

$p(1,1) \le p(2,1) < p(1,2)$

so are in bijection with arithmetic partitions with at most $3$ parts, whose largest part is strictly the largest. By the first section we deduce that

$\displaystyle \begin{aligned}\sum_{n=0}^\infty |\mathrm{RPP}_{(2,1)}(n)|z^n &= \frac{1+z}{(1-z)(1-z^2)(1-z^3)} \\&= \frac{1}{(1-z)^2(1-z^3)}.\end{aligned}$

The cancellation to leave a unit numerator shows one feature of the remarkably nice generating function for reverse plane partitions revealed in the final part below.

Labelled $\mathcal{P}$ -partitions

A surprisingly helpful way to keep track of the weak/strong inequalities seen above is to label the poset elements by natural numbers. We define a labelling of a poset $\mathcal{P}_\preceq$ of size $k$ to be a bijective function $L : \mathcal{P} \rightarrow \{1,\ldots, k\}$ . Suppose that $y$ covers $x$ in the order on $\mathcal{P}_\preceq$ . Either $L(x) < L(y)$ , in which case we say the labelling is natural for $(x,y)$ , or $L(x) > L(y)$ , in which case we say the labelling is strict for $(x,y)$ . A $(\mathcal{P}_\preceq,L)$ -partition is then an order preserving function $p : \mathcal{P} \rightarrow \mathbb{N}_0$ such that if $x \prec y$ is a covering relation and

$L(x) < L(y)$ (natural) then $p(x) \ge p(y)$ ;
$L(x) > L(y)$ (strict) then $p(x) > p(y)$ .

Note that the role of the labelling is only to distinguish weak/strong inequalities: the poset itself determines whether $p(u) \ge p(v)$ or $p(v) \le p(u)$ for each comparable pair $u$ , $v \in \mathcal{P}$ .

Let $\mathrm{Par}(\mathcal{P}_\preceq, L)$ denote the set of $(\mathcal{P}_\preceq,L)$ -partitions. For example, if $\mathcal{P} = \{(1,1),(1,2),(2,1)\}$ as in the example above, then the $\mathcal{P}_\preceq$ -partitions are precisely the $(\mathcal{P}_\preceq, L)$ -partitions for any all-natural labelling; the two choices are

$L(1,1) = 1, L(1,2) = 2, L(2,1) = 3,$

and

$L'(1,1) = 1, L'(1,2) = 3, L'(2,1) = 2.$

Working with $L$ , the partitions with $p(1,1) \le p(1,2) \le p(2,1)$ form the set $\mathrm{Par}(\mathcal{P}_\unlhd, L)$ where $\unlhd$ is the total order refining $\preceq$ such that

$(1,1) \unlhd (1,2) \unlhd (2,1)$

and the partitions with $p(1,1) \le p(2,1) < p(1,2)$ form the set $\mathrm{Par}(\mathcal{P}_{\unlhd'}, L)$ where

$(1,1) \unlhd' (2,1) \unlhd' (1,2).$

The division of $\mathcal{P}$ -partitions above is an instance of the following result.

Fundamental Lemma. Let $\mathcal{P}$ be a poset with partial order $\preceq$ and let $L : \mathcal{P} \rightarrow \{1,\ldots, k\}$ be a labelling. Then

$\mathrm{Par}(\mathcal{P}_\preceq, L) = \bigcup \mathrm{Par}(\mathcal{P}_\unlhd, L)$

where the union over all total orders $\unlhd$ refining $\preceq$ is disjoint.

Proof. Every $(\mathcal{P}_\preceq, L)$ partition appears in the right-hand side for some $\unlhd$ : just choose $\unlhd$ so that if $p(x) < p(y)$ then $x \lhd y$ and if $p(x)=p(y)$ and $x \prec y$ then $x \lhd y$ . On the other hand, suppose that $p \in \mathrm{Par}(\mathcal{P}_\preceq,L)$ is in both $\mathrm{Par}(\mathcal{P}_{\unlhd},L)$ and $\mathrm{Par}(\mathcal{P}_{\unlhd'},L)$ . Choose $x$ and $y \in \mathcal{P}$ incomparable under $\preceq$ and such that $x \lhd y$ and $y \lhd' x$ . From $\mathcal{P}_\lhd$ we get $p(x) \le p(y)$ and from $\mathcal{P}_{\lhd'}$ we get $p(y) \le p(x)$ . Therefore $p(x) = p(y)$ . Now using the labelling for the first time, we may suppose without loss of generality that $L(x) < L(y)$ , and using that $y \lhd' x$ and $x \preceq y$ we get $p(x) < p(y)$ , a contradiction. $\Box$ .

Suggested exercise.

Show that the generating functions enumerating $\mathrm{RPP}(2,2)$ and $\mathrm{RPP}(3,1)$ are $1/(1-q)^3(1-q^3)$ and

$(1/(1-q)^2(1-q^2)(1-q^4);$

there are respectively $2$ and $3$ linear extensions that must be considered.

Part 3: Permutations

Recall that $\mathcal{P}_{\preceq}$ is a poset, $L : \mathcal{P} \rightarrow \{1,\ldots, k\}$ is a bijective labelling and that a $(\mathcal{P}_{\preceq},L)$ -partition is a function $p : \mathcal{P} \rightarrow \mathbb{N}_0$ such that if $x \preceq y$ then $p(x) \le p(y)$ , with strict inequality whenever $L(x) > L(y)$ .

Connection with permutations

We write permutations of $\{1,\ldots, k\}$ in one-line form as $\pi_1\ldots \pi_k$ . Recall that $\pi$ has a descent in position $i$ if $\pi_i > \pi_{i+1}$ .

Example. Let $(1,1) \preceq (1,2)$ , $(1,1) \preceq (2,1)$ be the partial order used above to enumerate $\mathrm{RPP}(2,1)$ , as labelled by $L(1,1) = 1$ , $L(1,2) = 2$ , $L(2,1) = 3$ . The total order $(1,1) \unlhd (1,2) \unlhd (2,1)$ corresponds under $L$ to the identity permutation $123$ of $\{1,2,3\}$ , with no descents. The total order $(1,1) \unlhd' (2,1) \unlhd' (1,2)$ corresponds under $L$ to the permutation $132$ swapping $2$ and $3$ , with descent set $\{2\}$ .

In general, let $x_1 \unlhd \ldots \unlhd x_k$ be a total order refining $\preceq$ . Let $i \le k-1$ and consider the elements $x_i$ and $x_{i+1}$ of $\mathcal{P}$ labelled $L(x_i)$ and $L(x_{i+1})$ . In any $\mathcal{P}_\unlhd$ -partition $p$ we have $p(x_i) \le p(x_{i+1})$ , with strict inequality if and only if $L(x_i) > L(x_{i+1})$ . Therefore, using the total order $\unlhd$ to identify $p$ with a function on $\{1,\ldots, k\}$ , i.e. $i \mapsto p(x_i)$ , we require $p(i) \le p(i+1)$ for all $i$ , with strict inequality if and only if $L(x_i) > L(x_{i+1})$ . Equivalently,

$p(1) \le \ldots \le p(k)$

with strict inequality whenever there is a descent $L(x_i)L(x_{i+1})$ in the permutation $L(x_1) \ldots L(x_k)$ corresponding under $L$ to $\unlhd$ . Conversely, a permutation $\pi_1\ldots \pi_k$ of $\{1,\ldots, k\}$ corresponds to a total order refining $\preceq$ if and only if $L(x)$ appears left of $L(y)$ whenever $x \preceq y$ . Therefore Stanley’s Fundamental Lemma may be restated as follows.

Fundamental Lemma restated. Let $\mathcal{P}$ be a poset with partial order $\preceq$ and let $L : \mathcal{P} \rightarrow \{1,\ldots, k\}$ be a labelling such that if $x \preceq y$ then $L(x)$ appears before $L(y)$ in $\pi$ . Then, using the labelling $L$ to identity elements of $\mathrm{Par}(\mathcal{P}_\preceq, L)$ with functions on $\{1,\ldots, k\}$ ,

$\mathrm{Par}(\mathcal{P}_\preceq, L) = \bigcup P_\pi$

where $P_\pi$ is the set of all functions $p : \{1,\ldots, k\} \rightarrow \mathbb{N}_0$ such that $p(1) \le \ldots \le p(k)$ with strict inequality whenever $\pi_i > \pi_{i+1}$ , and the union is disjoint. $\Box$

Such sequences correspond to partitions whose $\bigl(k-(i+1)\bigr)$ th largest part is strictly more than their $(k-i)$ th largest part (which might be zero), and so are enumerated by

$\displaystyle \frac{q^{\sum_{j : \pi_i > \pi_{i+1}} (k-i)}}{(1-q)\ldots (1-q^k)}.$

The power of $x$ in the numerator is, by the standard definition, the comajor index of the permutation $\pi$ .

Example

We enumerate $\mathrm{RPP}(3,2)$ . There are $5$ extensions of the partial order on $[3,2]$ ,

$(1,1) \unlhd (1,2) \unlhd (1,3) \unlhd (2,1) \unlhd (2,2)$
$(1,1) \unlhd (1,2) \unlhd (2,1) \unlhd (1,3) \unlhd (2,2)$
$(1,1) \unlhd (1,2) \unlhd (2,1) \unlhd (2,2) \unlhd (1,3)$
$(1,1) \unlhd (2,1) \unlhd (1,2) \unlhd (1,3) \unlhd (2,2)$
$(1,1) \unlhd (2,1) \unlhd (1,2) \unlhd (2,2) \unlhd (1,3)$

corresponding under the labelling

to the permutations $12345, 12435, 12453, 14235, 14253$ with descent sets $\varnothing$ , $\{3\}, \{4\}, \{2\}, \{2,4\}$ and comajor indices $0$ , $2$ , $1$ , $3$ , $4$ , respectively. By the restatement of the fundamental lemma and the following remark,

$\begin{aligned}\sum_{n=0}^\infty |\mathrm{RPP}_{(3,2)}(n)|z^n &= \frac{1 + q^2 + q + q^3 + q^4}{(1-q)(1-q^2)(1-q^3)(1-q^4)(1-q^5)} \\ &= \frac{1}{(1-q)^2(1-q^2)(1-q^3)(1-q^4)}. \end{aligned}$

We end this part by digressing to outline a remarkably short proof of an identity due to MacMahon enumerating permutations by major index and descent count.

Exercise

If $\mathcal{P} = \{1,\ldots, k\}$ and all elements are incomparable under $\preceq$ , then a $\mathcal{P}_\preceq$ -partition is simply a function $p : \{1,\ldots, k\} \rightarrow \mathbb{N}_0$ .

How are such partitions enumerated by the restated Fundamental Lemma?
Deduce that
$\displaystyle \frac{1}{(1-q)^k} = \frac{\sum_{\pi} q^{\mathrm{comaj}(\pi)}}{(1-q)\ldots (1-q^k)}.$

where the sum is over all permutations of $\{1,\ldots, k\}$ .
Give an involution on permutations that preserves the number of descents and swaps the comajor and major indices. Deduce that $\mathrm{comaj}(\pi)$ can be replaced with $\mathrm{maj}(\pi)$ above.

Exercise

The argument at the start of this post shows that $1/(1-qt) \ldots (1-q^k t)$ enumerates partitions with at most $k$ parts by their size (power of $q$ ) and largest part (power of $t$ ).

Show that partitions whose $j$ th largest part is strictly larger than their $j+1$ th largest part for all $j \in J \subseteq \{1,\ldots,k-1\}$ are enumerated in this sense by
$\displaystyle \frac{q^{\sum_{j \in J}j}t^{|J|}}{(1-qt)\ldots (1-q^kt)}.$
Let $c_k(m)$ be the number of compositions with $k$ parts having $m$ as their largest part. Show that
$\displaystyle \sum_{m=0}^\infty c_k(m) t^m = \frac{\sum_{\pi} q^{\mathrm{comaj}(\pi)} t^{\mathrm{des}(\pi)}}{(1-qt)\ldots (1-q^k t)}$

where $\mathrm{des}(\pi)$ is the number of descents of $\pi$ .
Deduce that
$\displaystyle \sum_{m=0}^\infty \Bigl(\frac{q^{m+1}-1}{q-1}\Bigr)^k t^m = \frac{\sum_{\pi} q^{\mathrm{comaj}(\pi)} t^{\mathrm{des}(\pi)}}{(1-t)(1-qt)\ldots (1-q^k t)}.$
Hence prove MacMahon’s identity $\displaystyle \sum_{r=0}^\infty [r]_q t^r = \frac{\sum_\pi q^{\mathrm{maj}(\pi)} t^{\mathrm{des}(\pi)+1}}{(1-t)(1-qt)\ldots (1-q^k t)}$

where $[r]_q = (q^r-1)/(q-1) = 1 + q + \cdots + q^{r-1}$ .

Part 4: Proof of the Hook Formula

The restated Fundamental Lemma for reverse plane partitions

Fix a partition $\lambda$ of size $k$ and let $\mathcal{P}_{\preceq}$ be the poset with elements the boxes of the Young diagram $[\lambda]$ ordered by (the transitive closure of) $(a,b) \preceq (a+1,b)$ and $(a,b) \preceq (a,b+1)$ . Let $\gamma_a$ be the sum of the $a$ largest parts of $\lambda$ , and define a labelling $L : [\lambda] \rightarrow \{1,\ldots, k\}$ so that the boxes in row $a$ of the Young diagram $[\lambda]$ are labelled $\alpha_{a-1}+1,\ldots, \alpha_a$ . (This labelling was seen for $\lambda=(3,2)$ in the example at the end of the previous part.) Since this label is all-natural, the $(\mathcal{P}_\preceq, L)$ -partitions are precisely the reversed plane partitions of shape $\lambda$ . By the restated Fundamental Lemma and the following remark we get

$\displaystyle \sum_{n=0}^\infty |\mathrm{RPP}_\lambda(n)|q^n = \frac{\sum_{\pi} q^{\mathrm{comaj}(\pi)}}{(1-q) \ldots, (1-q^k)}$

where the sum is over all permutation $\pi$ such that the linear order defined by $\pi$ refines $\preceq$ . Equivalently, as seen in Part 3 and the final example, the label $L(a,b)$ appears before both $L(a+1,b)$ and before $L(a,b+1)$ in the one-line form of $\pi$ (when the boxes exist). This says that $\pi^{-1}_{L(a,b)} < \pi^{-1}_{L(a+1,b)}$ and $\pi^{-1}_{L(a,b)} < \pi^{-1}_{L(a,b+1)}$ . Therefore, when we put $\pi^{-1}_i$ in the box of $[\lambda]$ with label $i$ , we get a standard tableau. Moreover, $\pi$ has a descent in position $i$ , if and only if $i$ appears to the right of $i+1$ in the one-line form of $\pi^{-1}$ . Therefore defining $\mathrm{comaj}(t) = \sum_i (n-i)$ , where the sum is over all $i$ appearing strictly below $i+1$ in $t$ , we have $\mathrm{comaj}(\pi) = \mathrm{comaj}(t)$ . We conclude that

$\displaystyle \sum_{n=0}^\infty |\mathrm{RPP}_\lambda(n)|q^n = \frac{\sum_{t \in \mathrm{SYT}(\lambda)} q^{\mathrm{comaj}(t)}}{(1-q)\ldots (1-q^k)}$

where $\mathrm{SYT}(\lambda)$ is the set of standard tableaux of shape $\lambda$ .

For example we saw at the end of the previous part that the refinements of $\preceq$ when $\lambda = (3,2)$ correspond to the permutations

$12345, 12435, 12453, 14235, 14253.$

Their comajor indices are $0$ , $2$ , $1$ , $3$ , $4$ , their inverses are

$12345, 12435, 12534, 13425, 13524$

and the corresponding standard tableaux, obtained by putting $\pi^{-1}_i$ in the box of $[(3,2)]$ labelled $i$ are

Here the final tableau has $3$ strictly above $2$ and $5$ strictly above $4$ , so its comajor index is $(5-2) + (5-4) = 4$ .

Hillman–Grassl algorithm

Since this post is already rather long, I will refer to Section 7.22 of Stanley Enumerative Combinatorics II or, for a more detailed account that gives the details of how to invert the algorithm, Section 4.2 of Sagan The symmetric group: representations, combinatorial algorithms and symmetric functions. For our purposes, all we need is the remarkable corollary that

$\displaystyle \sum_{n=0}^\infty |\mathrm{RPP}_\lambda(n)|q^n = \frac{1}{\prod_{(a,b)\in[\lambda]} (1-q^{h_{(a,b)}})}$

where $h_{(a,b)}$ is the hook-length of the box $(a,b) \in [\lambda]$ . We saw the special cases for the partitions $(2,1)$ and $(3,2)$ above.

This formula can also be derived by letting $\ell \rightarrow \infty$ in Stanley’s Hook Content Formula: see Theorem 7.21.2 in Stanley’s book, or Theorem 2.6 in this joint paper with Rowena Paget, where we give the representation theoretic context.