# Skew domino Schensted algorithm and sign-imbalance

Jang Soo Kim

Department of Mathematical Sciences, Korea Advanced Institute of Science and Technology, Daejeon 305-701, Korea

**Abstract.** Using growth diagrams, we define a skew domino Schensted algorithm which is a domino analogue of the “Robinson-Schensted algorithm for skew tableaux” due to Sagan and Stanley. The color-to-spin property of Shimozono and White is extended. As an application, we give a simple generating function for a weighted sum of skew domino tableaux whose special case is a generalization of Stanley’s sign-imbalance formula. The generating function gives a method to calculate the generalized sign-imbalance formula.

**Résumé.** Nous définissons, à partir de diagrammes de croissances, un algorithme de Schensted pour les dominos gauches. Cet algorithme est un analogue de l’algorithme de Schensted pour les tableaux gauches dû à Sagan et Stanley. Nous généralisons la propriété couleur-à-spin de Shimozono et White. Comme application, nous présentons une fonction génératrice simple pour une somme pondérée de tableaux de dominos gauches qui, dans un cas particulier, généralise la formule de “sign-imbalance” de Stanley. La fonction génératrice donne aussi lieu à une méthode permettant de calculer la formule de “sign-imbalance”.

**Keywords:** Skew tableaux, Domino tableaux, Sign-imbalance, Growth diagrams, Schensted algorithm

## 1 Introduction

The domino Schensted algorithm is a bijection between colored permutations and pairs of domino tableaux of the same shape. It was first developed by Barbasch and Vogan [1] in 1982. Garfinkle [6] described this algorithm in terms of insertion. This algorithm was described in growth diagrams and extended in the presence of a nonempty core by van Leeuwen [23]. Shimozono and White [17] proved that this algorithm has the color-to-spin property. Lam [10] used growth diagram to prove the color-to-spin property and identities involving colored involutions. Using these properties, Lam [10] obtained enumerative results for domino tableaux and proved Stanley’s sign-imbalance conjectures [22].

For a standard Young tableau (SYT) $T$, the sign of $T$ is defined to be $sign(\pi)$, where $\pi$ is the permutation obtained by reading $T$ like a book. For example, if $T = \begin{bmatrix} 1 & 2 & 4 \\ 3 & 5 \end{bmatrix}$ then $sign(T) = sign(12435) = -1$. The sign-imbalance $I_{\lambda}$ of a partition $\lambda$ is the sum of $sign(T)$ for all SYTs of shape $\lambda$. In [22], Stanley suggested interesting sign-imbalance formulae:

$$ \sum_{\lambda \vdash n} x^{v(\lambda)} y^{h(\lambda)} z^{d(\lambda)} I_{\lambda} = (x+y)^{\lfloor \frac{n}{2} \rfloor}, \quad (1) $$
$$ \sum_{\lambda \vdash n} (-1)^{v(\lambda)} I_{\lambda}^{2} = 0, \qquad (2) $$

where $v(\lambda)$, $h(\lambda)$ and $d(\lambda)$ denote the maximum numbers of vertical dominoes, horizontal dominoes and $2 \times 2$ rectangles respectively that can be placed in the Young diagram of $\lambda$ without overlaps.

Sjöstrand [18] proved Eq. (1) and Eq. (2) using chess tableaux and by relating signs of a permutation and the corresponding tableaux in Robinson-Schensted correspondence. Reifegerste [14] independently obtained the sign relation and proved Eq. (2). White [24] observed that sign-imbalance is related to domino tableaux and proved that for a domino tableau $D$,

$$ \operatorname{sign}(D) = (-1)^{ev(D)}, \qquad (3) $$

where $ev(D)$ is the number of vertical dominoes of $D$ in even columns. Lam [10] proved Eq. (1) and Eq. (2) using properties obtained from growth diagrams.

In this paper, inspired by Lam's work [10], we describe a skew domino Schensted algorithm using growth diagrams, which is a domino analogue of "Robinson-Schensted algorithm for skew tableaux" due to Sagan and Stanley [16]. This growth diagram approach was once used in Roby's thesis [15] to describe Sagan and Stanley's algorithm. Fomin [4] proved the existence of this bijection in a more general context using operators on partitions. The color-to-spin property and Lam's identities for colored involutions are extended. As an application, we generalize Eq. (1) and Eq. (2) to skew shapes.

We should note that, in the literature, there are two different definitions of $sign(T)$ for a skew tableau $T$ of shape $\lambda/\mu$. In [11, 19], the sign of $T$ of shape $\lambda/\mu$ does not care about the cells in $\mu$, but in [12], it does. In this paper, we use the definition of $sign(T)$ in [12] and prove that Eq. (3) still holds.

The rest of this paper is organized as follows. In Section 2, we define skew shapes, reversed shapes, domino tableaux and colored permutations. In Section 3, we introduce growth diagrams and the skew domino Schensted algorithm, and extend the color-to-spin property and Lam's identities for colored involutions. We also find a generating function for the weighted sum of domino tableaux which turns out to be closely related to sign-imbalance. In Section 4, we define the sign of a skew tableau and generalize Eq. (2) whose special case was proved by Sjöstrand [19] and Lam [11, 12]. We also generalize Eq. (1) to skew shapes and give a closed formula for $\sum_{\lambda/\delta_k \vdash n} x^{v(\lambda/\delta_k)} y^{h(\lambda/\delta_k)} z^{d(\lambda/\delta_k)} I_{\lambda/\delta_k}$, where $\delta_k = (k, k-1, \dots, 1)$.

# 2 Preliminaries

## 2.1 Skew shapes and domino tableaux

Let $\mathbb{N}$ denote the set of nonnegative integers and $\mathbb{Z}$ denote the set of integers. For a positive integer $n$, we denote $[n] = \{1, 2, \dots, n\}$. A partition $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_l)$ of $n \in \mathbb{N}$, denoted by $\lambda \vdash n$, is a weakly decreasing (possibly empty) sequence of positive integers $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_l$ summing to $n$. Each $\lambda_i$ is called the *i-th part* of $\lambda$. Let $l(\lambda)$ denote the number of parts in $\lambda$.

