Séminaire Lotharingien de Combinatoire 50 (2004), Article B50d

Irreducible Symmetric Group Characters of Rectangular Shape

Richard P. Stanley^{1} Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02139 e-mail: rstan@math.mit.edu

1 The main result.

The irreducible characters χ^{λ} of the symmetric group 𝔖_{n} are indexed by partitions λ of n (denoted λ ⊢ n or |λ| = n), as discussed e.g. in [8, §1.7] or [12, §7.18]. If w ∈ 𝔖_{n} has cycle type ν ⊢ n then we write χ^{λ}(ν) for χ^{λ}(w). If λ has exactly p parts, all equal to q, then we say that λ has rectangular shape and write λ = p×q. In this paper we give a new formula for the values of the character χ^{p×q}.

Let μ be a partition of k ≤ n, and let (μ, 1^{n−k}) be the partition obtained by adding n−k 1’s to μ. Thus (μ, 1^{n−k}) ⊢ n. Define the normalized character χ̂^{λ}(μ, 1^{n−k}) by

χ̂^{λ}(μ, 1^{n−k}) = \frac{(n)_{k}χ^{λ}(μ, 1^{n−k})}{χ^{λ}(1^{n})},

where χ^{λ}(1^{n}) denotes the dimension of the character χ^{λ} and (n)_{k} = n(n − 1) ⋯ (n − k + 1). Thus [8, (7.6)(ii)][12, p. 349] χ^{λ}(1^{n}) is the number f^{λ} of standard Young tableaux of shape λ. Identify λ with its diagram {(i, j) : 1 ≤ j ≤ λ_{i}}, and regard the points (i, j) ∈ λ as squares (forming the Young diagram of λ). We write diagrams in “English notation,” with the first coordinate increasing from top to bottom and the second coordinate from left to right. Let λ = (λ_{1}, λ_{2}, …) and λ′ = (λ′_{1}, λ′_{2}, …), where λ′ is the conjugate partition to λ. The hook length of the square u = (i, j) ∈ λ is defined by

1Partially supported by NSF grant #DMS-9988459 and by the Isaac Newton Institute for Mathematical Sciences.

h(u) = λ_{i} + λ′_{j} − i − j + 1,

and the Frame-Robinson-Thrall hook length formula [8, Exam. I.5.2][12, Cor. 7.21.6] states that

f^{λ} = \frac{n!}{∏_{u∈λ} h(u)}.

For w ∈ 𝔖_{n} let κ(w) denote the number of cycles of w (in the disjoint cycle decomposition of w). The main result of this paper is the following.

Theorem 1. Let μ ⊢ k and fix a permutation w_{μ} ∈ 𝔖_{k} of cycle type μ. Then

χ̂^{p×q}(μ, 1^{pq−k}) = (−1)^{k} ∑_{uv=w_{μ}} p^{κ(u)}(−q)^{κ(v)},

where the sum ranges over all k! pairs (u, v) ∈ 𝔖_{k} × 𝔖_{k} satisfying uv = w_{μ}.

The proof of Theorem 1 hinges on a combinatorial identity involving hook lengths and contents. Recall [8, Exam. I.1.3][12, p. 373] that the content c(u) of the square u = (i, j) ∈ λ is defined by c(u) = j −i. We write s_{λ}(1^{p}) for the Schur function s_{λ} evaluated at x_{1} = ⋯ = x_{p} = 1, x_{i} = 0 for i > p. A well known identity [8, Exam. I.3.4][12, Cor. 7.21.4] in the theory of symmetric functions asserts that

s_{λ}(1^{p}) = ∏_{u∈λ} \frac{p + c(u)}{h(u)}.  (1)

Since the right-hand side is a polynomial in p, it makes sense to define

s_{λ}(1^{−q}) = ∏_{u∈λ} \frac{−q + c(u)}{h(u)}.  (2)

Equivalently, s_{λ}(1^{−q}) = (−1)^{|λ|}s_{λ′}(1^{q}). Regard p and q as fixed, and let λ = (λ_{1}, …, λ_{p}) ⊆ p × q (containment of diagrams). Define the partition λ̃ = (λ̃_{1}, …, λ̃_{p}) by

λ̃_{i} = q − λ_{p+1−i}.  (3)

Thus the diagram of λ̃ is obtained by removing from the bottom-right corner of p × q the diagram of λ rotated 180^{∘}. Write

H_{λ} = ∏_{u∈λ} h(u),

the product of the hook lengths of λ.

Lemma. With notation as above we have

H_{p×q} = (−1)^{|λ|}H_{λ}Hλ̃s_{λ}(1^{p})s_{λ}(1^{−q}).

