An Exceptional Equinumerosity of Lattice Paths and Young Tableaux

Liam Ayres

Department of Pure Mathematics University of Waterloo Waterloo, ON N2L 3G1 Canada

  liam.ayres@uwaterloo.ca

Evan Bialo Department of Statistics & Actuarial Science University of Waterloo Waterloo, ON N2L 3G1 Canada

                                          ebialo@uwaterloo.ca

Alwin Chen and Aidan Cook Department of Pure Mathematics

University of Waterloo Waterloo, ON N2L 3G1 Canada

   z786chen@uwaterloo.ca
  aidan.cook@uwaterloo.ca

Matteus Froese, Erica Liu, Maryam Mohammadi Yekta, Oliver Pechenik, and Benjamin Wong Department of Combinatorics & Optimization University of Waterloo Waterloo, ON N2L 3G1 Canada

                                         mjfroese@uwaterloo.ca
                                         e237liu@uwaterloo.ca
                                     m5mohammadiyekta@uwaterloo.ca
                                      oliver.pechenik@uwaterloo.ca
                                         b62wong@uwaterloo.ca

Abstract

We consider families P_{n} of plane lattice paths enumerated by Guy, Krattenthaler, and Sagan. We show by explicit bijection that these families are equinumerous with the set SYT(n + 2, 2, 1^{n}) of standard Young tableaux.

1 Introduction

We consider the set P_{n} of lattice paths from (0, 0) to (n, n) that • only use the steps N = (0, 1), S = (0, −1), E = (1, 0), and W = (−1, 0);

• stay weakly inside the first quadrant of the plane;

• have length 2n + 2.

For a picture of such a path, see (3). It was shown by Guy, Krattenthaler, and Sagan [6] that

|P_{n}| = \binom{2n}{n}\frac{(4n + 4)(2n + 1)}{n + 2}.  (1)

This integer sequence appears as \underline{A253487} in the On-Line Encyclopedia of Integer Sequences (OEIS) [11]. The same enumerations also appear in the context of integrals of incomplete beta functions [1].

What appears not to have been previously noticed is that (1) is also the enumeration of standard Young tableaux (see Section 2 for precise definitions and examples) of shape θ^{(n)} = (n+2, 2, 1^{n}), an easy consequence of the hook-length formula [2] for counting standard Young tableaux of any fixed shape. (The shape θ^{(n)} is an instance of the near-hook shapes studied by Langley and Remmel [10].) That is, we have

|SYT (θ^{(n)})| = \binom{2n}{n}\frac{(4n + 4)(2n + 1)}{n + 2}.  (2)

Here we give a direct proof of this equinumerosity by exhibiting an explicit bijection between the sets P_{n} of lattice paths and SYT(θ^{(n)}) of standard tableaux.

Special enumerations of families of standard Young tableaux are often a sign of deeper algebraic structure, which can often be revealed by finding bijections between tableaux of these families and other combinatorial objects. A famous example is the set SYT(k, k) of 2-row rectangular tableaux, which is enumerated by the Catalan numbers; an equivariant bijection to noncrossing matchings yields a cyclic sieving formula for the orbit structure of Schützenberger’s [18] promotion operator on SYT(k, k) (see [14–16] for discussion). Similarly, the orbit structure of promotion on SYT(k, k, k) and SYT(k, k, k, k) may be understood via exceptional bijections to Kuperberg’s SL_{3}-webs [7,9,14] and 4-hourglass plabic graphs [5].

Another class of standard tableaux with a special enumeration is SYT(n − k, n − k, 1^{k}), which was shown by Stanley [20] to be in bijection with polygon dissections of an (n+2)-gon by n − k − 1 diagonals. Here, the bijection does not explain the promotion action on the set SYT(n−k, n−k, 1^{k}). Instead, there are further bijections to rectangular increasing tableaux and to noncrossing matchings without singleton blocks and it is the K-theoretic promotion on these increasing tableaux that is explicated through these bijections [13]. These perspectives lead to a surprising diagrammatic basis for the Specht module [19] for the partition shape (n − k, n − k, 1^{k}) [3,8,12,17].

We do not know such an application to representation theory of the bijection for SYT(θ^{(n)}) given here, but in light of this bijection and the above results, we would suggest that the Specht module for shape θ^{(n)} receive further combinatorial study. An interesting feature of the correspondence between SYT(θ^{(n)}) and P_{n} is that the number of entries in each tableau does not match the number of steps in the corresponding lattice path; the lattice paths each have length 2n + 2, while the tableaux each have 2n + 4 boxes. This mismatch makes the correspondence rather subtle.

2 Notation

To fix notation and conventions, we recall some standard notions in tableau combinatorics. For further background, see, for example, the textbooks [4, 21]. The only non-standard content in this section is Definition 1.