A cell is a pair of positive integers. The Young diagram $Y(\lambda)$ of a partition $\lambda$ is the set of cells such that $(i, j) \in Y(\lambda)$ if and only if $i \le l(\lambda)$ and $j \le \lambda_i$. We can draw Young diagram $Y(\lambda)$ by placing a square in the *i-th row* and *j-th column* for each cell $(i, j) \in Y(\lambda)$. For example, the drawing of Young diagram

of $(4, 3, 1)$ is . We will identify a partition $\lambda$ with its Young diagram $Y(\lambda)$.
A skew shape $\lambda/\mu$ is an ordered pair $(\lambda, \mu)$ of partitions satisfying $\mu \subset \lambda$. We will also consider $\lambda/\mu$ as the set theoretic difference $Y(\lambda) \setminus Y(\mu)$. The size of $\lambda/\mu$, denoted by $|\lambda/\mu|$, is the number of cells in $\lambda/\mu$. The notation $\lambda/\mu \vdash n$ means that the size of $\lambda/\mu$ is $n$. For example, $(4, 3, 1)/(2, 1) = \square$ is a skew shape of size 5. We will identify a partition $\lambda$ with the skew shape $\lambda/\emptyset$.

A domino is a horizontal domino or a vertical domino where a horizontal (resp. vertical) domino is a skew shape consisting of two adjacent cells : $(i, j)$ and $(i, j + 1)$ (resp. $(i, j)$ and $(i + 1, j)$).

A standard skew tableau (SST) of shape $\lambda/\mu \vdash n$ is a bijection $T : \lambda/\mu \to [n]$ such that integers are increasing in each row and column. For a cell $c \in \lambda/\mu$, we call the integer $T(c)$ the entry of $c$. A standard Young tableau (SYT) of shape $\lambda$ is a SST of shape $\lambda/\emptyset$. A standard domino tableau (SDT) of shape $\lambda/\mu \vdash 2n$ is a SST such that two cells with entries $2i - 1$ and $2i$ make a domino for each $i = 1, 2, \dots, n$.

Thus we can consider a SDT as a collection of labeled dominoes. For example, $\begin{array}{c|c|c|c} 1 & 2 & 9 \\ 3 & 4 & 7 & 10 \\ 5 & 6 & 8 \end{array}$ and $\begin{array}{c|c|c} 1 & & \\ 2 & 4 & \\ 3 & & 5 \end{array}$ represent the same SDT. If there is a SDT of shape $\lambda/\mu$, then we say $\lambda/\mu$ is domino-tileable.

Let $T(\lambda/\mu)$ (resp. $D(\lambda/\mu)$) denote the set of all SSTs (resp. SDTs) of shape $\lambda/\mu$. Let $f^{\lambda/\mu} = |T(\lambda/\mu)|$ and $d^{\lambda/\mu} = |D(\lambda/\mu)|$.

For a given partition $\lambda$, let us take a maximal chain of partitions $\lambda^{(m)} \subset \lambda^{(m-1)} \subset \dots \subset \lambda^{(0)} = \lambda$ such that $\lambda^{(i-1)}/\lambda^{(i)}$ is a domino for $i = 1, 2, \dots, m$. Then the last partition $\lambda^{(m)}$ is always the same and called the 2-core of $\lambda$. We denote the 2-core of $\lambda$ by $\tilde{\lambda}$. Since there is no partition $\mu$ such that $\tilde{\lambda}/\mu$ is a domino, $\tilde{\lambda}$ must be a staircase partition $\delta_r = (r, r-1, \dots, 1)$ for some $r$. We refer the reader to [7, 9, 13] for details of p-cores.

Let $v(\lambda/\mu)$ (resp. $h(\lambda/\mu)$) denote the number of cells in even rows (resp. columns). Let $d(\lambda/\mu)$ denote the number of cells both in even columns and even rows. It is easy to see that $h(\lambda)$, $v(\lambda)$ and $d(\lambda)$ are the maximum numbers of horizontal dominoes, vertical dominoes and $2 \times 2$ squares respectively that can be placed in $\lambda$ without overlaps.

For a SDT $D$, let $oh(D)$, $eh(D)$, $ov(D)$ and $ev(D)$ denote the numbers of horizontal dominoes in odd rows, horizontal dominoes in even rows, vertical dominoes in odd columns and vertical dominoes in even columns respectively. The spin of a SDT is defined to be the number of vertical dominoes divided by 2, that is, $sp(D) = \frac{1}{2}(ov(D) + ev(D))$.

Next we prove some relations between a SDT and its shape. We note that these can also be obtained from Lam's results [10].

**Lemma 2.1.** If $D \in D(\lambda/\mu)$ then the following hold:

$$oh(D) - eh(D) = \frac{1}{2}|\lambda/\mu| - v(\lambda/\mu),$$

$$ov(D) - ev(D) = \frac{1}{2}|\lambda/\mu| - h(\lambda/\mu),$$

$$eh(D) + ev(D) = d(\lambda/\mu),$$

$$v(\lambda/\mu) + h(\lambda/\mu) = \frac{1}{2}|\lambda/\mu| + 2 \cdot d(\lambda/\mu).$$

*Remark 1.* In Lemma 2.1, (4) is not true if $\lambda/\mu$ is not domino-tileable. For example, if $\mu = (1)$ and $\lambda = (2, 1)$, then (4) does not hold.

## 2.2 Reversed shapes

Recall that a skew shape $\mu/\lambda$ is a pair $(\mu, \lambda)$ of partitions with $\lambda \subset \mu$. We define a reversed shape $\lambda/\mu$ to be a pair $(\lambda, \mu)$ of partitions with $\lambda \subset \mu$ and denote $\lambda/\mu \vdash |\lambda| - |\mu|$. Thus $\lambda/\mu$ is a reversed shape if
and only if $\mu/\lambda$ is a skew shape. We also see that $\lambda/\mu \vdash -n$ is equivalent to $\mu/\lambda \vdash n$. We extend each statistic stat of a skew shape to a reversed shape by $\text{stat}(\lambda/\mu) = -\text{stat}(\mu/\lambda)$, i.e., $|\lambda/\mu| = -|\mu/\lambda|$, $v(\lambda/\mu) = -v(\mu/\lambda)$ and so on. As a shape of a tableau, we will treat $\mu/\lambda$ and $\lambda/\mu$ equally, that is, $T(\lambda/\mu) = T(\mu/\lambda)$ and $D(\lambda/\mu) = D(\mu/\lambda)$.

