Humps in Motzkin Paths and Standard Young Tableaux in a (2, 1)-Hook

Xiaomei Chen School of Mathematics and Statistics Hunan University of Science and Technology Xiangtan 411201 China

                      xmchen@hnust.edu.cn

Abstract

We calculate the number of humps and peaks in Motzkin paths with a given height, and calculate the number of standard Young tableaux (SYTs) in a (2, 1)-hook with the difference of the first two parts fixed, which refine Regev’s results. We also give new bijective proofs of Regev’s results, and reveal some new recurrence relations related to humps, free Motzkin paths, and SYTs.

1 Introduction

A Motzkin path of order n is a lattice path from (0, 0) to (n, 0), using up steps U = (1, 1), down steps D = (1, −1) and flat steps F = (1, 0), and never going below the x-axis. A free Motzkin path is an unrestricted lattice path from (0, 0) to (n, 0) consisting of the steps U, D and F. We use M_{n} to denote the set of all Motzkin paths of order n. The cardinality of M_{n} is the nth Motzkin number m_{n}, listed as \underline{A001006} in the On-Line Encyclopedia of Integer Sequences (OEIS) [11].

A hump in a Motzkin path is a subpath of the form UF^{k}D for some k ∈ ℕ. In particular, a hump with no flat steps is called a peak. See Figure 1 for an example.

Let H_{n} (OEIS \underline{A097861}) denote the total number of humps in all Motzkin paths of order n. Let S_{n} (OEIS \underline{A002426}) denote the number of free Motzkin paths of order n. By applying

\begin{matrix}P_{1} \\ P_{2} \end{matrix}

Figure 1: An example of hump and peak, where the hump P_{1} is colored red, and the peak P_{2} is colored blue.

the Wilf-Zeilberger method [8, 14], Regev [9] proved that

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

A bijective proof of (1) was given by Ding and Du [1], and generalizations of this study to (k, a)-paths were given by Du, Nie and Sun [2], Mansour and Shattuck [5], and Yan [12].

Regev pointed out that (1) is also related to the number of standard Young tableaux (SYT) in a (2, 1)-hook, where a (k, ℓ)-hook is a partition λ = (λ_{1}, λ_{2}, …) with λ_{k+1} ≤ ℓ. Let SYT(k, ℓ; n) denote the number of all SYTs with order equal to n and shape being a (k, ℓ)-hook. It is obvious that SYT(1, 1; n) = 2^{n−1}. Regev [9, 10] proved that

SYT(2, 1; n) − 1 = H_{n} = \frac{1}{2} ∑_{j≥1} \binom{n}{j}\binom{n − j}{j}.  (2)

Du and Yu [3] gave a bijective proof of (2) by showing that

SYT(2, 1; n) = \frac{1}{2}(S_{n} + 1).

The goal of this paper is to reveal some further relations between humps of Motzkin paths and Young tableaux, and obtain some refinements of identities (1) and (2). The statistic height for a hump in a Motzkin path is defined to be the y-coordinate reached by the up step of the hump. Note that the number of peaks in Dyck paths with a given height has been studied in several papers [6, 7]. We set

H_{n,k} = {(M, P) | M ∈ M_{n}, P is a hump of M with height k},
P_{n,k} = {(M, P) | M ∈ M_{n}, P is a peak of M with height k}.

Let H_{n,k} and P_{n,k} denote the cardinality of H_{n,k} and P_{n,k}, respectively.

To count humps with a given height, we consider a relation between humps and Motzkin prefixes. Here a Motzkin prefix is a lattice path that is a prefix of a Motzkin path. We let M_{n,k} denote the set of Motzkin prefixes from (0, 0) to (n, k), and set

M_{n,k}^{∗U} = {M | M ∈ M_{n,k} whose last non-flat step is U},
M_{n,k}^{D∗} = {M | M ∈ M_{n,k} whose first non-up step is D}.

See the work of Krattenthaler and Yaqubi [4] as well as Yaqubi, Farrokhi Derakhshandeh Ghouchan and Ghasemian Zoeram [13] for some further results on Motzkin prefix numbers.

In Section 2, by constructing a bijection from H_{n,k} to M_{n,2k}^{∗U}, we show that

H_{n,k} = S_{n,k},  (3)
H_{n,k} = ∑_{i=2k−1}^{n−1} M_{i,2k−1},  (4)
M_{n,2k} = H_{n,k} + H_{n,k+1},  (5)

