Bijections between oscillating tableaux and

(semi)standard tableaux via growth diagrams

C. Krattenthaler

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

                 WWW: http://www.mat.univie.ac.at/~kratt

Abstract. We prove that the number of oscillating tableaux of length n with at most k columns, starting at ∅ and ending at the one-column shape (1^{m}), is equal to the number of standard Young tableaux of size n with m columns of odd length, all columns of length at most 2k. This refines a conjecture of Burrill, which it thereby establishes. We prove as well a “Knuth-type” extension stating a similar equi-enumeration result between generalised oscillating tableaux and semistandard tableaux.

1. Introduction. The Robinson–Schensted correspondence [23, 27] (see [26, Sec. 3.1]) is a bijection between permutations of {1, 2, …, n} and pairs of standard (Young) tableaux of the same shape of size n (see Section 2 for all definitions). Knuth’s extension, the so-called Robinson–Schensted–Knuth (RSK) correspondence [16] (see [26, Sec. 4.8]) is a bijection between non-negative integer matrices and pairs of semistandard tableaux of the same shape. These correspondences are not only attractive in their own right due to their elegance, but are important since they map several natural statistics of permutations, respectively matrices, to corresponding ones for tableaux, and thus allow for numerous refinements. An important statistic in this context is the length of the longest increasing (or decreasing) subsequence in a permutation (or of certain chains of entries in a matrix) which, by Schensted’s theorem [27], are mapped to the length of the first row (or first column) of the shapes of the tableaux. Greene [15] extended Schensted’s theorem by describing precisely how lengths of increasing (or decreasing) subsequences in permutations (chains in matrices) determine the shape of the tableaux in the image pair under these correspondences.

Standard or semistandard tableaux may be seen as sequences of Ferrers diagrams, where an element in the sequence is followed by a Ferrers diagram which is by one cell (in the case of standard tableaux) or by a horizontal strip (in the case of semistandard tableaux) larger. A variation consists in considering sequences of Ferrers diagrams where, from one element in the sequence to the next, one also allows sometimes to shrink by a cell or by a horizontal (or vertical) strip. This leads to the notion of oscillating tableaux. Also in this context, there are Robinson–Schensted(–Knuth) like algorithms which connect oscillating tableaux to, for instance, involutions, matchings, or set partitions; see [1, 7, 8, 22, 24, 25, 31, 32, 33]. Greene’s theorem [15] still applies, which has been particularly exploited in [6, 18].

2010 Mathematics Subject Classification. Primary 05A15; Secondary 05E10.

Key words and phrases. standard Young tableaux, semistandard tableaux, oscillating tableaux, Robinson–Schensted correspondence, Robinson–Schensted–Knuth correspondence, growth diagrams.

Research partially supported by the Austrian Science Foundation FWF, grant Z130-N13, and grant SFB F50 (Special Research Program “Algorithmic and Enumerative Combinatorics”) .

If one encounters families of tableaux, permutations, integer matrices, etc. which seem to be enumerated by the same numbers, then one must suspect that an RSK-like bijection lurks in the background. The purpose of the present paper is to illustrate this “principle” by applying it to a recent conjecture of Burrill [3, Conj. 6.2.1] (see [4, Conj. 4] for the formulation below; again, for all undefined terminology see Section 2).

Conjecture (Burrill). Let n and k be given non-negative integers. The number of oscillating tableaux of length n with at most k columns, starting at ∅ and ending at some one-column shape is the same as the number of standard Young tableaux of size n (meaning that its shape has n cells) with all columns of length at most 2k.

In Theorem 3 in Section 3, a refinement of this conjecture will be established, which in addition relates the length of the one-column shape in which the oscillating tableaux end to the number of odd-length columns of the standard tableaux. Moreover, in Theorem 4, we present a “Knuth-type” extension, in which we allow more general oscillating tableaux, and the standard Young tableaux get replaced by semistandard tableaux. We point out that a different bijection proving Theorem 3 has been presented by Burrill, Courtiel, Fusy, Melczer and Mishna in [5], the difference lying in the way the parameter m (the number of odd columns of the standard Young tableau, respectively the size of the final shape of the oscillating tableau) is kept track of.

While, originally, RSK-like correspondences are based on insertion-deletion algorithms, it is nowadays standard that the most transparent way to present these correspondences is by means of Fomin’s growth diagrams [9, 10, 11] (see [24, 25], [26, Sec. 5.2] and [30, Sec. 7.13] for non-technical expositions). This is also the point of view we shall adopt in our (bijective) proofs of Theorems 3 and 4. It will be combined with an application of Schützenberger’s [29] jeu de taquin (for which also geometric realisations have been proposed — see [19] —, which we shall however not use here).

