Séminaire Lotharingien de Combinatoire 63 (2010), Article B63c

IDENTITIES FOR THE NUMBER OF STANDARD YOUNG TABLEAUX IN SOME (k, ℓ)-HOOKS

A. REGEV

Abstract. Closed formulas are known for S(k, 0; n), the number of standard Young tableaux of size n and with at most k parts, where 1 ≤ k ≤ 5. Here we study the analogous problem for S(k, ℓ; n), the number of standard Young tableaux of size n which are contained in the (k, ℓ)-hook. We deduce some formulas for the cases k + ℓ ≤ 4.

1. Introduction

Given a partition λ of n, which we denote as usual by λ ⊢ n, let χ^{λ} denote the corresponding irreducible S_{n} character. Its degree is denoted by deg χ^{λ} = f^{λ} and is equal to the number of standard Young tableaux (SYT) of shape λ. (The reader is referred to [8, 9, 13, 15] for introductions into character theory of the symmetric group and symmetric functions.) The number f^{λ} can be calculated for example by the hook formula (see [8, Theorem 2.3.21], [13, Section 3.10], [15, Corollary 7.21.6]. We consider the number of SYT in the (k, ℓ)-hook. More precisely, given integers k, ℓ, n ≥ 0, we write

H(k, ℓ; n) = {λ = (λ_{1}, λ_{2}, …) | λ ⊢ n and λ_{k+1} ≤ ℓ} and S(k, ℓ; n) = ∑_{λ∈H(k,ℓ;n)} f^{λ}.

1.1. The cases where S(k, ℓ; n) are known. For the “strip” sums S(k, 0; n) it is known (see [11] and [15, Ex. 7.16.b]) that

S(2, 0; n) = \binom{n}{⌊\frac{n}{2}⌋} and S(3, 0; n) = ∑_{j≥0} \frac{1}{j + 1}\binom{n}{2j}\binom{2j}{j}.

Let C_{j} = \frac{1}{j+1} \binom{2j}{j} be the Catalan numbers. Gouyou-Beauchamps [7] (see also [15, Ex. 7.16.b]) proved that

S(4, 0; n) = C_{⌊ \frac{n+1}{2} ⌋} · C_{⌈ \frac{n+1}{2} ⌉} and S(5, 0; n) = 6 ∑_{j=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2j} · C_{j} · \frac{(2j + 2)!}{(j + 2)!(j + 3)!}.

As for the “hook” sums, until recently only S(1, 1; n) and S(2, 1; n) = S(1, 2; n) have

been calculated:

1. It easily follows that S(1, 1; n) = 2^{n−1}.

2000 Mathematics Subject Classification. 05C30.

2. The following identity was proved in [12, Theorem 8.1]:

S(2, 1; n) = \frac{1}{4}( ∑_{r=0}^{n−1} \binom{n − r}{⌊\frac{n−r}{2}⌋}\binom{n}{r}

+ ∑_{k=1}^{⌊ \frac{n}{2} ⌋−1} \frac{n!}{k! · (k + 1)! · (n − 2k − 2)! · (n − k − 1) · (n − k)}) + 1. (1)

1.2. The main results. In Section 2 we prove Equation (10), which gives (sort of) a closed formula for S(3, 1; n) in terms of the Motzkin-sums function. For the Motzkinsums function see [14, sequence A005043]. Equation (10) is in fact a “degree” consequence of a formula for S_{n} characters, of interest in its own right, see Equation (9).

In Section 3 we find some intriguing relations between the sums S(4, 0; n) and the “rectangular” sub-sums S^{∗}(2, 2,; n) (see Section 3 for their definition), see identities (12) and (13) below.

Finally, in Section 4 we review some cases where the hook sums S(k, ℓ; n) are related, in some rather mysterious ways, to hump enumerations on Dyck and on Motzkin paths, see (14), (16), and Theorem 4.1.

As usual, in some of the above identities it is of interest to find bijective proofs, which might explain these identities.

Acknowledgement. We thank D. Zeilberger for verifying some of the identities here by the WZ method.

2. The sums S(3, 1; n) and the characters χ(3, 1; n)

Define the S_{n} character

χ(k, ℓ; n) = ∑_{λ∈H(k,ℓ;n)} χ^{λ},  so that  deg(χ(k, ℓ; n)) = S(k, ℓ; n).  (2)

2.1. The Motzkin-sums function. Define the S_{n} character

Ψ(n) = ∑_{k=0}^{⌊n/2⌋} χ^{(k,k,1^{n−2k})},  and denote  deg Ψ(n) = a(n).  (3)

We call Ψ(n) the Motzkin-sums character. Note that

deg χ^{(k,k,1^{n−2k})} = f^{(k,k,1^{n−2k})} = \frac{n!}{(k − 1)! · k! · (n − 2k)! · (n − k) · (n − k + 1)},

hence

a(n) = ∑_{k=1}^{⌊n/2⌋} \frac{n!}{(k − 1)! · k! · (n − 2k)! · (n − k) · (n − k + 1)}.  (4)

By [14, sequence A005043], it follows that a(n) is the Motzkin-sums function. The reader is referred to [14] for various properties of a(n). For example, a(n) + a(n + 1) = M_{n}, where M_{n} are the Motzkin numbers. Also a(1) = 0, a(2) = 1, and a(n) satisfies the recurrence

a(n) = \frac{n − 1}{n + 1} · (2 · a(n − 1) + 3 · a(n − 2)),  for n ≥ 3.  (5)

Note also that for n ≥ 2 Equation (1) can be written as

S(2, 1; n) = \frac{1}{4} (∑_{r=0}^{n−1} \binom{n − r}{⌊\frac{n−r}{2}⌋}\binom{n}{r} + a(n) − 1) + 1.  (6)

The asymptotic behavior of a(n) can be deduced from that of M_{n}. We deduce it here, even though it is not needed in the sequel.

Remark 2.1. As n tends to infinity,

a(n) ≃ \frac{\sqrt{3}}{8 · \sqrt{2π}} · \frac{1}{n\sqrt{n}} · 3^{n} and a(n) ≃ \frac{1}{4} · M_{n}.

Proof. By standard techniques it can be shown that a(n) has asymptotic behavior

a(n) ≃ c · (\frac{1}{n})^{g} · α^{n}

for some constants c, g and α — which we now determine. By [11], we have

M_{n} ≃ \frac{\sqrt{3}}{2\sqrt{2π}} · (\frac{1}{n})^{3/2} · 3^{n}.

Together with

M_{n} = a(n) + a(n + 1) ≃ c · (1 + α) · (\frac{1}{n})^{g} · α^{n},

this implies that α = 3, that g = 3/2, and that c = \frac{\sqrt{3}}{8·\sqrt{2π}}.

□

2.2. The outer product of S_{m} and S_{n} characters. Given an S_{m} character χ_{m} and an S_{n} character χ_{n}, we can form their outer product χ_{n} ˆ⊗χ_{n}. The exact decomposition of χ_{m} ˆ⊗χ_{n} is given by the Littlewood–Richardson rule, see [8, 9, 13, 15]. In the special case that χ_{n} = χ^{(n)}, this decomposition is given, below, by Young’s rule. Furthermore, we have

deg(χ_{n} ˆ⊗χ^{(n)}) = deg(χ_{n}) · \binom{n + m}{n}.  (7)

Young’s Rule (see [9, Ch. I, Sec. 7 and (5.16)]): Let λ = (λ_{1}, λ_{2}, …) ⊢ m and denote by λ^{+n} the following set of partitions of m + n:

λ^{+n} = {μ ⊢ n + m | μ_{1} ≥ λ_{1} ≥ μ_{2} ≥ λ_{2} ≥ ⋯ }.

Then

χ^{λ} ˆ⊗χ^{(n)} = ∑_{μ∈λ^{+n}} χ^{μ}.

Example 2.2. Given n, it follows that (see [11], [15, Ex. 7.16.b])

χ^{(⌊n/2⌋)} ˆ⊗χ^{(⌈n/2⌉)} = χ(2, 0; n), and by taking degrees, S(2, 0; n) = \binom{n}{⌊n/2⌋}. (8)

2.3. A character formula for χ(3, 1; n).

Proposition 2.3. With the notations of (2) and (3),

χ(3, 1; n) = \frac{1}{2} · [χ(2, 0, n) + ∑_{j=0}^{n} Ψ(j) ˆ⊗χ^{(n−j)}] .  (9)

By taking degrees, Example 2.2 together with (3) and (7) imply that

S(3, 1; n) = \frac{1}{2} · [\binom{n}{⌊\frac{n}{2}⌋} + ∑_{j=0}^{n} a(j) · \binom{n}{j}] .  (10)

Proof. Denote

Ω(n) = ∑_{j=0}^{n} Ψ(j) ˆ⊗χ^{(n−j)},

and analyze this S_{n} character. Young’s rule implies the following:

If μ ⊢ n, then, by Young’s rule, χ^{μ} has a positive coefficient in Ω(n) if and only if μ ∈ H(3, 1; n). Moreover, all these coefficients are either 1 or 2, and such a coefficient equals 1 if and only if μ is a partition with at most two rows, say μ = (μ_{1}, μ_{2}). It follows that

χ(2, 0; n) + Ω(n) = 2 · ∑_{λ∈H(3,1;n)} χ^{λ}.  (11)

This implies (9) and completes the proof of Proposition 2.3. □

3. The sums S(4, 0; n) and S^{∗}(2, 2; n)

Definition 3.1. (1) Let n = 2m, m ≥ 2, and let H^{∗}(2, 2; 2m) ⊂ H(2, 2; 2m) denote the set of partitions H^{∗}(2, 2; 2m) = {(k+2, k+2, 2^{m−2−k}) ⊢ 2m | k = 0, … m−2} (the partitions in the (2, 2)-hook with both arm and leg being rectangular). Furthermore, write

S^{∗}(2, 2; 2m) = ∑_{λ∈H^{∗}(2,2;2m)} f^{λ}.

(2) Let n = 2m + 1, m ≥ 2, and let H^{∗}(2, 2; 2m + 1) ⊂ H(2, 2; 2m + 1) denote the set of partitions H^{∗}(2, 2; 2m + 1) = {(k + 3, k + 2, 2^{m−2−k}) ⊢ 2m + 1 | k = 0, … m − 2} (the partitions in the (2, 2)-hook with arm nearly rectangular and leg rectangular). Furthermore, let

S^{∗}(2, 2; 2m + 1) = ∑_{λ∈H^{∗}(2,2;2m+1)} f^{λ}.

Recall from Section 1.1 that S(4, 0; 2m − 1) = C_{m}^{2} and S(4, 0; 2m) = C_{m} · C_{m+1}. We have the following intriguing identities.

Proposition 3.2. (1) Let n = 2m. Then

S(4, 0; 2m − 2) = C_{m−1} · C_{m} = S^{∗}(2, 2; 2m).

Explicitly, we have the following identity:

C_{m−1} · C_{m} = \frac{1}{m · (m + 1)} · \binom{2m − 2}{m − 1} · \binom{2m}{m}

= ∑_{k=0}^{m−2} \frac{(2m)!}{k! · (k + 1)! · (m − k − 2)! · (m − k − 1)! · (m − 1) · m^{2} · (m + 1)}. (12)

(2) Let n = 2m + 1. Then

\frac{2m + 1}{m + 2} · S(4, 0; 2m − 1) = \frac{2m + 1}{m + 2} · C_{m}^{2} = S^{∗}(2, 2; 2m + 1).

Explicitly, we have the following identity:

\frac{2m + 1}{m + 2} · C_{m}^{2} = \frac{1}{(m + 1) · (m + 2)} · \binom{2m}{m}\binom{2m + 1}{m}

= ∑_{k=0}^{m−2} \frac{(2m + 1)! · 2}{k! · (k + 2)! · (m − k − 2)! · (m − k − 1)! · (m − 1) · m · (m + 1) · (m + 2)}. (13)

Proof. Equation (12) is the specialization of Gauß’s _{2}F_{1}(a, b; c; 1) with a = 2 − m, b = 1 − m, c = 2 (cf. [1]), and (13) is similar. Alternatively, the identities (12) and (13) can be verified by the WZ method (cf. [10, 16]). □

4. Hook sums and humps for paths

A Dyck path of length 2n is a lattice path, in ℤ×ℤ, from (0, 0) to (2n, 0), using up-steps (1, 1) and down-steps (1, −1) and never going below the x-axis. A hump in a Dyck path is an up-step followed by a down-step.^{1}

A Motzkin path of length n is a lattice path from (0, 0) to (n, 0), using flat-steps (1, 0), up-steps (1, 1) and down-steps (1, −1), and never going below the x-axis. A hump in a Motzkin path is an up-step followed by zero or more flat-steps followed by a down-step.

We now count humps for Dyck and for Motzkin paths and observe the following intriguing phenomena: The hump enumeration in the Dyck case associates the 2 × n rectangular shape λ = (n, n) to the (1, 1)-hook shape μ = (n, 1^{n}). Moreover, in the Motzkin case we show below that it associates the (3, 0) strip shape partitions H(3, 0; n) to the (2, 1)-hook shape partitions H(2, 1; n).

1In the Dyck path context, humps are usually called peaks. However, we prefer the term “hump”

because, in the context of Motzkin paths, this term will indeed differ from “peak.”

4.1. The Dyck case. The Catalan number

C_{n} = \frac{(2n)!}{n!(n + 1)!}

is the cardinality of a variety of sets (see [15, Ex. 6.19]); here we are interested in two such sets. First, C_{n} = f^{(n,n)}, the number of SYT of shape (n, n). Second, C_{n} is the number of Dyck paths of length 2n. Let HD_{n} denote the total number of humps in all Dyck paths of length 2n. Then

HD_{n} = \binom{2n − 1}{n},

see [3, 4, 6]. Since \binom{2n−1}{n} = f^{(n,1^{n})}, we have

C_{n} = f^{(n,n)} and HD_{n} = f^{(n,1^{n})}.

We denote this association by

H : (n, n) ⟶ (n, 1^{n}).  (14)

4.2. The Motzkin case. Like the Catalan numbers, also the Motzkin numbers M_{n} are the cardinality of a variety of sets (cf. [15, Ex. 6.38], [14, sequence A001006]). The result from [11] that M_{n} = S(3, 0; n) gives the Motzkin numbers a SYT interpretation. Moreover, M_{n} is the number of Motzkin paths of length n. Let HM_{n} denote the total number of humps in all Motzkin paths of length n. Then, according to [14, sequence A097861],

HM_{n} = \frac{1}{2} ∑_{j≥1} \binom{n}{j}\binom{n − j}{j}.  (15)

We show below that this implies the intriguing identity HM_{n} = S(2, 1; n) − 1, which gives a SYT-interpretation of the numbers HM_{n}. Thus, the hump enumeration in the Motzkin case associates the (3, 0) strip shape partitions H(3, 0; n) to the (2, 1)-hook shape partitions H(2, 1; n). We denote this by

H : H(3, 0; n) ⟶ H(2, 1; n).  (16)

Theorem 4.1. The number of humps of all Motzkin paths of length n satisfies

HM_{n} = S(2, 1; n) − 1.

Combining Equations (1) and (15), the proof of Theorem 4.1 will follow once the following binomial identity — of interest in its own right — is proved.

Lemma 4.2. For n ≥ 2, we have

2 ∑_{j=1}^{⌊n/2⌋} \binom{n}{j}\binom{n − j}{j} = ∑_{r=0}^{n−1} \binom{n − r}{⌊\frac{n−r}{2}⌋}\binom{n}{r} + a(n) − 1

= ∑_{r=0}^{n−1} \binom{n − r}{⌊\frac{n−r}{2}⌋}\binom{n}{r} + ∑_{k=1}^{⌊ \frac{n}{2} ⌋−1} \frac{n!}{k! · (k + 1)! · (n − 2k − 2)! · (n − k − 1) · (n − k)}. (17)

Equation (17) was first verified by the WZ method. About this method, see [10, 16]. Here is an elementary proof which is due to Ira Gessel [5].

Proof. Note first that a(n) is the nth Riordan number, [14, sequence A005043], defined (for example) by

∑_{n=0}^{∞} a(n)x^{n} = \frac{2}{1 + x + \sqrt{1 − 2x − 3x^{2}}} .

Adding 2 to both sides of (17) gives the equivalent identity

2 ∑_{j=0}^{⌊n/2⌋} \binom{n}{j}\binom{n − j}{j} = ∑_{r=0}^{n} \binom{n − r}{⌊\frac{n−r}{2}⌋}\binom{n}{r} + a(n).  (18)

Now let us replace r by n − r in the sum on the right-hand side of (18), thereby getting

∑_{r=0}^{n} \binom{r}{⌊\frac{r}{2}⌋}\binom{n}{r},

and then separate the even and odd values of r so that this sum is equal to u(n) + v(n) where

u(n) = ∑_{j} \binom{2j}{j}\binom{n}{2j}

and

v(n) = ∑_{j} \binom{2j + 1}{j}\binom{n}{2j + 1}.

Noting that the left-hand side of (18) is 2u(n), we see that the identity to be proved is equivalent to

u(n) = v(n) + a(n).  (19)

It is straightforward to show that u(n) is the coefficient of x^{n} in (1 + x + x^{2})^{n} [14, sequence A002426, central trinomial coefficients] and that v(n) is the coefficient of x^{n−1} (or of x^{n+1}) in (1 + x + x^{2})^{n} [14, sequence A005717]. With these interpretations for u(n) and v(n), a combinatorial proof of the identity u(n) − v(n) = a(n) has been given by David Callan [Riordan numbers are differences of trinomial coefficients, 2006,

http://www.stat.wisc.edu/~callan/notes/riordan/riordan.pdf]. Alternatively,

Equation (19) follows easily from the known generating functions for u(n), v(n), and a(n), which can all be found in [14] (or derived directly). □

This completes the proof of Theorem 4.1.

References

[1] G. E. Andrews, R. Askey and R. Roy, Special Functions, Encyclopedia of Mathematics and its Applications, Cambridge University Press (1999).

[2] C. Darasathy ans A. Yang, A transformation on ordered trees, Computer J. 23 (1980), 161–164.

[3] N. Dershowitz and S. Zaks, Enumeration of ordered trees, Discrete Math. 31 (1980), 9–28.

[4] N. Dershowitz and S. Zaks, Applied tree enumeration, Lecture Notes in Computer Science, vol. 112, Springer, Berlin, 1981, pp. 180–193.

[5] I. Gessel, private letter.

[6] E. Deutsch, Dyck path enumeration, Discrete Math 204 (1999), 167–202.

[7] D. Gouyou-Beauchamps, Standard Young tableaux of height 4 and 5, Europ. J. Combin. 10 (1989), 69–82.

[8] G.D. James and A. Kerber, The Representation Theory of the Symmetric Group, Encyclopedia of Mathematics and its Applications, vol. 16, Addison–Wesley, Reading, MA (1981).

[9] I.G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd edition, Oxford University Press (1995).

[10] M. Petkovšek, H.S. Wilf and D Zeilberger, A=B, A.K. Peters Ltd. (1996).

[11] A. Regev, Asymptotic values of degrees associated with strips of Young diagrams, Adv. Math. 41 (1981), 115–136.

[12] A. Regev, Probabilities in the (k, ℓ) hook, Israel J. Math. 169 (2009), 61–88.

[13] B. E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, 2nd edition, Graduate Texts in Mathematics 203, Springer-Verlag (2000).

[14] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences,

    http://www.research.att.com/~njas/sequences.

[15] R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge (1999).

[16] D. Zeilberger, The method of creative telescoping, J. Symbolic Comput. 11 (1991), 195–204.

Mathematics Department, The Weizmann Institute, Rehovot 76100, Israel

E-mail address: amitai.regev at weizmann.ac.il