where S_{n,k} denotes the number of free Motzkin paths of order n whose smallest y-coordinate is −k and last non-flat step is U, and M_{n,k} denotes the cardinality of M_{n,k} (OEIS \underline{A064189}). Note that Eq. (3) can be viewed as a generalization of Eq. (1).

Our first main result gives the following formulas for H_{n,k} and P_{n,k}.

Theorem 1. Let H_{n,k} (resp., P_{n,k}) be the total number of humps (resp., peaks) with height k in all Motzkin paths of order n. Then for n ≥ 2 and k ≥ 1, we have

H_{n,k} = ∑_{j=0}^{n−2k}[j ≡ n (mod 2)]\frac{4k}{n − j + 2k} \binom{n}{j}\binom{n − j − 1}{(n − j)/2 + k − 1},

P_{n,k} = ∑_{j=0}^{n−2k}[j ≡ n (mod 2)]\frac{4k}{n − j + 2k} \binom{n − 1}{j}\binom{n − j − 1}{(n − j)/2 + k − 1},

where [P] is the Iverson bracket, equal to 1 if P holds and 0 otherwise. Moreover, the number j in the sum tracks the number of flat steps of the Motzkin paths.

We also consider a relation between SYTs contained in a (2, 1)-hook and Motzkin prefixes. Let SYT_{k}(2, 1; n) denote the number of SYTs with shape λ, where λ = (λ_{1}, λ_{2}, …) ranges over all (2, 1)-hooks with λ_{1} − λ_{2} = k and order equal to n. We first show that

SYT_{2k−1}(2, 1; n + 1) + SYT_{2k−1}(2, 1; n) = H_{n+1,k} − H_{n,k}.  (6)

Then in Section 3, we give a new bijective proof of (2), and obtain the following formula for SYT_{k}(2, 1; n).

Theorem 2. For integers n, k with n − 2 ≥ k ≥ 0, we have

\begin{matrix}SYT_{k}(2, 1; n) \\ = (−1)^{n+k} + ∑_{i=0}^{⌊ \frac{n−k−1}{2} ⌋} ∑_{j=0}^{n−k−1−2i}[j ≡ n + k − 1 (mod 2)] · \frac{2k + 2}{n + k + 1 − 2i − j} \binom{n − 2i − 2}{j}\binom{n − 2i − j − 1}{(n + k − j − 1)/2 − i}. \end{matrix}

2 The number of humps and peaks with height k

A Motzkin prefix M of order n can be represented as a word M = w_{1}w_{2} ⋯ w_{n} with w_{i} ∈ \{U, D, F \}. We use \overline{M} to denote the path obtained from M by reading the steps in reverse order and then swapping the U’s and D’s.

Lemma 3. There is a bijection

ψ : ⋃_{1≤k≤⌊ \frac{n}{2} ⌋} H_{n,k} ↦ ⋃_{1≤k≤⌊ \frac{n}{2} ⌋} M_{n,2k}^{∗U},

such that (M, P) ∈ H_{n,k} if and only if ψ(M, P) ∈ M_{n,2k}^{∗U}. In particular, the subpath P is a peak of M if and only if ψ(M, P) ends with an up step.

Proof. Given (M, P) ∈ H_{n,k}, we assume that P = UF^{r}D, and decompose M as M = M_{1}P M_{2}. Let

ψ(M, P) = M_{1}U\overline{M_{2}}UF^{r}.

It is not difficult to see that ψ(M, P) ∈ M_{n,2k}^{∗U}. In particular, if M = M_{1}P M_{2} with P = UD a peak, then ψ(M, P) = M_{1}U\overline{M_{2}}U ends with an up step. See Figure 2 for an example of ψ.

M_{1} ; P ; M_{2} ; ψ ; M_{1} ; \overline{M_{2}}

Figure 2: An example of ψ with (M, P) ∈ H_{9,2}, where the hump P is colored red.

Conversely, given M ∈ M_{n,2k}^{∗U}, let M = M_{1}UM_{2}UF^{r} be the decomposition of M, such that the rightmost endpoint of M_{1} is the last endpoint of M with y-coordinate k − 1. Then we have ψ^{−1}(M) = (M_{1}UF^{r}D\overline{M_{2}}, P), where P is the hump connecting M_{1} and \overline{M_{2}}.

Similar to the proof of Lemma 3, we can give a bijective proof of Eq. (3).

Proof of Eq. (3). Given (M, P) ∈ H_{n,k}, assume that P = UF^{r}D. We decompose M as M = M_{1}P M_{2}, and define

ψ_{1}(M, P) = M_{2}DM_{1}UF^{r}.