If we write $\lambda/\mu \vdash n$ for $n \in \mathbb{Z}$, then it means $\lambda/\mu$ is a skew shape or reversed shape depending on $n$. The notion of reversed shapes is not essential. However it will give us a simple description for a generalization of Eq. (1). In Section 4, we will define the sign-imbalance $I_{\lambda/\mu}$ of a reversed shape $\lambda/\mu \vdash -2n$.

## 2.3 Colored permutations and colored involutions

A colored permutation $\pi$ of $[n]$ is a permutation of $[n]$ in which each integer can be barred or not. Let $\pi$ be a colored permutation. The total color $tc(\pi)$ of $\pi$ is the number of barred integers. The permutation matrix of $\pi$ is the matrix $M$ such that $M(i, j)$ is equal to 1 if $\pi_i = j$; -1 if $\pi_i \neq j$ and 0 otherwise. Let $CP_n$ denote the set of colored permutations of $[n]$.

A colored permutation $\pi$ is called an involution if the permutation matrix of $\pi$ is symmetric. We denote the set of involutions in $CP_n$ by $CI_n$. We will consider the empty word as an involution, thus $CI_0 = \{\emptyset\}$. We can represent a colored permutation in cycle notation as follows. Given a colored permutation $\pi$, write the underlying permutation of $\pi$ in cycle notation, and put a bar over $i$ in cycle notation if and only if $i$ is barred in $\pi$. For example, if $\pi = \bar{341}\bar{52}$ then $\pi = (13)(24\bar{5})$ in cycle notation.

A colored involution $\pi$ has only 1-cycles and 2-cycles. Moreover, the two integers in a 2-cycle of $\pi$ are both barred or both unbarred. Let $\sigma_1(\pi)$, $\sigma_2(\pi)$, $\bar{\sigma}_1(\pi)$ and $\bar{\sigma}_2(\pi)$ denote the numbers of unbarred 1-cycles, unbarred 2-cycles, barred 1-cycles and barred 2-cycles in $\pi$ respectively. For example, if $\pi = (14)(\bar{2})(\bar{36})(5)(7)$ then $\sigma_1(\pi) = 2$, $\bar{\sigma}_1(\pi) = 1$, $\sigma_2(\pi) = 1$ and $\bar{\sigma}_2(\pi) = 1$.

We define the weight of a colored involution $\pi$ by

$$ \text{wt}_{\pi} = \text{wt}_{\pi}(x, y, q) = x^{\sigma_1(\pi)} y^{\bar{\sigma}_1(\pi)} q^{\frac{1}{2}tc(\pi)}. $$

Since a colored involution $\pi$ can be considered as a partition of $[n]$ into 1-subsets and 2-subsets with a possible bar and $\frac{1}{2}tc(\pi) = \frac{1}{2}\bar{\sigma}_1(\pi) + \bar{\sigma}_2(\pi)$, by the exponential formula [20], we get the following exponential generating function:

$$ \sum_{n \ge 0} \left( \sum_{\pi \in CI_n} \text{wt}_{\pi} \right) \frac{t^n}{n!} = \exp \left( (x + y\sqrt{q})t + (1 + q)\frac{t^2}{2} \right). \quad (4) $$

# 3 Skew Domino Schensted Algorithm

## 3.1 Definition of a growth diagram

In this section we introduce growth diagrams. Our definition is based on Lam's [10]. We can define growth diagrams of an arbitrary skew shape. Nevertheless, we will restrict our definition to rectangular shapes for simplicity since we only need that case. The reader is referred to [5, 2, 3] for details of growth diagrams.

For partitions $\lambda$ and $\mu$, we write $\mu <_d \lambda$ if $\lambda/\mu$ is a domino and $\mu \le_d \lambda$ if $\mu = \lambda$ or $\mu <_d \lambda$. A d-chain is a chain of partitions $\lambda^{(0)} <_d \lambda^{(1)} <_d \cdots <_d \lambda^{(m)}$ and a d-multichain is a multichain of partitions $\lambda^{(0)} \le_d \lambda^{(1)} \le_d \cdots \le_d \lambda^{(m)}$.
An $n \times m$ growth array $\Gamma$ is an array of partitions $\Gamma_{(i,j)}$ for $0 \le i \le n$ and $0 \le j \le m$ such that each two adjacent partitions are equal or differ by a domino, i.e., $\Gamma_{(i-1,j)} \le_d \Gamma_{(i,j)}$ and $\Gamma_{(i,j-1)} \le_d \Gamma_{(i,j)}$ for all $1 \le i \le n$ and $1 \le j \le m$.

An $n \times m$ partial permutation matrix (PPM) $M$ is an $n \times m$ matrix whose elements are $1, -1$ or $0$, and which contains at most one nonzero element in each row and column. For a PPM $M$, let $cp(M)$ denote the colored permutation $\pi$ whose permutation matrix is the matrix obtained from $M$ by removing rows and columns consisting of zeroes only.

An $n \times m$ growth diagram $G$ is a pair $(\Gamma, M)$, where $\Gamma = \Gamma(G)$ is an $n \times m$ growth array and $M = M(G)$ is an $n \times m$ PPM satisfying the following local rules.

Let $\nu = \Gamma_{(i-1,j-1)}$, $\mu = \Gamma_{(i-1,j)}$, $\rho = \Gamma_{(i,j-1)}$ and $\lambda = \Gamma_{(i,j)}$. Then it must fall into one of the following conditions which determine $\lambda$:

1. If $M(i, j) = 1$ then $\nu = \mu = \rho$ and $\lambda$ is the partition obtained from $\mu$ by adding a horizontal domino to the first row.

2. If $M(i, j) = -1$ then $\nu = \mu = \rho$ and $\lambda$ is the partition obtained from $\mu$ by adding a vertical domino to the first column.

3. If $M(i, j) = 0$ then there are five cases.

