Séminaire Lotharingien de Combinatoire 74 (2016), Article B74d

PLAYING JEU DE TAQUIN ON D-COMPLETE POSETS

LUKAS RIEGLER AND CHRISTOPH NEUMANN

Abstract. Using a modified version of jeu de taquin, Novelli, Pak and Stoyanovskii gave a bijective proof of the hook-length formula for counting standard Young tableaux of fixed shape. In this paper we consider a natural extension of jeu de taquin to arbitrary posets. Given a poset P, jeu de taquin defines a map from the set of bijective labelings of the poset elements with {1, 2, …, |P |} to the set of linear extensions of the poset. One question of particular interest is for which posets this map yields each linear extension equally often. We analyze the double-tailed diamond poset D_{m,n} and show that uniform distribution is obtained if and only if D_{m,n} is d-complete. Furthermore, we observe that the extended hook-length formula for counting linear extensions on d-complete posets provides a combinatorial answer to a seemingly unrelated question, namely: Given a uniformly random standard Young tableau of fixed shape, what is the expected value of the left-most entry in the second row?

1. Introduction

1.1. Jeu de taquin on posets. Jeu de taquin (literally translated ’teasing game’) is a board game (also known as 15-puzzle) where fifteen square tiles numbered with {1, 2, …, 15} are arranged inside a 4 × 4 square. The goal of the game is to sort the tiles by consecutively sliding a square into the empty spot (see Figure 1). In combinatorics the concept of jeu de taquin was originally introduced by Schützenberger [Sch76] on skew standard Young tableaux. Two related operations called promotion and evacuation, which act bijectively on the set of linear extensions of a poset, were also defined by Schützenberger [Sch72]. A modified version of jeu de taquin [NPS97] has an obvious

Figure 1. An initial and final configuration of the board game jeu de taquin.

extension to arbitrary posets, which we describe first: The goal of jeu de taquin on an

Fakultät für Mathematik, Universität Wien, Oskar-Morgenstern-Platz 1, 1090 Wien, Austria

Key words and phrases. Jeu de taquin, d-complete poset, double-tailed diamond poset, linear extensions, uniform distribution.

E-Mail: lukas.riegler@univie.ac.at. Supported by the Austrian Science Foundation FWF, START grant Y463.

E-Mail: christoph.neumann@univie.ac.at. Supported by the Austrian Science Foundation FWF, Wittgenstein grant Z130-N13.

n-element poset P is to transform any (bijective) labeling of the poset elements with [n] := {1, 2, …, n} into a dual linear extension, i.e., a labeling ι such that ι(x) > ι(y) whenever x < y in the poset. For this, we first fix a linear extension σ : P → [n] of the poset, which defines the order in which the labels are sorted (see Figure 2). The

Figure 2. Hasse diagram of a poset and a linear extension σ.

sorting procedure consists of n rounds where after the first i rounds the poset elements {σ^{−1}(1), σ^{−1}(2), …, σ^{−1}(i)} have dually ordered labels. To achieve this, we compare in round i the current label of x := σ^{−1}(i) with the labels of all poset elements covered by x. If the current label is the smallest of them, we are done with round i. Otherwise, let y be the poset element with the smallest label. Swap the labels of x and y and repeat with the new label of y. An example can be seen in Figure 3. The fact that σ is a linear extension together with the minimality condition in the sorting procedure ensures that after i rounds the poset elements {σ^{−1}(1), σ^{−1}(2), …, σ^{−1}(i)} have dually ordered labels. In particular, the sorting procedure transforms each labeling of the poset into a dual linear extension. The question we are interested in is: Given a uniformly random labeling of

⇝ ⇝

⇝ ⇝

Figure 3. Example of jeu de taquin with the order σ as given in Figure 2.

the poset elements, does jeu de taquin output a uniformly random dual linear extension of the poset? More specifically, given a poset, is there an order σ such that playing jeu de taquin with all possible labelings yields each dual linear extension equally often? If yes, then jeu de taquin allows us to immediately extend each algorithm for creating uniformly random permutations to an algorithm creating uniformly random linear extensions of the poset.

1.2. (Shifted) standard Young tableaux and the hook-length formula. For certain classes of posets we know the answer: most famously, the Young diagram of an integer partition λ = (λ_{1}, λ_{2}, …, λ_{k}) ⊢ n can be considered as a poset (see Figure 4). A Young tableau is a bijective filling of the boxes with [n] and thus corresponds to a labeling of the poset. A standard Young tableau is a filling of the boxes where entries in

Figure 4. Young diagram of the partition (3, 3, 2, 1) and the corresponding poset.

each row (left-to-right) and column (top-down) are strictly increasing. Hence, standard Young tableaux correspond to the dual linear extensions of the respective poset. Novelli, Pak and Stoyanovskii gave a bijective proof [NPS97] of the fact that jeu de taquin with column-wise order σ (as in Figure 2) yields uniform distribution among standard Young tableaux. Their bijective proof can actually be extended to work for orders different from column-wise order (see also [Sag01]).

A second class of posets where we know the answer corresponds to shifted Young diagrams of strict integer partitions, i.e., partitions where λ_{1} > λ_{2} > ⋯ > λ_{k}. In this case, the boxes of the shifted Young diagram are indented (see Figure 5). It was shown by

Figure 5. A shifted standard Young tableau of shape (5, 4, 2, 1) and the dual linear extension of the corresponding poset.

Fischer [Fis01] that row-wise order σ yields uniform distribution among shifted standard Young tableaux (however column-wise order fails for the partition (4, 3, 2, 1)).

What both classes have in common is that the number of different standard fillings of fixed shape λ can be obtained by a simple product formula, called hook-length formula: in the case of Young diagrams the hook of a cell consists of all cells to the right in the same row, all cells below in the same column and the cell itself. The hook-length h_{c} of a cell c is the number of cells in its hook (see Figure 6(a)). The number f^{λ} of standard Young tableaux of fixed shape λ is then given by ([FRT54], [Gan78])

