# Symmetry properties of the Novelli-Pak-Stoyanovskii algorithm.

1 Introduction

The main motivation for this work was a conjecture by Krattenthaler and Muller stating that the average runtime of the Novelli-Pak-Stoyanovskii algorithm remains the same whether it is applied row-wise or column-wise. Equivalently, the sorting of all fillings of a partition [lambda] requires the same number of exchanges as the sorting of all fillings of its conjugate [lambda]'.

We consider two additional combinatorial objects, the drop function and exchange numbers, by means of which the complexity can be expressed. The aim of this paper is to provide formulae for the drop function (Theorem 2.2), the exchange numbers (Theorem 2.3) and the complexity (Theorem 2.4). The symmetry in [lambda] and [lambda]' will follow easily from these results (Corollary 2.1).

It should be mentioned that Neumann and the author obtain the symmetry result in a slightly more general setting, defining a family of closely related algorithms and proving that two such algorithms share the same complexity, drop function and exchange numbers if both algorithms produce each standard Young tableau equally often as an output. However, restricting ourselves to the original algorithm, we are able to deduce more explicit results.

[FIGURE 1 OMITTED]

Finally, some of these new formulae generalise the hook-length formula, and demand bijective proofs. We succeed in providing bijections for the drop function (Theorem 3.1) and the exchange numbers (Proposition 3.1), and give a bijective version of the symmetry of the complexity at the end of Section 3.

In the rest of this section we define the combinatorial objects we are going to consider, and recall the Novelli-Pak-Stoyanovskii algorithm.

Let n [member of] N. A partition of n is a sequence [lambda] = ([[lambda].sub.1], [[lambda].sub.2], ...) of non- negative integers such that [[lambda].sub.i] [greater than or equal to] [[lambda].sub.i+1] and [summation][[lambda].sub.i] = n. If this is the case we write [lambda] [??] n. For us the appropriate way to represent a partition is via its Young diagram [lambda] = {(i, j) [member of] [Z.sup.2]: 1 [less than or equal to] i, 1 [less than or equal to] j [less than or equal to] [[lambda].sub.j]}. The elements x = (i, j) [member of] [lambda] are called the cells of the partition. We visualise a partition as a left-justified array with [[lambda].sub.i] cells in the i-th row. Thus, the cells are arranged like the entries of a matrix (see Figure 1). The conjugated partition of [lambda] is defined as

[lambda]' = {(i,j) [member of] [Z.sup.2]: 1 [less than or equal to] i, 1 [less than or equal to] j [less than or equal to] [[lambda]'.sub.j]} := {(i,j): (j, i) [member of] [lambda]}.