(a) If $\nu = \mu$ or $\nu = \rho$ then $\lambda$ is the maximum among $\nu, \mu$ and $\rho$.

(b) If $\nu <_d \mu$, $\nu <_d \rho$, $\mu \neq \rho$ and $\mu/\nu \cap \rho/\nu = \emptyset$ then $\lambda = \mu \cup \rho$.

(c) If $\nu <_d \mu$, $\nu <_d \rho$, $\mu \neq \rho$ and $\mu/\nu \cap \rho/\nu \neq \emptyset$ then $\mu/\nu$ and $\rho/\nu$ share only one cell, say $(p, q)$, and $\lambda$ is the partition obtained from $\mu \cup \rho$ by adding the cell $(p+1, q+1)$.

(d) If $\nu <_d \mu$, $\nu <_d \rho$, $\mu = \rho$ and $\mu/\nu$ is a horizontal domino in $k$-th row then $\lambda$ is the partition obtained from $\mu$ by adding a horizontal domino to the $(k+1)$-th row.

(e) If $\nu <_d \mu$, $\nu <_d \rho$, $\mu = \rho$ and $\mu/\nu$ is a vertical domino in $k$-th column then $\lambda$ is the partition obtained from $\mu$ by adding a vertical domino to the $(k+1)$-th column.

The following represents a 3 × 5 growth diagram.

<figure><img src="image_1.png" /></figure>

## 3.2 Skew domino Schensted algorithm

Let $C = \lambda^{(0)} \le_d \lambda^{(1)} \le_d \cdots \le_d \lambda^{(n)}$ be a d-multichain. We can naturally construct a SDT from $C$ as follows. Let $(d_1, d_2, \ldots, d_k)$ be the sequence of dominoes obtained by removing empty sets from
($\lambda^{(1)}/\lambda^{(0)}$, $\lambda^{(2)}/\lambda^{(1)}$, ..., $\lambda^{(n)}/\lambda^{(n-1)}$). Let $C^{\text{SDT}}$ be the SDT of shape $\lambda^{(n)}/\lambda^{(0)}$ whose domino with entry $i$ is $d_i$ for $i = 1, 2, ..., k$.

Let $G = (\Gamma, M)$ be an $n \times m$ growth diagram. We define four special d-multichains of $G$ as follows:

$$ 
\begin{aligned}
G_{\text{top}} &= \Gamma_{(0,0)} \le_{d} \Gamma_{(0,1)} \le_{d} \cdots \le_{d} \Gamma_{(0,m)}, & G_{\text{left}} &= \Gamma_{(0,0)} \le_{d} \Gamma_{(1,0)} \le_{d} \cdots \le_{d} \Gamma_{(n,0)}, \\
G_{\text{bottom}} &= \Gamma_{(n,0)} \le_{d} \Gamma_{(n,1)} \le_{d} \cdots \le_{d} \Gamma_{(n,m)}, & G_{\text{right}} &= \Gamma_{(0,m)} \le_{d} \Gamma_{(1,m)} \le_{d} \cdots \le_{d} \Gamma_{(n,m)}.
\end{aligned}
$$

If both $G_{\text{bottom}}$ and $G_{\text{right}}$ are d-chains, then we call $G$ a full growth diagram. The local rules say that $G$ is completely determined by $G_{\text{top}}$, $G_{\text{left}}$ and $M$. On the other hand, one can easily see that the local rules are invertible in the sense that $\Gamma_{(i-1,j-1)}$ and $M(i, j)$ are determined by $\Gamma_{(i-1,j)}$, $\Gamma_{(i,j-1)}$ and $\Gamma_{(i,j)}$. Thus a growth diagram $G$ is also completely determined by $G_{\text{bottom}}$ and $G_{\text{right}}$. We define $\partial^{+}(G)$ to be the pair $(G_{\text{bottom}}^{\text{SDT}}, G_{\text{right}}^{\text{SDT}})$, and $\partial^{-}(G)$ to be the triple $(G_{\text{top}}^{\text{SDT}}, G_{\text{left}}^{\text{SDT}}, M)$.

Let $\alpha$ and $\beta$ be partitions. Let $\mathfrak{G}_{n,m}^{\alpha,\beta}$ denote the set of all $n \times m$ full growth diagrams $G = (\Gamma, M)$ satisfying $\Gamma_{(n,0)} = \alpha$ and $\Gamma_{(0,m)} = \beta$. We can check that the maps $\partial^{+}$ and $\partial^{-}$ are invertible when applied to a full growth diagram.

Now we get a skew domino Schensted algorithm.

**Theorem 3.1.** Let $\alpha$ and $\beta$ be fixed partitions and $n$ and $m$ be fixed nonnegative integers. Then $\Phi = \partial^{+} \circ (\partial^{-})^{-1}$ induces a bijection

$$ \Phi: \bigcup_{j \ge 0} \left( \bigcup_{\substack{\beta/\mu \vdash 2(m-j) \\ \alpha/\mu \vdash 2(n-j)}} \mathcal{D}(\beta/\mu) \times \mathcal{D}(\alpha/\mu) \times \mathfrak{M}_{n,m}^j \right) \to \bigcup_{\substack{\lambda/\alpha \vdash 2m \\ \lambda/\beta \vdash 2n}} \mathcal{D}(\lambda/\alpha) \times \mathcal{D}(\lambda/\beta), $$

where $\mathfrak{M}_{n,m}^j$ denotes the set of all $n \times m$ PPMs with $j$ nonzero elements.

We note that if $\pi$ corresponds to $(P, Q)$ in the domino Schensted algorithm and $M$ is the permutation matrix of $\pi$ then $\Phi(\emptyset_{\delta_r}, \emptyset_{\delta_r}, M) = (P, Q)$, where $\emptyset_{\delta_r}$ is the empty SDT of shape $\delta_r/\delta_r$. The bijection $\Phi$ is a domino analogue of “Robinson-Schensted algorithms for skew tableaux”, which was first developed using external and internal insertion by Sagan and Stanley [16] and was interpreted in terms of growth diagrams, as we did here, by Roby [15]. Fomin [4] proved the existence of this bijection using operators on partitions.

Since the local rules are symmetric we get the following proposition immediately.