In the final Section 4, we explain that — non-illuminating — computational proofs of Theorems 3 and 4 can be extracted from the literature by appropriately combining results of Gessel and Zeilberger [12] and of Goulden [13], we comment on what happens if, instead of an even number, we bound the length of columns of the standard Young tableaux in Theorem 3 by an odd number, and we provide a more detailed discussion of the differences between the bijection proving Theorem 3 presented here and the one in [5].

2. Definitions and notation. We start by fixing the standard partition notation (cf. e.g. [30, Sec. 7.2]). A partition is a weakly decreasing sequence λ = (λ_{1}, λ_{2}, …, λ_{ℓ}) of positive integers. This also includes the empty partition (), denoted by ∅. For the sake of convenience, we shall often tacitly identify a partition λ = (λ_{1}, λ_{2}, …, λ_{ℓ}) with the infinite sequence (λ_{1}, λ_{2}, …, λ_{ℓ}, 0, 0, …), that is, the sequence which arises from λ by appending infinitely many 0’s. To each partition λ, one associates its Ferrers diagram (also called Ferrers shape), which is the left-justified arrangement of squares with λ_{i} squares in the i-th row, i = 1, 2, . . .. The number of squares in the Ferrers diagram, λ_{1} + λ_{2} + ⋯ + λ_{ℓ}, is called the size of the partition λ, and is denoted by |λ|. We define a partial order ⊆ on partitions by containment of their Ferrers diagrams. The union μ ∪ ν of two partitions μ and ν is the partition which arises by forming the union of the Ferrers diagrams of μ and ν. Thus, if μ = (μ_{1}, μ_{2}, …) and ν = (ν_{1}, ν_{2}, …), then μ ∪ ν is the partition λ = (λ_{1}, λ_{2}, …), where λ_{i} = max{μ_{i}, ν_{i}} for i = 1, 2, . . .. The intersection μ ∩ ν of two partitions μ and ν is the partition which arises by forming the intersection of the Ferrers diagrams of μ and ν. Thus, if μ = (μ_{1}, μ_{2}, …) and ν = (ν_{1}, ν_{2}, …), then μ ∩ ν is the partition ρ = (ρ_{1}, ρ_{2}, …), where ρ_{i} = min{μ_{i}, ν_{i}} for i = 1, 2, . . ..

Given a partition λ = (λ_{1}, λ_{2}, …, λ_{ℓ}), a standard (Young) tableau of shape λ is a leftjustified arrangement of positive integers with λ_{i} entries in row i, i = 1, 2, …, such that the entries along rows and columns are increasing. An arrangement T of the same form as above is called semistandard tableau of shape λ if the entries along rows are weakly increasing and such that the entries along columns are strictly increasing. By considering the sequence of partitions (Ferrers shapes) (λ^{i})_{i≥0}, where λ^{i} is the shape formed by the entries of T which are at most i, i = 0, 1, 2, …, one sees that standard tableaux of shape λ are in bijection with sequences ∅ = λ^{0} ⊆ λ^{1} ⊆ ⋯ ⊆ λ^{n} = λ, where λ^{i−1} and λ^{i} differ by exactly one square for all i, while semistandard tableaux of shape λ are in bijection with such sequences where λ^{i−1} and λ^{i} differ by a horizontal strip for all i, that is, by an arrangement of squares with at most one square in each column.

Generalising the above concepts, we call a sequence ∅ = λ^{0}, λ^{1}, …, λ^{n} = λ of partitions an oscillating tableau of shape λ if either λ^{i−1} ⊆ λ^{i} or λ^{i−1} ⊇ λ^{i} and λ^{i−1} and λ^{i} differ by exactly one square, i = 1, 2, …, n. The number n is called the length of the (generalised) oscillating tableau. If we say that an oscillating tableau has “at most k columns” then we mean that all partitions in the sequence have at most k columns.

Growth diagrams are certain labellings of arrangements of cells. The arrangements of cells which we need here are arrangements which are left-justified (that is, they have a straight vertical left boundary), bottom-justified (that is, they have a straight horizontal bottom boundary), and rows and columns in the arrangement are “without” holes, that is, if we move along the top-right boundary of the arrangement, we always move either to the right or to the bottom. Figure 1.a shows an example of such a cell arrangement.

We fill the cells of such an arrangement C with non-negative integers. Most of the time, the fillings will be restricted to 0-1-fillings such that every row and every column contains at most one 1. See Figure 1.b for an example.

Next, the corners of the cells are labelled by partitions such that the following two conditions are satisfied:

