AN ANALOGUE TO ROBINSON-SCHENSTED CORRESPONDENCE FOR OSCILLATING TABLEAUX (*)

by

Marie Pierre Delest, Serge Dulucq and Luc Favreau

Abstract. We give the hook formula for oscillating tableaux of length n and final shape λ, and using a bijective proof we construct an analog of the Robinson-Schensted correspondence to prove the dimension identity,

1 · 3 · 5 ⋯ (2n − 1) = ∑_{λ}(f_{n}^{λ})^{2}

related to the irreducible representations of the Brauer algebra of the symplectic group, [2], [9]. This correspondence turns out to have most of the ordinary Robinson-Schensted correspondence properties.

1. Introduction. We define an oscillating tableau of length n and shape λ to be the sequence

∅, λ_{1}, λ_{2}, …, λ_{n}

of Ferrers diagrams such that λ_{1} is a single square (λ_{1} = □), λ_{n} is λ and for each i + 1, the shape λ_{i+1} is obtained from λ_{i} by adding or deleting an admissible square. For instance,

\begin{aligned}& & & & □ & & □ & & & & & & □ \\ ∅ & □ & □ & □ & □ & □ & □ & □ & ∅ & □ & □ & □ & □ & □ \end{aligned}

is an oscillating tableau of length 9 and of shape (2, 1). One can see that a standard tableau is just an oscillating tableau in which we never delete any cell. The usual Robinson-Schensted correspondence (R.S.C.) is an algorithm which associates bijectively to each permutation σ of the symmetric group S_{n} a pair of standard tableaux with the same shape. This correspondence gives a proof of the dimension formula

n! = ∑_{λ}(n_{λ})^{2} ,  (1.1)

where the sum ranges over all shapes and n_{λ} is the degree of the corresponding irreducible representation of S_{n}. For more details see [6], [8], [10]. We will write

σ ⟷ (P (σ), Q(σ)).

Typeset by AMS-TEX

(*) This work has been supported by the P.R.C. ”Mathematiques et Informatique.”

If we consider the P -tableau and the Q-tableau associated to the inverse permutation, we have the following identities,

P (σ^{−1}) = Q(σ) and Q(σ^{−1}) = P (σ).  (1.2)

For a beautiful proof of this fact see [8]. Also if we set σ^{∗} to be the reverse word σ_{n} ⋯ σ_{1}, we will get the following,

P (σ^{∗}) = P^{T} (σ) and Q(σ^{∗}) = Q_{V.R.}^{T}(σ),  (1.3)

where the superscript T means the transpose of the tableau and the subscript V.R. refers to the so-called ”vidage-remplissage” algorithm due to Schützenberger [5].

The hook formula for ordinary tableaux gives the number of standard tableaux of shape λ, that is

n_{λ} = \frac{n!}{∏ h_{λ}} ,

where ∏ h_{λ} is the product of all hook lengths of the shape λ, [4].

For instance, if

σ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 7 & 2 & 1 & 3 & 9 & 5 & 8 & 4 & 6 \end{matrix} ) ,

then

P (σ) = 7 9 2 5 8 1 3 4 6 and Q(σ) = \begin{matrix}3 & 8 \\ 2 & 6 & 9 \\ 1 & 4 & 5 & 7 . \end{matrix}

The inverse and mirror permutations are

σ^{−1} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 3 & 2 & 4 & 8 & 6 & 9 & 1 & 7 & 5 \end{matrix} ) , σ^{∗} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 6 & 4 & 8 & 5 & 9 & 3 & 1 & 2 & 7 \end{matrix} ) .

Applying R.S.C. to the inverse we get

P (σ^{−1}) = 3 8 2 6 9 1 4 5 7 and Q(σ^{−1}) = \begin{matrix}7 & 9 \\ 2 & 5 & 8 \\ 1 & 3 & 4 & 6 , \end{matrix}

that is

P (σ^{−1}) = Q(σ) and Q(σ^{−1}) = P (σ),

and finally

P (σ^{∗}) = 6 4 8 3 5 9 1 2 7 and Q(σ^{∗}) = \begin{matrix}7 \\ 6 & 8 \\ 2 & 4 & 9 \\ 1 & 3 & 5 , \end{matrix}

where