It is not difficult to check that ψ_{1} is a bijection from H_{n,k} to the set of free Motzkin paths of order n whose smallest y-coordinate is −k and last non-flat step is U, which implies Eq. (3).

Eqs. (4) and (5) can be deduced from Lemma 3.

Proof of Eqs. (4) and (5). Given P ∈ M_{n,2k}^{∗U}, we assume that P = M_{1}UH^{r}, and define ψ_{2}(P) = M_{1}. It is not difficult to check that

ψ_{2} : M_{n,2k}^{∗U} ⟶ ⋃_{i=2k−1}^{n−1} M_{i,2k−1}

is a bijection. Thus, Eq. (4) can be deduced from Lemma 3.

On the other hand, given P ∈ M_{n,2k}, we define ψ_{3}(P) as follows.

• If P ∈ M_{n,2k}^{∗U}, we define ψ_{3}(P) = P.

• If the last non-flat step of P is D, we define ψ_{3}(P) to be the path obtained from P by replacing the last D step with U.

Then ψ_{3} is a bijection from M_{n,2k} to the union of M_{n,2k}^{∗U} and M_{n,2k+2}^{∗U}, and Eq. (5) follows.

We are now ready to give the proof of Theorem 1. A Dyck prefix is a Motzkin prefix with no flat steps. It is well known that the number of Dyck paths of semilength n ending with UD^{m} is counted by \frac{m}{n} \binom{2n−m−1}{n−1}, which is also equal to the number of Dyck prefixes from (0, 0) to (2n − m, m) ending with U. See the OEIS \underline{A033184}.

Proof of Theorem 1. A path M ∈ M_{n,2k}^{∗U} with j flat steps can be obtained uniquely by inserting j flat steps into n − j + 1 positions of a Dyck prefix from (0, 0) to (n − j, 2k) ending with U. In particular, the path M ends with an up step if and only if the above insertion is not allowed at the end of the path. Combining the above fact and Lemma 3, we obtain the identities in Theorem 1.

k = 1  2  3  4 5 6
n = 2 1
3  3
4  8  1
5  20  5
6  50  19  1
7  126  63  7
8  322 196 34  1
9  834 588 138 9
10 2187 1728 507 53 1
11 5797 5016 1749 253 11
12 15510 14454 5786 1067 76 1
Table 1: The first few entries of (H_{n,k})_{n,k∈ℕ}.

Remark 4. The sequences (H_{n,k})_{n≥2,k≥1} and (H_{n,1})_{n≥1} are entries \underline{A379838} and \underline{A140662} in the OEIS [11], respectively.

We can also consider the generating function of (H_{n,k})_{n≥2,k≥1}. For fixed k, it is well known that the generating function of (M_{n,k})_{n≥k} is

∑_{n≥k} M_{n,k}x^{n} = x^{k}M^{k+1}(x),  (7)

where M(x) is the generating function of the Motzkin numbers. See \underline{A064189} in the OEIS [11] for instance. Combining Eqs. (5) and (7), we obtain the following result.

Corollary 5. The lower triangular array (H_{n,k})_{n,k∈ℕ} is the Riordan array (\frac{1}{1−x}, x^{2}M^{2}(x)). Equivalently, for k ≥ 1, we have

∑_{n≥2k} H_{n,k}x^{n} = \frac{x^{2k}M^{2k}(x)}{1 − x},

where M(x) is the generating function of the Motzkin numbers.

3 The number of SYTs in a (2, 1)-hook

In this section, our first goal is to give a new bijective proof of Eq. (2). Let S_{k}(2, 1; n) denote the set of SYTs with shape λ, where λ = (λ_{1}, λ_{2}, …) ranges over all (2, 1)-hooks with |λ| = n and λ_{1} − λ_{2} = k. Given

T ∈ ⋃_{0≤k≤n−2} S_{k}(2, 1; n),

we define ϕ(T) = w_{1}w_{2} ⋯ w_{n}, where

w_{i} = \begin{cases}U, & if i appears in the first row of T; \\ D, & if i appears in the second row of T; \\ F, & otherwise. \end{cases}

It is obvious that

ϕ : ⋃_{0≤k≤n−2} S_{k}(2, 1; n) ↦ ⋃_{0≤k≤n−2} M_{n,k}^{D∗}

is a bijection. Therefore, to prove Eq. (2), it is sufficient to prove the following result.

Lemma 6. There is a bijection

φ : ⋃_{0≤k≤n−2} M_{n,k}^{D∗} ↦ ⋃_{1≤k≤⌊ \frac{n}{2} ⌋} M_{n,2k}^{∗U}.