Proof. Let λ^{♮} denote the shape λ rotated 180^{∘}. Let SQ(λ) denote the skew shape obtained by removing λ^{♮} from the lower right-hand corner of p×q and adjoining λ^{♮} at the right-hand end of the top edge of p × q and at the bottom end of the left edge. See Figure 1 for the case p = 4, q = 6, and λ = (4, 3, 1). It follows immediately from [9, Thm. 1] that

H_{SQ(λ)} = Hλ̃ ∏_{u∈λ}(p + c(u)) ∏_{v∈λ′}(q + c(u))
= (−1)^{|λ|}Hλ̃ ∏_{u∈λ}(p + c(u))(−q + c(u)).  (4)

It was proved in [10, Thm. 1.2.2] that

H_{SQ(λ)} = H_{p×q}H_{λ}.  (5)

The proof now follows from equations (1), (2), (4), and (5). □

Note. It was proved in [1][5][11] that the multiset of hook lengths of the shape SQ(λ) is the union of those of the shapes p × q and λ, a strengthening of (5) that was conjectured in [10]. Moreover, bijective proofs of the identities in [9] (hence also in [1][5][11]) are given in [2][3][7].

Proof of Theorem 1. Let ℓ = ℓ(μ). We first obtain an expression for χ^{p×q}(μ, 1^{pq−k}) using the Murnaghan-Nakayama rule [8, Exam. I.7.5][12, Thm. 7.17.3]. According to this rule,

χ^{p×q}(μ, 1^{pq−k}) = ∑_{T}(−1)^{ht(T)},

where T ranges over all border-strip tableaux (B_{1}, B_{2}, …, B_{ℓ+pq−k}) of shape p × q and type (μ, 1^{n−k}). Here we are regarding T as a sequence of border strips removed successively from the shape p × q. (See [8] or [12] for further details.) The first ℓ border strips B_{1}, …, B_{ℓ} will occupy some shape λ ⊢ k,

Figure 1: The shape SQ(4, 3, 1) for p = 4, q = 6

rotated 180^{∘}, in the lower right-hand corner of p × q. If we fix this shape λ, then the number of choices for B_{1}, …, B_{ℓ}, weighted by (−1)^{ht(B_{1})+···+ht(B_{ℓ})}, is by the Murnaghan-Nakayama rule just χ^{λ}(μ). The remaining border strips B_{ℓ+1}, …, B_{ℓ+pq−k} all have one square (and hence height 0) and can be added in f λ̃ ways, where λ̃ has the same meaning as in (3). Hence

χ^{p×q}(μ, 1^{pq−k}) = ∑_{{λ⊆p×q \atop λ⊢k}} χ^{λ}(μ)f λ̃,

so

χ̂(μ, 1^{pq−k}) = \frac{(pq)_{k}}{f^{p×q}} ∑_{{λ⊆p×q \atop λ⊢k}} χ^{λ}(μ)f λ̃

= \frac{(pq)_{k}H_{p×q}}{(pq)!} ∑_{{λ⊆p×q \atop λ⊢k}} χ^{λ}(μ)\frac{(pq − k)!}{Hλ̃}

= H_{p×q} ∑_{{λ⊆p×q \atop λ⊢k}} χ^{λ}(μ)H−1 ; λ̃.  (6)

Now let ρ(w) denote the cycle type of a permutation w ∈ 𝔖_{k}. The following identity appears in [4, Prop. 2.2] and [12, Exer. 7.70]:

∑_{λ⊢k} H_{λ}s_{λ}(x)s_{λ}(y)s_{λ}(z) = \frac{1}{k!} ∑_{{uvw=1 \atop in 𝔖_{k}}} p_{ρ(u)}(x)p_{ρ(v)}(y)p_{ρ(w)}(z),

where p_{ν}(x) is a power sum symmetric function in the variables x = (x_{1}, x_{2}, …). Set x = 1^{p}, y = 1^{−q}, take the scalar product (as defined in [8, §I.4] or [12, §7.9]) of both sides with p_{μ}, and multiply by (−1)^{k}. Since (in standard symmetric function notation) the number of permutations in 𝔖_{k} of cycle type μ is k!/z_{μ}, and since ⟨p_{μ}, p_{μ}⟩ = z_{μ} and ⟨s_{λ}, p_{μ}⟩ = χ^{λ}(μ), we get

(−1)^{k} ∑_{λ⊢k} H_{λ}s_{λ}(1^{p})s_{λ}(1^{−q})χ^{λ}(μ) = (−1)^{k} ∑_{uv=w_{μ}} p^{κ(u)}(−q)^{κ(v)}.  (7)