We write θ^{(n)} for the integer partition (n + 2, 2, 1^{n}) of the number 2n + 4 into n + 2 parts. We conflate θ^{(n)} with its Young diagram in English orientation, so that the row of length n + 2 is at the top. For example, we draw θ^{(3)} as .

Definition 1. We refer to the first row of θ^{(n)} as its arm, the first column as its leg, and the unique box that is in neither its first row nor its first column as its heart.

A standard Young tableau T ∈ SYT(θ^{(n)}) is a bijective filling of the boxes of the Young diagram with the integers 1, …, 2n + 4 such that the entries increase along rows left to right and increase down columns top to bottom. For example, 1 2 4 5 3 7 6 8 ∈ SYT(θ^{(2)}). Here, the

entries of the arm are 1, 2, 4, 5, the entries of the leg are 1, 3, 6, 8, and the heart entry is 7.

For conciseness, we write our lattice paths P ∈ P_{n} as words in the alphabet {N, S, E, W} instead of drawing the paths in the plane. For example, NNES ∈ P_{1} denotes the lattice path that looks like

N N E S  (3)

We refer to the steps N and E as forward steps and refer to the steps S and W as backwards steps. Note that the length and endpoint conditions for P_{n} force that each P ∈ P_{n} must have exactly one backwards step.

3 First bijection

In this section, we describe and prove the correctness of an explicit bijection

ψ : SYT(θ^{(n)}) → P_{n}.

Let T ∈ SYT(θ^{(n)}). We construct the corresponding path ψ(T) = P = p_{1}p_{2} ⋯ p_{2n+2} ∈ P_{n} by noting the positions of the entries of T in increasing order. The entry 1 appears in the same position in all tableaux; hence, it carries no information and we ignore it entirely.

As mentioned at the end of Section 2, a path in P_{n} must have exactly one backwards step, either W or S. We construct the path P to explicitly have exactly one backwards step. If the value 2 appears in the arm of T, the backwards step in P is S. If instead 2 appears in the leg of T, the backwards step is W.

Now, for each 3 ≤ i ≤ 2n + 4, we construct a step of the lattice path P. If i lies in the arm, then set p_{i−2} = E. If i lies in the leg, then set p_{i−2} = N. If i is in the heart, then p_{i−2} ∈ {S, W} is the backwards step, with the type of this backwards step determined earlier by observing the position of the entry 2.

In summary, ψ(T) = p_{1}p_{2} ⋯ p_{2n+2} is given by

p_{i} = \begin{cases}E, & if i + 2 ∈ arm(T); \\ N, & if i + 2 ∈ leg(T); \\ S, & if i + 2 ∈ heart(T) and 2 ∈ arm(T); \\ W, & if i + 2 ∈ heart(T) and 2 ∈ leg(T). \end{cases}  (4)

For an example of the map ψ applied to all 16 tableaux in SYT(θ^{1}), see Figure 1.

Theorem 2. The map ψ : SYT(θ^{(n)}) → P_{n} given in (4) is a bijection.

Before proceeding with the proof of Theorem 2, we note that the definition of ψ is rather delicate. For example, the reader may enjoy verifying that swapping the conditions for the steps S and W would generate lattice paths that leave the first quadrant of the plane and hence are not in P_{n}.

Proof of Theorem 2. The primary aspect that needs proof is the well-definedness of the map ψ. Let T ∈ SYT(θ^{(n)}). Note that a word in {N, S, E, W} of length 2n + 2 giving a lattice path from (0, 0) to (n, n) must contain exactly one instance of either S or W; moreover, if it contains S, then the other letters must be n + 1 copies of N and n copies of E, while if it contains W, then the other letters must be n copies of N and n + 1 copies of E.

By construction, ψ(T) has exactly one instance of S if 2 is in the arm and exactly one instance of W if 2 is in the leg. (Note that by the increasingness conditions on tableaux that 2 cannot appear in the heart nor in the intersection of the leg and arm.) In the case where 2 is in the arm of T so that S is in ψ(T), there are n numbers from {3, …, 2n + 4} in the arm and n + 1 numbers from {3, …, 2n + 4} in the leg, so that ψ(T) has n copies of E and

1 2 3 4 5 6 E N S N 1 2 3 4 6 5 E N N S 1 2 4 3 5 6 N E S N 1 2 4 3 6 5 N E N S

1 2 5 3 4 6 N S E N 1 2 6 3 4 5 N S N E 1 2 5 3 6 4 N N E S 1 2 6 3 5 4 N N S E

1 3 4 2 5 6 E E W N 1 3 4 2 6 5 E E N W 1 3 5 2 4 6 E W E N 1 3 6 2 4 5 E W N E