Proof. Given 0 ≤ k ≤ n − 2 and M ∈ M_{n,k}^{D∗}, we define φ(M) as follows.

• If k is odd, we assume that M = U^{r}DM_{1}, and define φ(M) = U^{r−1}F M_{1}U.

• If k is even, we define φ(M) as follows.

* If the last non-flat step of M is U, then φ(M) = M.

* If M = U^{r_{1}}DM_{1}DF^{r_{2}}, then φ(M) = U^{r_{1}−1}F M_{1}UF^{r_{2}+1}.

* If M = U^{r_{1}}DF^{r_{2}}, then φ(M) = U^{r_{1}+1}F^{r_{2}}. Conversely, given 1 ≤ k ≤ ⌊\frac{n}{2}⌋ and M ∈ M_{n,2k}^{∗U}, we can obtain φ^{−1}(M) in the following

way.

• If the first non-up step of M is D, we have φ^{−1}(M) = M.

• If the first non-up step of M is F or M = U^{n}, we obtain φ^{−1}(M) as follows. * If M = U^{r}F M_{1}U, then φ^{−1}(M) = U^{r+1}DM_{1}.

* If M = U^{r_{1}}F M_{1}UF^{r_{2}} with r_{2} ≥ 1, then

φ^{−1}(M) = U^{r_{1}+1}DM_{1}DF^{r_{2}−1}.

* If M = U^{2k}F^{n−2k}, then φ^{−1}(M) = U^{2k−1}DF^{n−2k}.

We define

Φ : ⋃_{1≤k≤⌊ \frac{n}{2} ⌋} H_{n,k} ↦ ⋃_{0≤k≤n−2} S_{k}(2, 1; n)

as Φ = ϕ^{−1} ∘ φ^{−1} ∘ ψ. Then Φ is a bijection, which implies a bijective proof of Eq. (2). See Figure 3 for an example.

(M, P) Φ ψ φ^{−1} ϕ^{−1} 124573689

Figure 3: An example of Φ with (M, P) ∈ H_{9,2}, where the hump P is colored red. Next we calculate SYT_{k}(2, 1; n). Let

T_{n,k} = SYT_{k}(2, 1; n) + (−1)^{n+k+1},

where we set T_{0,0} = 0. We have the following result for the generating function of (T_{n,k})_{n≥k} for fixed k.

Lemma 7. The lower triangular array (T_{n,k})_{n,k∈ℕ} is the Riordan array (\frac{xM(x)}{1+x}, xM(x)). Equivalently, we have

T_{k}(x) = ∑_{n≥k} T_{n,k}x^{n} = \frac{1}{1 + x}(xM(x))^{k+1},

where M(x) is the generating function of the Motzkin numbers. Proof. For n ≥ k, we first show that

T_{n+1,k} + T_{n,k} = M_{n,k}.  (8)

It is obvious that T_{k,k} = 0 and T_{k+1,k} = 1 for k ≥ 0, which implies (8) for n = k. For n > k and M ∈ M_{n,k}, we define φ_{1}(M) as follows.

• If M ∈ M_{n,k}^{D∗}, we define φ_{1}(M) = M.

• If M = U^{r}F M_{1}, we define φ_{1}(M) = U^{r+1}DM_{1}. It is not difficult to check that

φ_{1} : M_{n,k} ↦ M_{n+1,k}^{D∗} ⋃ M_{n,k}^{D∗}

is a bijection. Since the left-hand side of (8) counts the number of paths in M_{n+1,k}^{D∗} ⋃ M_{n,k}^{D∗}, and the right-hand side counts the number of paths in M_{n,k}, we obtain the recurrence relation (8).

Combining Eqs. (7) and (8), we obtain Lemma 7. Remark 8. For k = 0 and k = 1, the sequences (T_{n,k})_{n≥k} are entries \underline{A187306} and \underline{A284778} in the OEIS [11], respectively.

As a direct consequence of Lemma 7, we have the following result. Corollary 9. For integers k ≥ 0, we have

∑_{n≥k} SYT_{k}(2, 1; n)x^{n} = \frac{x^{k}}{1 + x}(1 + xM^{k+1}(x)),  (9)

where M(x) is the generating function of the Motzkin numbers.

The proof of Eq. (8) also implies a bijective proof of the following recurrence relation. Corollary 10. For 1 ≤ k ≤ ⌊\frac{n}{2}⌋, we have

SYT_{2k−1}(2, 1; n + 1) + SYT_{2k−1}(2, 1; n) = H_{n+1,k} − H_{n,k}.