P (σ^{∗}) = P^{T} (σ) and Q(σ^{∗}) = Q_{V.R.}^{T}(σ).

Let λ be the shape (3, 2),

λ = \begin{matrix}□ □ \\ □ □ □ \end{matrix} .

The number of standard tableaux with this shape is obtained by first computing the hook length of each cell. That is, for each cell we count the number of cells belonging to the hook for which it is the corner. Labelling the cells by their hook length will give in this case

\begin{matrix}2 & 1 \\ 4 & 3 & 1 . \end{matrix}

Using the formula we obtain

n_{(3,2)} = \frac{5 · 4 · 3 · 2 · 1}{4 · 3 · 2 · 1 · 1} = 5 .

It means that there are exactly 5 tableaux with this shape, namely:

\begin{matrix}4 & 5 \\ 1 & 2 & 3 , \end{matrix} \begin{matrix}3 & 5 \\ 1 & 2 & 4 , \end{matrix} \begin{matrix}3 & 4 \\ 1 & 2 & 5 , \end{matrix} \begin{matrix}2 & 5 \\ 1 & 3 & 4 , \end{matrix} \begin{matrix}2 & 4 \\ 1 & 3 & 5 . \end{matrix}

The goal of the this paper is to recall the hook formula for oscillating tableaux, the result is due to S. Sundaram [7], then give an extension of the Robinson-Schensted algorithm in order to prove an analog of (1.1). It will turn out that the proposed algorithm gives properties analogous to (1.2) and (1.3) as well. There exist other correspondences in the literature, for instance see [1] or [3], but they are developed quite differently.

2. Hook formula for oscillating tableaux. We denote by f_{n}^{λ} the number of oscillating tableaux of length n and shape λ. It is easy to see that f_{n}^{λ} will be zero if n − |λ| is an odd number. One can also see that an oscillating tableau is a path in the Young lattice starting from ∅ and ending in the shape λ. But before going further we introduce some definitions and fix some notations.

Definition 1. Let n, m be two integers such that m ≤ n. An injective tableau T^{λ} is an exhaustive labelling of a Ferrers diagram of shape λ ⊢ m by numbers in a subset S included in {1, 2, …, n} of cardinality m, in such way that rows and columns are strictly increasing.

The number of such tableaux is \binom{n}{|λ|} · n_{λ}.

In the following, when we will say involution we mean an involution on a set S of even cardinality without fixed points. For a given set S there are exactly 1·3 ⋯ (|S|−1) such involutions. To have a convenient notation, we shall present an involution τ in form of two rows of distinct numbers

τ = ( \begin{matrix}α_{1} & α_{2} & … & α_{k} \\ β_{1} & β_{2} & … & β_{k} \end{matrix} ) ,

where α_{1} < α_{2} < ⋯ < α_{k} and for all i’s α_{i} > β_{i}. In fact, written in a more classical way, τ is just a product of transpositions

τ = (α_{1}β_{1})(α_{2}β_{2}) ⋯ (α_{k}β_{k}).

We are now ready to announce the Theorem 1. The number of oscillating tableaux of length n and shape λ is

f_{n}^{λ} = 1 · 3 ⋯ (n − |λ| − 1) · ( \begin{matrix}n \\ |λ| \end{matrix} ) · n_{λ},

where |λ| is the number of cells in the final shape and n_{λ} is the number of standard tableaux having this shape.

Let us write [m] for {1, 2, …, m}. To prove the assertion we construct a bijective map

Φ : O O O_{n}^{λ} ⟷ T^{λ} × III_{n−|λ|} × S S S ,

where O O O_{n}^{λ} is the set of all oscillating tableaux of length n and shape λ, T T T^{λ} is the set of all standard tableaux of shape λ, III_{n−|λ|} is the set of all involutions without fixed points on [n − |λ|], and S S S is the set of all subsets of [n] of cardinality |λ|.

Proof. Let O_{n}^{λ} be an oscillating tableau of length n and shape λ = λ_{n}

O_{n}^{λ} = ∅, λ_{1}, λ_{2}, …, λ_{n}.

We produce a pair (τ, T^{λ}), where T^{λ} is an injective tableau on an underlying subset S, and τ is an involution on the underlying complementary subset [n] − S of even cardinality. First we construct the sequence