(C1) A partition is either equal to its right neighbour or smaller by exactly one square,

the same being true for a partition and its top neighbour. (C2) A partition and its right neighbour are equal if and only if in the column of cells

of C below them there appears no 1 and if their bottom neighbours are also equal to each other. Similarly, a partition and its top neighbour are equal if and only

0 0 0 0 0  0 0 0 0 0 0 0 0 1 1  1

a. A cell arrangement b. A filling of the cell arrangement

Figure 1

if in the row of cells of C to the left of them there appears no 1 and if their left neighbours are also equal to each other.

See Figure 2 for an example. (More examples can be found in Figures 4–6.) There, we use a short notation for partitions. For example, 11 is short for (1, 1). Moreover, we changed the convention of representing the filling slightly for better visibility, by suppressing 0’s and by replacing 1’s by X’s. Indeed, the filling represented in Figure 2 is the same as the one in Figure 1.b.

Diagrams which obey the conditions (C1) and (C2) are called growth diagrams.

We are interested in growth diagrams which obey the following (forward) local rules (see Figure 3).

(F1) If ρ = μ = ν, and if there is no cross in the cell, then λ = ρ. (F2) If ρ = μ ≠ ν, then λ = ν. (F3) If ρ = ν ≠ μ, then λ = μ. (F4) If ρ, μ, ν are pairwise different, then λ = μ ∪ ν. (F5) If ρ ≠ μ = ν, then λ is formed by adding a square to the (k + 1)-st row of μ = ν,

given that μ = ν and ρ differ in the k-th row. (F6) If ρ = μ = ν, and if there is a cross in the cell, then λ is formed by adding a square

∅^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}  ^{1}^{1}^{1}^{∅}^{∅}^{∅}^{∅}  ^{11}^{11}^{1}^{1}^{∅}^{∅}  ^{1}^{1}^{∅}^{∅}  ^{∅}^{∅}  ^{1}^{∅} X X  X

A growth diagram

Figure 2

[figure: ρ; μ; ν; λ; ρ; μ; ν; λ]

a. A cell without cross b. A cell with cross

Figure 3

to the first row of ρ = μ = ν. Thus, if we label all the corners along the left and the bottom boundary by empty

partitions (which we shall always do in this paper), these rules allow one to determine all other labels of corners uniquely.

It is not difficult to see that the rules (F5) and (F6) are designed so that one can also work one’s way in the other direction, that is, given λ, μ, ν, one can reconstruct ρ and the filling of the cell. The corresponding (backward) local rules are:

(B1) If λ = μ = ν, then ρ = λ.

(B2) If λ = μ ≠ ν, then ρ = ν.

(B3) If λ = ν ≠ μ, then ρ = μ.

(B4) If λ, μ, ν are pairwise different, then ρ = μ ∩ ν.

(B5) If λ ≠ μ = ν, then ρ is formed by deleting a square from the (k − 1)-st row of

μ = ν, given that μ = ν and λ differ in the k-th row, k ≥ 2. (B6) If λ ≠ μ = ν, and if λ and μ = ν differ in the first row, then ρ = μ = ν.

In case (B6) the cell is filled with a 1 (an X). In all other cases the cell is filled with a 0.

Thus, given a labelling of the corners along the right/up boundary of a cell arrangement, one can algorithmically reconstruct the labels of the other corners of the cells and of the 0-1-filling by working one’s way to the left and to the bottom. These observations lead to the following theorem.

Theorem 1. Let C be an arrangement of cells. The 0-1-fillings of C with the property that every row and every column contains at most one 1 are in bijection with labellings (∅ = λ^{0}, λ^{1}, …, λ^{k} = ∅) of the corners of cells appearing along the top-right boundary of C, where λ^{i−1} and λ^{i} differ by at most one square, and λ^{i−1} ⊆ λ^{i} if λ^{i−1} and λ^{i} appear along a horizontal edge, whereas λ^{i−1} ⊇ λ^{i} if λ^{i−1} and λ^{i} appear along a vertical edge. Moreover, λ^{i−1} ⫋ λ^{i} if and only if there is a 1 in the column of cells of C below the corners labelled by λ^{i−1} and λ^{i}, and λ^{i−1} ⫌ λ^{i} if and only if there is a 1 in the row of cells of C to the left of the corners labelled by λ^{i−1} and λ^{i}.

In addition to its local description, the bijection of the above theorem has also a global description. The latter is a consequence of a theorem of Greene [15] (see also [2, Theorems 2.1 and 3.2]). In order to formulate the result, we need the following definitions: a NE-chain of a 0-1-filling is a sequence of 1’s in the filling such that any 1 in the sequence is above and to the right of the preceding 1 in the sequence. Similarly, a SE-chain of a 0-1-filling is a set of 1’s in the filling such that any 1 in the sequence is below and to the right of the preceding 1 in the sequence.