Proof. By the proof of (8), the left-hand side counts the number of paths in M_{n,2k−1}. By Lemma 3, the right-hand side counts the number of paths in M_{n+1,2k}^{∗U} ending with U, which is also equal to the number of paths in M_{n,2k−1}.

We are now ready to give the proof of Theorem 2. The weight w of a Motzkin prefix M ∈ M_{n,k}^{∗U} is defined as w(M) = (−1)^{r}, where r is the number of flat steps after the last up step.

Proof of Theorem 2. By Lemma 7, we have

T_{n,k} = ∑_{M∈M_{n,k+1}^{∗U}} w(M).

Given M ∈ M_{n,k+1}^{∗U} with weight −1, we define φ_{2}(M) to be the path obtained from M by moving the last flat step to the beginning. Then φ_{2} is a bijection from the set of paths in M_{n,k+1}^{∗U} with weight −1 to those with weight 1 beginning with a flat step.

As a consequence of the above bijection, we know that T_{n,k} equals the number of paths in M_{n,k+1}^{∗U} beginning with U and ending with an even number of flat steps. Since those paths can be obtained from the corresponding Dyck prefixes by inserting an even number of flat steps to the end and inserting some flat steps between the first up step and the last up step, we obtain the identity in Theorem 2.

k = 0 1 2 3 4 5 6 7 8
n = 0 1
1  0  1
2  1  0 1
3  1  2 0 1
4  3  3 3 0 1
5  6  9 6 4 0 1
6  15 21 19 10 5 0 1
7  36 55 50 34 15 6 0 1
8  91 141 139 99 55 21 7 0 1

Table 2: The first few entries of (SYT_{k}(2, 1; n))_{n,k∈ℕ}.

Remark 11. The sequence (SYT_{k}(2, 1; n))_{n≥k} is entry \underline{A379893} in the OEIS [11]. The sequence (SYT_{0}(2, 1; n))_{n≥0} gives a standard-Young-tableaux interpretation of Riordan numbers, which was first pointed out by Regev (OEIS \underline{A005043}).

4 Acknowledgments

The author was supported by the Natural Science Foundation of Hunan Province (No. 2021JJ40186). We greatly appreciate the referees for their valuable comments and helpful suggestions adopted in this revised version. We are also grateful to anonymous for providing helpful advice that improved some of the paper’s results.

References

[1] Y. Ding and R. R. X. Du, Counting humps in Motzkin paths, Discrete Appl. Math. 160 (2012), 187–191.

[2] R. R. X. Du, Y. Nie, and X. Sun, Enumerations of humps and peaks in (k, a)-paths and (n, m)-Dyck paths via bijective proofs, Discrete Appl. Math. 190-191 (2015), 42–49.

[3] R. R. X. Du and J. Yu, Standard Young tableaux in a (2, 1)-hook and Motzkin paths, Discrete Math. 344 (2021), 112395.

[4] C. Krattenthaler and D. Yaqubi, Some determinants of path generating functions, II, Adv. Appl. Math. 101 (2018), 232–265.

[5] T. Mansour and M. Shattuck, Counting humps and peaks in generalized Motzkin paths, Discrete Appl. Math. 161 (2013), 2213–2216.

[6] T. Mansour, Counting peaks at height k in a Dyck path, J. Integer Sequences 5 (2002), Article 02.1.1.

[7] P. Peart and W. J. Woan, Dyck paths with no peaks at height k, J. Integer Sequences 4 (2001), Article 01.1.3.

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

[9] A. Regev, Humps for Dyck and for Motzkin paths, arxiv preprint arXiv:1002.4504

[math.CO], 2010. Available at http://arxiv.org/abs/1002.4504.

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

[11] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2024. Available

at https://oeis.org.

[12] S. H. F. Yan, Bijective counting of humps and peaks in (k, a)-paths, Discrete Appl. Math. 193 (2015), 208–212.

[13] D. Yaqubi, M. Farrokhi Derakhshandeh Ghouchan, and H. Ghasemian Zoeram, Lattice paths inside a table, Math. Commun. 28 (2023), 181–201.

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

2020 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: Motzkin path, hump, peak, standard Young tableau, Motzkin prefix, Riordan array.

(Concerned with sequences \underline{A001006}, \underline{A002426}, \underline{A005043}, \underline{A033184}, \underline{A064189}, \underline{A097861}, \underline{A140662}, \underline{A187306}, \underline{A284778}, \underline{A379838}, and \underline{A379893}.)

Received January 3 2025; revised versions received January 6 2025; September 26 2025. Published in Journal of Integer Sequences, December 10 2025.

Return to Journal of Integer Sequences home page.