Note that s_{λ}(1^{p})s_{λ}(1^{−q}) = 0 unless λ ⊆ p × q. Hence we can assume that λ ⊆ p × q in the sum on the left-hand side of (7).

Now the coefficient of χ^{λ}(μ) in (6) is H_{p×q}H−1 ; λ̃, while the coefficient of χ^{λ}(μ) on the left-hand side of (7) is (−1)^{k}H_{λ}s_{λ}(1^{p})s_{λ}(1^{−q}). By the lemma these two coefficients are equal, and the proof follows. □

2 Generalizations.

The next step after rectangular shapes would be shapes that are the union of two rectangles, then three rectangles, etc. Figure 2 shows a shape σ ⊢ ∑_{i=1}^{m} p_{i}q_{i} that is a union of m rectangles of sizes p_{i} × q_{i}, where q_{1} > q_{2} > ⋯ > q_{m}.

Proposition 1. Let σ be the shape in Figure 2, and fix k ≥ 1. Set n = |σ| and

F_{k}(p_{1}, …, p_{m}; q_{1}, …, q_{m}) = χ̂^{σ}(k, 1^{n−k}).

Then F_{k}(p_{1}, …, p_{m}; q_{1}, …, q_{m}) is a polynomial function of the p_{i}’s and q_{i}’s with integer coefficients, satisfying

(−1)^{k}F_{k}(1, …, 1; −1, …, −1) = (k + m − 1)_{k}.

Proof. Let λ = (λ_{1}, …, λ_{r}) ⊢ n and

μ = (μ_{1}, …, μ_{r}) = (λ_{1} + r − 1, λ_{2} + r − 2, …, λ_{r}).

Define φ(x) = ∏_{i=1}^{r}(x − μ_{i}). A theorem of Frobenius (see [8, Exam. I.7.7]) asserts that

χ̂^{λ}(k, 1^{n−k}) = −\frac{1}{k}[x^{−1}]\frac{(x)_{k}φ(x − k)}{φ(x)},  (8)

Figure 2: A union of m rectangles

where [x^{−1}]f(x) denotes the coefficient of x^{−1} in the expansion of f(x) in descending powers of x (i.e., as a Taylor series at x = ∞).

If we let λ = σ in (8) and cancel common factors from the numerator and denominator, we obtain

χ̂^{σ}(k, 1^{n−k}) = −\frac{1}{k}[x^{−1}]\frac{(x)_{k} ∏_{i=1}^{m}(x − (q_{i} + p_{i} + p_{i+1} + ⋯ + p_{m}))_{k}}{∏_{i=1}^{m}(x − (q_{i} + p_{i+1} + p_{i+2} + ⋯ + p_{m}))_{k}} (9)

= −\frac{1}{k}[x^{−1}]H_{k}(x),

say. Since

\frac{1}{x − a} = \frac{1}{x} + \frac{a}{x^{2}} + \frac{a^{2}}{x^{3}} + ⋯,

it is clear that [x^{−1}]H_{k}(x) will be a polynomial F_{k}(p_{1}, …, p_{m}; q_{1}, …, q_{m}) in the p_{i}’s and q_{i}’s with integer coefficients. If we put p_{i} = 1 and q_{i} = −1 then we obtain (after cancelling common factors)

F_{k}(1, …, 1; −1, …, −1) = −\frac{1}{k}[x^{−1}]\frac{(x − k + 1)(x − m + 1)_{k}}{x + 1} .

Since the sum of the residues of a rational function R(x) in the extended complex plane is 0, it follows that

−\frac{1}{k}[x^{−1}]\frac{(x − k + 1)(x − m + 1)_{k}}{x + 1} = −\frac{1}{k}Res_{x=−1} (\frac{(x − k + 1)(x − m + 1)_{k}}{x + 1} )
= (−m)_{k}
= (−1)^{k}(k + m − 1)_{k}.

It remains to show that the coefficients of F_{k}(p_{1}, …, p_{m}; q_{1}, …, q_{m}) are integers. Equivalently, the coefficients of the polynomial

[x^{−1}]\frac{(x)_{k}φ(x − k)}{φ(x)}

are divisible by k. But

\frac{(x)_{k}φ(x − k)}{φ(x)} ≡ (x)_{k} (mod k)

and

[x^{−1}](x)_{k} = 0,

so the proof follows. □

Note. For any fixed μ ⊢ k, J. Katriel has shown (private communication), based on a method [6] for expressing χ̂^{λ}(μ, 1^{n−k}) in terms of the values χ̂^{λ}(j, 1^{n−j}), that χ̂^{σ}(μ, 1^{n−k}) is a polynomial F_{μ}(p_{1}, …, p_{m}; q_{1}, …, q_{m}) with rational coefficients satisfying