∅, T_{1}, T_{2}, …, T_{n} = T^{λ}

of injective tableaux having respectively shape

∅, λ_{1}, λ_{2}, …, λ_{n}.

Starting from ∅ we do,

(1) If |λ_{i+1}| > |λ_{i}| we construct T_{i+1} by adding to T_{i} the unique cell of the skew shape λ_{i+1}/λ_{i} labelled by i + 1.

(2) If |λ_{i+1}| < |λ_{i}| we construct T_{i+1} from T_{i} by applying the inverse of R.S.C. to bump out a unique element x of T_{i} in a way to obtain an injective tableau of shape λ_{i+1}.

At the same time we keep track of the bumped numbers, which we do by creating a list consisting of two rows,

( \begin{matrix}i_{1} & i_{2} & … & i_{k} \\ x_{1} & x_{2} & … & x_{k} \end{matrix} ) ,

where i_{k} is the number of the step that we are in, and x_{k} is the bumped number. Using this process we will end with an injective tableau of shape λ_{n} and an involution τ on some subset. Clearly the obtained tableau is an injective one. To see that we get an involution just observe that numbers are always added during the process before they are bumped, hence we will always have

i_{j} > x_{j},

and by construction we have

i_{1} < i_{2} < ⋯ < i_{k},

and all the x_{j} coming out of the tableaux are distinct because they were originally step numbers. To be convinced that the subset underlying the involution is exactly S^{c}, the complement of S, note that no x_{i} can be in T^{λ} (the x_{i}’s have been bumped out), and that any i_{j} is not in T^{λ} because only step numbers appear in T^{λ} where an etnry was added, while the i_{j}’s are step numbers where an entry was deleted.

To see that the map is a bijection we just construct the inverse map.

Let T^{λ} be an injective tableau on a certain subset S, and an injective involution

τ = ( \begin{matrix}i_{1} & i_{2} & … & i_{k} \\ x_{1} & x_{2} & … & x_{k} \end{matrix} ) ,

on the complement S^{c}. We construct the sequence of injective tableaux

T_{n}, T_{n−1}, …, T_{1}, ∅,

where T_{n} = T^{λ}, by applying one of the following two exhaustive rules.

(1) If i is one of the i_{j} then T_{i−1} is obtained from T_{i} by inserting the corresponding element x_{j} into T_{i} by R.S.C.

(2) If i is not one of the i_{j}, then the tableau T_{i} must contain i (otherwise it means that x_{j} = i for some j < i, contradicting the presentation of τ in which we should always have x_{j} < j, in fact i is the biggest element of T_{i}). In this case, just remove from T_{i} the corner cell containing i, this gives T_{i−1}.

At the end, just keep the corresponding shapes,

∅, λ_{1}, λ_{2}, …, λ_{n}.

One can see that this map is exactly the inverse of Φ. This complete the proof. ■

Example. Take an oscillating tableau,

\begin{aligned}& & & & □ & & □ & & & & & & □ & & □ \\ ∅ & □ & □ & □ & □ & □ & □ & □ & ∅ & □ & □ & □ & □ & □ & □ \end{aligned} .

Then we construct the sequence of injective tableaux,

\begin{aligned}& & & & 3 & & 3 & & & & & & 9 & & 9 \\ ∅ & 1 & 1 & 2 & 1 & 2 & 1 & 3 & ∅ & 7 & 7 & 8 & 7 & 8 & 7 \end{aligned} .

Taking note of the bumped elements in order, we get the involution

τ = ( \begin{matrix}4 & 5 & 6 & 10 \\ 2 & 1 & 3 & 8 \end{matrix} ) .

3. Symmetric correspondence for oscillating tableaux. Looking at the formula of Theorem 1, one can see that when the shape λ is a partition of n, we get back the usual hook formula for standard tableaux. On the other hand, if the shape λ is the empty one, we get an interesting identity,

1 · 3 ⋯ (m − 1) = f_{m}^{∅} .

This expression means that m is an even number, so we might as well set m = 2n and,

1 · 3 ⋯ (2n − 1) = f_{2n}^{∅} .  (3.1)