1 3 5 2 6 4 E N E W 1 3 6 2 5 4 E N W E 1 4 5 2 6 3 N E E W 1 4 6 2 5 3 N E W E

Figure 1: The 16 standard Young tableaux in SYT(θ^{(1)}). Below each tableau T appears the corresponding lattice path ψ(T) ∈ P_{1}.

n + 1 copies of N, as desired. In the case where 2 is in the leg of T so that W is in ψ(T), there are n numbers from {3, …, 2n + 4} in the leg and n + 1 numbers from {3, …, 2n + 4} in the arm, so that ψ(T) has n + 1 copies of E and n copies of N, again as desired. Thus, ψ(T) gives a lattice path of the correct length, ending at the correct position.

We now verify that these lattice paths remain inside the first quadrant. We must show that, if S appears, it appears after an instance of N, while, if W appears, it appears after an instance of E. Suppose p_{i} = S. Then i + 2 ∈ heart(T) and 2 ∈ arm(T). Since the second row of T is increasing, the entry j appearing directly left of the i + 2 in the heart must satisfy j < i + 2. Moreover, we know the locations of 1 and 2 in T, so j ≥ 3. It follows that p_{j−2} = N is a letter of ψ(T) appearing before p_{i}, as required. Similarly if p_{i} = W, then i + 2 ∈ heart(T) and 2 ∈ leg(T), so that the entry k directly above the i + 2 in the heart satisfies 3 ≤ k < i + 2. We conclude that p_{k−2} = E is a letter of ψ(T) appearing before p_{i}. This completes the proof that ψ is well-defined.

The injectivity of ψ is clear. Surjectivity follows from the existence of an inverse map ϕ. Given P = p_{1} ⋯ p_{2n+2} ∈ P_{n}, we produce T = ϕ(P) as follows. Place value 1 in the intersection of the arm and leg of θ^{(n)}. The elements of {i + 2 : p_{i} = E} go in the arm of T, while the elements of {i + 2 : p_{i} = N} go in the leg of T. For p_{j} the unique backwards step of P, place j + 2 in the heart of T. If p_{j} = S, include 2 in the arm of T, while if p_{j} = W, include 2 in the leg of T. It is straightforward to check that this produces a valid standard Young tableau of the desired shape and that ϕ, ψ are mutually inverse.

4 Additional bijections

Given two sets of cardinality k, there are k! distinct bijections between them. However, for sets of combinatorial interest, there is often one (or perhaps a small number) of these bijections that are understood to be the “best” or “most natural” ones. For example, one might desire the bijection to preserve important weight functions on the sets or to preserve the action of some group. While we find the bijection ψ of Section 3 attractive, we are not yet certain what properties one most wants a bijection SYT(θ^{(n)}) → P_{n} to preserve. In this section, we describe without proof several additional such bijections for possible future application.

Given a bijection κ : SYT(θ^{(n)}) → P_{n}, one may obtain another κ^{⊤} by first transposing each tableau T by reflecting across the main diagonal and then applying κ. These bijections κ, κ^{⊤} are essentially the same up to convention choices. We now proceed to give another bijection that, while similar in flavour to the bijection ψ, is fundamentally distinct.

4.1 Second bijection

Define a map ξ : SYT(θ^{(n)}) → P_{n} as follows. Let T ∈ SYT(θ^{(n)}) and let H be the entry in the heart of T. We define ξ(T) = p_{1}p_{2} ⋯ p_{2n+2} by

p_{i} = \begin{cases}E, & if i + 1 ∈ arm(T) and i + 2 < H; \\ N, & if i + 1 ∈ leg(T) and i + 2 < H; \\ S, & if i + 1 ∈ arm(T) and i + 2 = H; \\ W, & if i + 1 ∈ leg(T) and i + 2 = H; \\ E, & if i + 2 ∈ arm(T) and H < i + 2; \\ N, & if i + 2 ∈ leg(T) and H < i + 2. \end{cases}  (5)

For example, if S = 1 2 4 3 6 5 is the tableau in the upper right of Figure 1, then ξ(S) =

ENEW, while if T = 1 3 6 2 4 5 is the rightmost tableau from the third row of Figure 1, then

ξ(T) = NSNE.

We have the following.

Proposition 3. The map ξ : SYT(θ^{(n)}) → P_{n} given in (5) is a bijection.

Note that the backwards step of ψ(T) is determined by the entry of the heart of T and the position of 2, whereas the backwards step of ξ(T) is determined by the entry of the heart of T and the numerically previous entry. Of course, ξ^{⊤} yields yet another bijection.

5 Acknowledgments