(−1)^{k}F_{μ}(1, …, 1; −1, …, −1) = (k + m − 1)_{k}.

It can be deduced from the Murnaghan-Nakayama rule that in fact the function F_{μ}(p_{1}, …, p_{m}; q_{1}, …, q_{m}) is a polynomial with integer coefficients. We conjecture that in fact the coefficients of F_{μ}(p_{1}, …, p_{m}; q_{1}, …, q_{m}) are nonnegative:

Conjecture 1. For fixed μ ⊢ k, χ̂^{σ}(μ, 1^{n−k}) is a polynomial F_{μ}(p_{1}, …, p_{m}; q_{1}, …, q_{m}) with integer coefficients such that (−1)^{k}F_{μ}(p_{1}, …, p_{m}; −q_{1}, …, −q_{m}) has nonnegative coefficients summing to (k + m − 1)_{k}.

We do not have a conjectured combinatorial interpretation of the coefficients of (−1)^{k}F_{μ}(p_{1}, …, p_{m}; −q_{1}, …, −q_{m}). When m = 2 we have the following data, where we write a = p_{1}, p = p_{2}, b = q_{1}, q = q_{2}:

−F_{1}(a, p; −b, −q) = ab + pq
F_{2}(a, p; −b, −q) = a^{2}b + ab^{2} + 2apq + p^{2}q + pq^{2}
−F_{3}(a, p; −b, −q) = a^{3}b + 3a^{2}b^{2} + 3a^{2}pq + ab^{3} + 3abpq + 3ap^{2}q + 3apq^{2}
+p^{3}q + 3p^{2}q^{2} + pq^{3} + ab + pq
F_{4}(a, p; −b − q) = a^{4}b + 6a^{3}b^{2} + 4a^{3}pq + 6a^{2}b^{3} + 12a^{2}bpq + 6a^{2}p^{2}q
+6a^{2}pq^{2} + ab^{4} + 4ab^{2}pq + 4abp^{2}q + 4abpq^{2} + 4ap^{3}q

+14ap^{2}q^{2} + 4apq^{3} + p^{4}q + 6p^{3}q^{2} + 6p^{2}q^{3} + pq^{4} + 5a^{2}b

+5ab^{2} + 10apq + 5p^{2}q + 5pq^{2}.

We can say something more specific about the leading terms of F_{k}(p_{1}, …, p_{m}; q_{1}, …, q_{m}). Let G_{k}(p_{1}, …, p_{m}; q_{1}, …, q_{m}) denote these leading terms, viz., the terms of total degree k + 1.

Proposition 2. We have

\frac{1}{x} + ∑_{k≥0} G_{k}(p_{1}, …, p_{m}; q_{1}, …, q_{m})x^{k} =

\frac{1}{(\frac{x ∏_{i=1}^{m}(1 − (q_{i} + p_{i+1} + p_{i+2} + ⋯ + p_{m})x)}{∏_{i=1}^{m}(1 − (q_{i} + p_{i} + p_{i+1} + ⋯ + p_{m})x)})^{⟨−1⟩}} ,  (10)

where ^{⟨−1⟩} denotes compositional inverse [12, §5.4] with respect to x. In particular, the generating function ∑ G_{k}x^{k} is algebraic over ℚ(p_{1}, …, p_{m}, q_{1}, …, q_{m}, x).

Proof. From (9) we have

G_{k}(p_{1}, …, p_{k}; q_{1}, …, q_{k}) = −\frac{1}{k}[x^{−1}]\frac{x^{k} ∏_{i=1}^{m}(x − (q_{i} + p_{i} + p_{i+1} + ⋯ + p_{m}))^{k}}{∏_{i=1}^{m}(x − (q_{i} + p_{i+1} + p_{i+2} + ⋯ + p_{m}))^{k}}

= −\frac{1}{k}[x^{−1}]L(x)^{k},

say. Let L(1/x) = M(x)/x, so M(0) = 1. Regard M(x) as a power series in ascending powers of x, i.e., an ordinary Taylor series at x = 0. Then by the Lagrange inversion formula [12, Thm. 5.4.2] we have

[x^{−1}]L(x)^{k} = [x^{k+1}]M(x)^{k} = −k[x^{k}]\frac{1}{(x/M(x))^{⟨−1⟩}} ,

so equation (10) follows. □

Proposition 2 was also proved by Philippe Biane (private communication) in the same way as here, though using the language of free probability theory.