f^{λ} = \frac{n!}{∏_{c∈λ} h_{c}} ,  (1.1)

where the product is taken over all cells c in the Young diagram. For shifted Young diagrams the number of standard fillings can be obtained by the same hook-formula (1.1) by modifying the definition of the hooks: the shifted hook of a cell contains the same cells as the hook before, and additionally, if the hook contains the left-most cell in row i, then the shifted hook is extended to all cells in row i + 1 (see Figure 6(b)).

(a)  (b)

Figure 6. The hook-lengths of all cells in a Young diagram and a shifted Young diagram.

1.3. d-complete posets. The definition of the hook-lengths can be generalized so that the hook-length formula extends to further classes of posets, called d-complete posets [Pro99].

For m, n ≥ 2 the poset D_{m,n} consists of m + n elements for which the Hasse diagram is obtained by taking a diamond of four elements and appending a chain of m − 2 elements at the top element of the diamond and a chain of n − 2 elements at the bottom element of the diamond (see Figure 7). The poset D_{m,n} is referred to as double-tailed diamond. As elementary building blocks the double-tailed diamonds play a fundamental role in the

Figure 7. Hasse diagram of the double-tailed diamond D_{m,n}.

definition of d-complete posets [Pro99]: Given a poset P and k ≥ 3, an interval [w, z] in the poset is called a d_{k}-interval if [w, z] ≅ D_{k−1,k−1}. An interval [w, y] is called a d_{k}^{−}- interval if [w, y] ≅ D_{k−2,k−1} (in the special case k = 3 let us abuse notation and say that a d_{3}^{−}-interval is a diamond with top element removed). A poset P is called d_{k}-complete if it satisfies the following three conditions:

(1) [w, y] is a d_{k}^{−}-interval ⇒ ∃ z ∈ P : [w, z] is a d_{k}-interval,

(2) [w, z] is a d_{k}-interval ⇒ z does not cover an element outside of [w, z] and

(3) [w, z] is a d_{k}-interval ⇒ there exists no w′ ≠ w such that [w′, z] is a d_{k}-interval. A poset P is called d-complete if and only if P is d_{k}-complete for all k ≥ 3. The posets corresponding to Young diagrams and shifted Young diagrams are examples of d-complete posets (see Figure 8). A full classification of d-complete posets can be found in [Pro99].

Recall that for any poset P a map σ : P → ℕ is called P -partition of n if σ is orderreversing and satisfies ∑_{x∈P} σ(x) = n. Let G_{P} (x) denote the corresponding generating

Figure 8. Two d-complete posets with assigned hook-lengths.

function, i.e.,

G_{P} (x) := ∑_{n≥0} a_{n}x^{n},

where a_{n} denotes the number of P -partitions of n. As a result by R.P. Stanley [Sta11, Theorem 3.15.7] the generating function can be factorized into

G_{P} (x) = \frac{W_{P} (x)}{(1 − x)(1 − x^{2}) ⋯ (1 − x^{|P |})}  (1.2)

with a polynomial W_{P} (x) such that W_{P} (1) is the number of linear extensions of P. A poset P is called hook-length poset if there exists a map h : P → ℤ^{+} such that

G_{P} (x) = ∏_{z∈P} \frac{1}{1 − x^{h(z)}} .  (1.3)

The number f^{P} of linear extensions of a hook-length poset can be obtained by equating (1.2) and (1.3), and taking the limit x → 1:

f^{P} = \frac{|P |!}{∏_{z∈P} h(z)}.  (1.4)

Every d-complete poset is a hook-length poset [Pro]. In fact, d-complete posets were generalized to so-called leaf posets [IT07], which are also hook-length posets. The hooklengths h_{z} := h(z) for d-complete posets can be obtained in the following way:

(1) Assign all minimal elements of the poset the hook-length 1.

(2) Repeat until all elements have their hook-length assigned: choose a poset element z where all smaller elements have their hook-length assigned. Check whether z is the top element of a d_{k}-interval [w, z]. • If no, set h_{z} := #{y ∈ P : y ≤ z}.

• If yes, set h_{z} := h_{l} +h_{r} −h_{w}, where l and r are the two incomparable elements

of the double-tailed diamond [w, z].

By definition of d-complete posets the procedure is well-defined (there exists at most one d_{k}-interval with z as top element). Moreover, it is a nice exercise to check that this definition is equivalent to the previous definition of hook-lengths for Young diagrams (which only contain D_{2,2} intervals) and shifted Young diagrams (which additionally contain D_{3,3} intervals along the left rim). As an example compare Figure 6 and Figure 8.

1.4. Jeu de taquin on the double-tailed diamond. Since there is exactly one pair of incomparable elements in the double-tailed diamond D_{m,n}, there are two different dual linear extensions T_{1} and T_{2} of D_{m,n} (see Figure 9). For jeu de taquin we choose without

Figure 9. The two possible dual linear extension of D_{m,n}.

loss of generality the order σ that corresponds to the reverse order of T_{1}. In Section 2 we show that jeu de taquin yields uniform distribution if and only if m ≥ n. We proceed by defining a related statistic on permutations generalizing right-to-left minima. In terms of this statistic we can analyze a refined counting problem, namely counting the number of permutations for which jeu de taquin swaps the order between the labels of the two incomparable elements exactly k times. As it turns out this counting problem has a nice closed solution (Proposition 2.2) as well as the resulting difference between the number of permutations yielding T_{1} and T_{2}.

Theorem 1.1. Let s_{m,n}^{(1)} (respectively s_{m,n}^{(2)}) denote the number of permutations in S_{m+n} which jeu de taquin on D_{m,n} with the order σ maps to T_{1} (respectively T_{2}). Then

s_{m,n}^{(1)} − s_{m,n}^{(2)} = (−1)^{m}\binom{n − 1}{m}m! n!, m, n ≥ 2.  (1.5)