The left side of the equation can be interpreted as the Brauer algebra dimension, that is the number of generators of this algebra. As in [2], those generators can be visualised by graphs whose vertex contains two parallels rows of n dots, in which each dot is connected by an edge to exactly one other dot. Among these generators some can be identified with permutations in S_{n}. They are those for which every edge connects a dot in a row with a dot in the other row.

Let us look at the right side of equation (3.1), this number enumerates all the oscillating tableaux of length 2n and shape ∅, they have the form

O_{2n}^{∅} = ∅, λ_{1}, λ_{2}, …, λ_{n}, …, λ_{2n−2}, λ_{2n−1}, ∅ .

Now, a simple but very efficient remark will allow us to produce the analog of R.S.C. as a consequence of Theorem 1, just note that there is no restriction on λ_{n} in the tableau O_{2n}^{∅}. So we just set

P = ∅, λ_{1}, λ_{2}, …, λ_{n} ,  (3.2)
Q = ∅, λ_{2n−1}, λ_{2n−2}, …, λ_{n} .  (3.3)

The equation (3.1) can be rewritten as

1 · 3 · 5 ⋯ (2n − 1) = ∑_{λ}(f_{n}^{λ})^{2} ,

where λ range over all admissibles shapes. All we have to show now is how to pass from generators to involutions. After a few trials, we can see that labelling the second row of dots from left to right by numbers 1 to n, and the first row of dots from right to left by n + 1 to 2n, keeping the edges, will produce the proper involution assuring the translation by means of the usual correspondence in the case where the generator is an element of S_{n}, call this translation Υ . For instance,

10 9 8 7 6 1 2 3 4 5 \underleftrightarrow{Υ} ( \begin{matrix}3 & 6 & 7 & 9 & 10 \\ 2 & 1 & 5 & 4 & 8 \end{matrix} ) .

We can then state the Theorem 2. The generators of B_{n}, the Brauer algebra of the symplectic group, is in bijection with pairs of oscillating tableaux of length n and same shape λ, that is

1 · 3 · 5 ⋯ (2n − 1) = ∑_{λ}(f_{n}^{λ})^{2} .

Proof. Take any generator γ, construct Υ(γ), its associated involution, then application of Φ^{−1} to the involution will produce an oscillating tableau of shape ∅, break the sequence as in (3.2) and (3.3), that is the pair (P (γ), Q(γ)). ■

For instance, let

γ = 10 9 8 7 6 1 2 3 4 5 and Υ(γ) = ( \begin{matrix}3 & 6 & 7 & 9 & 10 \\ 2 & 1 & 5 & 4 & 8 \end{matrix} ) .

Applying Φ^{−1}, we get, from right to left

\begin{aligned}& & & & & 4 & 4 & & & & & 8 \\ ∅ & 1 & 1 & 2 & 1 & 1 & 1 & 5 & 4 & 5 & 4 & 4 & 8 & ∅ . \end{aligned}

Keeping only the shapes,

\begin{aligned}& & & & & □ & □ & & & & & □ \\ ∅ & □ & □ & □ & □ & □ & □ & □ & □ & □ & □ & □ & □ & ∅ . \end{aligned}

Breaking the sequence in two parts we obtain

P (γ) = \begin{aligned}& & & & & □ & □ \\ ∅ & □ & □ & □ & □ & □ & □ & □ \end{aligned} ,

Q(γ) = \begin{aligned}& & □ & & & & □ \\ ∅ & □ & □ & □ & □ & □ & □ & □ \end{aligned} .

Theorem 3. If γ is a generator of the Brauer algebra belonging to S_{n}, then the pair (P (γ), Q(γ)) of oscillating tableaux is a pair of standard tableaux, and these tableaux are the ones we obtained by applying R.S.C. to γ considered as an element of S_{n}.

Proof. Let γ be a generator which is also an element σ of S_{n}, the corresponding involution will be of the type

( \begin{matrix}n + 1 & n + 2 & ⋯ & 2n − 1 & 2n \\ σ_{n} & σ_{n−1} & ⋯ & σ_{2} & σ_{1} \end{matrix} ) .

Be applying Φ^{−1} to the involution we will produce a sequence of injective tableaux

∅, T_{1}, T_{2}, …, T_{n−1}, T_{n}, T_{n+1}, …, T_{2n−1}, T_{2n} = ∅ .

The underlying shapes are