**Proposition 3.2.** Let $\Phi(U, V, M) = (P, Q)$. Then $\Phi(V, U, M^T) = (Q, P)$.

In the above proposition, if $U = V$ and $M$ is symmetric then $\Phi(U, U, M) = (P, P)$. Let $\Phi_{\text{sym}}(U, M) = P$. Then we get another bijection.

**Corollary 3.3.** Let $\alpha$ be a fixed partition and $n$ be a fixed nonnegative integer. Then $\Phi_{\text{sym}}$ induces a bijection

$$ \Phi_{\text{sym}}: \bigcup_{j \ge 0} \left( \bigcup_{\alpha/\mu \vdash 2(n-j)} \mathcal{D}(\alpha/\mu) \times \mathfrak{S}\mathfrak{M}_n^j \right) \to \bigcup_{\lambda/\alpha \vdash 2n} \mathcal{D}(\lambda/\alpha), $$

where $\mathfrak{S}\mathfrak{M}_n^j$ denotes the set of all symmetric $n \times n$ PPMs with $j$ nonzero elements.
Shimozono and White [17] proved that the domino Schensted algorithm has the color-to-spin property, that is, if $\pi$ corresponds to $(P, Q)$ then $tc(\pi) = sp(P) + sp(Q)$. The next proposition generalizes this property.

**Proposition 3.4.** Let $\Phi(U, V, M) = (P, Q)$ and $\pi = cp(M)$. Then

$$tc(\pi) = sp(P) + sp(Q) - sp(U) - sp(V).$$

Lam [10] proved that if a colored involution $\pi$ corresponds to $(D, D)$ in the domino Schensted algorithm then $\bar{\sigma}_1(\pi) = ov(D) - ev(D)$ and $\bar{\sigma}_2(\pi) = ev(D)$. We can generalize Lam's results as follows.

**Proposition 3.5.** Let $M$ be an $n \times n$ symmetric PPM and $\pi = cp(M)$. Let $U$ and $P$ be SDTs satisfying $\Phi_{\text{sym}}(U, M) = P$. Then we have

$$\begin{align*}
\sigma_1(\pi) &= (oh(P) - eh(P)) + (oh(U) - eh(U)), & \sigma_2(\pi) &= eh(P) - oh(U), \\
\bar{\sigma}_1(\pi) &= (ov(P) - ev(P)) + (ov(U) - ev(U)), & \bar{\sigma}_2(\pi) &= ev(P) - ov(U).
\end{align*}$$

As an application of the skew domino Schensted algorithm, we get some enumerative results. Following Lam's notation [10], let

$$f_2^{\lambda/\mu}(q) = \sum_{D \in \mathcal{D}(\lambda/\mu)} q^{sp(D)}.$$

By Theorem 3.1, Proposition 3.4 and the identity $\sum_{\pi \in CP_j} q^{tc(\pi)} = (1+q)^j j!$, we get the following corollary.

**Corollary 3.6.** Let $\alpha$ and $\beta$ be fixed partitions and $n$ and $m$ be fixed nonnegative integers. Then,

$$\sum_{\substack{\lambda/\alpha \vdash 2m \\ \lambda/\beta \vdash 2n}} f_2^{\lambda/\alpha}(q) f_2^{\lambda/\beta}(q) = \sum_{j \ge 0} \binom{n}{j} \binom{m}{j} (1+q)^j j! \sum_{\substack{\beta/\mu \vdash 2(m-j) \\ \alpha/\mu \vdash 2(n-j)}} f_2^{\beta/\mu}(q) f_2^{\alpha/\mu}(q).$$

There are three interesting specializations of Corollary 3.6. We can consider a SYT of shape $\lambda$ as a SDT of shape $2\lambda$, the partition obtained by multiplying each part of $\lambda$ by 2, consisting of horizontal dominoes by identifying a cell with a horizontal domino. Then by letting $q = 0$ in Corollary 3.6, we get the following corollary due to Sagan and Stanley [16]. We note that Roby [15] also proved the following corollary using growth diagrams and our proof is essentially the same as Roby's.

**Corollary 3.7.** [16, Sagan and Stanley] Let $\alpha$ and $\beta$ be fixed partitions and $n$ and $m$ be fixed nonnegative integers. Then,

$$\sum_{\substack{\lambda/\alpha \vdash m \\ \lambda/\beta \vdash n}} f^{\lambda/\alpha} f^{\lambda/\beta} = \sum_{j \ge 0} \binom{n}{j} \binom{m}{j} j! \sum_{\substack{\beta/\mu \vdash m-j \\ \alpha/\mu \vdash n-j}} f^{\beta/\mu} f^{\alpha/\mu}.$$

When we set $q = 1$ in Corollary 3.6, we get a domino analogue.

**Corollary 3.8.** Let $\alpha$ and $\beta$ be fixed partitions and $n$ and $m$ be fixed nonnegative integers. Then,

$$\sum_{\substack{\lambda/\alpha \vdash 2m \\ \lambda/\beta \vdash 2n}} d^{\lambda/\alpha} d^{\lambda/\beta} = \sum_{j \ge 0} \binom{n}{j} \binom{m}{j} 2^j j! \sum_{\substack{\beta/\mu \vdash 2(m-j) \\ \alpha/\mu \vdash 2(n-j)}} d^{\beta/\mu} d^{\alpha/\mu}.$$

If $q = -1$ then, as we will see in the next section, Corollary 3.6 induces a sign-imbalance formula.
### 3.3 A weighted sum of domino tableaux

For a SDT $D$, we define a weight $wt_D$ of $D$ by

$$wt_D = wt_D(x, y, q) = x^{oh(D)-eh(D)}y^{ov(D)-ev(D)}q^{sp(D)}.$$

Note that if a colored involution $\pi$ corresponds to $(D, D)$ in the domino Schensted algorithm, then $wt_D = wt_\pi$.

Recall that a reversed shape $\lambda/\mu \vdash -n$ is the one obtained from reversing a skew shape $\mu/\lambda \vdash n$ and $D(\lambda/\mu) = D(\mu/\lambda)$. Thus $f_2^{\lambda/\mu}(q) = f_2^{\mu/\lambda}(q)$.