In particular, s_{m,n}^{(1)} = s_{m,n}^{(2)} if and only if m ≥ n.

What is interesting about the result is that the poset D_{m,n} is d-complete if and only if m ≥ n. Together with Young diagrams and shifted Young diagrams (two further classes of d-complete posets) this hints towards a connection between d-completeness of a poset and the property that jeu de taquin with respect to an appropriate order yields uniform distribution.

In Section 3 we give a purely combinatorial proof of Theorem 1.1 by constructing an appropriate involution Φ_{m,n} on S_{m+n} if m ≥ n. In the case m < n we identify a set E of of \binom{n−1}{m}m! n! exceptional permutations and construct an appropriate involution Φ_{m,n} on S_{m+n} \ E.

1.5. Jeu de taquin on insets. The class of insets (fourth class in the classification of d-complete posets in [Pro99]) can be defined in terms of the shape of its corresponding diagram. For k ≥ 2 and λ = (λ_{1}, …, λ_{k}) ⊢ n the inset P_{k,λ} is obtained by taking the Young diagram corresponding to λ and adding k − 1 boxes at the left end of the first row and one box at the left end of the second row (see Figure 10). The hook-lengths of the

Figure 10. The inset P_{4,(3,2,2,1)} and its corresponding box diagram.

cells in λ can be computed like for Young diagrams. The additional box in the second row is not the maximum of a double-tailed diamond interval, whereas each of the k − 1 additional boxes in the first row is the top element of a double-tailed diamond interval. The resulting hook-lengths are depicted in Figure 11. The hook-length formula (1.4)

Figure 11. The hook-lengths of P_{k,λ} with λ = (λ_{1}, …, λ_{k}) ⊢ n.

implies that the number f^{k,λ} of standard fillings is given by

f^{k,λ} = \frac{(n + k)!}{(∏_{c∈λ} h_{c}) (∏_{i=1}^{k}(n − λ_{i} + i))}.  (1.6)

Computational experiments indicate that jeu de taquin on P_{k,λ} with row-wise order again yields uniform distribution. Even though we were so far not able to modify the techniques of [NPS97] and [Fis01] to prove that jeu de taquin indeed yields uniform distribution, a quick analysis of insets yields a solution to a different, nice problem:

Fix an integer partition λ = (λ_{1}, …, λ_{k}) and consider uniform distribution on the set of standard Young tableaux of shape λ. What is the expected value of the left-most entry in the second row? Three examples are depicted in Figure 12. In Section 4 we prove the answer given in Corollary 1.2.

Corollary 1.2. Fix a partition λ = (λ_{1}, …, λ_{k}) ⊢ n. Let (Ω, 2^{Ω}, P) be the probability space containing the f^{λ} different standard Young tableaux of shape λ and uniform probability measure P. Let X^{λ} ∈ {2, 3, …, λ_{1} + 1} denote the random variable measuring the Figure 12. What is 𝔼X^{λ} under uniform distribution among standard Young tableaux?

left-most entry in the second row. Then

𝔼X^{λ} = \frac{f^{k,λ}}{f^{λ}} = ∏_{i=1}^{k} \frac{n + i}{n + i − λ_{i}} .  (1.7)

Take for example the partition (3, 3, 2, 1) from Figure 6(a) which has according to the hook-length formula \frac{9!}{6·5·4·3·3·2} = 168 different standard Young tableaux. The corresponding inset has f^{4,(3,3,2,1)} = 429 standard fillings. Hence, (1.7) tells us that in a standard Young tableau of shape (3, 3, 2, 1) the left-most entry in the second row is on average \frac{429}{168} ≈ 2.554.

The expected value could also be expressed as a sum of determinants by Aitken’s determinant formula for skew standard Young tableaux [Ait43; Sta01, Corollary 7.16.3]. It should be possible to derive the same product formula (1.7) from this expression. We, however, give a combinatorial argument in Section 4 to show that (1.6) implies (1.7).

A different approach for generating uniformly random linear extensions was taken by Nakada and Okamura [NO10, Nak12]. They use a probabilistic algorithm for generating linear extensions and compute the probability p(L) that a fixed linear extension L is generated by the algorithm. Since they show that p(L) actually does not depend on L their statement not only implies that the algorithm yields uniform distribution among linear extensions but also that the number of linear extensions is given by \frac{1}{p}.

2. Jeu de taquin on the double-tailed diamond

2.1. Reducing the problem to understanding a permutation statistic. For the purpose of this section let us visualize the elements of the double-tailed diamond D_{m,n} as boxes and labelings as fillings of the boxes. Let B_{i,j} denote the box in row i and column j and given a filling of the boxes let T_{i,j} denote the entry in box B_{i,j} (see Figure 13). We

Figure 13. Coordinates of the boxes in D_{6,5} and a filling.

perform modified jeu de taquin on D_{m,n} with respect to the linear extension σ satisfying σ(B_{2,m−1}) = n and σ(B_{1,m}) = n + 1. Given a permutation π = π_{1}π_{2} … π_{m+n} ∈ S_{m+n} we start jeu de taquin by assigning (π_{1}, π_{2}, …, π_{m+n}) to the boxes in reverse order of σ (see Figure 14).

Figure 14. Linear extension σ for jeu de taquin and the initial filling.

Let x_{i} := x_{i}(π) (respectively y_{i} := y_{i}(π)) denote the entry T_{1,m} (respectively T_{2,m−1}) after i rounds of jeu de taquin. So, the initial values are x_{0} = π_{m} and y_{0} = π_{m+1} and we know that in the end we have {x_{m+n}, y_{m+n}} = {m, m + 1}. As in Theorem 1.1 we denote by s_{m,n}^{(1)} the number of permutations π ∈ S_{m+n} with x_{m+n}(π) = m and by s_{m,n}^{(2)} the number of permutations with x_{m+n}(π) = m + 1.