∅, λ_{1}, λ_{2}, …, λ_{n−1}, λ_{n}, λ_{n+1}, …, λ_{2n−1}, λ_{2n} = ∅ .

Note that the sequence is constructed from right to left. At each step, from 2n down to n, we will insert the sequence

σ_{1} σ_{2} … σ_{n} .

That means that T_{n} is just P (σ), and it also shows that the sequence λ_{2n}, …, λ_{n} is just Q(σ).

After that we will remove the entries of T_{n}, one by one, starting from the biggest element. It is just the backward construction of P (σ), which simply means that

P (γ) = P (σ) and Q(γ) = Q(σ). ■

As we pointed out in the introduction, this correspondence has symmetry properties. Inspired by the fact that if any generator is a permutation, then the inverse is obtained by turning the corresponding graph upside down. We want to do the same for all the generators.

Definition 2. Let γ be any generator of the Brauer algebra. We define γ^{−1} to be the inverse generator obtained from γ by turning it upside down.

For instance, if

γ =  then γ^{−1} =  .

It is perfectly clear that for generators belonging to S_{n}, the property (1.2) holds. We wish to extend the property to every generator. Let γ be a generator, we will use the notation γ_{⇆} when the labelling is from left to right in the second row with numbers from 1 to n, and from right to left in the top row with numbers from n + 1 to 2n. We also use the notation γ_{⇉} when the labelling is from left to right for both rows with numbers from 1 to n. Using that latter notation we can break γ into three constituents, namely, an involution γ_{u} on a certain subset of the upper row, an involution γ_{l} on a subset of same cardinality on the lower row, and a bijection γ_{b} between the remaining dots of boths rows. For instance if

γ = 1 2 3 4 5 6 7 1 2 3 4 5 6 7 ,

then

γ_{u} = ( \begin{matrix}5 & 7 \\ 3 & 6 \end{matrix} ) , γ_{l} = ( \begin{matrix}3 & 5 \\ 2 & 1 \end{matrix} ) , γ_{b} = ( \begin{matrix}1 & 2 & 4 \\ 6 & 4 & 7 \end{matrix} ) .

Theorem 4. Let γ be a generator of B_{n}, and the corresponding constituents γ_{u}, γ_{l}, γ_{b}. Using Υ and Φ^{−1} we produce

P (γ) = ∅, λ_{1}, …, λ_{n} = λ,
Q(γ) = ∅, λ_{2n}, …, λ_{n} = λ.

Applying Φ to both P and Q will give

Φ(P (γ)) = (T_{P}^{λ}, τ_{P}) , Φ(Q(γ)) = (T_{Q}^{λ}, τ_{Q}).

Then

γ_{l} = τ_{P} , γ_{u} = τ_{Q},

and

P (γ_{b}) = T_{P}^{λ} , Q(γ_{b}) = T_{Q}^{λ},

where (P (γ_{b}), Q(γ_{b})) is obtained by applying R.S.C. to γ_{b}.

Before showing the proof, let us examine an example. Let γ be

γ = .

Using two different notations we get

γ_{⇆} = 14 13 12 11 10 9 8 1 2 3 4 5 6 7 and γ_{⇉} = 1 2 3 4 5 6 7 1 2 3 4 5 6 7 ,

and

γ_{u} = ( \begin{matrix}5 & 6 \\ 1 & 3 \end{matrix} ) , γ_{1} = ( \begin{matrix}3 & 7 \\ 2 & 4 \end{matrix} ) and γ_{b} = ( \begin{matrix}2 & 4 & 7 \\ 6 & 1 & 5 \end{matrix} ) .

Using the translation Υ, we get

Υ(γ) = ( \begin{matrix}3 & 7 & 8 & 11 & 12 & 13 & 14 \\ 2 & 4 & 5 & 1 & 9 & 6 & 10 \end{matrix} ) .

Applying Φ^{−1}, we produce a sequence of injective tableaux, keeping the shapes and breaking the sequence in two parts,

\begin{aligned}& & & & & & & & & & □ \\ & & & & & & & & □ & & □ & & □ \\ P (γ) = & ∅ & □ & □ & □ & □ & □ & □ & □ & □ & □ & □ & □ & □ \end{aligned} ,