For a fixed partition $\alpha$ and $n \in \mathbb{Z}$, we define

$$W_n^\alpha = W_n^\alpha(x, y, q) = \sum_{\lambda/\alpha \vdash 2n} x^{n-v(\lambda/\alpha)} y^{n-h(\lambda/\alpha)} f_2^{\lambda/\alpha}(q).$$

Then, by definition, for $n \ge 0$, we have $W_{-n}^\alpha = \sum_{\alpha/\lambda \vdash 2n} x^{-n+v(\alpha/\lambda)} y^{-n+h(\alpha/\lambda)} f_2^{\alpha/\lambda}(q)$. Thus $W_{-n}^\alpha = 0$ if $\alpha/\tilde{\alpha} \vdash 2k$ and $n > k$.

By Lemma 2.1, if $n \ge 0$ then $W_n^\alpha$ is a weighted sum of SDTs: $W_n^\alpha = \sum_{\lambda/\alpha \vdash 2n} \sum_{D \in D(\lambda/\alpha)} wt_D$.

**Theorem 3.9.** Let $\alpha$ be a fixed partition with $\alpha/\tilde{\alpha} = 2k$ and $n \ge 0$. Then

$$W_n^\alpha = \sum_{j=0}^{k} \binom{n}{j} W_{-j}^\alpha \sum_{\pi \in CI_{n-j}} wt_\pi.$$

Using Theorem 3.9 and Eq. (4), we get a simple generating function for the weighted sum.

**Corollary 3.10.** Let $\alpha$ be a fixed partition. Then

$$\frac{\sum_{n \ge 0} W_n^\alpha t^n / n!}{\sum_{n \ge 0} W_{-n}^\alpha t^n / n!} = \exp \left( (x + y\sqrt{q})t + (1 + q)\frac{t^2}{2} \right).$$

By the argument following Corollary 3.6, if we set $x = 1$ and $y = q = 0$ in Theorem 3.9, then we obtain Sagan and Stanley's theorem [16] which was reproved by Roby [15], Stanley [21] and Jaggard [8].

**Corollary 3.11.** [16, Sagan and Stanley] Let $\alpha \vdash k$ be a fixed partition. Then

$$\sum_{\lambda/\alpha \vdash n} f^{\lambda/\alpha} = \sum_{j=0}^{k} \binom{n}{j} t_{n-j} \sum_{\alpha/\mu \vdash j} f^{\alpha/\mu},$$

where $t_m$ denotes the number of involutions of $[m]$.

If we set $x = y = q = 1$ in Theorem 3.9, we get the following domino analogue.

**Corollary 3.12.** Let $\alpha$ be a fixed partition with $\alpha/\tilde{\alpha} \vdash 2k$. Then

$$\sum_{\lambda/\alpha \vdash 2n} d^{\lambda/\alpha} = \sum_{j=0}^{k} \binom{n}{j} \xi_{n-j} \sum_{\alpha/\mu \vdash 2j} d^{\alpha/\mu},$$

where $\xi_m$ denotes the number of colored involutions of $[m]$.

The skew Cauchy identities corresponding to Corollary 3.7 and Corollary 3.11 were obtained by Zelvin-sky in the 1985 translation of [13]. The skew domino Cauchy identity corresponding to Corollary 3.6 was introduced by Lam [11].
# 4 A generalized sign-imbalance formula

## 4.1 Definition of the sign of a skew tableau

For two cells $a = (i, j)$ and $b = (i', j')$, we write $a \triangleleft b$ if $i < i'$ or $(i = i'$ and $j < j'$). For a SST $T$ of shape $\lambda/\mu$, we denote $\text{Inv}(T) = \{(a, b) : a \triangleleft b, T(a) > T(b)\}$ and $\text{inv}(T) = |\text{Inv}(T)|$.

The sign of a SYT $T$ is defined by $\text{sign}(T) = (-1)^{\text{inv}(T)}$. The sign-imbalance $I_\lambda$ of a partition $\lambda$ is defined by

$$I_{\lambda} = \sum_{T \in \mathcal{T}(\lambda)} \text{sign}(T).$$

The purpose of this section is to define $I_{\lambda/\mu}$ and generalize Eq. (1) and Eq. (2). In the literature, there are two different definitions of a sign of a SST $T$. We will write them as $\text{sign}_1(T)$ and $\text{sign}_2(T)$ temporarily. Sjöstrand [19] and Lam [11] used $\text{sign}_1(T)$ defined by

$$\text{sign}_1(T) = (-1)^{\text{inv}(T)}.$$

Lam [12] used $\text{sign}_2(T)$, which we will use in this paper. To define $\text{sign}_2(T)$, we introduce an operation on two SSTs.

Assume $\mu \subset \nu \subset \lambda$ and $\nu/\mu \vdash k$. Let $T_1$ and $T_2$ be SSTs of shape $\nu/\mu$ and $\lambda/\nu$ respectively. Then we define $T_1 \diamond T_2$ to be the SST $T \in \mathcal{T}(\lambda/\mu)$ such that $T(c) = T_1(c)$ if $c \in \nu/\mu$, and $T_2(c) + k$ if $c \in \lambda/\nu$.

For example, if $T_1 = \begin{bmatrix} 2 & 3 \end{bmatrix}$ and $T_2 = \begin{bmatrix} 2 & 3 \end{bmatrix}$ then $T_1 \diamond T_2 = \begin{bmatrix} 2 & 3 & 5 \end{bmatrix}$.

Now we define $\text{sign}_2(T)$ for a SST $T \in \mathcal{T}(\lambda/\mu)$ by

$$\text{sign}_2(T) = \text{sign}(T_0)\text{sign}(T_0 \diamond T),$$

where $T_0$ is an arbitrary SYT of shape $\mu$. It is straightforward to show the next proposition which implies that $\text{sign}_2$ is well-defined.

**Proposition 4.1.** Let $T$ be a SST of shape $\lambda/\mu$. Then $\text{sign}(T_0)\text{sign}(T_0 \diamond T)$ is independent on the choice of $T_0 \in \mathcal{T}(\mu)$. Moreover, $\text{sign}(T_0)\text{sign}(T_0 \diamond T) = (-1)^m \text{sign}_1(T)$, where $m = \sum_{i \ge 1} (\lambda_i - \mu_i) \cdot \sum_{j>i} \mu_j$.