In the first n rounds of jeu de taquin the elements π_{m+n}, π_{m+n−1}, …, π_{m+1} are simply sorted in increasing order (cf. Insertion-Sort algorithm). Therefore

x_{n}(π) = π_{m} and y_{n}(π) = min{π_{m+1}, π_{m+2}, …, π_{m+n}}.

In the following we are no longer interested in the exact values of x_{i} and y_{i} but only whether x_{i} < y_{i} or x_{i} > y_{i}. If x_{n} < y_{n}, then x_{n} < T_{2,m}, so nothing happens in the (n + 1)- st round of jeu de taquin and x_{n+1} < y_{n+1}. If on the other hand x_{n} > y_{n}, then T_{1,m} may or may not be swapped with T_{2,m} (and further entries), but in any case x_{n+1} > y_{n+1}. Therefore, x_{n+1}(π) < y_{n+1}(π) if and only if π_{m} = min{π_{m}, π_{m+1}, …, π_{m+n}}, i.e., if π_{m} is a right-to-left minimum of π.

For the remaining rounds we observe the following: before moving π_{i} at the start of round m + n + 1 − i the boxes B_{1,i+1}, …, B_{1,m}, B_{2,m−1} contain the m + 1 − i smallest elements of {π_{i+1}, π_{i+2}, …, π_{m+n}}. We have to distinguish between two cases, namely whether π_{i} is among the m + 1 − i smallest elements of {π_{i}, π_{i+1}, …, π_{m+n}} or not.

If on the one hand π_{i} > max{x_{m+n−i}, y_{m+n−i}}, then jeu de taquin first moves π_{i} to B_{1,m−1} and then swaps π_{i} with min{x_{m+n−i}, y_{m+n−i}}, which – by assumption – changes the order between T_{1,m} and T_{2,m−1}. After that π_{i} may or may not move further, but in any case the order between x_{m+n−i+1} and y_{m+n−i+1} is exactly the opposite of the order between x_{m+n−i} and y_{m+n−i}. If on the other hand π_{i} < max{x_{m+n−i}, y_{m+n−i}}, then jeu de taquin moves π_{i} at most to B_{1,m} or B_{2,m−1} and – by assumption – does not change the order. Thus x_{m+n−i+1} and y_{m+n−i+1} are in the same order as x_{m+n−i} and y_{m+n−i}.

Summed up, we have observed that x_{n+1}(π) < y_{n+1}(π) if and only if π_{m} is a rightto-left minimum. After that, the order between T_{1,m} and T_{2,m−1} is kept the same in the round starting with π_{i} if and only if π_{i} is among the m + 1 − i smallest elements of {π_{i}, π_{i+1}, …, π_{m+n}}. Therefore, we have reduced the problem to understanding a corresponding statistic on permutations.

2.2. Definition and analysis of a statistic on permutations. The previous observations motivate the following definition generalizing right-to-left-minima of permutations.

Definition 2.1 (RL_{k} – min). Let π = π_{1}π_{2} … π_{n} ∈ S_{n}. We say that π_{i} is a RL_{k} – min if and only if π_{i} is among the k smallest elements of {π_{i}, π_{i+1}, …, π_{n}}.

To solve our counting problem, we need to understand the distribution of

c_{m,n}(π) := ∑_{i=1}^{m} [π_{i} is RL_{m+1−i} – min] , π = π_{1} ⋯ π_{m+n} ∈ S_{m+n},  (2.1)

where the square brackets denote Iverson brackets, i.e., [ϕ] := 1 if ϕ is true, and 0 otherwise. As it turns out the distribution of c_{m,n} can be simply expressed in the following way.

Proposition 2.2. Let

c_{m,n,k} := |{π ∈ S_{m+n} : c_{m,n}(π) = m − k}| , m, n ≥ 1, 0 ≤ k ≤ m.

Then

c_{m,n,k} = n^{k}\left[{m + 1 \atop k + 1}\right]n!,  (2.2)

where \left[{s \atop t}\right] denotes the unsigned Stirling numbers of first kind, i.e., the number of permutations of s elements with t disjoint cycles.

Remark 2.3. From the previous observations it follows that c_{m,n,k} counts the number of π ∈ S_{m+n} for which the order between T_{1,m} and T_{2,m−1} in jeu de taquin is changed exactly k times (with π_{m} contributing to k if and only if π_{m} is not a right-to-left minimum). In particular, x_{m+n}(π) < y_{m+n}(π) if and only if k = m − c_{m,n}(π) is even.

Proof of Proposition 2.2. The proof is split into the two edge cases k = m and k = 0 and the case 0 < k < m.

• k = 0: We show that

c_{m,n}(π) = m ⟺ {π_{1}, …, π_{m}} = {1, …, m}.

Assume s(π_{i}) := [π_{i} is RL_{m+1−i} – min] = 1 for all i = 1, …, m. Then s(π_{m}) = 1 implies 1 ∈ {π_{1}, …, π_{m}}. Suppose there exists 2 ≤ k ≤ m such that k ∈ {π_{m+1}, …, π_{m+n}}. It then follows from s(π_{m}) = s(π_{m−1}) = ⋯ = s(π_{m+2−k}) = 1 that none of π_{m}, π_{m−1}, …, π_{m+2−k} can be greater than k, i.e., {π_{m+2−k}, …, π_{m}} = {1, 2, …, k − 1}. But this contradicts π_{m+1−k} being a RL_{k} – min. The reverse direction is obvious. Since there are exactly m! permutations in S_{m+1} consisting of one cycle, we obtain

c_{m,n,0} = m! n! = n^{0}\left[{m + 1 \atop 1}\right]n!.

• k = m: In this case we observe that

c_{m,n}(π) = 0 ⟺ j ∈ {π_{m+2−j}, π_{m+3−j}, …, π_{m+n}} for all j = 1, …, m.