Theorem 2. Given a growth diagram on a cell arrangement with empty partitions labelling all the corners along the left boundary and the bottom boundary of the cell arrangement, the partition λ = (λ_{1}, λ_{2}, …, λ_{ℓ}) labelling corner c satisfies the following two properties:

(G1) For any k, the maximal cardinality of the union of k NE-chains situated in the

rectangular region to the left and below of c is equal to λ_{1} + λ_{2} + ⋯ + λ_{k}. (G2) For any k, the maximal cardinality of the union of k SE-chains situated in the

rectangular region to the left and below of c is equal to λ′_{1} + λ′_{2} + ⋯ + λ′_{k}, where λ′ denotes the partition conjugate to λ.

In particular, λ_{1} is the length of the longest NE-chain in the rectangular region to the left and below of c, and λ′_{1} is the length of the longest SE-chain in the same rectangular region.

3. The main theorems. Here, we state and prove our main results. The theorem below proves and, at the same time, refines Burrill’s conjecture from the introduction. In the statement of the theorem and later, the symbol (1^{m}) stands for the partition (1, 1, …, 1), with m components 1, that is, the one-column shape of length m.

Theorem 3. Let n, m, k be given non-negative integers. The number of oscillating tableaux of length n with at most k columns, starting at ∅ and ending at the one-column shape (1^{m}), is equal to the number of standard Young tableaux of size n with m columns of odd length, all columns of length at most 2k.

Proof. We start with a standard Young tableau T of size n with at most 2k rows and with m columns of odd length. As a running example, we choose

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

with n = 12, k = 3, and m = 2. Indeed, this standard Young tableau has 12 entries, it has less than or equal to 2k = 6 rows (namely 5) and 2 columns of odd length.

Step 1. At the end of the odd-length columns, we put I, II, III, …, from left to right. In our running example, we obtain

1 3 4 8
2 6 7 II
5 10
9 12

11 I

We slide I, II, III, …, in this order, to the top-left of the tableau, using (inverse) jeu de taquin (cf. [26, Sec. 3.7]). That is, as long as above I we find an entry belonging to {1, 2, …, n}, we interchange I with this entry; then, as long as to the left of or above II we find entries belonging to {1, 2, …, n}, we interchange II with the larger of the two entries; then we do the same with III, IV, etc. In the end, we obtain the standard tableau T′ in the alphabet I, II, III, …, 1, 2, . . .. In our running example, we get

\begin{matrix}I & II & 3 & 4 \\ 1 & 6 & 7 & 8 \\ 2 & 10 \\ 5 & 12 \\ 9 \\ 11 \end{matrix}

It should be observed that, necessarily, I, II, III, … come to rest in the first row, in this order. The reason is that successive jeu de taquin paths cannot cross each other, of which one can easily convince oneself. More precisely, the jeu de taquin path of I has to stay (weakly) to the left of the path of II, but strictly to the left along vertical pieces, the same being true for the jeu de taquin paths of II and III, etc.

Step 2. We interpret the tableau T′ as a sequence of partitions ∅ = λ^{0} ⊆ λ^{1} ⊆ ⋯ ⊆ λ^{n+m} = λ, as described in Section 2. The partitions are placed along the corners of the upper boundary of an (n + m) × (n + m) square cell arrangement from right to left, and along the left boundary from bottom to top. Then we apply the inverse growth diagram algorithm described in Section 2, however, not in direction bottom/left but instead in direction bottom/right. For the result in our running example see Figure 4.^{1} In the figure, we have “separated” the rows and columns corresponding to the “extra” letters I and II by thick lines.

Clearly, the growth diagram is symmetric with respect to the main diagonal (i.e., the top/left–bottom/right diagonal). Furthermore, by Greene’s theorem, the lengths of northeast chains of 1’s (i.e., of X’s) are at most 2k. Moreover, again by Greene’s theorem (but now using item (G2)), since we started with a tableau with all columns of even length, there cannot be any crosses along the main diagonal. (This is a fact observed earlier by Schützenberger [28, p. 127] in a more general form.)

Finally, since the letters I, II, III, … appeared in the first row of T′ in that order, the X’s in the rows labelled by these letters (the last rows; in the running example these are the last two rows) form one SE-chain. (Also this follows from Greene’s theorem.) Together with the earlier observations that the diagram is symmetric with respect to the main diagonal and that there are no crosses along the main diagonal, it follows that the region below the thick horizontal line and to the right of the thick vertical horizontal line does not contain any crosses.