It follows from Proposition 1 or Proposition 2 that (−1)^{k}G_{k}(p_{1}, …, p_{m}; −q_{1}, …, −q_{m}) is a polynomial with integer coefficients summing to

S_{k} := (−1)^{k}G_{k}(1, …, 1; −1, …, −1).

From Proposition 2 we have

−\frac{1}{x} + ∑_{k≥0} S_{k}x^{k} = \frac{−1}{(\frac{x(1 − x)}{1 − (m − 1)x})^{⟨−1⟩}} ,

an algebraic function of degree two. When m = 1 we have S_{k} = C_{k}, the kth Catalan number. Hence by Theorem 1 C_{k} is equal to the number of pairs (u, v) ∈ 𝔖_{k} × 𝔖_{k} such that κ(u) + κ(v) = k + 1 and uv = (1, 2, …, k), a known result (e.g., [12, Exer. 6.19(hh)]). Moreover, it follows easily from Proposition 2 that

(−1)^{k}G_{k}(p; −q) = ∑_{i=1}^{k} N(k, i)p^{k+1−i}q^{i},

where N(k, i) = \frac{1}{k} \binom{k}{i}\binom{k}{i−1}, a Narayana number [12, Exer 6.36]. Hence N(k, i) is equal to the number of pairs (u, v) ∈ 𝔖_{k} × 𝔖_{k} such that κ(u) = i, κ(v) = k + 1 − i, and uv = (1, 2, …, k). When m = 2 we have S_{k} = r_{k}, a (big) Schröder number [12, p. 178].

It would follow from Conjecture 1 that the polynomial (−1)^{k}G_{k}(p_{1}, …, p_{m}; −q_{1}, …, −q_{m}) has nonnegative coefficients. In fact, Sergi Elizalde has shown (private communication of May, 2002) that

(−1)^{k}G_{k}(p_{1}, …, p_{m}; −q_{1}, …, −q_{m})

= \frac{1}{k} ∑_{i_{1}+···+i_{m}+j_{1}+···+j_{m}=k+1} \binom{k}{i_{1}}\begin{aligned}( \\ ( & {i_{1} \atop j_{1}} & ) \\ & & ) \end{aligned}

∏_{s=2}^{m} ( ∑_{r=0}^{min(i_{s},j_{s})} \binom{k}{r}\begin{aligned}( \\ ( & {r \atop j_{s} − r} & ) \\ & & ) \end{aligned}\binom{k − r − i_{1} − ⋯ − i_{s−1} − j_{1} − ⋯ − j_{s−1}}{i_{s} − r_{s}})

p_{1}^{i_{1}} ⋯ p_{m}^{i_{m}}q_{1}^{j_{1}} ⋯ q_{m}^{j_{m}},

where \begin{aligned}( \\ ( & {a \atop b} & ) \\ & & ) \end{aligned} = \binom{a+b−1}{b}. Thus in particular (−1)^{k}G_{k}(p_{1}, …, p_{m}; −q_{1}, …, −q_{m})

indeed does have nonnegative coefficients. Do they have a simple combinatorial interpretation?

References

[1] C. Bessenrodt, On hooks of Young diagrams, Ann. Combinatorics 2 (1998), 103–110.

[2] C. Bessenrodt, On hooks of skew Young diagrams and bars in shifted diagrams, Ann. Combinatorics 5 (2001), 37–49.

[3] I. Goulden and A. Yong, Dyck paths and a bijection for multisets of hook numbers, Discrete Math. 254 (2002), 153–164.

[4] P. J. Hanlon, R. Stanley, and J. R. Stembridge, Some combinatorial aspects of the spectra of normal distributed random matrices, Contemporary Mathematics 158 (1992), 151–174.

[5] S. Janson, Hook lengths in a skew Young diagram, Electron. J. Combinatorics 4 (1997), 5, #R24.

[6] J. Katriel, Explicit expressions for the central characters of the symmetric group, Discrete Applied Math. 67 (1996), 149–156.

[7] C. Krattenthaler, Bijections for hook pair identities, Elec. J. Combinatorics 7 (2000), R27 (electronic).

[8] I. G. Macdonald, Symmetric Functions and Hall Polynomials, second ed., Oxford University Press, Oxford, 1995.

[9] A. Regev, Generalized hook and content numbers identities, Europ. J. Combinatorics 21 (2000), 949–957.

[10] A. Regev and A. Vershik, Asymptotics of Young diagrams and hook numbers, Elec. J. Combinatorics 4(1) (1997), R22 (electronic).

[11] A. Regev and D. Zeilberger, Proof of a conjecture on multisets of hook numbers, Ann. Combinatorics 1 (1997), 391–394.

[12] R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, New York/Cambridge, 1999.