\begin{aligned}& & & & & & □ \\ & & & □ & □ & & □ & & □ & & □ & □ \\ Q(γ) = & ∅ & □ & □ & □ & □ & □ & □ & □ & □ & □ & □ & □ \end{aligned} .

Reapplying Φ to both P (γ) and Q(γ), we get

Φ(P (γ)) = ( \begin{matrix}6 \\ 1 & 5 , \end{matrix} ( \begin{matrix}3 & 7 \\ 2 & 4 \end{matrix} )) ,

and

Φ(Q(γ)) = ( \begin{matrix}4 \\ 2 & 7 , \end{matrix} ( \begin{matrix}5 & 6 \\ 1 & 3 \end{matrix} )) .

Proof (Theorem 4). Let γ be a generator, If we use the translation Υ a generator looks like

( \begin{matrix}i_{1} & i_{2} & ⋯ & i_{n} \\ x_{1} & x_{2} & ⋯ & x_{n} \end{matrix} ) .

Application of the correspondence Φ^{−1} will produce a sequence of injective tableaux

∅^{·} ← T_{1} ← T_{2} ← ⋯ ← T_{n} ← ⋯ ← T_{2n−1} ← T_{2n} = ∅ .

We keep the first half of it and the underlying shapes, that is

λ_{n}, λ_{n+1}, …, λ_{2n−1}, λ_{2n} = ∅,

corresponding to Q(γ). We also produce the sequence of injective tableaux corresponding to the application of Φ to the oscillating tableau Q(γ),

\begin{matrix}S_{n} & ← & S_{n+1} & ← & ⋯ & ← & S_{2n−2} & ← & S_{2n−1} & ← & S_{2n} & = & ∅ \\ n & & n−1 & & ⋯ & & 2 & & 1 & & 0 & & & . \end{matrix}

Note that the relation between step index i and subscript index of the tableaux S is

i ⟷ 2n − i .  (3.4)

Consider the sequence

(T_{2n}, S_{2n}), (T_{2n−1}, S_{2n−1}), …, (T_{n}, S_{n})

of pairs of injective tableaux with the same shape, coding respectively β_{2n}, β_{2n−1}, …, β_{n} and suppose that T_{2n−k} is the first tableau where we delete an element. In fact, as pointed out in Theorem 1, this element is 2n − k + 1, and of course this element was inserted at a certain step, say j, for k < j ≤ 2n. Note that at step k − 1, the pair (T_{2n−k+1}, S_{2n−k+1}) is coding

β_{2n−k+1} = ( \begin{matrix}1 & 2 & ⋯ & k − 1 \\ x_{n} & x_{n−1} & ⋯ & x_{n−k} \end{matrix} ) ,

and that 2n − k + 1 must be one of the x_{i}’s, that is

β_{2n−k+1} = ( \begin{matrix}1 & 2 & ⋯ & j & ⋯ & k − 1 \\ x_{n} & x_{n−1} & ⋯ & 2n − k + 1 & ⋯ & x_{n−k} \end{matrix} ) .

Because deleting in T_{2n−k} and ejecting the corresponding element in S_{2n−k} is the backward construction of

β_{2n−k+1}^{−1} ( \begin{matrix}· & · & · & ⋯ & 2n − k + 1 \\ · & · & · & ⋯ & j \end{matrix} ) ,

we see that at step k, the pair (T_{2n−k}, S_{2n−k}) is coding the bijection β_{2n−k+1}^{−} obtained from β_{2n−k+1} by removing the vertical pair (j, 2n − k + 1), but in notation γ_{⇆} this is the transposition (2n − k + 1, 2n − j + 1), and in notation γ_{⇉} it is the transposition (k, j). Application of this procedure each time we delete an element allows us to conclude that

γ_{u} = τ_{Q} .

Since all transpositions in the top row are going to be omitted, the last pair (T_{n}, S_{n}) will code a bijection which is exactly γ_{b}.

To see that P (γ_{b}) is T_{P}, just note that T_{n} is exactly T_{P}, and finally, to see that γ_{l} = τ_{P}, we can argue that for any i, where i > k, inserting an element at step i means to insert its corresponding element in the transposition (i, j) of γ_{l}, where j < i. Now at step j, because there will be nothing to insert, we will remove the biggest element, which is i. But all this is just the backward construction of τ_{P}. ■