Suppose j ∉ {π_{m+2−j}, π_{m+3−j}, …, π_{m+n}}. Then there exists an i ∈ {1, …, m + 1−j} such that π_{i} = j ≤ m+1−i. But this implies that π_{i} is a RL_{m+1−i} – min, so c_{m,n}(π) > 0. If we conversely assume that {1, 2, …, m + 1 − i} ⊆ {π_{i+1}, …, π_{m+n}} for all i = 1, …, m, it follows that π_{i} is not among the m + 1 − i smallest elements of {π_{i}, …, π_{m+n}}, and therefore c_{m,n}(π) = 0.

Therefore we have exactly n^{m} possibilities to choose the preimage of {1, 2, …, m} and for each such choice the preimages of {m + 1, …, m + n} can be chosen in any order, i.e.,

c_{m,n,m} = n^{m}n! = n^{m}\left[{m + 1 \atop m + 1}\right]n!.

• 0 < k < m: We proceed by induction on m. From the recurrence relation \left[{s+1 \atop t}\right] = s\left[{s \atop t}\right] + \left[{s \atop t−1}\right] and the induction hypothesis (respectively the edge cases) it follows that

n^{k}\left[{m + 1 \atop k + 1}\right]n! = n^{k}m\left[{m \atop k + 1}\right]n! + n^{k}\left[{m \atop k}\right]n! = m c_{m−1,n,k} + n c_{m−1,n,k−1}.

So it only remains to show that

m c_{m−1,n,k} + n c_{m−1,n,k−1} = c_{m,n,k}.  (2.3)

For a bijective proof of (2.3) consider the position of 1 in π_{1} … π_{m}π_{m+1} … π_{m+n}. Let π′ denote the permutation π with π_{j} = 1 removed and each number reduced by 1, so that π′ ∈ S_{m+n−1}.

If on the one hand 1 ≤ j ≤ m, note that c_{m−1,n}(π′) = c_{m,n}(π) − 1 and thus c_{m−1,n}(π′) = (m − 1) − k if and only if c_{m,n}(π) = m − k. For each 1 ≤ j ≤ m this establishes a one-to-one correspondence between the permutations π ∈ S_{m+n} with π_{j} = 1 that are counted by c_{m,n,k} and permutations π′ ∈ S_{m+n−1} counted by c_{m−1,n,k}.

If on the other hand m + 1 ≤ j ≤ m + n, note that c_{m−1,n}(π′) = c_{m,n}(π) and therefore c_{m−1,n}(π′) = (m − 1) − (k − 1) if and only if c_{m,n}(π) = m − k. For each m + 1 ≤ j ≤ m + n this is a one-to-one correspondence between the permutations π ∈ S_{m+n} with π_{j} = 1 that are counted by c_{m,n,k} and permutations π′ ∈ S_{m+n−1} counted by c_{m−1,n,k−1}.

□

Proof of Theorem 1.1. In Remark 2.3 we have observed that

s_{m,n}^{(1)} − s_{m,n}^{(2)} = |{π ∈ S_{m+n} : m − c_{m,n}(π) is even}| − |{π ∈ S_{m+n} : m − c_{m,n}(π) is odd}| .

Together with Proposition 2.2 it follows that

s_{m,n}^{(1)} − s_{m,n}^{(2)} = ∑_{k=0}^{m}(−1)^{k}c_{m,n,k} = ∑_{k=1}^{m+1}(−1)^{k−1}n^{k−1}\left[{m + 1 \atop k}\right]n!

= (−1)^{m}(n − 1)! ∑_{k=0}^{m+1}(−1)^{m+1−k}\left[{m + 1 \atop k}\right]n^{k}.

Since

(x)_{s} := x(x − 1) ⋯ (x − s + 1) = ∑_{k=0}^{s}(−1)^{s−k}\left[{s \atop k}\right]x^{k}

we obtain

s_{m,n}^{(1)} − s_{m,n}^{(2)} = (−1)^{m}(n − 1)!(n)_{m+1} = (−1)^{m}\binom{n − 1}{m}m! n!.  □

So, in particular jeu de taquin yields uniform distribution on the double-tailed diamond D_{m,n} if and only if m ≥ n.

Let us close this section by noting that the if-direction can also be obtained by a simple inductive argument, which can be extended to general posets: if we play jeu de taquin on D_{m,m} with all permutations where π_{1} has a fixed value and stop the sorting procedure before π_{1} is moved, then we obtain a (non-uniform) distribution (α, β) with α+β = (2m−1)! and α, β independent from π_{1}. As previously observed π_{1} does not change the order between T_{1,m} and T_{2,m−1} if and only if π_{1} is a RL_{m} – min, i.e., π_{1} ∈ {1, 2, …, m}. After completing jeu de taquin by moving π_{1}, we therefore obtain the distribution (α, β) if π_{1} ∈ {1, 2, …, m} and the distribution (β, α) if π_{1} ∈ {m + 1, m + 2, …, 2m}. In total each of the two standard fillings occurs m(α + β) times, i.e., jeu de taquin yields a uniform distribution on D_{m,m}. In the same way we can now fix π_{1} in jeu de taquin on D_{m,n} with m > n. Inductively we obtain a uniform distribution on D_{m−1,n} for each fixed π_{1} ∈ {1, 2, …, m + n}. Since each fixed π_{1} either always or never changes the order of the entries in the incomparable boxes, we also obtain a uniform distribution on D_{m,n}.

Given an n-element poset P and an order σ such that jeu de taquin yields uniform distribution, we can extend this property to the poset P′ obtained by adding a maximum element m to P: first it is clear that the total number of (dual) linear extensions remains the same, i.e., f^{P} = f^{P′}. As order for jeu de taquin choose σ′|_{P} := σ|_{P} and σ′(m) := n+1. Now consider all labelings π of P′ where π_{m} = i is fixed. If we play jeu de taquin with all such labelings and stop before moving i we obtain (restricted to P) a uniform distribution among the f^{P} different dual linear extensions (with entries [n+1]\{i}). Note that in each dual linear extension of P′ the label i has a unique reverse path back to the top. Thus, moving i in the last step of jeu de taquin preserves the uniform distribution. Having a uniform distribution for each π_{m} = i ∈ [n + 1] implies uniform distribution in total.