The paper originates in a course CO 431/631 “Symmetric Functions” taught by Pechenik in Fall 2024 at the University of Waterloo. The other authors were all students in this course.

Liu was partially supported by Discovery Grant RGPIN-2021-02382 from the Natural Sciences and Engineering Research Council (NSERC) of Canada. Mohammadi Yekta was partially supported by Jonathan Leake’s NSERC Discovery Grant. Pechenik was partially supported by an NSERC Discovery Grant (RGPIN-2021-02391) and Launch Supplement (DGECR-2021-00010). Wong was partially supported by an NSERC Alexander Graham Bell CGSM as well as David Gosset’s NSERC Discovery Grant.

We are grateful to the anonymous referees for their comments and suggestions.

References

[1] Stephen B. Connor and Christopher J. Fewster, Integrals of incomplete beta functions, with applications to order statistics, random walks and string enumeration, Braz. J. Probab. Stat. 36 (2022), 185–198.

[2] J. S. Frame, G. de B. Robinson, and R. M. Thrall, The hook graphs of the symmetric groups, Canad. J. Math. 6 (1954), 316–324.

[3] Chris Fraser, Rebecca Patrias, Oliver Pechenik, and Jessica Striker, Web invariants for flamingo Specht modules, Algebr. Comb. 8 (2025), 235–266.

[4] William Fulton, Young Tableaux. With Applications to Representation Theory and Geometry, Vol. 35 of London Mathematical Society Student Texts, Cambridge University Press, 1997.

[5] Christian Gaetz, Oliver Pechenik, Stephan Pfannerer, Jessica Striker, and Joshua P. Swanson, Rotation-invariant web bases from hourglass plabic graphs, arxiv preprint arXiv:2306.12501 [math.CO], 2023. Available at https://arxiv.org/abs/2306.12501.

[6] Richard K. Guy, C. Krattenthaler, and Bruce E. Sagan, Lattice paths, reflections, & dimension-changing bijections, Ars Combin. 34 (1992), 3–15.

[7] Mikhail Khovanov and Greg Kuperberg, Web bases for sl(3) are not dual canonical, Pacific J. Math. 188 (1999), 129–153.

[8] Jesse Kim and Brendon Rhoades, Set partitions, fermions, and skein relations, Int. Math. Res. Not. IMRN (2023), 9427–9480.

[9] Greg Kuperberg, Spiders for rank 2 Lie algebras, Comm. Math. Phys. 180 (1996), 109– 151.

[10] T. M. Langley and J. B. Remmel, The plethysm s_{λ}[s_{μ}] at hook and near-hook shapes, Electron. J. Combin. 11 (2004), Research Paper 11, 26 pages.

[11] OEIS Foundation, The On-Line Encyclopedia of Integer Sequences. https://oeis.

org/.

[12] Rebecca Patrias, Oliver Pechenik, and Jessica Striker, A web basis of invariant polynomials from noncrossing partitions, Adv. Math. 408 (2022), Paper No. 108603, 33 pages.

[13] Oliver Pechenik, Cyclic sieving of increasing tableaux and small Schröder paths, J. Combin. Theory Ser. A 125 (2014), 357–378.

[14] T. Kyle Petersen, Pavlo Pylyavskyy, and Brendon Rhoades, Promotion and cyclic sieving via webs, J. Algebraic Combin. 30 (2009), 19–41.

[15] V. Reiner, D. Stanton, and D. White, The cyclic sieving phenomenon, J. Combin. Theory Ser. A 108 (2004), 17–50.

[16] Brendon Rhoades, Cyclic sieving, promotion, and representation theory, J. Combin. Theory Ser. A 117 (2010), 38–76.

[17] Brendon Rhoades, A skein action of the symmetric group on noncrossing partitions, J. Algebraic Combin. 45 (2017), 81–127.

[18] M. P. Schützenberger, Promotion des morphismes d’ensembles ordonnés, Discrete Math. 2 (1972), 73–94.

[19] Wilhelm Specht, Die irreduziblen Darstellungen der symmetrischen Gruppe, Math. Z. 39 (1935), 696–711.

[20] Richard P. Stanley, Polygon dissections and standard Young tableaux, J. Combin. Theory Ser. A 76 (1996), 175–177.

[21] Richard P. Stanley, Enumerative Combinatorics. Vol. 2, Vol. 208 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, second edition, 2024. With an appendix by Sergey Fomin.

2020 Mathematics Subject Classification: Primary 05A19; Secondary 05A15. Keywords: lattice path, standard Young tableau.

(Concerned with sequence \underline{A253487}.)

Received June 19 2025; revised versions received September 13 2025; September 14 2025. Published in Journal of Integer Sequences, September 15 2025.

Return to Journal of Integer Sequences home page.