Given a cell x = (i, j) in [lambda] we define its arm [arm.sub.[lambda]](x) := [[lambda].sub.i] - j as the number of cells to the right of x. The leg [leg.sub.[lambda]](x) := [[lambda]'.sub.j] - i is defined as the number of cells below x. Furthermore, we define the hook-length of x as [h.sub.[lambda]](x) := [arm.sub.[lambda]](x) + [leg.sub.[lambda]](x) + 1, and the cohook-length as h'(x) := i + j - 2. Finally, we denote the set of top and left neighbours of x by [N.sup.-.sub.[lambda]](x) := {(i - 1, j), (i,j - 1)} [intersection] [lambda] and the set of right and bottom neighbours of x by [N.sup.+.sub.[lambda]](x) := {(i, j + 1), (i + 1, j)} [intersection] [lambda].

We want to consider integer fillings of partitions, i.e. maps T: [lambda] [right arrow] Z. The image k = T(x) is called the entry of the cell x. The partition [lambda] is also called the shape of the filling. A tabloid is a bijection T: [lambda] [right arrow] {1, ..., n}, i.e. a filling where each entry between 1 and n occurs exactly once. We say a tabloid T is sorted at x if T(x) is less than all entries among the bottom and right neighbours of x. A tabloid which is sorted at every cell is called a standard Young tableau. Finally, a hook tableau is a map H: [lambda] [right arrow] Z such that -[leg.sub.[lambda]](x) [less than or equal to] H(x) [less than or equal to] [arm.sub.[lambda]](x) for all x [member of] [lambda].

Let T([lambda]) denote the set of all tabloids, SYT([lambda]) the set of all standard Young tableaux and H([lambda]) the set of all hook tableaux of shape [lambda]. It is obvious that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

The symmetric group [S.sub.n] acts simply transitively on T([lambda]) via [sigma](T) := [sigma] [omicron] T. Let T [member of] T([lambda]) and [sigma] = ([k.sub.0], ..., [k.sub.r]) be a cycle such that [T.sup.-1]([k.sub.i]) is a right or bottom neighbour of [T.sup.-1] ([k.sub.i-1]) for all 1 [less than or equal to] i [less than or equal to] r. Then [sigma] is called a forward slide on T at x if T(x) = [k.sub.0], [k.sub.i] < [k.sub.i+1] for all 1 [less than or equal to] i < r and [k.sub.0] > [k.sub.r]. If instead [k.sub.0] = T(x) and [k.sub.i] < [k.sub.i+1] for all 0 [less than or equal to] i < r then the inverse [[sigma].sup.-1] is called a backward slide on T at x. For example (7,1,2,5) is a forward slide on the (left) tabloid in Figure 1 while [(1, 2, 8).sup.-1] is a backward slide.

An exchange on T is a transposition [tau] = (k,l) such that k and l are entries of neighbouring cells in T. If [[sigma].sub.1] = ([k.sub.0], [k.sub.1], ..., [k.sub.r]) is a forward slide on T and [[sigma].sub.2] = ([k.sub.0], [l.sub.1], ..., [l.sub.s]) is a forward slide on [[sigma].sub.1] [omicron] T then [[sigma].sub.2][[sigma].sub.1] = ([k.sub.0], [k.sub.1], ..., [k.sub.r], [l.sub.1], ..., [l.sub.s]) is a forward slide on T if and only if [k.sub.r] < [l.sub.1]. In particular [[sigma].sub.2][[sigma].sub.1] has to be a forward slide on T if T is ordered at [T.sup.-1]([k.sub.r]). Conversely, every forward slide [sigma] = ([k.sub.0], [k.sub.1], ..., [k.sub.r+s]) has a unique decomposition [sigma] = [[sigma].sub.2][[sigma].sub.1] into a forward slide [[sigma].sub.1] on T of length r and a forward slide [[sigma].sub.2] on [[sigma].sub.1] [omicron] T of length s. We say [sigma] is an extension of [[sigma].sub.1], and call a forward slide maximal if it possesses no nontrivial extension. Along the same lines, each forward slide of length r has a unique decomposition

([k.sub.0], ..., [k.sub.r]) = ([k.sub.r], [k.sub.0]) ... ([k.sub.2], [k.sub.0])([k.sub.1], [k.sub.0])

into r exchanges, where each transposition ([k.sub.i], [k.sub.0]) is an exchange on ([k.sub.i-1], [k.sub.0]) ... ([k.sub.1], [k.sub.0]) [omicron] T.

The number of standard Young tableaux is famously given by the hook-length formula due to Frame et al. (1954):

[f.sub.[lambda]] := #SYT([lambda]) = [n!/[[PI].sub.x[member of][lambda]][h.sub.[lambda]](x)] (2)

While there are many proofs of this formula, we are particularly interested in the proof due to Novelli et al. (1997). They construct a bijection

[PHI]: T([lambda]) [right arrow] H([lambda]) x SYT([lambda]), (3)

hence, the respective cardinalities are equal and the formula follows from (1). The induced map T([lambda]) [right arrow] SYT([lambda]) which transforms each tabloid T into a standard Young tableau, is especially nice since it is given as a sequence of maximal forward slides and can be fully explained without considering hook tableaux at all:

Impose the reverse lexicographic order on the cells of [lambda], i.e. (i, j) [??] (k, l) if either j < l or j = l and i < k. Initialise y to be the maximal cell with respect to [??] and [T.sub.y] := T. Then iterate the following steps:

Given a pair (y, [T.sub.y]) let x be precursor of y with respect to [??]. Define a maximal forward slide [[sigma].sub.x] on [T.sub.y] at x by letting [k.sub.0] := T(x) and choosing each [k.sub.i] minimal for i [greater than or equal to] 1. Set [T.sub.x] := [[sigma].sub.x] [omicron] [T.sub.y] and return the pair (x, [T.sub.x]).

The algorithm terminates after the minimal cell (1,1) is reached. At each step the tabloid [T.sub.x] will be ordered at all cells y with y [??] x. Thus, [T.sub.(1,1)] is a standard Young tableau. An example is given in Figure 2.

The inverse algorithm is given as a sequence of backward slides, however, to determine the correct backward slide at each step, the hook tableau has to be taken into account. For details see Novelli et al. (1997); Sagan (2001).

We remark that Neumann and Sulzgruber (2013) define analogous sorting algorithms, by replacing [??] with a more general order [[??].sub.U]. This order is induced by an arbitrary standard Young tableaux U of the same shape as T, and defined by x [[??].sub.U] y if and only if U(x) < U(y).

[FIGURE 2 OMITTED]

The order [??] is special in the following sense: If we sort all tabloids in T([lambda]) with respect to [??] then each standard Young tableau in SYT([lambda]) is met exactly [[PI].sub.x[member of][lambda]] [h.sub.[lambda]](x) times. If we sort with respect to [[??].sub.U] for an arbitrary standard Young tableau U, this need not be the case anymore. Interestingly, it turns out that if two algorithms arising from different orders, produce each standard Young tableau equally often as an output, then they must automatically share a lot of properties (Neumann and Sulzgruber, 2013, Corollary 4.5, Corollary 5.4). In this paper we restrict ourselves to the order [??] and improve the previous general results for this special case.

The following property of the Novelli-Pak-Stoyanovskii algorithm is so useful that it deserves its own lemma.

Lemma 1.1 (Invariance) Let k,n [member of] N such that k [less than or equal to] n, let [lambda] [??] n be a partition, [pi] [member of] [S.sub.n] be a permutation that fixes all l where 1 [less than or equal to] l < k, and T [member of] T([lambda]) be a tabloid. Set T := [pi] [omicron] T and let [T.sub.x], [T.sub.x] be the tabloids which arise during the sorting of T and T, respectively. Then each permutation [[pi].sub.x] defined by [[??].sub.x] = [[pi].sub.x] [omicron] [T.sub.x] fixes all l with 1 [less than or equal to] l < k.

Proof: We apply induction on x with respect to [??]. The claim is trivial for the maximal cell. Thus, let x [member of] [lambda] be a cell with successor y [??] x, and suppose that [[pi].sub.y] fixes all l with l < k.

Let [[sigma].sub.x] = ([a.sub.0], [a.sub.1], ... [a.sub.r]) and [[??].sub.x] = ([b.sub.0], [b.sub.1], ..., [b.sub.s]) be the maximal forward slides defined as above, such that [a.sub.0] = [T.sub.y](x) and [b.sub.0] = [[??].sub.y](x). Since we always prefer smaller entries over larger ones, and since all entries l with l < k appear in the same positions in [T.sub.y] and [[??].sub.y], whenever we choose an entry [a.sub.i] < k we must make the same choice for [b.sub.i]. Thus, we may decompose [[sigma].sub.x] and [[??].sub.x] into forward slides

[[sigma].sub.x] = [[pi].sub.1] [omicron] ([a.sub.0], [a.sub.1], ..., [a.sub.t]) and [[??].sub.x] = [[pi].sub.2] [omicron] ([b.sub.0], [a.sub.1], ..., [a.sub.t]),

such that [a.sub.t] < k and where [[pi].sub.1] and [[pi].sub.2] fix all l with l < k. If [a.sub.0] < k then [a.sub.0] = [b.sub.0] and [[sigma].sub.x] = [[??].sub.x] fixes all l with l [greater than or equal to] k. Hence,

[[??].sub.x] = [[sigma].sub.x] [omicron] [[??].sub.y] = [[sigma].sub.x][[pi].sub.y] [omicron] [T.sub.y] = [[pi].sub.y][[sigma].sub.x] [omicron] [T.sub.y] = [[pi].sub.y] [omicron] [T.sub.x].

On the other hand, if [a.sub.0] [greater than or equal to] k then also [b.sub.0] [greater than or equal to] k. Write [[pi].sub.y] = [[pi].sub.3] [omicron] ([a.sub.0], [b.sub.0], [c.sub.1], ..., [c.sub.p]) such that fixes [a.sub.0], [b.sub.0] and all l with l < k. Then we compute

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus, we have [[pi].sub.x] = [[pi].sub.y] in the first case and [[pi].sub.x] = [[pi].sub.2][[pi].sub.y][[pi].sup.- 1.sub.1] in the second case.

Krattenthaler and Muller were interested in the average number of steps needed to sort a tabloid of a given shape. Therefore, fix T [member of] T([lambda]) and let r(T, x) be the length of the forward slide [[sigma].sub.x]. As [[sigma].sub.x] can be decomposed into r(T, x) exchanges, the total number of exchanges needed to transform T into a standard Young tableau is

r(T) := [summation over (x [member of] [lambda])]r(T, x).

The average number of needed exchanges is

C([lambda]) := [1/n!] [summation over (T[member of]T([lambda]))] r(T).

We call the number C([lambda]) the complexity of the Novelli-Pak-Stoyanovskii algorithm on the shape [lambda]. The surprising observation by Krattenthaler and Muller can now be stated as C([lambda]) = C([lambda]'). Neumann and Sulzgruber (2013) regard two related objects. The first of these is the drop function which counts the number of tabloids in which the entry k, where 1 [less than or equal to] k [less than or equal to] n, is moved to the cell x [member of] [lambda] by its own forward slide. We denote the drop function by

[d.sub.[lambda]](k, x) := #{T [member of] T([lambda]): there exists z [member of] [lambda] such that T(z) = k, Tz(x) = k}.

The second kind of objects are exchange numbers which count how often two entries are exchanged. That is, given entries k and l, where 1 [less than or equal to] k < l [less than or equal to] n, we are interested in the number of tabloids such that the exchange (k, l) appears in the decomposition of a maximal forward slide [[sigma].sub.z] into exchanges, for some cell z [member of] [lambda]. Formally, we define the exchange numbers as

[[epsilon].sub.[lambda]](k, l) := #{T [member of] T([lambda]): k < l and there exists z [member of] [lambda] such that T(z) = l, [[sigma].sub.z](k) [not equal to] k}.

For example, in Figure 2 the entries 5, 9 and 11 all drop to the cell (2,4). The entry 1 is exchanged with the entries 7 and 11, and the tabloid contributes ten exchanges to the overall complexity C([lambda]), where [lambda] = (4, 4, 3).

2 Formulae

In this section we start out with some preparations we need to define signed exit numbers. Afterwards, we prove formulae for the complexity, the drop function and the exchange numbers, which imply their symmetry in [lambda] and [lambda]'. We shall derive them from Theorem 2.1 which is a result on signed exit numbers.

Let k and l be two entries such that 1 [less than or equal to] k < l [less than or equal to] n and x, y [member of] [lambda] two cells. We are interested in the number of times k and l are exchanged at the positions x and y during the sorting of all tabloids. Suppose that [T.sup.-1](l) = z, then this happens if and only if [[sigma].sub.z] moves the entry k from the cell x to the cell y. To make this precise, let [z.sub.1] [??] ... [??] [z.sub.n] be the cells of [lambda]. We define the local exchange numbers as

[[epsilon].sub.[lambda]] (k, l, x, y) := #{T [member of] T([lambda]): k < l, there exists i such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It is immediate from their definition that [epsilon](k, l, x, y) = 0 unless x and y are neighbouring cells. More precisely, since k < l the cell x must be a bottom of right neighbour of y. An interesting property of local exchange numbers is that they do not depend on the larger argument l.

Lemma 2.1 Let k, l, m, n [member of] N such that 1 [less than or equal to] k < l,m [less than or equal to] n, let [lambda] [??] n be a partition and x,y [member of] [lambda] be two cells. Then

[[epsilon].sub.[lambda]] (k, l, x, y) = [[epsilon].sub.[lambda]] (k, m, x, y).

It is therefore convenient to define [[epsilon].sub.[lambda]] (k, x, y) := [[epsilon].sub.[lambda]] (k, n, x, y) and [[epsilon].sub.[lambda]](k) := [[epsilon].sub.[lambda]](k, n). This lemma is proven in (Neumann and Sulzgruber, 2013, Proposition 4.1). We shall give a short proof using the Invariance Lemma 1.1.

Proof: Let T [member of] T([lambda]), and set [??] := (l, m) [omicron] T. Let z := [T.sup.-1](l) = [[??].sup.-1](m). By Lemma 1.1 the forward slide [[sigma].sub.z] moves k from x to y during the sorting of T if and only if [[??].sub.z] does the same during the sorting of [??]. Thus, the map T [??] (l,m) [omicron] T provides an involution on T([lambda]) mapping tabloids which contributing to [[epsilon].sub.[lambda]] (k, l, x, y) to those which contribute to [[epsilon].sub.[lambda]](k, m, x, y).

Following Neumann and Sulzgruber (2013), we define the signed exit numbers as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

While this definition is not very intuitive at first glance, the signed exit numbers allow for a unified approach to the exchange numbers and the drop function. For k [member of] N and a cell x [member of] [lambda] we define

[f.sub.[lambda]] (k, x) := #{T [member of] SYT([lambda]): T(x) = k}.

Theorem 2.1 (Signed Exit Numbers) Let k,n [member of] N such that 1 [less than or equal to] k < n, let [lambda] [??] n be a partition and x [member of] [lambda] be a cell. Then we have the recursion

(n - k) [[DELTA].sub.[lambda]] (k, x) = (n - 1)! - [n![f.sub.[lambda]](k, x)/[f.sub.[lambda]]] + [k-1.summation over (l=1)] [[DELTA].sub.[lambda]] (l, x). (4)

Solving the recursion we obtain

[[DELTA].sub.[lambda]] (k, x) = [n!/(n - k)(n - k + 1)] (1 - [[f.sub.[lambda]](k,x)/[f.sub.[lambda]]] (n - k + 1) - [k- 1.summation over (l=1)] [[f.sub.[lambda]](l,x)/[f.sub.[lambda]]]). (5)

Proof: The recursion (4) was deduced in (Neumann and Sulzgruber, 2013, Theorem 5.3) in a slightly more general setting. Its proof makes use of Lemma 2.1.

One can derive (5) from (4) by induction on k where the base of the induction and the induction step are both covered by the same computation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that the recursion (4) cannot be solved in the setting of Neumann and Sulzgruber (2013). In contrast to the more general approach we obtain the following formula for the drop function.

Theorem 2.2 (Drop Function) Let k,n [member of] N such that 1 [less than or equal to] k [less than or equal to] n, let [lambda] [??] n be a partition and x [member of] [lambda] be a cell. Then

[d.sub.[lambda]] (k, x) = [n!/n - k + 1] (1 - [k-1.summation over (l=1)] [[f.sub.[lambda]](l,x)/[f.sub.[lambda]]]) (6)

= [[[PI].sub.y[member of][lambda]][h.sub.[lambda]](y)/n - k + 1] [n.summation over (l=k)] [f.sub.[lambda]](l, x). (7)

Proof: An entry k drops to x if it starts there or is moved there by an exchange with a smaller entry and is not moved away by an exchange with a smaller entry. Thus,

[d.sub.[lambda]] (k, x) = (n - 1)! + [k-1.summation over (l=1)] [[DELTA].sub.[lambda]] (l, x) = (n - k) [[DELTA].sub.[lambda]] (k, x) + [n![f.sub.[lambda]](k,x)/[f.sub.[lambda]]]. (8)

Substituting (5) in (8) yields (6). Now, (7) follows from (6) using [[summation].sup.n.sub.k=1][f.sub.[lambda]](k, x) = [f.sub.[lambda]] and the hook-length formula (2).

Note that (7) can be viewed as a generalised hook-length formula. In the case n =1 it reduces to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Next, we obtain a description of the exchange numbers.

Theorem 2.3 (Exchange Numbers) Let k,n [member of] N such that 1 [less than or equal to] k < n, and [lambda] [??] n be a partition. Then we have the recursion

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (9)

Furthermore,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (10)

Proof: The recursion was deduced in (Neumann and Sulzgruber, 2013, Theorem 4.4) (again in a slightly more general setting) but both claims now follow directly from Theorem 2.1 and the fact that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For n [member of] N let [H.sub.n] := [[summation].sup.n.sub.k=1] [1/k] denote the n-th harmonic number.

Theorem 2.4 (Complexity) Let n [member of] N and [lambda] [??] n be a partition. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

= [summation over (x[member of][lambda])][n-1.summation over (k=1)] h'(x) [f.sub.[lambda]](k, x)/[f.sub.[lambda]] ([H.sub.n] - [H.sub.n-k] - 1). (12)

Proof: On the one hand, the complexity is given in terms of exchange numbers as

C([lambda]) = [1/n!] [n-1.summation over (k=1)](n - k) [[epsilon].sub.[lambda]] (k). (13)

On the other hand, the complexity can be expressed in terms of the drop function as

C([lambda]) = [1/n!] [summation over (x[member of][lambda])][n.summation over (k=1)]h'(x) ([d.sub.[lambda]] (k, x) - (n - 1)!) (14)

= [1/n!] [summation over (x[member of][lambda])] [n.summation over (k=1)] h'(x) ([d.sub.[lambda]] (k, x) - [n![f.sub.[lambda]](k,x)/[f.sub.[lambda]]]), (15)

where (14) counts how often an entry is exchanged with a smaller one (i.e., it drops), and (15) counts how often an entry is exchanged with a larger one.

There are various possibilities to prove the claims. Substitution of either (10) in (13) or (6) in (14) yields (11). Inserting (7) into (15) we obtain (12). Moreover, (11) can easily be transformed into (12) and vice versa using

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

As promised, the symmetry conjecture is now an immediate consequence. For any cell x = (i, j) [member of] [lambda] set x' := (j, i) [member of] [lambda]'. For any tabloid T [member of] T([lambda]) define a tabloid T' [member of] T([lambda]') by letting T'(x') := T(x). For any hook tableau H [member of] H([lambda]) define a hook tableau H' [member of] H([lambda]') by H'(x') := -H(x). The induced maps [lambda] [right arrow] [lambda]', T([lambda]) [right arrow] T([lambda]') and H([lambda]) [right arrow] H([lambda]') are obviously bijective and involutive in the sense that (x')' = x, (T')' = T, and (H')' = H. Moreover, T [member of] SYT([lambda]) if and only if T' [member of] SYT([lambda]').

Corollary 2.1 (Symmetry) Let k, n [member of] N such that 1 [less than or equal to] k [less than or equal to] n, let [lambda] [??] n be a partition and x [member of] [lambda] be a cell. Then

C([lambda]) = C([lambda]'), [d.sub.[lambda]](k, x) = [d.sub.[lambda]'] (k, x'), [[epsilon].sub.[lambda]](k) = [[epsilon].sub.[lambda]'](k), and [[DELTA].sub.[lambda]](k,x) = [[DELTA].sub.[lambda]']/(k, x').

Proof: The assertions follow from Theorems 2.1, 2.2, 2.3 and 2.4 and the fact that [f.sub.[lambda]](k, x) = [f.sub.[lambda]'] (k, x') by virtue of the bijection T [??] T'.

However, note that [[epsilon].sub.[lambda]] (k, x, y) = [[epsilon].sub.[lambda]'](k, x', y') is false in general.

In the rest of this section we explain how the complexity C([lambda]) of the Novelli-Pak-Stoyanovskii algorithm on a given shape [lambda] [??] n can actually be computed.

The most primitive approach is certainly to sort all n! tabloids, counting the exchanges. Theorem 2.4 allows for a somewhat better method. That is, now we "only" need to consider all standard Young tableaux of shape [lambda], and count how often each entry occurs in each cell, in order to get a hold on the numbers [f.sub.[lambda]] (k, x). In some special cases these numbers can be given a closed form. In general the cost of computing [f.sub.[lambda]] (k, x) "only" depends on the number of sub-partitions of [lambda]. To see this, decompose a tabloid T with T(x) = k into the parts U with entries smaller than k and V with entries larger than k. Then U is a standard Young tableau of shape [mu] for some [mu] [subset or equal to] [lambda] while V corresponds to a skew standard Young tableaux. Hence, the numbers [f.sub.[lambda]](k, x) can be computed by counting standard Young tableaux and skew tableaux whose shape depends on a suitable [mu]. This can be done using the hook-length formula (2) for standard Young tableaux and the determinant formula of Aitken (1943) for the skew tableaux.

3 Bijections

We are now going to give bijective proofs of the formulae and symmetry results in the last section.

Let T([lambda], k [right arrow] x) denote the set of all tabloids of shape [lambda] such that the entry k drops to the cell x during the application of the sorting algorithm. Moreover, let SYT([lambda], x [greater than or equal to] k) be the set of standard Young tableaux of shape [lambda] such that the entry of the cell x is at least k. Theorem 2.2 (7) suggests we should look for a bijection

[PSI]: T([lambda], k [right arrow] x) x {k, ..., n} [right arrow] H([lambda]) x SYT([lambda], x [greater than or equal to] k).

Indeed, given a tabloid T [member of] T([lambda], k [right arrow] x) we notice that the bijection (3) maps T to a pair [PHI](T) = (H, U) of a hook tableau H and a standard Young tableau U [member of] SYT([lambda], x [greater than or equal to] k). This is true because k drops to the cell x, and can only be moved away by a larger entry afterwards. Now, consider a pair (T, l) of a tabloid T [member of] T([lambda], k [right arrow] x) and an integer k [less than or equal to] l [less than or equal to] n. If we apply [PHI] to the tabloid (kl) [omicron] T then by the Invariance Lemma 1.1 we will again obtain a hook tableau H and a standard Young tableau U [member of] SYT([lambda], x [greater than or equal to] k).

Theorem 3.1 Let k, n [member of] N such that 1 [less than or equal to] k [less than or equal to] n, [lambda] [??] n be a partition and x [member of] [lambda] be a cell. Then the map

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [PHI] is given by the Novelli-Pak-Stoyanovskii algorithm, is a bijection.

Proof: The remarks above show that [PSI] is well-defined. We prove the claim by constructing an inverse map. Therefore, let (H, U) [member of] H([lambda]) x SYT([lambda], x [greater than or equal to] k). Since the map [PHI]: T([lambda]) [right arrow] H([lambda]) x SYT([lambda]) is a bijection, there is a well-defined tabloid T := [[PHI].sup.-1] (H, U). If T [member of] T([lambda], k [right arrow] x) then set [[PSI].sup.-1] (H, U) := (T, k). In this case we have [[PSI].sup.-1] [omicron] [PSI](T, k) = (T, k) and [PSI] [omicron] [[PSI].sup.-1] (H, U) = (H, U).

If T [not member of] T([lambda], k [right arrow] x) then we have to determine an integer l, where k < l [less than or equal to] n, such that k drops to x during the sorting of (kl) [omicron] T. To this end, let I(x) [subset or equal to] [lambda] be the set of cells which lie to the right and below x. That is, z [member of] I(x) if and only if z [member of] [lambda] and z [greater than or equal to] x with respect to the component-wise order.

We consider the tabloid [T.sub.x]. If [T.sub.x](z) [greater than or equal to] k for all cells z [member of] I(x) then we set l := T(x), and claim that (kl) [omicron] T [member of] T([lambda], k [right arrow] x). To see this, let [??] := (kl) [omicron] T. By the Invariance Lemma 1.1 we have [[??].sub.x](z) [greater than or equal to] k for all z [member of] I(x). Since [[??].sub.x] is sorted on I(x) it follows that [[??].sub.x](z) > k for all z [member of] I(x)\{x} and [[??].sub.x](x) = k. But this means that the entry k has not moved at all but dropped to its initial cell x.

Otherwise, there is a z [member of] I(x) such that [T.sub.x](z) < k. Indeed, we must have [T.sub.x](x) < k since [T.sub.x] is sorted on I(x). In this case let y be the maximal cell with respect to the order [??] used in the Novelli-Pak- Stoyanovskii algorithm such that [T.sub.y](z) [greater than or equal to] k for all z [member of] I(x). Such a y must exist because U(x) [greater than or equal to] k. We set l := T(y) and claim that [??] := (kl) [omicron] T [member of] T([lambda], k [right arrow] x) as before. By the Invariance Lemma 1.1, y is the maximal cell with respect to [??] such that [[??].sub.y](z) [greater than or equal to] k for all z [member of] I(x). This means that the entry [??](y) must drop to a cell in I(x). But [??](y) = k is the smallest entry of [[??].sub.y] among the cells of I(x). Since [[??].sub.y] is ordered on I(x), the entry k must drop to the cell x.

Once we have found a suitable l as described above, we set [[PSI].sup.-1](H, U) := ((kl) [omicron] T, l). Clearly, we have [PSI] [omicron] [[PSI].sup.-1] (H, U) = (H, U).

[FIGURE 3 OMITTED]

Conversely, let T [member of] T([lambda], k [right arrow] x) and k < l [less than or equal to] n. Set [??] := (kl) [omicron] T and y := [T.sup.-1](k) = [[??].sup.-1](l). Then y = x or y is the maximal cell of [lambda] with respect to [??] such that [[??].sub.y](z) [greater than or equal to] k for all z [member of] I(x). This once again follows from the Invariance Lemma 1.1.

Hence, [[PSI].sup.-1] [omicron] [PSI](T, l) = (T, l), and the proof is complete.

Note that [PSI] induces a bijection

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (16)

which is an involution in the obvious sense. Unfortunately, it does not seem to be easy to eliminate the auxiliary integers. As Figure 3 shows, even in simple cases distinct tabloids may be mapped to the same tabloid with different integer labels.

Using the ideas from Theorem 3.1, we want to find a bijective proof of the formula (10) for the number of exchanges of k with a larger entry. Suppose during the sorting of the tabloid T [member of] T([lambda]) the entries k and l with k < l are exchanged. We identify this exchange with the pair (T, l). Let Ex([lambda], k) denote the set of all such exchanges, i.e. #Ex([lambda], k) = (n - k) [[epsilon].sub.[lambda]] (k).

Now, fix a tabloid U. Suppose that k drops to x during the sorting of U, and is afterwards moved to the final cell y. Clearly,

#{(T, l) [member of] Ex([lambda], k): T = U} = h'(x) - h'(y).

We denote this cardinality by e(U, k). Thus, we obtain a bijection

Ex([lambda], k) [right arrow] {(T, i): T [member of] T([lambda]), 1 [less than or equal to] i [less than or equal to] e(T, k)},

for example by ordering the exchanges (T, [l.sub.i]), 1 [less than or equal to] i [less than or equal to] e(T, k) with respect to the order in which they occur during the sorting. Thereby, letting

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

we have an inclusion [iota]: Ex([lambda], k) [right arrow] A([lambda], k). Moreover, set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proposition 3.1 Let k, n [member of] N such that 1 [less than or equal to] k [less than or equal to] n, and [lambda] [??] n be a partition. Then the map

[psi]: A([lambda], k)\Ex([lambda], k) [right arrow] B([lambda], k)

defined by (T, i) [??] (H,U, i - e(T, k)), where (H, U) := [PHI](T) is given by the Novelli-Pak-Stoyanovskii algorithm, is a bijection.

Proof: Let (T, i) be a pair of a tabloid and an integer, and let x be the cell to which k drops during the sorting of T. Set (H, U) := [PHI](T) and y := [U.sup.-1](k). Then the inequalities

e(T, k) = h'(x) - h'(y) < i [less than or equal to] h'(x) and 0 < i - e(T, k) [less than or equal to] h'(y)

are equivalent. Thus, (T, i) lies in A([lambda], k) but not in Ex([lambda], k) if and only if (H, U, i - e(T, k)) lies in B([lambda], k). It follows that [PSI] is well defined and a bijection.

Considering only cardinalities, where we use Theorem 3.1 to specify the cardinality of A([lambda], k), Proposition 3.1 reduces to (10). Lastly, we want to give a bijective proof of C([lambda]) = C([lambda]'). We do this by indicating a bijection

[??]: Ex([lambda], k) x {k, ..., n} [right arrow] Ex([lambda]', k) x {k, ..., n}.

The bijections [PSI] and [psi] of Theorem 3.1 and Proposition 3.1 provide a bijection

f: (Ex([lambda], k) [union] B([lambda], k)) x {k ..., n} [right arrow] (Ex([lambda]', k) [union] B([lambda]', k)) x {k ..., n}.

However, we have an additional bijection g: B([lambda], k) [right arrow] B([lambda]', k) given by (H, T, i) [right arrow] (H', T', i) at our disposal. Consider a sequence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where a [member of] Ex([lambda], k), [b'.sub.j] [member of] B([lambda]', k) and [b.sub.j] [member of] B([lambda], k). Since f and g are bijections, no pair ([b'.sub.j], [l'.sub.j]) or ([b.sub.j], [l.sub.j]) can recur. Since the considered sets are finite the sequence must end at some point with a pair (a', l') where a' [member of] Ex([lambda]', k). Hence, by setting [??](a, l) := (a', l') we have found the desired bijection.

Acknowledgements

The author wants to thank Christian Krattenthaler and Christoph Neumann for their helpful comments.

References

A. C. Aitken. The monomial expansion of determinantal symmetric functions. Proc. Royal Soc. Edinburgh (A) 61, pages 300-310, 1943.

J. S. Frame, G. d. B. Robinson, and R. M. Thrall. The hook graphs of the symmetric group. Canadian Journal of Mathematics 6, pages 316-325, 1954.

C. Neumann and R. Sulzgruber. A complexity theorem for the Novelli-Pak-Stoyanovskii-algorithm. Electronic preprint at arXiv: 1306.5134v1, 2013.

J.-C. Novelli, I. Pak, and A. V. Stoyanovskii. A direct bijective proof of the hook-length formula. Discrete Mathematics and Theoretical Computer Science 1, pages 53-67, 1997.

B.E. Sagan. The Symmetric Group. Springer, New York, 2nd edition, 2001.

Robin Sulzgruber *

Universitit Wien, Austria

* Email: robin.sulzgruber@univie.ac.at. Supported by the Austrian Science Foundation FWF, grant S50-N15 in the framework of the Special Research Program "Algorithmic and Enumerative Combinatorics" (SFB F50).

The main motivation for this work was a conjecture by Krattenthaler and Muller stating that the average runtime of the Novelli-Pak-Stoyanovskii algorithm remains the same whether it is applied row-wise or column-wise. Equivalently, the sorting of all fillings of a partition [lambda] requires the same number of exchanges as the sorting of all fillings of its conjugate [lambda]'.

We consider two additional combinatorial objects, the drop function and exchange numbers, by means of which the complexity can be expressed. The aim of this paper is to provide formulae for the drop function (Theorem 2.2), the exchange numbers (Theorem 2.3) and the complexity (Theorem 2.4). The symmetry in [lambda] and [lambda]' will follow easily from these results (Corollary 2.1).

It should be mentioned that Neumann and the author obtain the symmetry result in a slightly more general setting, defining a family of closely related algorithms and proving that two such algorithms share the same complexity, drop function and exchange numbers if both algorithms produce each standard Young tableau equally often as an output. However, restricting ourselves to the original algorithm, we are able to deduce more explicit results.

[FIGURE 1 OMITTED]

Finally, some of these new formulae generalise the hook-length formula, and demand bijective proofs. We succeed in providing bijections for the drop function (Theorem 3.1) and the exchange numbers (Proposition 3.1), and give a bijective version of the symmetry of the complexity at the end of Section 3.

In the rest of this section we define the combinatorial objects we are going to consider, and recall the Novelli-Pak-Stoyanovskii algorithm.

Let n [member of] N. A partition of n is a sequence [lambda] = ([[lambda].sub.1], [[lambda].sub.2], ...) of non- negative integers such that [[lambda].sub.i] [greater than or equal to] [[lambda].sub.i+1] and [summation][[lambda].sub.i] = n. If this is the case we write [lambda] [??] n. For us the appropriate way to represent a partition is via its Young diagram [lambda] = {(i, j) [member of] [Z.sup.2]: 1 [less than or equal to] i, 1 [less than or equal to] j [less than or equal to] [[lambda].sub.j]}. The elements x = (i, j) [member of] [lambda] are called the cells of the partition. We visualise a partition as a left-justified array with [[lambda].sub.i] cells in the i-th row. Thus, the cells are arranged like the entries of a matrix (see Figure 1). The conjugated partition of [lambda] is defined as

[lambda]' = {(i,j) [member of] [Z.sup.2]: 1 [less than or equal to] i, 1 [less than or equal to] j [less than or equal to] [[lambda]'.sub.j]} := {(i,j): (j, i) [member of] [lambda]}.

Given a cell x = (i, j) in [lambda] we define its arm [arm.sub.[lambda]](x) := [[lambda].sub.i] - j as the number of cells to the right of x. The leg [leg.sub.[lambda]](x) := [[lambda]'.sub.j] - i is defined as the number of cells below x. Furthermore, we define the hook-length of x as [h.sub.[lambda]](x) := [arm.sub.[lambda]](x) + [leg.sub.[lambda]](x) + 1, and the cohook-length as h'(x) := i + j - 2. Finally, we denote the set of top and left neighbours of x by [N.sup.-.sub.[lambda]](x) := {(i - 1, j), (i,j - 1)} [intersection] [lambda] and the set of right and bottom neighbours of x by [N.sup.+.sub.[lambda]](x) := {(i, j + 1), (i + 1, j)} [intersection] [lambda].

We want to consider integer fillings of partitions, i.e. maps T: [lambda] [right arrow] Z. The image k = T(x) is called the entry of the cell x. The partition [lambda] is also called the shape of the filling. A tabloid is a bijection T: [lambda] [right arrow] {1, ..., n}, i.e. a filling where each entry between 1 and n occurs exactly once. We say a tabloid T is sorted at x if T(x) is less than all entries among the bottom and right neighbours of x. A tabloid which is sorted at every cell is called a standard Young tableau. Finally, a hook tableau is a map H: [lambda] [right arrow] Z such that -[leg.sub.[lambda]](x) [less than or equal to] H(x) [less than or equal to] [arm.sub.[lambda]](x) for all x [member of] [lambda].

Let T([lambda]) denote the set of all tabloids, SYT([lambda]) the set of all standard Young tableaux and H([lambda]) the set of all hook tableaux of shape [lambda]. It is obvious that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

The symmetric group [S.sub.n] acts simply transitively on T([lambda]) via [sigma](T) := [sigma] [omicron] T. Let T [member of] T([lambda]) and [sigma] = ([k.sub.0], ..., [k.sub.r]) be a cycle such that [T.sup.-1]([k.sub.i]) is a right or bottom neighbour of [T.sup.-1] ([k.sub.i-1]) for all 1 [less than or equal to] i [less than or equal to] r. Then [sigma] is called a forward slide on T at x if T(x) = [k.sub.0], [k.sub.i] < [k.sub.i+1] for all 1 [less than or equal to] i < r and [k.sub.0] > [k.sub.r]. If instead [k.sub.0] = T(x) and [k.sub.i] < [k.sub.i+1] for all 0 [less than or equal to] i < r then the inverse [[sigma].sup.-1] is called a backward slide on T at x. For example (7,1,2,5) is a forward slide on the (left) tabloid in Figure 1 while [(1, 2, 8).sup.-1] is a backward slide.

An exchange on T is a transposition [tau] = (k,l) such that k and l are entries of neighbouring cells in T. If [[sigma].sub.1] = ([k.sub.0], [k.sub.1], ..., [k.sub.r]) is a forward slide on T and [[sigma].sub.2] = ([k.sub.0], [l.sub.1], ..., [l.sub.s]) is a forward slide on [[sigma].sub.1] [omicron] T then [[sigma].sub.2][[sigma].sub.1] = ([k.sub.0], [k.sub.1], ..., [k.sub.r], [l.sub.1], ..., [l.sub.s]) is a forward slide on T if and only if [k.sub.r] < [l.sub.1]. In particular [[sigma].sub.2][[sigma].sub.1] has to be a forward slide on T if T is ordered at [T.sup.-1]([k.sub.r]). Conversely, every forward slide [sigma] = ([k.sub.0], [k.sub.1], ..., [k.sub.r+s]) has a unique decomposition [sigma] = [[sigma].sub.2][[sigma].sub.1] into a forward slide [[sigma].sub.1] on T of length r and a forward slide [[sigma].sub.2] on [[sigma].sub.1] [omicron] T of length s. We say [sigma] is an extension of [[sigma].sub.1], and call a forward slide maximal if it possesses no nontrivial extension. Along the same lines, each forward slide of length r has a unique decomposition

([k.sub.0], ..., [k.sub.r]) = ([k.sub.r], [k.sub.0]) ... ([k.sub.2], [k.sub.0])([k.sub.1], [k.sub.0])

into r exchanges, where each transposition ([k.sub.i], [k.sub.0]) is an exchange on ([k.sub.i-1], [k.sub.0]) ... ([k.sub.1], [k.sub.0]) [omicron] T.

The number of standard Young tableaux is famously given by the hook-length formula due to Frame et al. (1954):

[f.sub.[lambda]] := #SYT([lambda]) = [n!/[[PI].sub.x[member of][lambda]][h.sub.[lambda]](x)] (2)

While there are many proofs of this formula, we are particularly interested in the proof due to Novelli et al. (1997). They construct a bijection

[PHI]: T([lambda]) [right arrow] H([lambda]) x SYT([lambda]), (3)

hence, the respective cardinalities are equal and the formula follows from (1). The induced map T([lambda]) [right arrow] SYT([lambda]) which transforms each tabloid T into a standard Young tableau, is especially nice since it is given as a sequence of maximal forward slides and can be fully explained without considering hook tableaux at all:

Impose the reverse lexicographic order on the cells of [lambda], i.e. (i, j) [??] (k, l) if either j < l or j = l and i < k. Initialise y to be the maximal cell with respect to [??] and [T.sub.y] := T. Then iterate the following steps:

Given a pair (y, [T.sub.y]) let x be precursor of y with respect to [??]. Define a maximal forward slide [[sigma].sub.x] on [T.sub.y] at x by letting [k.sub.0] := T(x) and choosing each [k.sub.i] minimal for i [greater than or equal to] 1. Set [T.sub.x] := [[sigma].sub.x] [omicron] [T.sub.y] and return the pair (x, [T.sub.x]).

The algorithm terminates after the minimal cell (1,1) is reached. At each step the tabloid [T.sub.x] will be ordered at all cells y with y [??] x. Thus, [T.sub.(1,1)] is a standard Young tableau. An example is given in Figure 2.

The inverse algorithm is given as a sequence of backward slides, however, to determine the correct backward slide at each step, the hook tableau has to be taken into account. For details see Novelli et al. (1997); Sagan (2001).

We remark that Neumann and Sulzgruber (2013) define analogous sorting algorithms, by replacing [??] with a more general order [[??].sub.U]. This order is induced by an arbitrary standard Young tableaux U of the same shape as T, and defined by x [[??].sub.U] y if and only if U(x) < U(y).

[FIGURE 2 OMITTED]

The order [??] is special in the following sense: If we sort all tabloids in T([lambda]) with respect to [??] then each standard Young tableau in SYT([lambda]) is met exactly [[PI].sub.x[member of][lambda]] [h.sub.[lambda]](x) times. If we sort with respect to [[??].sub.U] for an arbitrary standard Young tableau U, this need not be the case anymore. Interestingly, it turns out that if two algorithms arising from different orders, produce each standard Young tableau equally often as an output, then they must automatically share a lot of properties (Neumann and Sulzgruber, 2013, Corollary 4.5, Corollary 5.4). In this paper we restrict ourselves to the order [??] and improve the previous general results for this special case.

The following property of the Novelli-Pak-Stoyanovskii algorithm is so useful that it deserves its own lemma.

Lemma 1.1 (Invariance) Let k,n [member of] N such that k [less than or equal to] n, let [lambda] [??] n be a partition, [pi] [member of] [S.sub.n] be a permutation that fixes all l where 1 [less than or equal to] l < k, and T [member of] T([lambda]) be a tabloid. Set T := [pi] [omicron] T and let [T.sub.x], [T.sub.x] be the tabloids which arise during the sorting of T and T, respectively. Then each permutation [[pi].sub.x] defined by [[??].sub.x] = [[pi].sub.x] [omicron] [T.sub.x] fixes all l with 1 [less than or equal to] l < k.

Proof: We apply induction on x with respect to [??]. The claim is trivial for the maximal cell. Thus, let x [member of] [lambda] be a cell with successor y [??] x, and suppose that [[pi].sub.y] fixes all l with l < k.

Let [[sigma].sub.x] = ([a.sub.0], [a.sub.1], ... [a.sub.r]) and [[??].sub.x] = ([b.sub.0], [b.sub.1], ..., [b.sub.s]) be the maximal forward slides defined as above, such that [a.sub.0] = [T.sub.y](x) and [b.sub.0] = [[??].sub.y](x). Since we always prefer smaller entries over larger ones, and since all entries l with l < k appear in the same positions in [T.sub.y] and [[??].sub.y], whenever we choose an entry [a.sub.i] < k we must make the same choice for [b.sub.i]. Thus, we may decompose [[sigma].sub.x] and [[??].sub.x] into forward slides

[[sigma].sub.x] = [[pi].sub.1] [omicron] ([a.sub.0], [a.sub.1], ..., [a.sub.t]) and [[??].sub.x] = [[pi].sub.2] [omicron] ([b.sub.0], [a.sub.1], ..., [a.sub.t]),

such that [a.sub.t] < k and where [[pi].sub.1] and [[pi].sub.2] fix all l with l < k. If [a.sub.0] < k then [a.sub.0] = [b.sub.0] and [[sigma].sub.x] = [[??].sub.x] fixes all l with l [greater than or equal to] k. Hence,

[[??].sub.x] = [[sigma].sub.x] [omicron] [[??].sub.y] = [[sigma].sub.x][[pi].sub.y] [omicron] [T.sub.y] = [[pi].sub.y][[sigma].sub.x] [omicron] [T.sub.y] = [[pi].sub.y] [omicron] [T.sub.x].

On the other hand, if [a.sub.0] [greater than or equal to] k then also [b.sub.0] [greater than or equal to] k. Write [[pi].sub.y] = [[pi].sub.3] [omicron] ([a.sub.0], [b.sub.0], [c.sub.1], ..., [c.sub.p]) such that fixes [a.sub.0], [b.sub.0] and all l with l < k. Then we compute

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus, we have [[pi].sub.x] = [[pi].sub.y] in the first case and [[pi].sub.x] = [[pi].sub.2][[pi].sub.y][[pi].sup.- 1.sub.1] in the second case.

Krattenthaler and Muller were interested in the average number of steps needed to sort a tabloid of a given shape. Therefore, fix T [member of] T([lambda]) and let r(T, x) be the length of the forward slide [[sigma].sub.x]. As [[sigma].sub.x] can be decomposed into r(T, x) exchanges, the total number of exchanges needed to transform T into a standard Young tableau is

r(T) := [summation over (x [member of] [lambda])]r(T, x).

The average number of needed exchanges is

C([lambda]) := [1/n!] [summation over (T[member of]T([lambda]))] r(T).

We call the number C([lambda]) the complexity of the Novelli-Pak-Stoyanovskii algorithm on the shape [lambda]. The surprising observation by Krattenthaler and Muller can now be stated as C([lambda]) = C([lambda]'). Neumann and Sulzgruber (2013) regard two related objects. The first of these is the drop function which counts the number of tabloids in which the entry k, where 1 [less than or equal to] k [less than or equal to] n, is moved to the cell x [member of] [lambda] by its own forward slide. We denote the drop function by

[d.sub.[lambda]](k, x) := #{T [member of] T([lambda]): there exists z [member of] [lambda] such that T(z) = k, Tz(x) = k}.

The second kind of objects are exchange numbers which count how often two entries are exchanged. That is, given entries k and l, where 1 [less than or equal to] k < l [less than or equal to] n, we are interested in the number of tabloids such that the exchange (k, l) appears in the decomposition of a maximal forward slide [[sigma].sub.z] into exchanges, for some cell z [member of] [lambda]. Formally, we define the exchange numbers as

[[epsilon].sub.[lambda]](k, l) := #{T [member of] T([lambda]): k < l and there exists z [member of] [lambda] such that T(z) = l, [[sigma].sub.z](k) [not equal to] k}.

For example, in Figure 2 the entries 5, 9 and 11 all drop to the cell (2,4). The entry 1 is exchanged with the entries 7 and 11, and the tabloid contributes ten exchanges to the overall complexity C([lambda]), where [lambda] = (4, 4, 3).

2 Formulae

In this section we start out with some preparations we need to define signed exit numbers. Afterwards, we prove formulae for the complexity, the drop function and the exchange numbers, which imply their symmetry in [lambda] and [lambda]'. We shall derive them from Theorem 2.1 which is a result on signed exit numbers.

Let k and l be two entries such that 1 [less than or equal to] k < l [less than or equal to] n and x, y [member of] [lambda] two cells. We are interested in the number of times k and l are exchanged at the positions x and y during the sorting of all tabloids. Suppose that [T.sup.-1](l) = z, then this happens if and only if [[sigma].sub.z] moves the entry k from the cell x to the cell y. To make this precise, let [z.sub.1] [??] ... [??] [z.sub.n] be the cells of [lambda]. We define the local exchange numbers as

[[epsilon].sub.[lambda]] (k, l, x, y) := #{T [member of] T([lambda]): k < l, there exists i such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It is immediate from their definition that [epsilon](k, l, x, y) = 0 unless x and y are neighbouring cells. More precisely, since k < l the cell x must be a bottom of right neighbour of y. An interesting property of local exchange numbers is that they do not depend on the larger argument l.

Lemma 2.1 Let k, l, m, n [member of] N such that 1 [less than or equal to] k < l,m [less than or equal to] n, let [lambda] [??] n be a partition and x,y [member of] [lambda] be two cells. Then

[[epsilon].sub.[lambda]] (k, l, x, y) = [[epsilon].sub.[lambda]] (k, m, x, y).

It is therefore convenient to define [[epsilon].sub.[lambda]] (k, x, y) := [[epsilon].sub.[lambda]] (k, n, x, y) and [[epsilon].sub.[lambda]](k) := [[epsilon].sub.[lambda]](k, n). This lemma is proven in (Neumann and Sulzgruber, 2013, Proposition 4.1). We shall give a short proof using the Invariance Lemma 1.1.

Proof: Let T [member of] T([lambda]), and set [??] := (l, m) [omicron] T. Let z := [T.sup.-1](l) = [[??].sup.-1](m). By Lemma 1.1 the forward slide [[sigma].sub.z] moves k from x to y during the sorting of T if and only if [[??].sub.z] does the same during the sorting of [??]. Thus, the map T [??] (l,m) [omicron] T provides an involution on T([lambda]) mapping tabloids which contributing to [[epsilon].sub.[lambda]] (k, l, x, y) to those which contribute to [[epsilon].sub.[lambda]](k, m, x, y).

Following Neumann and Sulzgruber (2013), we define the signed exit numbers as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

While this definition is not very intuitive at first glance, the signed exit numbers allow for a unified approach to the exchange numbers and the drop function. For k [member of] N and a cell x [member of] [lambda] we define

[f.sub.[lambda]] (k, x) := #{T [member of] SYT([lambda]): T(x) = k}.

Theorem 2.1 (Signed Exit Numbers) Let k,n [member of] N such that 1 [less than or equal to] k < n, let [lambda] [??] n be a partition and x [member of] [lambda] be a cell. Then we have the recursion

(n - k) [[DELTA].sub.[lambda]] (k, x) = (n - 1)! - [n![f.sub.[lambda]](k, x)/[f.sub.[lambda]]] + [k-1.summation over (l=1)] [[DELTA].sub.[lambda]] (l, x). (4)

Solving the recursion we obtain

[[DELTA].sub.[lambda]] (k, x) = [n!/(n - k)(n - k + 1)] (1 - [[f.sub.[lambda]](k,x)/[f.sub.[lambda]]] (n - k + 1) - [k- 1.summation over (l=1)] [[f.sub.[lambda]](l,x)/[f.sub.[lambda]]]). (5)

Proof: The recursion (4) was deduced in (Neumann and Sulzgruber, 2013, Theorem 5.3) in a slightly more general setting. Its proof makes use of Lemma 2.1.

One can derive (5) from (4) by induction on k where the base of the induction and the induction step are both covered by the same computation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that the recursion (4) cannot be solved in the setting of Neumann and Sulzgruber (2013). In contrast to the more general approach we obtain the following formula for the drop function.

Theorem 2.2 (Drop Function) Let k,n [member of] N such that 1 [less than or equal to] k [less than or equal to] n, let [lambda] [??] n be a partition and x [member of] [lambda] be a cell. Then

[d.sub.[lambda]] (k, x) = [n!/n - k + 1] (1 - [k-1.summation over (l=1)] [[f.sub.[lambda]](l,x)/[f.sub.[lambda]]]) (6)

= [[[PI].sub.y[member of][lambda]][h.sub.[lambda]](y)/n - k + 1] [n.summation over (l=k)] [f.sub.[lambda]](l, x). (7)

Proof: An entry k drops to x if it starts there or is moved there by an exchange with a smaller entry and is not moved away by an exchange with a smaller entry. Thus,

[d.sub.[lambda]] (k, x) = (n - 1)! + [k-1.summation over (l=1)] [[DELTA].sub.[lambda]] (l, x) = (n - k) [[DELTA].sub.[lambda]] (k, x) + [n![f.sub.[lambda]](k,x)/[f.sub.[lambda]]]. (8)

Substituting (5) in (8) yields (6). Now, (7) follows from (6) using [[summation].sup.n.sub.k=1][f.sub.[lambda]](k, x) = [f.sub.[lambda]] and the hook-length formula (2).

Note that (7) can be viewed as a generalised hook-length formula. In the case n =1 it reduces to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Next, we obtain a description of the exchange numbers.

Theorem 2.3 (Exchange Numbers) Let k,n [member of] N such that 1 [less than or equal to] k < n, and [lambda] [??] n be a partition. Then we have the recursion

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (9)

Furthermore,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (10)

Proof: The recursion was deduced in (Neumann and Sulzgruber, 2013, Theorem 4.4) (again in a slightly more general setting) but both claims now follow directly from Theorem 2.1 and the fact that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For n [member of] N let [H.sub.n] := [[summation].sup.n.sub.k=1] [1/k] denote the n-th harmonic number.

Theorem 2.4 (Complexity) Let n [member of] N and [lambda] [??] n be a partition. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

= [summation over (x[member of][lambda])][n-1.summation over (k=1)] h'(x) [f.sub.[lambda]](k, x)/[f.sub.[lambda]] ([H.sub.n] - [H.sub.n-k] - 1). (12)

Proof: On the one hand, the complexity is given in terms of exchange numbers as

C([lambda]) = [1/n!] [n-1.summation over (k=1)](n - k) [[epsilon].sub.[lambda]] (k). (13)

On the other hand, the complexity can be expressed in terms of the drop function as

C([lambda]) = [1/n!] [summation over (x[member of][lambda])][n.summation over (k=1)]h'(x) ([d.sub.[lambda]] (k, x) - (n - 1)!) (14)

= [1/n!] [summation over (x[member of][lambda])] [n.summation over (k=1)] h'(x) ([d.sub.[lambda]] (k, x) - [n![f.sub.[lambda]](k,x)/[f.sub.[lambda]]]), (15)

where (14) counts how often an entry is exchanged with a smaller one (i.e., it drops), and (15) counts how often an entry is exchanged with a larger one.

There are various possibilities to prove the claims. Substitution of either (10) in (13) or (6) in (14) yields (11). Inserting (7) into (15) we obtain (12). Moreover, (11) can easily be transformed into (12) and vice versa using

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

As promised, the symmetry conjecture is now an immediate consequence. For any cell x = (i, j) [member of] [lambda] set x' := (j, i) [member of] [lambda]'. For any tabloid T [member of] T([lambda]) define a tabloid T' [member of] T([lambda]') by letting T'(x') := T(x). For any hook tableau H [member of] H([lambda]) define a hook tableau H' [member of] H([lambda]') by H'(x') := -H(x). The induced maps [lambda] [right arrow] [lambda]', T([lambda]) [right arrow] T([lambda]') and H([lambda]) [right arrow] H([lambda]') are obviously bijective and involutive in the sense that (x')' = x, (T')' = T, and (H')' = H. Moreover, T [member of] SYT([lambda]) if and only if T' [member of] SYT([lambda]').

Corollary 2.1 (Symmetry) Let k, n [member of] N such that 1 [less than or equal to] k [less than or equal to] n, let [lambda] [??] n be a partition and x [member of] [lambda] be a cell. Then

C([lambda]) = C([lambda]'), [d.sub.[lambda]](k, x) = [d.sub.[lambda]'] (k, x'), [[epsilon].sub.[lambda]](k) = [[epsilon].sub.[lambda]'](k), and [[DELTA].sub.[lambda]](k,x) = [[DELTA].sub.[lambda]']/(k, x').

Proof: The assertions follow from Theorems 2.1, 2.2, 2.3 and 2.4 and the fact that [f.sub.[lambda]](k, x) = [f.sub.[lambda]'] (k, x') by virtue of the bijection T [??] T'.

However, note that [[epsilon].sub.[lambda]] (k, x, y) = [[epsilon].sub.[lambda]'](k, x', y') is false in general.

In the rest of this section we explain how the complexity C([lambda]) of the Novelli-Pak-Stoyanovskii algorithm on a given shape [lambda] [??] n can actually be computed.

The most primitive approach is certainly to sort all n! tabloids, counting the exchanges. Theorem 2.4 allows for a somewhat better method. That is, now we "only" need to consider all standard Young tableaux of shape [lambda], and count how often each entry occurs in each cell, in order to get a hold on the numbers [f.sub.[lambda]] (k, x). In some special cases these numbers can be given a closed form. In general the cost of computing [f.sub.[lambda]] (k, x) "only" depends on the number of sub-partitions of [lambda]. To see this, decompose a tabloid T with T(x) = k into the parts U with entries smaller than k and V with entries larger than k. Then U is a standard Young tableau of shape [mu] for some [mu] [subset or equal to] [lambda] while V corresponds to a skew standard Young tableaux. Hence, the numbers [f.sub.[lambda]](k, x) can be computed by counting standard Young tableaux and skew tableaux whose shape depends on a suitable [mu]. This can be done using the hook-length formula (2) for standard Young tableaux and the determinant formula of Aitken (1943) for the skew tableaux.

3 Bijections

We are now going to give bijective proofs of the formulae and symmetry results in the last section.

Let T([lambda], k [right arrow] x) denote the set of all tabloids of shape [lambda] such that the entry k drops to the cell x during the application of the sorting algorithm. Moreover, let SYT([lambda], x [greater than or equal to] k) be the set of standard Young tableaux of shape [lambda] such that the entry of the cell x is at least k. Theorem 2.2 (7) suggests we should look for a bijection

[PSI]: T([lambda], k [right arrow] x) x {k, ..., n} [right arrow] H([lambda]) x SYT([lambda], x [greater than or equal to] k).

Indeed, given a tabloid T [member of] T([lambda], k [right arrow] x) we notice that the bijection (3) maps T to a pair [PHI](T) = (H, U) of a hook tableau H and a standard Young tableau U [member of] SYT([lambda], x [greater than or equal to] k). This is true because k drops to the cell x, and can only be moved away by a larger entry afterwards. Now, consider a pair (T, l) of a tabloid T [member of] T([lambda], k [right arrow] x) and an integer k [less than or equal to] l [less than or equal to] n. If we apply [PHI] to the tabloid (kl) [omicron] T then by the Invariance Lemma 1.1 we will again obtain a hook tableau H and a standard Young tableau U [member of] SYT([lambda], x [greater than or equal to] k).

Theorem 3.1 Let k, n [member of] N such that 1 [less than or equal to] k [less than or equal to] n, [lambda] [??] n be a partition and x [member of] [lambda] be a cell. Then the map

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [PHI] is given by the Novelli-Pak-Stoyanovskii algorithm, is a bijection.

Proof: The remarks above show that [PSI] is well-defined. We prove the claim by constructing an inverse map. Therefore, let (H, U) [member of] H([lambda]) x SYT([lambda], x [greater than or equal to] k). Since the map [PHI]: T([lambda]) [right arrow] H([lambda]) x SYT([lambda]) is a bijection, there is a well-defined tabloid T := [[PHI].sup.-1] (H, U). If T [member of] T([lambda], k [right arrow] x) then set [[PSI].sup.-1] (H, U) := (T, k). In this case we have [[PSI].sup.-1] [omicron] [PSI](T, k) = (T, k) and [PSI] [omicron] [[PSI].sup.-1] (H, U) = (H, U).

If T [not member of] T([lambda], k [right arrow] x) then we have to determine an integer l, where k < l [less than or equal to] n, such that k drops to x during the sorting of (kl) [omicron] T. To this end, let I(x) [subset or equal to] [lambda] be the set of cells which lie to the right and below x. That is, z [member of] I(x) if and only if z [member of] [lambda] and z [greater than or equal to] x with respect to the component-wise order.

We consider the tabloid [T.sub.x]. If [T.sub.x](z) [greater than or equal to] k for all cells z [member of] I(x) then we set l := T(x), and claim that (kl) [omicron] T [member of] T([lambda], k [right arrow] x). To see this, let [??] := (kl) [omicron] T. By the Invariance Lemma 1.1 we have [[??].sub.x](z) [greater than or equal to] k for all z [member of] I(x). Since [[??].sub.x] is sorted on I(x) it follows that [[??].sub.x](z) > k for all z [member of] I(x)\{x} and [[??].sub.x](x) = k. But this means that the entry k has not moved at all but dropped to its initial cell x.

Otherwise, there is a z [member of] I(x) such that [T.sub.x](z) < k. Indeed, we must have [T.sub.x](x) < k since [T.sub.x] is sorted on I(x). In this case let y be the maximal cell with respect to the order [??] used in the Novelli-Pak- Stoyanovskii algorithm such that [T.sub.y](z) [greater than or equal to] k for all z [member of] I(x). Such a y must exist because U(x) [greater than or equal to] k. We set l := T(y) and claim that [??] := (kl) [omicron] T [member of] T([lambda], k [right arrow] x) as before. By the Invariance Lemma 1.1, y is the maximal cell with respect to [??] such that [[??].sub.y](z) [greater than or equal to] k for all z [member of] I(x). This means that the entry [??](y) must drop to a cell in I(x). But [??](y) = k is the smallest entry of [[??].sub.y] among the cells of I(x). Since [[??].sub.y] is ordered on I(x), the entry k must drop to the cell x.

Once we have found a suitable l as described above, we set [[PSI].sup.-1](H, U) := ((kl) [omicron] T, l). Clearly, we have [PSI] [omicron] [[PSI].sup.-1] (H, U) = (H, U).

[FIGURE 3 OMITTED]

Conversely, let T [member of] T([lambda], k [right arrow] x) and k < l [less than or equal to] n. Set [??] := (kl) [omicron] T and y := [T.sup.-1](k) = [[??].sup.-1](l). Then y = x or y is the maximal cell of [lambda] with respect to [??] such that [[??].sub.y](z) [greater than or equal to] k for all z [member of] I(x). This once again follows from the Invariance Lemma 1.1.

Hence, [[PSI].sup.-1] [omicron] [PSI](T, l) = (T, l), and the proof is complete.

Note that [PSI] induces a bijection

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (16)

which is an involution in the obvious sense. Unfortunately, it does not seem to be easy to eliminate the auxiliary integers. As Figure 3 shows, even in simple cases distinct tabloids may be mapped to the same tabloid with different integer labels.

Using the ideas from Theorem 3.1, we want to find a bijective proof of the formula (10) for the number of exchanges of k with a larger entry. Suppose during the sorting of the tabloid T [member of] T([lambda]) the entries k and l with k < l are exchanged. We identify this exchange with the pair (T, l). Let Ex([lambda], k) denote the set of all such exchanges, i.e. #Ex([lambda], k) = (n - k) [[epsilon].sub.[lambda]] (k).

Now, fix a tabloid U. Suppose that k drops to x during the sorting of U, and is afterwards moved to the final cell y. Clearly,

#{(T, l) [member of] Ex([lambda], k): T = U} = h'(x) - h'(y).

We denote this cardinality by e(U, k). Thus, we obtain a bijection

Ex([lambda], k) [right arrow] {(T, i): T [member of] T([lambda]), 1 [less than or equal to] i [less than or equal to] e(T, k)},

for example by ordering the exchanges (T, [l.sub.i]), 1 [less than or equal to] i [less than or equal to] e(T, k) with respect to the order in which they occur during the sorting. Thereby, letting

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

we have an inclusion [iota]: Ex([lambda], k) [right arrow] A([lambda], k). Moreover, set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proposition 3.1 Let k, n [member of] N such that 1 [less than or equal to] k [less than or equal to] n, and [lambda] [??] n be a partition. Then the map

[psi]: A([lambda], k)\Ex([lambda], k) [right arrow] B([lambda], k)

defined by (T, i) [??] (H,U, i - e(T, k)), where (H, U) := [PHI](T) is given by the Novelli-Pak-Stoyanovskii algorithm, is a bijection.

Proof: Let (T, i) be a pair of a tabloid and an integer, and let x be the cell to which k drops during the sorting of T. Set (H, U) := [PHI](T) and y := [U.sup.-1](k). Then the inequalities

e(T, k) = h'(x) - h'(y) < i [less than or equal to] h'(x) and 0 < i - e(T, k) [less than or equal to] h'(y)

are equivalent. Thus, (T, i) lies in A([lambda], k) but not in Ex([lambda], k) if and only if (H, U, i - e(T, k)) lies in B([lambda], k). It follows that [PSI] is well defined and a bijection.

Considering only cardinalities, where we use Theorem 3.1 to specify the cardinality of A([lambda], k), Proposition 3.1 reduces to (10). Lastly, we want to give a bijective proof of C([lambda]) = C([lambda]'). We do this by indicating a bijection

[??]: Ex([lambda], k) x {k, ..., n} [right arrow] Ex([lambda]', k) x {k, ..., n}.

The bijections [PSI] and [psi] of Theorem 3.1 and Proposition 3.1 provide a bijection

f: (Ex([lambda], k) [union] B([lambda], k)) x {k ..., n} [right arrow] (Ex([lambda]', k) [union] B([lambda]', k)) x {k ..., n}.

However, we have an additional bijection g: B([lambda], k) [right arrow] B([lambda]', k) given by (H, T, i) [right arrow] (H', T', i) at our disposal. Consider a sequence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where a [member of] Ex([lambda], k), [b'.sub.j] [member of] B([lambda]', k) and [b.sub.j] [member of] B([lambda], k). Since f and g are bijections, no pair ([b'.sub.j], [l'.sub.j]) or ([b.sub.j], [l.sub.j]) can recur. Since the considered sets are finite the sequence must end at some point with a pair (a', l') where a' [member of] Ex([lambda]', k). Hence, by setting [??](a, l) := (a', l') we have found the desired bijection.

Acknowledgements

The author wants to thank Christian Krattenthaler and Christoph Neumann for their helpful comments.

References

A. C. Aitken. The monomial expansion of determinantal symmetric functions. Proc. Royal Soc. Edinburgh (A) 61, pages 300-310, 1943.

J. S. Frame, G. d. B. Robinson, and R. M. Thrall. The hook graphs of the symmetric group. Canadian Journal of Mathematics 6, pages 316-325, 1954.

C. Neumann and R. Sulzgruber. A complexity theorem for the Novelli-Pak-Stoyanovskii-algorithm. Electronic preprint at arXiv: 1306.5134v1, 2013.

J.-C. Novelli, I. Pak, and A. V. Stoyanovskii. A direct bijective proof of the hook-length formula. Discrete Mathematics and Theoretical Computer Science 1, pages 53-67, 1997.

B.E. Sagan. The Symmetric Group. Springer, New York, 2nd edition, 2001.

Robin Sulzgruber *

Universitit Wien, Austria

* Email: robin.sulzgruber@univie.ac.at. Supported by the Austrian Science Foundation FWF, grant S50-N15 in the framework of the Special Research Program "Algorithmic and Enumerative Combinatorics" (SFB F50).

Printer friendly Cite/link Email Feedback | |

Author: | Sulzgruber, Robin |
---|---|

Publication: | DMTCS Proceedings |

Article Type: | Report |

Date: | Jan 1, 2014 |

Words: | 6160 |

Previous Article: | The purity of set-systems related to Grassmann necklaces. |

Next Article: | On the rearrangement conjecture for generalized factor order over P. |

Topics: |