With all this in mind, it should be obvious that property (1.2) holds for oscillating tableaux.

Corollary 4.1. Let γ be a generator of the Brauer algebra, and let γ^{−1} be the corresponding inverse generator. By applying Φ^{−1} to each of them we produce pairs of oscillating tableaux

Φ^{−1}(γ) = (P (γ), Q(γ)),
Φ^{−1}(γ^{−1}) = (P (γ^{−1}), Q(γ^{−1})).

Then

P (γ^{−1}) = Q(γ) and Q(γ^{−1}) = P (γ).

Proof. Let γ be a generator and γ^{−1} its inverse. Break γ and γ^{−1} into their three constituents,

γ ⟷ (γ_{u}, γ_{l}, γ_{b}),
γ^{−1} ⟷ (γ_{u}^{−1}, γ_{l}^{−1}, γ_{b}^{−1}).

By definition of the inverse γ^{−1}, it is obvious that γ_{u}^{−1} = γ_{l}, γ_{l}^{−1} = γ_{u} and that γ_{b}^{−1} = (γ_{b})^{−1}. Then using Theorem 4, we immediatly get the result. ■

Now, we want to show that our correspondence has a property analogous to (1.3). Regarding our presentation of the generators, instead of just reversing the lower row of dots, as we do to get the reverse word of a permutation, we will reverse, with respect to a vertical axis, the whole generator. This choice was suggested by the fact that to get the inverse generator, we reverse the object with respect to a horizontal axis. Note that reversing a permutation, with respect to a vertical axis, we get a much more symmetric relation, namely

P (σ^{∗}) = P_{V.R.}(σ) and Q(σ^{∗}) = Q_{V.R.}(σ).

Definition 3. Let γ be any generator of the Brauer algebra, we define γ^{∗} to be the mirror generator obtained from γ by a reflexion about a vertical axis.

For instance, if

γ =  then γ^{∗} =  .

In what follows we need to define the ”vidage-remplissage” for injective tableaux. We recall that this algorithm is a process, which applied to a standard tableau gives another tableau of the same shape. It can be described as follows. Take a standard tableau T and replace the leftmost and bottommost cell by a blank, remembering the element that was there. Then, exchange the blank with the cell to its right or with the cell on top of it, according to the smallest entry, repeat this procedure until the blank reaches a corner cell, and replace the blank by the remembered element. We start over again with the leftover tableau, disregarding the remembered element. The process stops when the leftover tableau is empty. The new tableau obtained in this manner is not standard, all lines and columns are strictly decreasing. To get back a standard tableau, replace all entries i by n + 1 − i. It is the ”vidé-rempli” of T. For instance, take

T = \begin{matrix}7 \\ 3 & 4 & 8 \\ 1 & 2 & 5 & 6 & 9. \end{matrix}

We move the blank to a corner cell,

\begin{matrix}7 \\ 3 & 4 & 8 \\ □ & 2 & 5 & 6 & 9 \end{matrix} → \begin{matrix}7 \\ 3 & 4 & 8 \\ 2 & □ & 5 & 6 & 9 \end{matrix} → \begin{matrix}7 \\ 3 & □ & 8 \\ 2 & 4 & 5 & 6 & 9 \end{matrix} → \begin{matrix}7 \\ 3 & 8 & □ \\ 2 & 4 & 5 & 6 & 9 . \end{matrix}

Now we replace the blank by 1, and start over again. In the end we get 2

6 5 1
9 8 7 4 3 .

Finally we apply the transformation i ⟷ n + 1 − i to get the ”vidé-rempli” tableau 8

4 5 9
1 2 3 6 7 .

In what follows, we need to extend the process to injective tableaux. If T is an injective tableau with m cells on the set [n], a natural way to produce the analog for those tableaux is to do the same, and at the end, instead of performing the transformation i↔m + 1 − i, we replace i by n + 1 − i. For instance, if

T = 7 9 2 4 5 8

is an injective tableau on [10], then the ”vidé-rempli” will be

T_{V.R.} = \begin{matrix}3 & 6 \\ 2 & 4 & 7 & 9 . \end{matrix}