Since jeu de taquin with row-wise order on Young tableaux yields a uniform distribution [NPS97], it follows from the previous observation that the poset obtained from removing the top row of P_{k,λ} has the same property. It remains an open problem to understand why the uniform distribution is also preserved when adding the top row.

3. A combinatorial proof of Theorem 1.1

In this section we give a bijective proof of Theorem 1.1. For this purpose we define the type τ for each permutation π ∈ S_{m+n} by setting τ(π) := 1 if jeu de taquin with input permutation π yields the output tableau T_{1}, and τ(π) = −1 if the output tableau is T_{2} (see Figure 9 and Figure 14). Given two subsets S_{1}, S_{2} ⊆ S_{m+n} we say that f : S_{1} → S_{2} is type-inverting if τ(π) = −τ(f(π)) for all π ∈ S_{1}. To give a combinatorial proof of Theorem 1.1 we define a type-inverting involution Φ_{m,n} : S_{m+n} → S_{m+n} for all m ≥ n. In the case m < n we identify a set E of \binom{n−1}{m}m! n! exceptional permutations in S_{m+n} of the same type. On the remaining set S_{m+n} \ E we then define a type-inverting involution Φ_{m,n}.

As in Section 2 let x_{i}(π) and y_{i}(π) denote the entries T_{1,m} and T_{2,m−1} after i rounds of jeu de taquin. Before giving the formal definition of Φ_{m,n} let us first state the basic ideas:

First, if the last i entries of π are in the same relative order as the last i entries of π′, then x_{i}(π) < y_{i}(π) if and only if x_{i}(π′) < y_{i}(π′). This means that whether or not x_{i}(π) < y_{i}(π) for i = n + 1, …, n + m depends on the relative order of π_{m+n+1−i}, π_{m+n+2−i}, …, π_{m+n} but not the absolute values.

Second, we have noted in Section 2 that π_{i} does not change the order between T_{1,m} and T_{2,m−1} if and only if π_{i} is among the m + 1 − i smallest elements of {π_{i}, π_{i+1}, …, π_{m+n}}. This implies that whether or not π_{i} changes the order only depends on the set of elements {π_{i+1}, π_{i+2}, …, π_{m+n}}, but not their relative order. In particular, π_{1} changes the order between T_{1,m} and T_{2,m−1} if and only if π_{1} > m.

In the case m = n we therefore construct an involution Φ_{n,n} on S_{2n} such that the relative order of all entries in π and the relative order of all entries in π′ := Φ_{n,n}(π) is the same if we exclude π_{1} and π′_{1} = 2n + 1 − π_{1}. In the case m > n we let Φ_{m,n} fix the first m − n entries of each permutation and apply the type-inverting involution Φ_{n,n} to the bottom 2n entries. If m < n we apply Φ_{m,m} to the smallest 2m entries if π_{1} ≤ 2m. Otherwise, we apply Φ_{m−1,m−1} to the smallest 2(m − 1) entries if π_{2} ≤ 2(m − 1), and so on. Either one of the first m entries is small enough to apply the type-inverting involution Φ_{m+1−i,m+1−i} or π_{1}, π_{2}, …, π_{m} are all too large. In the latter case we call the permutation exceptional and exclude it from the involution Φ_{m,n}. As it turns out there are exactly \binom{n−1}{m}m! n! exceptional permutations all having the same type, thus proving Theorem 1.1.

Let us now formally define the involution Φ_{m,n} in all three cases, prove the correctness and give examples.

3.1. Case m = n. For n ∈ ℕ and 1 ≤ t ≤ 2n define the permutation χ_{n,t} ∈ S_{2n} by

1 ≤ t ≤ n :  χ_{n,t}(i) := \begin{cases}2n + 1 − t & if i = t, \\ i − 1 & if t < i ≤ 2n + 1 − t, \\ i & otherwise. \end{cases}  (3.1)

n + 1 ≤ t ≤ 2n : χ_{n,t}(i) := \begin{cases}2n + 1 − t & if i = t, \\ i + 1 & if 2n + 1 − t ≤ i < t, \\ i & otherwise. \end{cases}  (3.2)

For all 1 ≤ t ≤ 2n we have

χ_{n,t} ∘ χ_{n,2n+1−t} = χ_{n,2n+1−t} ∘ χ_{n,t} = id

and χ_{n,t} |_{[2n]\t} is order-preserving. The desired involution Φ_{n,n} : S_{2n} → S_{2n} is

Φ_{n,n}(π) := χ_{n,π_{1}} ∘ π.  (3.3)

An example can be seen in Figure 15. As composition of permutations it is clear that

Figure 15. The involution Φ_{4,4} applied to π = 25631748.

Φ_{n,n}(π) ∈ S_{2n}, and from χ_{n,π_{1}}(π_{1}) = 2n + 1 − π_{1} it follows that

Φ_{n,n}^{2}(π) = Φ_{n,n}(χ_{n,π_{1}} ∘ π) = χ_{n,2n+1−π_{1}} ∘ χ_{n,π_{1}} ∘ π = π,

i.e., Φ_{n,n} is an involution. Since χ_{n,π_{1}} is order-preserving except for π_{1} the entries of π and π′ := Φ_{n,n}(π) have the same relative order except for π_{1} and π′_{1}. Therefore

x_{2n−1}(π) < y_{2n−1}(π) ⟺ x_{2n−1}(π′) < y_{2n−1}(π′).

As π′_{1} = 2n+1−π_{1} exactly one of π_{1} > n or π′_{1} > n holds, and thus the two permutations π and π′ are of different type, i.e., Φ_{n,n} is a type-inverting involution on S_{2n}.