We take $\text{sign}_2(T)$ for the sign of a SST $T$. From now on, we will write $\text{sign}(T)$ instead of $\text{sign}_2(T)$. The $\text{sign}(T)$ has the following product property.

**Proposition 4.2.** Let $\mu \subset \nu \subset \lambda$, $T_1 \in \mathcal{T}(\nu/\mu)$ and $T_2 \in \mathcal{T}(\lambda/\nu)$. Then $\text{sign}(T_1 \diamond T_2) = \text{sign}(T_1)\text{sign}(T_2)$.

The following proposition was proved by White [24] and Lam [10] for $\mu = \emptyset$ and $\mu = (1)$. In our definition of $\text{sign}(D)$, it holds for any $\mu$.

**Proposition 4.3.** Let $D$ be a SDT of shape $\lambda/\mu$. Then $\text{sign}(D) = (-1)^{\text{ev}(D)}$.

## 4.2 Sign-imbalance of skew shapes

The sign-imbalance $I_{\lambda/\mu}$ of a skew shape $\lambda/\mu$ is defined by

$$I_{\lambda/\mu} = \sum_{T \in \mathcal{T}(\lambda/\mu)} \text{sign}(T).$$
Let $\lambda/\mu \vdash 2n$ and $T \in \mathcal{T}(\lambda/\mu)$. If $2k-1$ and $2k$ are neither in the same row nor same column of $T$ for some $k$, let $T'$ be the SST obtained from $T$ by switching the entries $2k-1$ and $2k$ for the smallest such $k$. Then $T \mapsto T'$ is a sign reversing involution on $\mathcal{T}(\lambda/\mu)$. Thus we only need to consider SDTs. Then, using Proposition 4.3, we get $I_{\lambda/\mu} = \sum_{D \in \mathcal{D}(\lambda/\mu)} \text{sign}(D) = \sum_{D \in \mathcal{D}(\lambda/\mu)} (-1)^{\text{ev}(D)}$.

The idea of the following lemma is found in the proof of Corollary 24 in Lam's paper [10].

**Lemma 4.4.** Let $n \in \mathbb{N}$ and $\lambda/\mu \vdash 2n$. Then $I_{\lambda/\mu} = (-1)^{-\frac{1}{2}(\frac{1}{2}|\lambda/\mu|-h(\lambda/\mu))} f_2^{\lambda/\mu}(-1)$.

Now we get a generalization of Eq. (2).

**Theorem 4.5.** Let $\alpha$ and $\beta$ be fixed partitions and $n$ and $m$ be fixed nonnegative integers. Then

$$ \sum_{\substack{\lambda/\alpha \vdash 2m \\ \lambda/\beta \vdash 2n}} (-1)^{v(\lambda)} I_{\lambda/\alpha} I_{\lambda/\beta} = (-1)^{v(\alpha)+v(\beta)} \sum_{\substack{\beta/\mu \vdash 2m \\ \alpha/\mu \vdash 2n}} (-1)^{v(\mu)} I_{\beta/\mu} I_{\alpha/\mu}. $$

If we set $\alpha = \beta$ in the above theorem then we get Sjöstrand's identity [19], which was also proved by Lam [11, 12].

**Remark 2.** Sjöstrand defined $I_{\lambda/\mu} = \sum_{T \in \mathcal{T}(\lambda/\mu)} \text{sign}_1(T)$ which is different from ours. Despite the difference, by Proposition 4.1, both are the same when squared.

## 4.3 Definition of a generalized sign-imbalance formula

For a fixed partition $\alpha$ and $n \in \mathbb{N}$, let

$$ F_n^{\alpha} = F_n^{\alpha}(x, y, z) = \sum_{\lambda/\alpha \vdash n} x^{v(\lambda/\alpha)} y^{h(\lambda/\alpha)} z^{d(\lambda/\alpha)} I_{\lambda/\alpha}. $$

Then Eq. (1) can be written as $F_n^0(x, y, z) = (x + y)^{\lfloor \frac{n}{2} \rfloor}$.

For a partition $\mu$, let $\mu^+ = \{\nu : |\nu| = |\mu| + 1, \mu \subset \nu\}$. For $\mu$ and $\nu \in \mu^+$, let $u(\nu, \mu)$ denote the number of cells $a \in \mu$ such that $b \prec a$ for the unique cell $b \in \nu/\mu$. For example, if $\mu = (7, 5, 5, 2)$ and $\nu = (7, 6, 5, 2)$ then $u(\nu, \mu) = 7$.

**Proposition 4.6.** For a partition $\alpha$ and a positive integer $n$, we have $F_{n+1}^{\alpha} = \sum_{\nu \in \alpha^+} (-1)^{u(\nu, \alpha)} \psi_{\nu/\alpha} F_{n}^{\nu}$, where $\psi_{\nu/\alpha} = x^{v(\nu/\alpha)} y^{h(\nu/\alpha)} z^{d(\nu/\alpha)}$.

Using Proposition 4.6, we can calculate $F_n^\alpha$ for all $n \in \mathbb{N}$ if we have $F_n^\alpha$ for even $n$. We will focus on skew shape(or reversed shape) $\lambda/\mu \vdash 2n$.

We extend the definition of the sign-imbalance $I_{\lambda/\mu}$ as follows. For a skew(or reversed) shape $\lambda/\mu \vdash 2n$ with $n \in \mathbb{Z}$, define

$$ I_{\lambda/\mu} = (-1)^{-\frac{1}{2}(\frac{1}{2}|\lambda/\mu|-h(\lambda/\mu))} f_2^{\lambda/\mu}(-1). $$

Then, by Lemma 4.4, the above definition is compatible with the old one. We have a relation between $I_{\lambda/\mu}$ and $I_{\mu/\lambda}$.

**Proposition 4.7.** Let $n \ge 0$ and $\lambda/\mu \vdash -2n$ be a reversed shape. Then $I_{\lambda/\mu} = (-1)^{v(\mu/\lambda)} I_{\mu/\lambda}$.

