NOTE ON THE EXPECTED NUMBER OF YANG-BAXTER MOVES APPLICABLE TO REDUCED

DECOMPOSITIONS

VICTOR REINER

Consider the symmetric group 𝔖_{n} as a Coxeter group generated by the adjacent transpositions {s_{1}, …, s_{n−1}}. Its longest element w_{0} is the permutation sending i to n + 1 − i for each i. A reduced decomposition for w_{0} is an expression w_{0} = s_{i_{1}}s_{i_{2}} ⋯ s_{i_{ℓ}} where ℓ = \binom{n}{2}. See [3] and the references therein for more on these notions, and for undefined terms below.

For any value k = 1, 2, …, ℓ − 2, say that a reduced decomposition s_{i_{1}}s_{i_{2}} ⋯ s_{i_{ℓ}} for w_{0} supports a Yang-Baxter move in position k if

\begin{matrix}(i_{k}, i_{k+1}, i_{k+2}) & = & ( & j, & j + 1, & j & ) \\ or & & ( & j + 1, & j, & j + 1 & ) \end{matrix}

for some j = 1, 2, …, n − 2.

Let X_{n} be the random variable on a reduced decomposition for w_{0} in 𝔖_{n} (chosen from the uniform probability distribution on all reduced decompositions) which counts the number of positions in which it supports a Yang-Baxter move. Surprisingly, its expectation turns out to be independent of n.

Theorem 1. For all n ≥ 3, one has E(X_{n}) = 1.

Proof. Write X_{n} as the sum of the indicator random variables X_{n}^{(k,j)} for the event that the reduced decomposition supports a Yang-Baxter move in position k and with value j as described above. The fact that s_{i}w_{0}s_{n−i} = w_{0} leads to a ℤ/ℓℤ-action by cyclic rotation on the set of reduced decompositions:

s_{i_{1}}s_{i_{2}}s_{i_{3}} ⋯ s_{i_{ℓ}} ↦ s_{i_{2}}s_{i_{3}} ⋯ s_{ℓ}s_{n−i_{1}}.

This symmetry implies that the distribution of X_{n}^{(k,j)} is independent of k, so one only needs to compute E(X_{n}^{(1,j)}). Note that this is the same Figure 1. For n = 9, j = 5, the staircase partition δ_{n} and the almost-staircase partition δ_{n}^{(j)}. Cells in which the hook-lengths for the two diagrams will differ are highlighted.

Key words and phrases. symmetric group, Yang-Baxter, reduced decomposition, reduced word, Poisson.

Supported by NSF grant DMS–9877047.

as the probability that the reduced decomposition for w_{0} is of either form

s_{j}s_{j+1}s_{j} · s_{i_{4}}s_{i_{5}} ⋯ s_{i_{ℓ}} or s_{j+1}s_{j}s_{j+1} · s_{i_{4}}s_{i_{5}} ⋯ s_{i_{ℓ}}.

In either case, this means that s_{i_{4}}s_{i_{5}} ⋯ s_{i_{ℓ}} is a reduced decomposition for s_{j}s_{j+1}s_{j}w_{0}, so E(X_{n}^{(1,j)}) is twice the quotient of the cardinalities of the set of reduced decompositions for s_{j}s_{j+1}s_{j}w_{0} and for w_{0}. Since these two permutations w_{0} and s_{j}s_{j+1}s_{j}w_{0} are both vexillary (that is, they both satisfy the conditions of [3, Corollary 4.2]), their numbers of reduced decompositions are the numbers f_{δ_{n}}, f_{δ_{n}^{(j)}} of standard Young tableaux for the staircase and “almost-staircase” Ferrers diagrams δ_{n} and δ_{n}^{(j)} illustrated in Figure 1.

Using the hook-length formula [2, Cor. 7.21.6] for f_{λ}, and the fact that most of the corresponding cells in these two diagrams have the same hook-length, one can then compute

(1)  \begin{aligned}E(X_{n}) & = ∑_{k=1}^{ℓ−2} ∑_{j=1}^{n−2} E(X_{n}^{(k,j)}) = (ℓ − 2) ∑_{j=1}^{n−2} E(X_{n}^{(1,j)}) \\ & = (ℓ − 2) ∑_{j=1}^{n−2} 2\frac{f_{δ_{n}^{(j)}}}{f_{δ_{n}}} = \binom{ℓ}{2}^{−1} \frac{1}{3} ∑_{j=1}^{n−2} c_{j}c_{n−j−1} \end{aligned}

where

c_{j} := \frac{3 · 5 ⋯ (2j + 1)}{2 · 4 ⋯ (2j − 2)} for j ≥ 2, and c_{1} := 3.

This last sum is easy to evaluate, for example by noting that

∑_{j≥1} c_{j}x^{j} = \frac{3x}{(1 − x)^{\frac{5}{2}}} .

Using this, and letting [x^{m}]f(x) denote the coefficient of x^{m} in a formal power series f(x), one has

\begin{aligned}∑_{j=1}^{n−2} c_{j}c_{n−j−1} & = [x^{n−1}] (∑_{j≥1} c_{j}x^{j})^{2} \\ & = [x^{n−1}]\frac{9x^{2}}{(1 − x)^{5}} = 9\binom{n + 1}{4} = 3\binom{ℓ}{2}. \end{aligned}

Combining this with (1) gives E(X_{n}) = 1. □

The referee suggests a nice alternate proof ending: the Murnaghan-

Nakayama rule [2, §7.17] shows ∑_{j=1}^{n−2} \frac{f_{δ{(j) \atop n}}}{f_{δn}} = −\frac{χ^{δn}(π)}{χ^{δn}(id)} where π is a 3-cycle.

Now use known explicit formulas for such characters (e.g. [1, 4]).

Conjecture 2. As n approaches infinity, the distribution of X_{n} approaches that of a Poisson random variable with mean 1. That is, for each k = 0, 1, 2, …, one has lim_{n→∞} Prob(X_{n} = k) = \frac{1}{e·k!}.

The following conjecture on the variance of X_{n} was suggested by computations for n = 4, 5, 6, and is consistent with Conjecture 2.

Conjecture 3. For all n ≥ 4, one has Var(X_{n}) = \frac{ℓ−4}{ℓ−2}, where ℓ = \binom{n}{2}.

Acknowledgements

Thanks to David Gillman for suggesting Conjecture 2 based on preliminary data, and to an anonymous referee for helpful comments.

References

[1] R. Ingram, Some characters of the symmetric group, Proc. Amer. Math. Soc. 1 (1950), 358–369.

[2] R.P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics 62. Cambridge University Press, Cambridge, 1999.

[3] R.P. Stanley, On the number of reduced decompositions of elements of Coxeter groups, European J. Combin. 5 (1984), 359–372.

[4] M. Suzuki, The values of irreducible characters of the symmetric group, AMS Proceedings of Symposia in Pure Mathematics 47(2) (1987), 317–319.

School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA

E-mail address: reiner@math.umn.edu