3.2. Case m > n. Given two subsets A, B ⊆ ℕ with |A| = |B|, let σ_{A,B} : A → B denote the unique order-preserving bijection between A and B, i.e., the bijection satisfying (a_{1} < a_{2}) → (σ_{A,B}(a_{1}) < σ_{A,B}(a_{2})) for all a_{1}, a_{2} ∈ A. Obviously, we have σ_{B,A} ∘ σ_{A,B} = σ_{A,B} ∘ σ_{B,A} = id.

If m > n and π ∈ S_{m+n} set A := A^{π} := {π_{m−n+1}, π_{m−n+2}, …, π_{m+n}}, B := {1, 2, …, 2n} and t := t^{π} := σ_{A,B}(π_{m−n+1}). The type-inverting involution Φ_{m,n} in this case is

Φ_{m,n}(π) := \begin{cases}i ↦ π_{i} & if 1 ≤ i ≤ m − n, \\ i ↦ σ_{B,A} ∘ χ_{n,t} ∘ σ_{A,B}(π_{i}) & if m − n + 1 ≤ i ≤ m + n. \end{cases}  (3.4)

Note that Φ_{m,n}(π) is well-defined and an element of S_{m+n} (see Figure 16 for an example). Moreover we have

Figure 16. The involution Φ_{5,3} applied to π = 41357826 with A^{π} = {2, 3, 5, 6, 7, 8}.

\begin{aligned}Φ_{m,n}(π) |_{\{1,...,m−n\}} & = π, \\ Φ_{m,n}(π) |_{\{m−n+1,...,m+n\}} & = σ_{B,A} ∘ χ_{n,t} ∘ σ_{A,B} ∘ π. \end{aligned}

Therefore A^{Φ_{m,n}(π)} = A^{π} and t^{Φ_{m,n}(π)} = σ_{A,B}(σ_{B,A} ∘ χ_{n,t^{π}} ∘ σ_{A,B}(π_{m−n+1})) = χ_{n,t^{π}}(t^{π}) = 2n + 1 − t^{π}. It follows that

Φ_{m,n}^{2}(π) |_{{1,...,m−n}} = π |_{{1,...,m−n}}

and

Φ_{m,n}^{2}(π) |_{{m−n+1,...,m+n}} = Φ_{m,n}(σ_{B,A} ∘ χ_{n,t^{π}} ∘ σ_{A,B} ∘ π) |_{{m−n+1,...,m+n}}

= σ_{B,A} ∘ χ_{n,2n+1−t^{π}} ∘ σ_{A,B} ∘ σ_{B,A} ∘ χ_{n,t^{π}} ∘ σ_{A,B} ∘ π |_{{m−n+1,...,m+n}} = π |_{{m−n+1,...,m+n}},

i.e., Φ_{m,n}^{2} = id. As in the case m = n the relative order of the last 2n − 1 entries of π and π′ := Φ_{m,n}(π) is the same. The entry π_{m−n+1} is among the n smallest elements of {π_{m−n+1}, …, π_{m+n}} if and only if π′_{m−n+1} is not among the n smallest elements of {π′_{m−n+1}, …, π′_{m+n}}. Therefore

x_{2n}(π) < y_{2n}(π) ⟺ x_{2n}(π′) > y_{2n}(π′).

Since π_{i} = π′_{i} for all i = 1, …, m − n, the permutations π and π′ are of different type.

3.3. Case m < n. In the case m < n let us define a subset E ⊆ S_{m+n} of exceptional permutations which we exclude from the involution: we say that π = π_{1} … π_{m+n} is exceptional if and only if π_{i} > 2(m + 1 − i) for all i = 1, …, m. Note that the number of exceptional permutations is (n − m)(n − m + 1) ⋯ (n − 1) n! = \binom{n−1}{m}m! n!. Given π ∈ S_{m+n} \ E, let k := k^{π} ≥ 1 minimal such that π_{k} ≤ 2(m + 1 − k). Define

Φ_{m,n}(π) := \begin{cases}i ↦ π_{i} & if π_{i} > 2(m + 1 − k), \\ i ↦ χ_{m+1−k,π_{k}}(π_{i}) & otherwise. \end{cases}  (3.5)

An example can be seen in Figure 17. Note that Φ_{m,n}(π) is well-defined and since

Figure 17. The involution Φ_{5,7} with k^{π} = 3.

χ_{m+1−k,π_{k}}(π_{k}) = 2(m + 1 − k) + 1 − π_{k} we have k^{Φ_{m,n}(π)} = k^{π} and Φ_{m,n}(π) ∈ S_{m+n} \ E. With L := {1 ≤ i ≤ m + n : π_{i} > 2(m + 1 − k)} it follows that

Φ_{m,n}^{2}(π) |_{L} = Φ_{m,n}(π) |_{L} = π |_{L}

and

Φ_{m,n}^{2}(π) |_{[m+n]\L} = Φ_{m,n}(χ_{m+1−k,π_{k}} ∘ π) |_{[m+n]\L}
= χ_{m+1−k,2(m+1−k)+1−π_{k}} ∘ χ_{m+1−k,π_{k}} ∘ π |_{[m+n]\L} = π |_{[m+n]\L},

i.e., Φ_{m,n} is an involution. The relative order of the entries in π and π′ := Φ_{m,n}(π) is the same except for π_{k} and π′_{k}. Since π_{k} is among the m + 1 − k smallest elements of {π_{k}, …, π_{m+n}} if and only if π′_{k} is not among the m + 1 − k smallest elements of {π′_{k}, …, π′_{m+n}} the involution Φ_{m,n} is type-inverting. We can conclude the proof by noting that all exceptional permutations are of the same type, since π_{i} > 2(m + 1 − i) for all i = 1, …, m implies that π_{i} is not among the m+1−i smallest elements of {π_{i}, π_{i+1}, …, π_{m+n}}.

4. Proof of Corollary 1.2 and Examples