Now, the definition of $F_{2n}^\alpha$ can be extended to all even integers $2n$. Then, by Proposition 4.7, for $n \ge 0$, we have $F_{-2n}^\alpha = \sum_{\alpha/\lambda \vdash 2n} (-x)^{-v(\alpha/\lambda)} y^{-h(\alpha/\lambda)} z^{-d(\alpha/\lambda)} I_{\alpha/\lambda}$.
## 4.4 A method to obtain a generalized sign-imbalance formula

Now we get a generating function for $F_{2n}^{\alpha}$.

**Theorem 4.8.** Let $\alpha$ be a fixed partition. Then

$$ \frac{\sum_{n \ge 0} F_{2n}^{\alpha} \frac{t^n}{n!}}{\sum_{n \ge 0} F_{-2n}^{\alpha} \frac{(x^2 y^2 z t)^n}{n!}} = \exp((x+y)t). $$

**Proof:** We can check that $F_{2n}^{\alpha} = W_n^{\alpha}((x\sqrt{z})^{-1}, (y\sqrt{z}\sqrt{-1})^{-1}, -1) \cdot (xy\sqrt{z})^n$. Then by Theorem 3.9, the theorem is proved. □

**Corollary 4.9.** Let $\alpha$ be a fixed partition with $\alpha/\tilde{\alpha} \vdash 2k$. Then

$$ F_{2n}^{\alpha} = \sum_{j=0}^{k} \binom{n}{j} (x+y)^{n-j} (x^2 y^2 z)^j F_{-2j}^{\alpha}. $$

Using Corollary 4.9 and Proposition 4.6 with some calculations, we get a closed formula for $F_n^{\delta_k}$. This is a generalization of the original sign-imbalance formula Eq. (1).

**Theorem 4.10.** For any integers $k \ge 0$ and $n \ge 0$, we have

$$ F_{2n}^{\delta_k} = (x+y)^n, \qquad F_{2n+1}^{\delta_k} = \begin{cases} (x+y)^n, & \text{if } k \equiv 0 \bmod 4, \\ (x+y)^{n+1}, & \text{if } k \equiv 1 \bmod 4, \\ xyz(x+y)^n, & \text{if } k \equiv 2 \bmod 4, \\ 0, & \text{if } k \equiv 3 \bmod 4. \end{cases} $$

## References

[1] D. Barbasch and D. Vogan. Primitive ideals and orbital integrals in complex classical groups. *Math. Ann.*, 259(2):153–199, 1982.

[2] S. Fomin. Duality of graded graphs. *J. Algebraic Combin.*, 3(4):357–404, 1994.

[3] S. Fomin. Schensted algorithms for dual graded graphs. *J. Algebraic Combin.*, 4(1):5–45, 1995.

[4] S. Fomin. Schur operators and Knuth correspondences. *J. Combin. Theory Ser. A*, 72(2):277–292, 1995.

[5] S. V. Fomin. The generalized Robinson-Schensted-Knuth correspondence. *Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI)*, 155(Differentsialnaya Geometriya, Gruppy Li i Mekh. VIII):156–175, 195, 1986.

[6] D. Garfinkle. On the classification of primitive ideals for complex classical Lie algebra. II. *Compositio Math.*, 81(3):307–336, 1992.

[7] F. Garvan, D. Kim, and D. Stanton. Cranks and t-cores. *Invent. Math.*, 101(1):1–17, 1990.
[8] A. D. Jaggard. Subsequence containment by involutions. *Electron. J. Combin.*, 12:Research Paper 14, 15 pp. (electronic), 2005.

[9] G. James and A. Kerber. *The representation theory of the symmetric group*, volume 16 of *Encyclopaedia of Mathematics and its Applications*. Addison-Wesley Publishing Co., Reading, Mass., 1981. With a foreword by P. M. Cohn, With an introduction by Gilbert de B. Robinson.

[10] T. Lam. Growth diagrams, domino insertion and sign-imbalance. *J. Combin. Theory Ser. A*, 107(1):87-115, 2004.

[11] T. Lam. On sjöstrand skew sign-imbalance identity. arXiv:math.CO/0607516, 2006.

[12] T. Lam. Signed differential posets and sign-imbalance. arXiv:math.CO/0611296, 2006.

[13] I. G. Macdonald. *Symmetric functions and Hall polynomials*. Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York, second edition, 1995. With contributions by A. Zelevinsky, Oxford Science Publications.

[14] A. Reifegerste. Permutation sign under the Robinson-Schensted correspondence. *Ann. Comb.*, 8(1):103-112, 2004.

[15] T. Roby. *Applications and Extensions of Fomin's Generalization of the Robinson-Schensted Correspondence to Differential Posets*. PhD thesis, MIT, 1991.

[16] B. E. Sagan and R. P. Stanley. Robinson-Schensted algorithms for skew tableaux. *J. Combin. Theory Ser. A*, 55(2):161-193, 1990.

[17] M. Shimozono and D. E. White. A color-to-spin domino Schensted algorithm. *Electron. J. Combin.*, 8(1):Research Paper 21, 50 pp. (electronic), 2001.

[18] J. Sjöstrand. On the sign-imbalance of partition shapes. *J. Combin. Theory Ser. A*, 111(2):190-203, 2005.

[19] J. Sjöstrand. On the sign-imbalance of skew partition shapes. *European J. Combin.*, 28(6):1582-1594, 2007.

[20] R. P. Stanley. *Enumerative combinatorics. Vol. 2*, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

[21] R. P. Stanley. On the enumeration of skew Young tableaux. *Adv. in Appl. Math.*, 30(1-2):283-294, 2003. Formal power series and algebraic combinatorics (Scottsdale, AZ, 2001).

[22] R. P. Stanley. Some remarks on sign-balanced and maj-balanced posets. *Adv. in Appl. Math.*, 34(4):880-902, 2005.

[23] M. A. A. van Leeuwen. The Robinson-Schensted and Schützenberger algorithms, an elementary approach. *Electron. J. Combin.*, 3(2):Research Paper 15, approx. 32 pp. (electronic), 1996. The Foata Festschrift.

[24] D. E. White. Sign-balanced posets. *J. Combin. Theory Ser. A*, 95(1):1-38, 2001.