Step 3. Since the diagram is symmetric without crosses on the main diagonal, we may forget about one half of the diagram, say the upper half (including the main diagonal). In our running example, we arrive at the filling of the staircase diagram displayed in Figure 5.

Now we place empty partitions along the corners of the left and the bottom boundary of the staircase diagram. To the resulting diagram we apply the (forward) growth diagram construction as described in Section 2, here in direction top/right. Figure 6 shows the result in our running example.

(I, 5)(II, 11)(1, 9)(2, 6)(3, 7)(4, 12)(8, 10).

1Alternatively, we could have applied the inverse Robinson–Schensted algorithm to the tableau pair (T′, T′). This yields an involution (since we started with a tableau pair consisting of two identical tableaux)

on I, II, III, …, 1, 2, . . .. In our running example, we obtain the involution We represent this involution as a 0-1-filling of a square, where we label the rows I, II, III, …, 1, 2, … from bottom to top, and columns by the same labels from right to left (skipping unconcerned labels). In our running example, this leads to the 0-1-filling in Figure 4 (with X’s representing the 1’s, while empty cells represent the 0’s). That this is indeed equivalent is due to the fact (cf. [2, pp. 95–98], [30, Theorem 7.13.5])

that the bijection between permutations and pairs of standard tableaux defined by the growth diagram on the square coincides with the Robinson–Schensted correspondence.