Corollary 4.2. Let γ be a generator of the Brauer algebra, and let γ^{∗} be the corresponding mirror generator. By applying Φ^{−1} we produce pairs of oscillating tableaux,

Φ^{−1}(γ) = (P (γ), Q(γ)),

and

Φ^{−1}(γ^{∗}) = (P (γ^{∗}), Q(γ^{∗})).

Ry applying Φ to those oscillating tableaux, we will get

Φ(P (γ)) = (T_{P} , τ_{P}),
Φ(Q(γ)) = (T_{Q}, τ_{Q}),
Φ(P (γ^{∗})) = (T_{P^{∗}}, τ_{P^{∗}}),
Φ(Q(γ^{∗})) = (T_{Q^{∗}}, τ_{Q^{∗}}).

Then

T_{P V.R.} = T_{P^{∗}} and T_{Q V.R.} = T_{Q^{∗}},

and τ_{P^{∗}} and T_{Q^{∗}} are respectively obtained from τ_{P} and τ_{Q} by applying the transformation i ⟷ n + 1 − i.

Proof. Using theorem 4, the proof is straight forward. ■

4. A few remarks. The main argument to get the correspondence between the generators and pairs of oscillating tableaux of same shape and length, was to produce a sequence

∅, λ_{1}λ_{2}, …, λ_{n}, …, λ_{2n−2}, λ_{2n−1}, ∅,

and cut it in half. But we could cut it somewhere else and get a more general formula,

1 · 3 · 5 ⋯ (2n − 1) = ∑_{μ} f_{n−m}^{μ}.f_{n+m}^{μ},

where μ is a partition of p ≤ n − m, that might be of some significance in the context of representation theory. To support this remark, we notice that a class of oscillating tableaux including the standard ones is connected with representations of the symmetric group. Take all oscillating tableaux, of length m and shape μ, that increase from step 1 to a certain step n ≤ m, and decrease from step n + 1 to m. The number of such tableaux, denoted by c_{m}^{μ}, (c for ”colline”), is

c_{m}^{μ} = \frac{n_{μ} · n!}{|μ|} ,

where m = 2n − |μ|. This allows us to rewrite equation (1.1) in a more general form,

n! = ∑_{μ} n_{μ} · c_{2n−|μ|}^{μ},

where n_{μ} is the dimension of the irreducible representation of S_{|μ|}, indexed by μ, and c_{2n−|μ|}^{μ} is the multiplicity of that same representation, induced to S_{n}, in the left regular representation of S S S_{n}.

References

[1] BERELE (Alan), A Schensted–Type Correspondence for the Symplectic Group, J. Combin. Theory Ser. A 43 (1986), 320–328.

[2] BRAUER (Richard), On Algebras which are connected with the Semisimple Continuous Groups, Ann. Math. 38 (1937), 857–872.

[3] McLARNAN (Timothy J.), Tableau Recursions and Symmetric Schensted Correspondence for Ordinary, Shifted and Oscillating Tableaux, Ph. D. dissertation, Univ. Calif. San Diego, 1986.

[4] NIJENHUIS (Albert) and WILF (Herbert S.), Combinatorial Algorithms, Academic Press, 2nd ed., 1975.

[5] SCHÜTZENBERGER (Marcel-Paul), Quelques remarques sur une construction de Schensted, Math. Scand. 12 (1963), 117–128.

[6] SCHÜTZENBERGER (Marcel-Paul), La correspondance de Robinson, Combinatoire et représen-tation du groupe symétrique [Table Ronde C.N.R.S., Strasbourg. 1976], Berlin, Springer– Verlag (Lecture Notes in Math., 579), 1977, pp. 59–135.

[7] SUNDARAM (Sheila), On the Combinatorics of Sp(2n, ℂ), Ph. D. dissertation M.I.T., 1986.

[8] VIENNOT (Xavier G.), Chain and Antichain Families, Grids and Young Tableaux, Ann. Disc. Math. 23 (1984), 409–464.

[9] WEYL (Hermann), The Classical Groups, Their Invariants and Representations, Princeton Univ. Press, 2nd ed., 1946.

[10] YOUNG (Alfred), The Collected Papers of Alfred Young, 1873–1940, Univ. Toronto Press, (Math. Expositions, 21), 1977.

Départment d’Informatique, Université de Bordeaux I, F-33405 Talence.