The statement of Corollary 1.2 can be observed by computing the number f^{k,λ} of standard fillings of P_{k,λ} in two different ways. On the one hand we can use the hooklength formula (1.6) for insets. On the other hand we could refine the counting with respect to the left-most entry in the second row: in each standard filling of P_{k,λ} the k − 1 left-most entries in the first row are (T_{1,1}, T_{1,2}, …, T_{1,k−1}) = (1, 2, …, k − 1). For i = 0, 1, …, λ_{1} let f_{i}^{k,λ} denote the number of standard fillings of P_{k,λ} where the left-most entry in the second row is T_{2,k−1} = k + i (see Figure 18). Now note that for each fixed

Figure 18. Standard fillings counted by f_{i}^{k,λ}.

i ∈ {0, 1, …, λ_{1}} the standard fillings counted by f_{i}^{k,λ} are in one-to-one correspondence with standard Young tableaux of shape λ where the left-most entry in the second row is at least i + 1 (by considering the entries in λ and the order-preserving map). Together with f^{k,λ} = ∑_{i=0}^{λ_{1}} f_{i}^{k,λ}, (1.1) and (1.6) we obtain

𝔼X^{λ} = ∑_{i=1}^{λ_{1}+1} ℙ\{X^{λ} ≥ i\} = ∑_{i=0}^{λ_{1}} \frac{f_{i}^{k,λ}}{f^{λ}} = \frac{f^{k,λ}}{f^{λ}} = ∏_{i=1}^{k} \frac{n + i}{n + i − λ_{i}} .

Let us apply this result to the three families of partitions in Figure 12.

Example 4.1. Consider the partition λ = (k, 1^{k−1}) ⊢ 2k − 1. From Corollary 1.2 we obtain

𝔼X^{λ} = ∏_{i=1}^{k} \frac{2k − 1 + i}{2k − 1 + i − λ_{i}} = \frac{2k}{k} ∏_{i=2}^{k} \frac{2k − 1 + i}{2k − 2 + i} = 3 − \frac{1}{k}.

Of course, this could also be obtained by the elementary observation that f^{λ} = \binom{2k−2}{k−1} and

𝔼X^{λ} = ∑_{i≥1} ℙ(X^{λ} ≥ i) = \frac{1}{\binom{2k−2}{k−1}} [\binom{2k − 2}{k − 1} + ∑_{i≥2} \binom{2k − i}{k − 1}] = 1 + \begin{matrix}( & {2k−1 \atop k} & ) \\ ( & {2k−2 \atop k−1} & ) \end{matrix} = 3 − \frac{1}{k}.

Example 4.2. Fix c ≥ 1 and consider the partition λ = (c, …, c) ⊢ kc. For k ≥ c it follows that

𝔼X^{λ} = ∏_{i=1}^{k} \frac{kc + i}{kc + i − c} = ∏_{i=1}^{c} \frac{k(c + 1) + 1 − i}{kc + 1 − i} ⟶^{k→∞} (1 + \frac{1}{c})^{c} .

Example 4.3. Let λ = (k, k − 1, …, 1) ⊢ \binom{k+1}{2} be of staircase shape. After a short computation one obtains

𝔼X^{λ} = \frac{(\binom{k+1}{2} + k)!! (\binom{k+1}{2} − k − 1)!!}{\binom{k+1}{2}!},

where !! denotes the double factorial, i.e., (2n)!! = 2^{n}n! and (2n−1)!! = \frac{(2n)!}{2^{n}n!}. By applying Stirling’s formula one can show that asymptotically 𝔼X^{λ} ∼ e ≈ 2.71828.

References

[Ait43] A. C. Aitken, The monomial expansion of determinantal symmetric functions, Proc. Royal Soc. Edinburgh (A) 61 (1943), 300–310.

[Fis01] I. Fischer, A bijective proof of the hook-length formula for shifted standard tableaux, arXiv:math/0112261 (2001).

[FRT54] J. S. Frame, G.B. Robinson, and R.M. Thrall, The hook graphs of the symmetric group, Canad. J. Math. 6 (1954), 316–324.

[Gan78] E. R. Gansner, Matrix Correspondences and the Enumeration of Plane Partitions, Ph.D. thesis, 1978.

[IT07] M. Ishikawa and H. Tagawa, Schur function identities and hook length posets, 2007. http://www.fpsac.org/FPSAC07/SITE07/PDF-Proceedings/Posters/55.pdf.

[Nak12] K. Nakada, An algorithm which generates linear extensions for a non-simply laced d-complete poset with uniform probability, DMTCS (2012), 661–666.

[NO10] K. Nakada and S. Okamura, An algorithm which generates linear extensions for a generalized Young diagram with uniform probability, DMTCS (2010), 801–808.

[NPS97] J.-C. Novelli, I. Pak, and A. V. Stoyanovskii, A direct bijective proof of the hook-length formula,

DMTCS 1 (1997), 53–67.

[Pro] R. A. Proctor, d-Complete posets generalize Young diagrams for the hook product formula: partial presentation of proof, in: Algebraic Combinatorics related to Young diagram and statistical physics, M. Ishikawa (ed.), RIMS Kôkyûroku, no. 1913, Kyoto, Japan, pp. 120–140, 2014.

[Pro99] , Dynkin diagram classification of λ-minuscule Bruhat lattices and of d-complete posets, J. Alg. Combin. 9 (1999), 61–94.

[Sag01] B. E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, Springer, 2001.

[Sch72] M.-P. Schützenberger, Promotion des morphismes d’ensembles ordonnés, Discrete Math. 2 (1972), 73 –94.

[Sch76] , La correspondance de Robinson, Combinatoire et représentation du groupe symétrique (D. Foata), Springer (1976), 59–113.

[Sta01] R. P. Stanley, Enumerative Combinatorics, Volume 2, Cambridge University Press, 2001.

[Sta11] R.P. Stanley, Enumerative Combinatorics, Volume 1, Second Edition, Cambridge University Press, 2011.