X X  X  X X X  X X X X  X X  X X_{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{1}^{1}^{1}^{1}^{1}^{1}^{1}^{1}  ^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{1}^{1}^{1}^{1}^{1}^{1}^{2}^{2}  ^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{1}^{1}^{1}^{1}^{2}^{2}^{21}^{21}  ^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{1}^{2}^{2}^{2}^{21}^{21}^{211}^{211}  ^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{1}^{2}^{3}^{3}^{31}^{31}^{311}^{311}  ^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{1}^{2}^{3}^{3}^{31}^{31}^{311}^{411}  ^{1}^{1}^{1}^{1}^{1}^{1}^{11}^{21}^{31}^{31}^{311}^{311}^{3111}^{4111}  ^{1}^{1}^{1}^{2}^{2}^{2}^{21}^{22}^{32}^{32}^{321}^{321}^{3211}^{4211}  ^{1}^{1}^{1}^{2}^{3}^{3}^{31}^{32}^{33}^{33}^{331}^{331}^{3311}^{4311}  ^{1}^{1}^{1}^{2}^{3}^{3}^{31}^{32}^{33}^{33}^{331}^{431}^{4311}^{4411}  ^{1}^{1}^{2}^{21}^{31}^{31}^{311}^{321}^{331}^{331}^{3311}^{4311}^{43111}^{44111}  ^{1}^{1}^{2}^{21}^{31}^{31}^{311}^{321}^{331}^{431}^{4311}^{4411}^{44111}^{44211}  ^{1}^{2}^{21}^{211}^{311}^{311}^{3111}^{3211}^{3311}^{4311}^{43111}^{44111}^{441111}^{442111}  ^{1}^{2}^{21}^{211}^{311}^{411}^{4111}^{4211}^{4311}^{4411}^{44111}^{44211}^{442111}^{442211}

Figure 4

X X  X  X X X  X

Figure 5

X X  X  X X X  X_{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}  ^{∅}  ^{∅}  ^{∅}  ^{∅}  ^{∅}  ^{∅}  ^{∅}  ^{1}  ^{1}  ^{1}  ^{1}  ^{1}^{∅}  ^{1}  ^{1}  ^{1}  ^{1}  ^{1}  ^{1}  ^{11}  ^{11}  ^{11}  ^{11}^{∅}  ^{1}  ^{1}  ^{2}  ^{2}  ^{2}  ^{2}  ^{21}  ^{21}  ^{21}^{∅}  ^{1}  ^{1}  ^{2}  ^{2}  ^{2}  ^{3}  ^{31}  ^{31}^{∅}  ^{1}  ^{1}  ^{2}  ^{2}  ^{3}  ^{31}  ^{311}^{1}  ^{11}  ^{11}  ^{21}  ^{21}  ^{31}  ^{311}^{1}  ^{11}  ^{11}  ^{21}  ^{21}  ^{31}^{1}  ^{11}  ^{11}  ^{21}  ^{21}^{1}  ^{11}  ^{11}  ^{21}^{1}  ^{11}  ^{21}^{1}  ^{11}^{1}^{1} ^{11} ^{21} ^{22} ^{21} ^{31} ^{311} ^{3111} ^{311} ^{31} ^{21} ^{11} ^{1}

Figure 6

Along the corners on the main diagonal one reads an oscillating tableau of length n + m. (In the running example in Figure 6, this is the sequence of larger printed partitions.) However, since by one of the previous observations (plus Greene’s theorem) we know that the last m + 1 partitions (shapes) in the oscillating tableau will be (1^{m}), (1^{m−1}), (1^{m−2}), …, (1, 1), (1), ∅, we may discard all of them except (1^{m}), and in this way obtain an oscillating tableau of length n, starting at ∅ and ending at (1^{m}). Using Greene’s theorem once more, we also see that no shape along the main diagonal can have more than k columns.

Since every step in this construction can be reversed in straightforward fashion, this yields the desired bijection. □

The announced “Knuth-type” extension of Theorem 3 is the following.

Theorem 4. Let n, m, k and j_{1}, j_{2}, …, j_{n} be non-negative integers. The number of sequences of partitions ∅ = λ^{0}, λ^{1}, …, λ^{2n} = (1^{m}) of length 2n, with λ^{2i−2} ⊇ λ^{2i−1} and λ^{2i−1} ⊆ λ^{2i} for i = 1, 2, …, n, where each pair (λ^{i−1}, λ^{i}) differs by a vertical strip (that is, by a collection of cells which contains at most one cell in each row), i = 1, 2, …, n, where each partition λ^{i} has at most k columns, and where |λ^{2i−2}| − 2|λ^{2i−1}| + |λ^{2i}| = j_{n−i+1} (the left-hand side is the sum of the differences in sizes of (λ^{2i−2}, λ^{2i−1}) and of (λ^{2i−1}, λ^{2i})), i = 1, 2, …, n, is equal to the number of semistandard tableaux with j_{i} entries i, i = 1, 2, …, n, with m columns of odd length, all columns of length at most 2k.

Remark. Theorem 3 is the special case of Theorem 4 where j_{1} = j_{2} = ⋯ = j_{n} = 1.

Sketch of proof. One proceeds in analogy with the proof of Theorem 3. As a running example for illustration, we choose n = 4, m = 2, k = 2, j_{1} = 5, j_{2} = 2, j_{3} = 6, j_{4} = 3, and the semistandard tableau

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

4

Indeed, this semistandard tableau has m = 2 columns of odd length, all columns of length at most 2k = 4, j_{1} = 5 entries 1, j_{2} = 2 entries 2, j_{3} = 6 entries 3, and j_{4} = 3 entries 4.

Step 1. We place I, II, … at the end of the columns of odd length, from left to right. In our running example, we obtain

1 1 1 1 1 3 3
2 2 3 3 4 4 II
3 3
4 I

Then we slide I, II, … up to the first row. The result in our example is

I II 1 1 1 3 3
1 1 2 3 3 4 4
2 3
3 4

Step 2. Instead of applying the (ordinary) inverse growth diagram algorithm, we apply its Knuth-type extension as described in [18, Sec. 4.1] or [24, Sec. 4.1]. Instead of a symmetric 0-1-filling, here we obtain a symmetric matrix with non-negative integer entries. Again, along the diagonal there will be only 0’s. Figure 7.a shows what we obtain in our running example.

Step 3. For the final step, in place of the (ordinary) growth diagram algorithm, we apply its Knuth-type extension described in [18, Sec. 4.4] or [20, Sec. 3.2]. The result

0 0 0 1 0 0 0 1 0 0 0 0 1 2 1 0 0 1 0 1 0 1 0 0 2 0 1 2 1 0 0 2 0 1 0 0_{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{∅}^{1}^{1}^{1}^{1}  ^{∅}^{∅}^{1}^{1}^{2}^{2}  ^{1}^{1}^{11}^{21}^{42}^{52}  ^{1}^{1}^{21}^{22}^{521}^{531}  ^{1}^{2}^{42}^{521}^{5511}^{7521}  ^{1}^{2}^{52}^{531}^{7521}^{7722}  0 0 0 1 0 0 1 0 0 1 2 1 0 1 2_{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}  _{∅}^{∅}  ^{∅}  ^{∅}  ^{∅}  ^{1}  ^{1}^{∅}  ^{∅}  ^{1}  ^{1} ^{11}^{∅}  ^{1}  ^{1111} ^{2111}^{∅}  ^{1} ^{2111}^{∅}  ^{111}^{∅}

a. Second step b. Third step

Figure 7

for our running example is shown in Figure 7.b. To obtain the (generalised) oscillating tableau, we must read all partitions along the top-right boundary of the cell arrangement (that is, including those which label “inner” corners), again skipping the ones in the region to the right of the thick vertical line. In Figure 7, these are the large printed partitions, namely

∅, ∅, 111, 1, 2111, 1111, 2111, 1, 11.

It is not difficult to see that this map has all the desired properties. □

4. Concluding remarks.

(1) For both numbers in Theorem 3, there are explicit formulae available. As pointed out in [5, paragraphs around Theorem 19], Gessel and Zeilberger’s general result [12] on enumeration of lattice paths by means of the reflection principle yields (see Eq. (38) in [14] with n replaced by k, λ = (k, k − 1, …, 1), and η = (m + k, k − 1, k − 2, …, 1)) that the number of oscillating tableaux in Theorem 3 is given by the coefficient of t^{n}/n! in

det (I_{i−j+m·χ(i=k)}(2t) − I_{i+j+m·χ(i=k)}(2t))_{1≤i,j≤k} ,  (4.1)

where I_{α}(x) is the modified Bessel function of the first kind

I_{α}(x) = ∑_{ℓ=0}^{∞} \frac{(x/2)^{2ℓ+α}}{ℓ! (ℓ + α)!} ,

and χ(A) = 1 if A is true and χ(A) = 0 otherwise. On the other hand, one obtains the same formula for the number of standard Young tableaux in Theorem 3 from a result of Goulden [13] (see [17, Eq. (3.6)] for a different proof). Namely, if one extracts the coefficient of x_{1}x_{2} ⋯ x_{n} in Theorem 2.6 of [13] with m and k interchanged, and after having applied the involution ω on symmetric functions which maps the complete homogeneous symmetric functions to the elementary symmetric functions (cf. [21]), then the conclusion is that the number of standard Young tableaux in Theorem 3 is given by the coefficient of t^{n}/n! in (4.1). This amounts to an alternative — albeit very roundabout and involved, nonilluminating — computational proof of Theorem 3. A proof of Theorem 4 along the same lines is also possible.

(2) What happens if we want to count standard Young tableaux of size n with m columns of odd length, all columns of length at most 2k+1 (instead of at most 2k)? As it turns out, the corresponding number equals \binom{n}{m} times the number of all standard Young tableaux of size n − m with all columns of even length not exceeding 2k. (In other words: the above problem can be reduced to the m = 0 case in Theorem 3.) This is seen as follows: let T be a standard Young tableau of size n with m columns of odd length, all columns of length at most 2k + 1. To the last entries in the odd columns of T one applies the inverse mapping of Robinson–Schensted insertion (cf. [26, Proof of Theorem 3.1.1]), starting with the last entry in the right-most odd column, continuing with the last entry in the (then) right-most odd column, until all odd columns have disappeared. This produces a standard Young tableau of size n − m with only even columns, all of which have length at most 2k, and a subset of {1, 2, …, n} of cardinality m. It is easy to see that all the steps in this mapping can be reversed so that this describes a bijection.

(3) As indicated in the introduction, the difference between the bijection proving Theorem 3 presented here and that of [5] lies in the way one keeps track of the parameter m in Theorem 3. Namely, in Step 1 of our proof of Theorem 3, we introduce the auxiliary letters I, II, III, … in order to “make the m odd columns even,” and move the letters inside the tableau by jeu de taquin. Then, in Step 2, we apply the (inverse) growth diagram construction to the complete square, and finally, in Step 3, we apply the (forward) growth diagram construction to half of the square to obtain the corresponding oscillating tableau.

On the other hand, if one realises the construction in [5] by means of growth diagrams, then Burrill, Courtiel, Fusy, Melczer and Mishna apply the (inverse) growth diagram construction directly, without any “preprocessing.” The “price to pay” is that they do obtain X’s on the main diagonal. These m X’s must be somehow moved “into the half-square,” and in order to be able to do this without creating any unwanted chains, the growth diagram construction has to be first played forth and back on the half-square. Only then, the X’s on the diagonal can be “moved inside,” and a final application of the (forward) growth diagram construction on the half-square completes the bijection. As far as I can see, other than that, the two constructions do not seem to be more deeply related.

References

1. A. Berele, A Schensted-type correspondence for the symplectic group, J. Combin. Theory Ser. A 43 (1986), 320–328.

2. T. Britz and S. Fomin, Finite posets and Ferrers shapes, Adv. Math. 158 (2001), 86–127.

3. S. Burrill, A generating tree approach to k-nonnesting arc diagrams, Ph.D. thesis, Simon Fraser University, Burnaby, Canada, 2014, available at http://summit.sfu.ca/item/14390.

4. S. Burrill, S. Melczer and M. Mishna, A Baxter class of a different kind, and other bijective results using tableau sequences ending with a row shape, manuscript; arχiv:1411.6606.

5. S. Burrill, J. Courtiel, E. Fusy, S. Melczer and M. Mishna, Tableau sequences, open diagrams, and Baxter families, preprint; arχiv:1506.03544v1.

6. W. Y. C. Chen, E. Y. P. Deng, R. R. X. Du, R. P. Stanley and C. H. Yan, Crossings and nestings of matchings and partitions, Trans. Amer. Math. Soc. 359 (2007), 1555–1575.

7. M.-P. Delest, S. Dulucq and L. Favreau, An analogue to Robinson–Schensted correspondence for oscillating tableaux, Sém. Lotharingien Combin. B20 (1988), Article B20b, 11 pp.

8. S. Dulucq and B. E. Sagan, La correspondance de Robinson–Schensted pour les tableaux oscillants gauches, Discrete Math. 139 (1995), 129–142.

9. S. V. Fomin, Generalized Robinson–Schensted–Knuth correspondence, (Russian), Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 155 (1986), translation in J. Soviet Math. 41 (1988), 979–991.

10. S. Fomin, Schensted algorithms for graded graphs, J. Alg. Combin. 4 (1995), 5–45.

11. S. Fomin, Schur operators and Knuth correspondences, J. Combin. Theory Ser. A 72 (1995), 277–292.

12. I. M. Gessel and D. Zeilberger, Random walk in a Weyl chamber, Proc. Amer. Math. Soc. 115 (1992), 27–31.

13. I. P. Goulden, A linear operator for symmetric functions and tableaux in a strip with given trace, Discrete Math. 99 (1992), 69–77.

14. D. J. Grabiner and P. Magyar, Random walks in Weyl chambers and the decomposition of tensor products, J. Alg. Combin. 2 (1993), 239–260.

15. C. Greene, An extension of Schensted’s theorem, Adv. Math. 14 (1974), 254–265.

16. D. E. Knuth, Permutations, matrices, and generalized Young tableaux, Pacific J. Math. 34 (1970), 709–727.

17. C. Krattenthaler, Identities for classical group characters of nearly rectangular shape, J. Algebra 209 (1998), 1–64.

18. C. Krattenthaler, Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes, Adv. Appl. Math. 37 (2006), 404–431.

19. M.van Leeuwen, The Robinson–Schensted and Schützenberger algorithms, an elementary approach, Electron. J. Combin. 3 (no. 2, “The Foata Festschrift”) (1996), Article #R15, 32 pp.

20. M. van Leeuwen, Spin-preserving Knuth correspondences for ribbon tableaux, Electron. J. Combin. 12(1) (2005), Article #R10, 65 pp.

21. I. G. Macdonald, Symmetric Functions and Hall Polynomials, second edition, Oxford University Press, New York/London, 1995.

22. R. A. Proctor, A generalized Berele–Schensted algorithm and conjectured Young tableaux for intermediate symplectic groups, Trans. Amer. Math. Soc. 324 (1991), 655–692.

23. G. de B. Robinson, On representations of the symmetric group, Amer. J. Math. 60 (1938), 745–760.

24. T. W. Roby, Applications and extensions of Fomin’s generalization of the Robinson–Schensted correspondence to differential posets, Ph.D. thesis, M.I.T., Cambridge, Massachusetts, 1991.

25. T. W. Roby, The connection between the Robinson–Schensted correspondence for skew oscillating tableaux and graded graphs, Discrete Math. 139 (1995), 481–485.

26. B. E. Sagan, The symmetric group, 2nd edition, Springer–Verlag, New York, 2001.

27. C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179–191.

28. M.-P. Schützenberger, Quelques remarques sur une construction de Schensted, Math. Scand. 14 (1963), 117–128.

29. M.-P. Schützenberger, La correspondance de Robinson, Combinatoire et Représentation du Groupe Symétrique, Lecture Notes in Math., vol. 579, Springer–Verlag, Berlin–Heidelberg–New York, 1977, pp. 59–113.

30. R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.

31. S. Sundaram, Tableaux in the representation theory of the classical Lie groups, Invariant theory and tableaux (D. Stanton, ed.), The IMA Volumes in Math. And Its Appl., Vol. 19, Springer–Verlag, New York, Berlin, Heidelberg, 1989, pp. 191–225.

32. S. Sundaram, Orthogonal tableaux and an insertion algorithm for SO(2n + 1), J. Combin. Theory Ser. A 53 (1990), 239–256.

33. S. Sundaram, The Cauchy identity for Sp(2n), J. Combin. Theory Ser. A 53 (1990), 209–238.

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

WWW: http://www.mat.univie.ac.at/~kratt