Jeu de Taquin of Set-Valued Young Tableaux

Paul Drube and Nichole Smith Department of Mathematics and Statistics Valparaiso University Valparaiso, IN 46383 USA

                 paul.drube@valpo.edu
                nichole.smith@valpo.edu

Abstract

Jeu de taquin is a well-known operation on standard Young tableaux that may be used to define an equivalence relation on tableaux of any fixed rectangular shape. Via the well-studied bijection between two-row standard Young tableaux and non-crossing matchings, jeu de taquin is known to correspond to rotation of the associated matching by one strand. In this paper, we adapt jeu de taquin to standard set-valued Young tableaux — a generalization of standard Young tableaux where cells contain unordered sets of integers. Our modified jeu de taquin operation is shown to correspond to to rotation of various classes of non-crossing matchings by one strand. In the case corresponding to k-equal non-crossing matchings, closed formulas are derived for the number of jeu de taquin equivalence classes of standard set-valued Young tableaux.

1 Introduction: jeu de taquin of Young tableaux

Let λ = (λ_{1}, …, λ_{m}) be a non-increasing integer partition of n. A Young diagram (Ferrers diagram) Y of shape λ is a left-aligned array of cells such that there are precisely λ_{i} cells in the i^{th} row of Y. An assignment of [n] = {1, …, n} to the cells Y produces what is known as a Young tableau of shape λ. A Young tableau T is column-standard if entries increase from top to bottom down every column, and is row-standard if entries increase from left to right across each row. If a Young tableau is both column-standard and row-standard, it is referred to as a standard Young tableau. We establish S(λ) as notation for the set of all standard Young tableaux of shape λ; for the m-row rectangular shape λ = (n, …, n) we use the condensed notation S(n^{m}). Comprehensive introductions to Young tableaux have been given by Fulton [7] and Stanley [17]

For any shape λ, one may define a bijection p : S(λ) → S(λ) that adapts Schützenberger’s “jeu de taquin” promotion action on posets [15]. For T ∈ S(λ), where λ ⊢ n, we construct p(T) as follows:

1. Delete the entry of T at position (1, 1) and renumber the remaining entries of T by x ↦ x − 1, producing a skew standard Young tableaux to which Schützenberger’s original operation applies.

2. Proceed through Schützenberger’s algorithm by recursively identifying the smaller of the two entries directly to the right and directly below the single vacated cell, and then sliding that smaller entry into the vacated cell (producing another vacated cell elsewhere).

3. Repeat the process of Step #2 until the single vacated cell is located in a lower-right corner. Then fill the vacated cell in the lower-right corner of the resulting tableau with n.

See Figure 1 for an example of p. Note that p has already been applied to various classes of tableaux by Shimozono [16], Stembridge [19], Rhoades [14], and Petersen, Pylyavskyy, and Rhoades [12]. For a recent generalization of the promotion operation that is entirely distinct from the generalization of this paper, see the work of Pechenik on promotion in increasing tableaux [10, 11].

1 3 4 2 5 6 7 ⇒  2 3 1 4 5 6 ⇒  1 2 3 4 5 6 ⇒  1 2 3 4 5 6 ⇒  1 2 3 4 6 5 ⇒  1 2 3 4 6 5 7

Figure 1: The map p : S(λ) → S(λ) applied to T ∈ S(λ) with λ = (3, 2, 2).

In a slight abuse of terminology, we refer to p : S(λ) → S(λ) as jeu de taquin. Associated with this operation is an equivalence relation ∼_{p} whereby T_{1}, T_{2} ∈ S(λ) satisfy T_{1} ∼_{p} T_{2} if and only if p^{k}(T_{1}) = T_{2} for some k ∈ ℤ. In this situation we say that T_{1} and T_{2} are jeu de taquin equivalent. We use S̃(λ) to denote the set of jeu de taquin equivalence classes in S(λ).

For λ = n^{2} it is well-known that |S(n^{2})| = C_{n}, where C_{n} = \frac{1}{n+1} \binom{2n}{n} is the n^{th} Catalan number. This places S(n^{2}) in bijection with the hundreds of combinatorial interpretations of C_{n} compiled by Stanley [18]. Relevant to this discussion is the bijection ϕ between S(n^{2}) and the set M_{n} of non-crossing matchings on 2n points, which associates first-row entries of T ∈ S(n^{2}) with left endpoints of half-circles in ϕ(T) ∈ M_{n} and second-row entries of T with right endpoints of half-circles in ϕ(T).

Now consider a pair of tableaux T, p(T) ∈ S(n^{2}) that are related by a single jeu de taquin. As noted by Petersen, Pylyavskyy, and Rhoades [12], the associated non-crossing matchings ϕ(T), ϕ(p(T)) ∈ M_{n} are related via “rotation” by the leftmost strand in ϕ(T) over the top of the matching. It quickly follows that the jeu de taquin equivalence classes of S̃(n^{2}) are in bijection with the set M̃_{n} of “circular non-crossing matchings” on 2n points: noncrossing partitions of [2n] into n blocks of size 2 (2-equal noncrossing partitions), modulo rotation by multiples of π/n radians when its endpoints are evenly spaced about the unit circle. See Figure 2 for an example of these phenomena.

1 3 4 6 2 5 7 8_{ϕ ↓} 1 2 3 4 5 6 7 8 ⟶p

⟶ rotation

1 2 3 5 4 6 7 8_{ϕ ↓} 1 2 3 4 5 6 7 8

Figure 2: A pair of tableaux T, p(T) ∈ S(n^{2}) and their associated non-crossing matchings. On the right is the circular non-crossing matching in M̃_{4} to which both tableaux correspond.

The jeu de taquin equivalence classes of S̃(n^{2}) may be enumerated via several techniques that already appear in the literature. The earliest such enumeration was given by Goldbach and Tijdeman [8], who directly counted the number of circular non-crossing matchings fixed by an arbitrary rotation and applied Burnside’s lemma to give

|M̃_{n}| = \frac{1}{2n} (∑_{d|n} φ(n/d)\binom{2d}{d}) − \frac{1}{2}C_{n} + \frac{1}{2}C_{(n−1)/2}.  (1)

In Eq. (1), φ represents Euler’s totient function and the final term on the right is taken to be zero if the subscript is not an integer.

Working within the more general setting of rational Catalan combinatorics, Bodnar and Rhoades [3] showed that the aforementioned rotational action on non-crossing matchings provides an example of the cyclic sieving phenomenon. This allows for a much easier enumeration of circular non-crossing matchings fixed by an arbitrary rotation, via the evaluation of q-Catalan numbers at an appropriate root of unity.

The goal of this paper is to explore a generalization of the jeu de taquin promotion operator to standard set-valued Young tableaux. In Section 2, we define set-valued jeu de taquin and look to generalize the phenomenon of Figure 2 to the most general setting in which there exists a straightforward bijection between noncrossing partitions and standard set-valued Young tableaux. That phenomenon admits a direct analogue in the case of setvalued tableaux with shape λ = n^{2} and row-constant density (Theorem 3). Generalizing the phenomenon of Figure 2 to arbitrary tableaux of shape λ = n^{2} is only possible after we define a slight modification of our jeu de taquin operator that we refer to as “rotational jeu de taquin” (Theorem 5). Section 3 is dedicated to the enumeration of jeu de taquin equivalence classes of set-valued tableaux in the case of row-constant density. This results in a one-parameter generalization of Eq. (1) that counts circular k-equal noncrossing partitions for any k ≥ 2 (Theorem 10) as well as an equivalent formula obtained via cyclic sieving (Theorem 6). It should be noted that, in the case of rational noncrossing partitions, our constructions are outwardly similar to yet subtly different from the approach of Armstrong, Rhoades, and Williams [1], which does not involve the associated tableaux.

2 Jeu de taquin of standard set-valued Young tableaux

Let Y be a Young diagram of shape λ. For any collection of positive integers ρ = {ρ_{i,j}} such that ∑_{i,j} ρ_{i,j} = m, a set-valued Young tableau of shape λ and density ρ is a map from [m] to the cells of Y such that the cell at position (i, j) receives precisely ρ_{i,j} integers. A standard set-valued Young tableau is a set-valued Young tableau with the added conditions that every integer at position (i, j) is smaller than every integer at positions (i + 1, j) and (i, j + 1). We use 𝕊(λ, ρ) to denote the set of all standard set-valued Young tableaux of shape λ and density ρ. If ∑_{i,j} ρ_{i,j} = m, we adopt the notation |ρ| = m. See Figure 3 for an illustration of 𝕊(λ, ρ) when λ = (2, 2).

1 2 3 4 5 6 7 8 9 10  1 2 3 4 5 7 6 8 9 10  1 2 3 4 5 8 6 7 9 10  1 2 3 4 6 7 5 8 9 10  1 2 3 4 6 8 5 7 9 10

1 2 3 4 7 8 5 6 9 10  1 2 3 5 6 7 4 8 9 10  1 2 3 5 6 8 4 7 9 10  1 2 3 5 7 8 4 6 9 10  1 2 3 6 7 8 4 5 9 10

Figure 3: The set 𝕊(λ, ρ) of standard set-valued Young tableaux with λ = (2, 2) and rowconstant density ρ with ρ_{1,j} = 3, ρ_{2,j} = 2.

Standard set-valued Young tableaux were originally defined by Buch [5] in his work on the K-theory of Grassmanians, and were later used by Heubach, Li, and Mansour [9] to provide a new combinatorial interpretation of the k-Catalan numbers. Those results were extended by the first author [6], who used set-valued tableaux with λ = n^{2} to give new combinatorial interpretations of the Raney numbers, the rational Catalan numbers, and the solution to the (s, t)-tennis ball problem.

The jeu de taquin operation admits a straightforward generalization p : 𝕊(λ, ρ) → 𝕊(λ, ρ) to set-valued tableaux of any shape and density. Given T ∈ 𝕊(λ, ρ), where |ρ| = m, obtain p(T) as follows:

1. Delete the smallest integer at position (1, 1), and renumber remaining entries by x ↦ x − 1.

2. Recursively identify the sole cell (i, j) in the resulting tableau T′ ∈ 𝕊(λ, ρ′) whose density ρ′_{i,j} satisfies ρ′_{i,j} = ρ_{i,j} − 1. Then identify the smallest integer between the cells at (i, j +1) and (i+1, j), and slide that entry to (i, j). This yields an “under-weighted” cell at either (i + 1, j) or (i, j + 1).

3. Repeat Step #2 until obtaining a set-valued tableau whose sole cell satisfying ρ′_{i,j} = ρ_{i,j} −1 lies in a lower-right corner. Then add m to the set of integers at this lower-right cell.

In analogy with Section 1, we refer to the map p : 𝕊(λ, w) → 𝕊(λ, w) as set-valued jeu de taquin. We once again define an equivalence relation ∼_{p} on 𝕊(λ, w) whereby T_{1} ∼_{p} T_{2} if and only if p^{k}(T_{1}) = T_{2} for some k ∈ ℤ. We say that T_{1} and T_{2} are jeu de taquin equivalent if T_{1} ∼_{p} T_{2}, and let 𝕊̃(λ, w) denote the set of jeu de taquin equivalence classes on 𝕊(λ, w).

2.1 Set-valued tableaux and generalized non-crossing matchings

We begin by establishing our general bijection between standard set-valued Young tableaux of shape λ = n^{2} and noncrossing partitions. This is possible for all set-valued tableaux whose densities carry a constant value of ρ_{2,j} = 1 across their second-row, with specific sets 𝕊(λ, ρ) of this type corresponding to noncrossing partitions with different block structures. The authors realize that much of the formalism below is a recasting of existing terminology in more convenient/concise language.

So consider a tuple of positive integers b⃗ = (b_{1}, …, b_{n}), where b_{i} ≥ 2 for all 1 ≤ i ≤ n and b_{1} + ⋯ + b_{n} = N. A non-crossing matching of type b⃗ is a noncrossing partition of [N] into n blocks whose respective sizes, when ordered via their largest elements, are b_{1}, …, b_{n}. As in Section 1, we represent our matchings as a collection of b_{i}-stars with endpoints along the x-axis.

Denote the set of all non-crossing matchings of type b⃗ by Mb⃗. When it is notationally convenient, we will reference a particular matching M ∈ Mb⃗ via the blocks of its corresponding noncrossing partition, listing the elements of each block in increasing order. For example, the matching in Figure 4 will be denoted M = {(1, 7, 8, 9), (2, 5, 6), (3, 4), (10, 11)}.

Proposition 1. Take any tuple of positive integers b⃗ = (b_{1}, …, b_{n}). The set Mb⃗ of noncrossing matchings of type b⃗ is in bijection with 𝕊(n^{2}, ρ) for density ρ with ρ_{1,j} = b_{j} − 1 and ρ_{2,j} = 1 for all j.

Proof. For any T ∈ 𝕊(λ, w), we define an injective map ϕ : 𝕊(λ, w) → Mb⃗ by working from left to right through the second row of T. For each entry a_{j} in the second row of T, identify the b_{j} − 1 largest integers x_{j,1}, …, x_{1,b_{j}−1} in the first row of T that have not already been associated to a star and which satisfy x_{j,1} < ⋯ < x_{j,b_{j}−1} < a_{j}. Then add a b_{j}-star to ϕ(T) whose endpoints lie at x_{j,1}, …, x_{j,b_{j}−1}, a_{j}. The fact that T is standard ensures that at least b_{j} −1 such integers exist. Our method of selecting the x_{j,i} ensures that stars are added “from the inside out” and hence cannot intersect.

To construct an injective inverse ϕ^{−1} : Mb⃗ → 𝕊(λ, w), take any M ∈ Mb⃗ and identify the rightmost endpoint of each b_{i}-star. Place those integers in the second row of ϕ^{−1}(M), in increasing order from left to right. Then place all remaining elements of [N] in increasing order across the first row of ϕ^{−1}(M), making sure that the cell at position (1, j) contains b_{j} − 1 integers. As the integer corresponding to the rightmost endpoint of each b_{j}-star is larger than the integers corresponding to its remaining endpoints, the tableau ϕ^{−1}(M) is column-standard.

1 2 3 5 7 8 10 4 6 9 11  ⇔  1 2 3 4 5 6 7 8 9 10 11

Figure 4: A non-crossing matching of weight b⃗ = (2, 3, 4, 2) and its corresponding standard set-valued Young tableau.

See Figure 4 for an example of the bijection from Proposition 1. For constant type b⃗ = (k, …, k), Proposition 1 reduces to the bijection involving k-equal matchings that we will examine in Subsection 2.2. For coprime positive integers a, b and using the result of Drube [6], Proposition 1 also places matchings of type b⃗_{(a,b)} = (⌈\frac{b}{a}⌉−⌈0⌉+1, …, ⌈\frac{ab}{a}⌉−⌈\frac{(a−1)b}{a}⌉+1) in bijection with a collection of set-valued tableaux that are enumerated by the rational Catalan number C(a, b) = \frac{1}{a+b} \binom{a+b}{a}. See Appendix A for a thorough discussion of how these “rational non-crossing matchings” differ from the homogeneous (a, b)-noncrossing partitions of Armstrong, Rhoades, and Williams [1], which are also enumerated by C(a, b).

Before proceeding, note that the bijection of Proposition 1 may be used to easily identify where the tableau T splits. A standard set-valued Young tableau T is said to split after its m^{th} column if the set of integers filling its first m columns equals [M] for some M ∈ ℕ. It is easy to see that T ∈ 𝕊(n^{2}, ρb⃗) splits after its m^{th} column if and only if the m leftmost stars of ϕ(T) ∈ M_{n}^{k} constitute a non-crossing matching of type b⃗′ = (b_{1}, …, b_{m}). Even more specifically:

Proposition 2. Let ϕ : 𝕊(n^{2}, w) → Mb⃗ be the bijection of Proposition 1, and take ϕ(T) ∈ Mb⃗. If x is the rightmost endpoint of the star whose leftmost endpoint is 1, then x = b_{1} + ⋯ + b_{m} for some m ≥ 1 and m is the smallest positive integer such that T splits after its m^{th} column.

2.2 Jeu de taquin and rotation of equal non-crossing matchings

In this subsection we restrict our attention to non-crossing matchings of constant type b⃗ = (k, …, k), corresponding to tableaux 𝕊(n^{2}, ρ) with row-constant density ρ satisfying ρ_{1,j} = k − 1, ρ_{2,j} = 1. These are precisely the sets 𝕊(n^{2}, ρ) and Mb⃗ that Heubach, Li, and Mansour present as two of their many combinatorial interpretations of the k-Catalan numbers [9]. In particular, those authors show that | 𝕊(λ, ρ)| = |Mb⃗| = C_{n}^{k} = \frac{1}{n(k−1)+1} \binom{kn}{n}. We henceforth

refer to non-crossing matchings of constant type b⃗ = (k, …, k) as k-equal non-crossing matchings, and denote the set of all k-equal non-crossing matchings on kn points by M_{n}^{k}.

For any (not necessarily constant) type b⃗ = (b_{1}, …, b_{m}), where b_{1} + ⋯ + b_{m} = N, there exists a rotation operator r : Mb⃗ → Mb⃗ in which r(M) is obtained by replacing the leftmost b_{1}-star (1, c_{2}, …, c_{b_{1}}) of M with the b_{1}-star (c_{2} − 1, …, c_{k} − 1, N), and then re-indexing the endpoints of all remaining stars by x ↦ x − 1. Graphically, the matchings M and r(M) are related by “swinging” the leftmost strand of the leftmost b_{1}-star in M over the top of the rest of the matching. In the case of constant type b⃗ = (k, …, k), rotation of M ∈ M_{n}^{k} directly corresponds to jeu de taquin on the associated tableau ϕ^{−1}(M) ∈ 𝕊(n^{2}, ρ) from the bijection of Proposition 1:

Theorem 3. Fix n ≥ 1, k ≥ 2, and take any row-constant density ρ with ρ_{1,j} = k − 1 and ρ_{2,j} = 1. If ϕ : 𝕊(n^{2}, ρ) → M_{n}^{k} is the bijection from Proposition 1, then ϕ(p(T)) = r(ϕ(T)) for any T ∈ 𝕊(n^{2}, ρ).

Proof. Take T ∈ 𝕊(n^{2}, ρ), and assume ϕ(T) = {(1, a_{1}^{2}, …, a_{1}^{k}), (a_{2}^{1}, …, a_{2}^{k}), …, (a_{n}^{1}, …, a_{n}^{k})}. We have r(ϕ(T)) = {(a_{1}^{2} − 1, …, a_{1}^{k} − 1, nk), (a_{2}^{1} − 1, …, a_{2}^{k} − 1), …, (a_{n}^{1} − 1, …, a_{n}^{k} − 1)}.

To characterize ϕ(p(T)), let b_{1} < ⋯ < b_{n} denote the second row entries of T. We have {a_{1}^{k}, a_{2}^{k}, …, a_{n}^{k}} = {b_{1}, …, b_{n}} as sets, yet needn’t have a_{i}^{k} = b_{i} for fixed i. Assume a_{1}^{k} = b_{α}.

Then consider the application of our set-valued jeu de taquin operation to T. If b_{i} < b_{α}, the definition of ϕ ensures that there exist at least i(k − 1) + 1 entries x in the first row of T such that x < b_{i}. This means that the re-indexed second row entry b_{i} − 1 must be larger than at least one first row entry from a more rightward column of T, and hence that b_{i} − 1 cannot be slid upward at the point in Step #2 of the set-valued jeu de taquin procedure when it lies directly below the under-weighted cell. Thus b_{i} − 1 lies at position (2, i) of p(T).

For b_{α} itself, Proposition 2 guarantees that b_{α} = kα and hence that b_{α} is smaller than every integer at position (1, α + 1) of T. This ensures that the re-indexed second row entry b_{α} − 1 must be slid upward at the point in Step #2 when it lies directly below the underweighted cell. After sliding b_{α} into the first column, the rest of Step #2 involves sliding each remaining second-row entry by one cell. All of this implies that the second row of p(T) is b_{1} − 1 < ⋯ < b_{α−1} − 1 < b_{α+1} − 1 < ⋯ < b_{n} − 1 < kn.

It is only left to determine how the first-row entries of p(T) are partitioned among the k-stars of ϕ(p(T)). We work left-to-right through the second row entries of p(T). For every i < α, all first row entries of the k-star (c_{1}, …, c_{k−1}, b_{i}) of ϕ(T) are slid precisely one entry leftward as we pass from T to p(T), allowing us to assert that ϕ(p(T)) contains the k-star (c_{1} − 1, …, c_{k−1} − 1, b_{i} − 1). For every i > α, observe that the k-star (c_{1}, …, c_{k−1}, b_{i}) of ϕ(T) satisfies c_{j} > kα for all j and hence that the corresponding k-star (c′_{1}, …, c′_{k−1}, b_{i} − 1) of ϕ(p(T)) must satisfy c′_{j} > kα − 1 for all j. The definition of ϕ then implies that ϕ(p(T)) must contain the k-star (c_{1} − 1, …, c_{k−1} − 1, b_{i} − 1). This leaves k unassigned endpoints (γ_{1}, …, γ_{k−1}, nk) for the final k-star of ϕ(p(T)), where we must have γ_{j} ≤ kα−1 for all j and thus are forced to conclude that γ_{j} = a_{1}^{j−1}−1, yielding the final k-star (a_{1}^{2}−1, …, a_{1}^{k} −1, nk).

It follows that ϕ(p(T)) = {(a_{1}^{2} − 1, …, a_{1}^{k} − 1, nk), (a_{2}^{1} − 1, …, a_{2}^{k} − 1), …, (a_{n}^{1} − 1, …, a_{n}^{k} − 1)}.

See Figure 5 for an illustration of Theorem 3. One immediate corollary of Theorem 3 is that the jeu de taquin equivalence classes of 𝕊̃(n^{2}, ρ) with ρ_{1,j} = k − 1, ρ_{2,j} = 1 are in bijection with “circular k-equal non-crossing matchings” on kn points. In analogy with Section 1, by circular k-equal non-crossing matchings we mean M_{n}^{k}, modulo rotation by multiples of 2π/kn radians when the endpoints of matchings are evenly spaced about the unit circle. We denote the set of circular k-equal non-crossing matchings on kn points by M̃_{n}^{k}.

Corollary 4. Take any n ≥ 1, k ≥ 2. Given the row-constant density ρ with ρ_{1,j} = k − 1 and ρ_{2,j} = 1, jeu de taquin equivalence classes of 𝕊̃(n^{2}, ρ) are in bijection with the set M̃_{n}^{k} of circular non-crossing k-point matchings on kn points.

1 2 3 5 6 7 4 8 9 ; ϕ ↓ ; 1 2 3 4 5 6 7 8 9  \begin{matrix}⟶ & p \\ ⟶ & r \end{matrix} 1 2 4 5 6 8 3 7 9 ; ϕ ↓ ; 1 2 3 4 5 6 7 8 9

Figure 5: A pair of set-valued tableaux related via a single jeu de taquin and the associated 3-equal non-crossing matchings. On the right is the element of M̃_{n}^{k} to which both tableaux correspond.

2.3 Jeu de taquin and rotation of generalized non-crossing matchings

Now consider non-crossing matchings of arbitrary type b⃗. The difficulty in generalizing Theorem 3 to non-constant b⃗ derives from the fact that the bijection of Proposition 1 is dependent upon the left-to-right ordering of blocks in the non-crossing matchings. As such, repeated application of the rotation operator will eventually permute the ordering of the blocks and require a set-valued tableaux with a different sequence of first-row densities. See Figure 6 for an example of how Theorem 3 can fail if generalized to non-constant b⃗.

Failings such as the one in Figure 6 may be addressed via a slight modification of our jeu de taquin operator, a modification that specializes to our original operator in the case of constant type b⃗. So take T ∈ 𝕊(n^{2}, ρ), where the density ρ satisfies ρ_{2,j} = 1 for all 1 ≤ j ≤ n,

1 2 4 5 3 6 7 ; ϕ ↓ ; 1 2 3 4 5 6 7  \begin{matrix}⟶ \\ p \\ ⟶ & r \end{matrix} 1 2 3 4 5 6 7 1 2 3 4 5 6 7  ^{⟶ ϕ} 1 2 3 4 5 6 7

Figure 6: A set-valued tableaux T where ϕ(p(T)) ≠ r(ϕ(T)), as rotation of ϕ(T) changes the matching’s type from b⃗ = (3, 2, 2) to b⃗′ = (2, 2, 3).

and assume that m is the smallest integer such that T splits after its m^{th} column. Then define ρ̃ to be the density satisfying ρ̃_{2,j} = 1 for all 1 ≤ j ≤ n, ρ̃_{1,j} = ρ_{1,j} for 1 ≤ j < m, ρ̃_{1,j} = ρ_{1,j+1} for m ≤ j < n, and ρ̃_{1,n} = ρ_{1,m}. We informally refer to ρ̃ as the “rotated density” for T. See the first row of Figure 8 for an illustration of the relationship between ρ and ρ̃.

We may then define an operator p_{r} : 𝕊(n^{2}, ρ) → ⋃ρ̃ 𝕊(n^{2}, ρ̃) that applies to any set 𝕊(n^{2}, ρ) with a density satisfying ρ_{2,j} = 1 for all j. For any T ∈ 𝕊(n^{2}, ρ), p_{r}(T) is obtained as follows:

1. Identify the smallest positive integer m such that T splits after its m^{th} column.

2. Perform the full set-valued jeu de taquin operation on T, yielding p(T) ∈ 𝕊(λ, ρ).

3. Re-partition entries in the first row of p(T) to produce a tableau p_{r}(T) ∈ 𝕊(λ, ρ̃) with rotated density ρ̃ determined by the integer m from Step #1.

To see that a tableau above remains column-standard as we pass from p(T) to p_{r}(T) in Step #3, let c_{1} < ⋯ < c_{n} denote the second-row entries of T. The sole entry to slide upward during Step #2 is the shifted entry c_{m} − 1 that began at position (i, j) = (2, m). All subsequent second row entries c_{m+1} − 1, …, c_{n} − 1 are slid one cell leftward. When first-row entries are re-partitioned during Step #3, entries in the first m − 1 columns are unmoved whereas entries in columns m − 1 through n are moved at most one cell leftward (some first row entries may move rightward). It follows that all first-row entries of p_{r}(T) lie above second-row entries that are at least as large as the entries that appeared below them in p(T).

We refer to the map p_{r} as rotational set-valued jeu de taquin. See the top row of Figure 7 for an application of p_{r} that isn’t equivalent to our original set-valued jeu de taquin. As seen in the bottom row of Figure 7, the passage from p(T) to p_{r}(T) is precisely the correction needed for set-valued jeu de taquin to correspond to rotation of the associated matchings.

Theorem 5. Fix n ≥ 1, and take any density ρ such that ρ_{2,j} = 1 for all 1 ≤ j ≤ n. For any T ∈ 𝕊(n^{2}, ρ) with rotated density ρ̃, define b⃗ = (ρ_{1,1} + 1, …, ρ_{1,n} + 1) and b⃗′ =

1 2 3 5 6 9 10 11 12 4 7 8  13 14 ⟶  1 2 4 5 7 8 9 10 11 3 6 12 13 14 ⟶  1 2 4 5 7 8 9 10 11 3 6 12 13 14

1 2 3 4 5 6 7 8 9 10 11 12 13 14  ⟶

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Figure 7: Rotational set-valued jeu de taquin applied to a tableau T ∈ 𝕊(5^{2}, ρ) that splits after its third column, as well as a comparison of ϕ(T) with ϕ(p_{r}(T)).

(ρ̃_{1,1} + 1, …, ρ̃_{1,n} + 1). If ϕ : 𝕊(n^{2}, ρ) → Mb⃗ and ϕ′ : 𝕊(n^{2}, ρ̃) → Mb⃗′ are defined as in the proof of Proposition 1, then ϕ′(p_{r}(T)) = r(ϕ(T)).

Proof. The operator p_{r} has been defined so that ϕ′(p_{r}(T)) and r(ϕ(T)) both lie in Mb⃗′. See Figure 8 for a demonstration of this phenomenon. An equivalent argument to Theorem 3 shows that the blocks of ϕ′(p_{r}(T)) and r(ϕ(T)) have the same right endpoints, at identical locations. As the blocks of ϕ′(p(r(T)) and r(ϕ(T)) cannot intersect, all that remains to be shown is that each of those right endpoints (when ordered from left-to-right) is associated with a block of equivalent size in both matchings. Yet this follows directly from the fact that both ϕ′(p_{r}(T)) and r(ϕ(T)) are matchings of weight b⃗′.

\begin{matrix}ρ_{1} & ⋯ & ρ_{m−1} & ρ_{m} & ρ_{m+1} & ⋯ & ρ_{n} \\ 1 & ⋯ & 1 & 1 & 1 & ⋯ & 1 \end{matrix} ; \begin{matrix}x \\ B_{1} \\ B_{2} \end{matrix}  \overrightarrow{⟶}  \begin{matrix}ρ_{1} & ⋯ & ρ_{m−1} & ρ_{m+1} & ⋯ & ρ_{n} & ρ_{m} \\ 1 & ⋯ & 1 & 1 & ⋯ & 1 & 1 \end{matrix} ; \begin{matrix}x-1 \\ B_{1} \\ B_{2} \end{matrix}

Figure 8: Density ρ and rotated density ρ̃ for a tableau T whose leftmost split occurs after its m^{th} column. The bottom row demonstrates how rotation of ϕ(T) reorders rightmost endpoints of blocks in a manner consistent with the relationship between ρ and ρ̃. Here x = ρ_{1} + ⋯ + ρ_{m} + m.

3 Enumeration of jeu de taquin equivalence classes

In this section we restrict our attention to sets 𝕊(n^{2}, ρ) with row-constant density ρ of the form ρ_{1,j} = k − 1, ρ_{2,j} = 1, and look to provide closed formulas for the number of jeu de taquin equivalence classes in 𝕊̃(n^{2}, ρ). Via Corollary 4 this is equivalent to enumerating M̃_{n}^{k} for any n ≥ 1, k ≥ 2, meaning that our formulas should specialize to Eq. (1) in the case of k = 2.

As M̃_{n}^{k} may be defined via a cyclic action of ℤ_{nk} on M_{n}^{k}, we utilize pre-existing machinery for investigating that action. We present two distinct methods that yield equivalent yet vastly different looking summations for |M̃_{n}^{k}|. In Subsection 3.1 we apply the cyclic sieving phenomenon in a manner than relies upon Bodnar and Rhodes [3]. In Subsection 3.2 we take a more direct combinatorial approach in the flavor of Goldbach and Tijdeman [8]. Although cyclic sieving yields an enumeration with far less effort, the methodology of the direct approach reveals more about the combinatorial structure of M_{n}^{k} and admits a major simplification when k is prime. The authors are unsure how the q-Catalan evaluations of Subsection 3.1 may be reduced to the binomial coefficients of Subsection 3.2.

With both of our methods relying upon Burnside’s lemma, we pause to recap that classic result. Burnside’s lemma, also known as the Cauchy-Frobenius lemma, applies whenever a finite group G acts upon a set A. The lemma states that the number of orbits with respect to the action, namely |A/G|, is equal to the average size of all sets A^{g} = {a ∈ A|ga = a}. That is, |A/G| = \frac{1}{|G|} ∑_{g∈G} |A^{g}|.

In our situation let A = M_{n}^{k} and G = ℤ_{nk}, with left action of g ∈ ℤ_{nk} on M ∈ M_{n}^{k} given by g applications of the rotation operator, namely g · M = r^{g}(M). The orbits of this action are clearly the set of circular non-crossing k-point matchings M̃_{n}^{k}. In order to determine |M̃_{n}^{k}|, it is then our task to determine |A^{g}| for arbitrary g ∈ ℤ_{nk}. For any g ∈ ℤ_{nk}, we henceforth refer to an element M ∈ A^{g} as a k-equal non-crossing matching of order g.

See Table 1 for values of |M̃_{n}^{k}|, all of which were calculated in Maple 18 via Theorem 10. The k = 2 row of that table predictably corresponds to \underline{A002995}. All later rows reveal a surprising correspondence to the numbers of k-gonal cacti having n polygons, as studied by Bóna, Bousquet, Labelle, and Leroux [4]. In particular, later rows of Table 1 appear as \underline{A054423} (k = 3), \underline{A054362} (k = 4), \underline{A054365} (k = 5), and \underline{A054368} (k = 6). Finding an explicit bijection between our jeu de taquin equivalence classes and these k-gonal cacti is an interesting topic for future investigation. Note that, even if an elementary bijection were to exist, our approach has the advantage that it may be easily generalized to rectangular setvalued tableaux of distinct densities, yielding sequences that may not correspond to known statistics on k-gonal cacti.

In all that follows we use standard notation for the q-number [p]_{q} = 1 + q + ⋯ + q^{p−1}, the q-factorial [p]_{q}! = [1]_{q}[2]_{q} ⋯ [p]_{q}, and the q-binomial coefficient \binom{a}{b}_{q} = \frac{[a]_{q}!}{[b]_{q}![a−b]_{q}!}.

n = 1 n = 2 n = 3 n = 4 n = 5 n = 6 n = 7 n = 8  n = 9  n = 10
k = 2  1  1  2  3  6  14  34  95  280  854
k = 3  1  1  2  7  19  86  372  1825  9143  47801
k = 4  1  1  3  11  52  307 1936 13207  93496  683988
k = 5  1  1  3  17  102  811 6626 58385  532251  5011934
k = 6  1  1  4  25  187 1772 17880 191967 2141232 24640989
k = 7  1  1  4  33  300 3412 40770 518043 6830545 92909684
k = 8  1  1  5  43  463 5993 82887 1213879 18471584 289883603
Table 1: |𝕊̃(n^{2}, ρ| = |M̃_{n}^{k}| for ρ the row-constant density ρ_{1,j} = k − 1, ρ_{2,j} = 1.

3.1 Enumeration via cyclic sieving

As defined by Reiner, Stanton, and White [13], cyclic sieving is a phenomenon that may be associated with the action of a cyclic group G = ⟨c⟩ upon a finite set X. For X(q) ∈ ℕ(q) and ω ∈ ℂ a root of unity of order |G|, the ordered triple (X, G, X(q)) exhibits cyclic sieving if X(ω^{d}) = |X^{c^{d}}| = {x ∈ X|c^{d}x = x}.

For relatively prime positive integers a < b and X the set of homogeneous (a, b)- noncrossing partitions, Bodnar, and Rhodes [3] proved that (X, G, X(q)) exhibited cyclic sieving when G = ℤ_{a+b−1} acts on X by rotation and X(q) = C_{q}(a, b) = \frac{1}{[a+b]_{q}} \binom{a+b}{a,b}_{q} is the q-rational Catalan number. See Appendix A for a fuller discussion of homogeneous (a, b)-noncrossing partitions, as originally defined by Armstrong, Rhoades, and Williams [1]. Central to our situation is the fact that, as outlined in Armstrong, Rhaodes, and Williams [1], homogeneous (a, b)-noncrossing partitions specialize to k-equal non-crossing matchings on kn points in the specific case of (a, b) = (n, (k −1)n+1). This mirrors the straightforward identity that C(n, (k − 1)n + 1) = \frac{1}{kn+1} \binom{kn+1}{n} = C_{n}^{k}.

It follows that (M_{n}^{k}, ℤ_{nk}, X(q)) exhibits the cyclic sieving phenomenon with respect to the rotational action of ℤ_{nk} on M_{n}^{k} when X(q) = \frac{1}{[kn+1]_{q}} \binom{kn+1}{n}_{q} is the q-analogue of the k-Catalan number. This allows us to conclude that |A^{g}| = X(ω^{g}) for any g ∈ ℤ_{nk}, where ω = e^{\frac{2πi}{nk}} is the primitive (nk)^{th} root of unity. A direct application of Burnside’s lemma then yields

Theorem 6. Fix k ≥ 2, n ≥ 1, and let ρ be the row-constant density with ρ_{1,j} = k − 1 and ρ_{2,j} = 1 for all j. Then

|𝕊̃(n^{2}, ρ)| = |M̃_{n}^{k}| = \frac{1}{nk} ∑_{g=0}^{nk−1} X(ω^{g}).

Here φ is Euler’s phi function, X(q) = \frac{1}{[kn+1]_{q}} \binom{kn+1}{n}_{q}, and ω = e^{\frac{2πi}{nk}}.

3.2 Enumeration via sub-matchings

For our direct approach, begin by noting that |A^{g}| = 0 if gcd(g, nk) = 1. It is also immediate that |A^{0}| = |M_{n}^{k}| = C_{n}^{k}. For non-zero g with gcd(g, nk) = d > 1, a matching M ∈ A^{g} must decompose into nk/d “sub-matchings” on d points, each of which follows an identical pattern in how it divides its endpoints among k-stars. Notice that these sub-matchings need not define non-crossing k-point matchings on d points when considered individually, as they may contain “outgoing” strands from k-stars whose endpoints are divided between multiple submatchings. We refer to the process by which sub-matchings are pieced together to create M ∈ A^{g} as horizontal concatenation, and write q_{j}(M) = m if j copies of m horizontally concatenate to produce M. See Figure 9 for several sub-matchings and their corresponding k-point matchings.

⇒

⇒

Figure 9: Non-crossing 3-point matchings M_{1}, M_{2} ∈ M_{7}^{3} of order 7, constructed from their sub-matchings q_{3}(M_{1}), q_{3}(M_{2}). Notice that r(M_{1}) = M_{2}, implying that their associated set-valued tableaux are jeu de taquin equivalent.

Our strategy is to place A^{g} in bijection with certain sets of sub-matchings on d points, using the map q_{nk/d}. This map q_{nk/d} is injective for any g ∈ ℤ_{nk}, as distinct matchings must feature distinct patterns in their sub-matchings. The difficulty is then in describing Im(q_{nk/d}), as not all potential sub-matchings may be horizontally concatenated when one allows for outgoing strands.

So consider the nk/d sub-matchings of M ∈ A^{g} as if they were ordered cyclically. As our matchings are non-crossing, it is not possible for a k-star of M to have identically placed endpoints in more than two sub-matchings unless it has endpoints in all nk/d sub-matchings. Furthermore, M can contain at most one “topmost” k-star with identically placed endpoints in all nk/d sub-matchings. These observations allow us to place all outgoing strands into two basic categories. “Unpaired” outgoing strands belong to the k-star of M whose k endpoints are equivalently partitioned within every sub-matching. “Paired” outgoing strands belong to k-stars of M whose endpoints are split between precisely two sub-matchings, with the “leftbound” and “right-bound” strands of each pair connecting to distinctly positioned endpoints within their respective sub-matchings.^{1}

See the top matching of Figure 9 for an example of sub-matchings with paired and unpaired strands. When depicting sub-matchings, unpaired strands will always be drawn as vertical rays.

It is immediate that any sub-matching in Im(q_{nk/d}) must feature the same number of left-bound and right-bound outgoing strands. Delaying a consideration of unpaired strands, let m^{k}(d, x) denote the set of non-crossing k-point sub-matchings on d points that contain precisely x unpaired outgoing strands as well as identical numbers of right-bound and leftbound strands.

Lemma 7. Fix k ≥ 2, d ≥ 1, and x ≥ 0. Then

|m^{k}(d, x)| = \begin{cases}\binom{d}{(d − x)/k}, & if k | (d − x); \\ 0, & if k ∤ (d − x). \end{cases}

Proof. As any m ∈ m^{k}(d, x) contains d − x endpoints that aren’t associated with unpaired strands, |m^{k}(d, x)| = 0 if k | (d−x). When k | (d−x), we define a bijection ψ : m^{k}(d, x) → S with the set S of ordered d-tuples in {R, L} that contain precisely (d − x)/k copies of R.

For any m ∈ m^{k}(d, x), identify the rightmost endpoint of each k-star that doesn’t include an unpaired strand, assuming that k-stars involving left-bound (resp. right-bound) outgoing strands include more leftward (resp. rightward) endpoints. There will always be (d − x)/k such rightmost endpoints. Then define the d-tuple ψ(M) by associating our our rightmost endpoints with R coordinates and all other endpoints with L coordinates.

The map ψ is clearly injective. To show ψ is bijective we define an injective map ψ^{−1} : S → m^{k}(d, x). So take any d-tuple v⃗ ∈ S and consider its coordinates as if they were ordered cyclically. We construct ψ^{−1}(v⃗) one k-star at a time, from the “innermost” k-stars outward. As v⃗ contains at most d/k copies of R, there will be at least one length-k sub-string of the form LL ⋯ LR. Identify the substring of this form whose R entry lies farthest to the right, and place a k-star in ψ^{−1}(v⃗) whose endpoints lie at the coordinates in that sub-string. Notice that if our distinguished sub-string “wraps around” the end of v⃗, the resulting k-star will include paired outgoing strands. Recursively apply the process above for the substring of v⃗ whose endpoints have not yet been assigned to a k-star. This will eventually leave x total L coordinates, which we associate with the endpoints of unpaired outgoing strands.

It is easy to see that m^{k}(d, 0) ⊆ Im(q_{nk/d}) for all g ∈ ℤ_{nk} with gcd(g, nk) = d > 1, as horizontal concatenation merely involves an identification of right-bound outgoing strands with left-bound outgoing strands. It is only left to determine when m^{k}(d, x) ⊆ Im(q_{nk/d}) in the case of x > 0:

Lemma 8. Fix k ≥ 2 and non-zero g ∈ ℤ_{nk} with gcd(g, nk) = d > 1. Then m^{k}(d, x) ⊆ Im(q_{nk/d}) if and only if either 1. x = 0, or

1The apparent ambiguity in the case of nk/d = 2 is eliminated by our requirement that any fixed k-star associated with paired strands cannot have identically placed endpoints within each sub-matching.

2. x = \frac{d}{n} and \frac{nk}{d} is a non-trivial divisor of gcd(k, n − 1).

Proof. Assume \frac{nk}{d} > 1 and that a sub-matching m ∈ m^{k}(d, x) with q_{nk/d}(M) = m has unpaired outgoing strands. We have already established that all unpaired strands, across all sub-matchings of M, must belong to the same k-star. With k total unpaired strands for \frac{nk}{d} sub-matchings, it follows that \frac{nk}{d} | k and that m contains precisely x = \frac{d}{n} unpaired strands. This leaves d− \frac{d}{n} endpoints that are not unpaired outgoing strands, further requiring that k | (d − \frac{d}{n}) and hence that \frac{nk}{d} | (n − 1). Whenever \frac{nk}{d} | gcd(k, n − 1), \frac{nk}{d} copies of m ∈ m^{k}(d, \frac{d}{n}) may always be horizontally concatenated to produce a matching M. To do this, simply identify right-bound strands with left-bound strands in the unique non-crossing manner, and then identify all unpaired strands with a single topmost k-star.

In the horizontal concatenation of m ∈ m^{k}(d, \frac{d}{n}) from the proof of Lemma 8, observe that the “topmost” k-star composed of unpaired outgoing strands need not lie at the “top” of M ∈ A^{g}. If m also has paired outgoing strands, left-bound strands from the leftmost submatching will wrap around the topmost k-star on their way to the rightmost sub-matching. We are now ready to characterize Im(q_{nk/d}) and calculate |M̃_{n}^{k}|:

Lemma 9. Fix k ≥ 2 and non-zero g ∈ ℤ_{nk} with gcd(g, nk) = d > 1. Then |A^{g}| =

\binom{d}{d/k} + \binom{d}{(d − \frac{d}{n})/k}, where binomial coefficients involving non-integers are taken to be zero.

Proof. Lemma 8 and the observation that m^{k}(d, x) = ∅ if k ∤ (d − x) allow us to assert that

Im(q_{nk/d}) = \begin{cases}m^{k}(d, 0), & if \frac{nk}{d} ∤ gcd(k, n − 1); \\ m^{k}(d, 0) + m^{k}(d, \frac{d}{n}), & if \frac{nk}{d} | gcd(k, n − 1). \end{cases}  (2)

Since q_{nk/d} is an injection, applying Lemma 7 to Eq. (2) gives

|A^{g}| = \begin{cases}\binom{d}{d/k}, & if \frac{nk}{d} ∤ gcd(k, n − 1); \\ \binom{d}{d/k} + \binom{d}{(d − \frac{d}{n})/k}, & if \frac{nk}{d} | gcd(k, n − 1). \end{cases}  (3)

In Eq. (3) and in all subsequent equations, binomial coefficients are taken to be zero if their bottom entry is not an integer.

As k, n, d are non-zero integers such that \frac{nk}{d} ∈ ℤ, we know that \frac{nk}{d} | k if and only if n | d. This implies that, if \frac{nk}{d} ∤ k, then (d − \frac{d}{n}) ∉ ℤ and hence that (d − \frac{d}{n})/k ∉ ℤ. Similarly, if \frac{nk}{d} ∤ (n − 1) we may conclude that nk ∤ (dn − d) and hence that k ∤ (d − \frac{d}{n}). Combining these observations, we may conclude that k ∤ (d − \frac{d}{n}) whenever \frac{nk}{d} ∤ gcd(k, n − 1). This allows us to add the missing second binomial coefficient (necessarily zero) to the first case of Eq. (3) and drop all conditional statements.

Theorem 10. Fix k ≥ 2, n ≥ 1, and let ρ be the row-constant density with ρ_{1,j} = k − 1 and ρ_{2,j} = 1 for all j. Then

|𝕊̃(n^{2}, ρ)| = |M̃_{n}^{k}| = \frac{1}{nk} ∑_{d|nk} φ(nk/d) (\binom{d}{d/k} + \binom{d}{(d − \frac{d}{n})/k}) − C_{n}^{k}.

Here φ is Euler’s phi function and binomial coefficients involving non-integers are zero.

Proof. By Burnside’s lemma applied to A = M_{n}^{k} and G = ℤ_{nk} we have

|M̃_{n}^{k}| = \frac{1}{nk} |A^{0}| + \frac{1}{nk} ∑_{g≠0} |A^{g}| = \frac{1}{nk} C_{n}^{k} + \frac{1}{nk} ∑_{g≠0} |A^{g}|.  (4)

We have already argued that |A^{g}| = 0 if gcd(g, nk) = 1. For any d | nk with d > 1, basic number theory states that there are precisely φ(\frac{nk}{d}) elements g ∈ ℤ_{nk} such that gcd(g, nk) = d. Ranging over all non-zero divisors d of nk allows us to rewrite Eq. (4) as

|M̃_{n}^{k}| = \frac{1}{nk} C_{n}^{k} + \frac{1}{nk} ∑_{d|nk,d≠nk} φ(nk/d)|A^{d}|.  (5)

Applying Lemma 9, note that the d = nk case gives φ(nk/d) (\binom{d}{d/k} + \binom{d}{(d− \frac{d}{n})/k}) =

φ(1) (\binom{nk}{n} + \binom{nk}{n−1}) = (1)\binom{nk+1}{n} = (nk + 1)C_{n}^{k}. Forcing the d = nk case into our sum gives

|M̃_{n}^{k}| = \frac{1}{nk} C_{n}^{k} + \frac{1}{nk} ∑_{d|nk} φ(nk/d) (\binom{d}{d/k} + \binom{d}{(d − \frac{d}{n})/k}) − \frac{nk + 1}{nk}C_{n}^{k}.  (6)

One specific advantage of Theorem 10 over Theorem 6 is that the summation of Theorem 10 may be significantly simplified when k is prime. Notice that Corollary 11 recovers Goldbach and Tijdeman’s original result of Eq. (1) when k = 2.

Corollary 11. Fix k ≥ 2 and let p be prime. Then

|M̃_{n}^{p}| = (\frac{1}{np} ∑_{d|n} φ(n/d)\binom{pd}{d}) − \frac{p − 1}{p}C_{n}^{p} + \frac{p − 1}{p}C_{(n−1)/p}^{p}.

Here φ is Euler’s phi function and p-Catalan numbers with non-integer subscripts are zero.

Proof. Theorem 10 immediately gives

|M̃_{n}^{p}| = \frac{1}{np} ∑_{d|np,d≠np} φ(np/d) (\binom{d}{d/p} + \binom{d}{(d − \frac{d}{n})/p}) + \frac{1}{np}C_{n}^{p}.  (7)

Whenever p ∤ d, \binom{d}{d/p} = 0. In this case we also have (d − \frac{d}{n})/p ∈ ℤ only if n | d, which requires d = n since p is prime. It follows that \binom{d}{(d− \frac{d}{n})/p} ≠ 0 only if \binom{d}{(d− \frac{d}{n})/p} = \binom{n}{(n−1)/p} and p | (d − 1). Alternatively, when p | d we may assert that d = pm for some m with m | n. For p | d, also note that \binom{d}{(d− \frac{d}{n})/p} = \binom{pm}{(m− \frac{m}{n}} ≠ 0 only when n | m and hence when m = n, a case that is excluded from our summation. Applying these observations to Eq. (7) gives

|M̃_{n}^{p}| = (\frac{1}{np} ∑_{m|n,m≠n} φ(n/m)\binom{pm}{m}) + \frac{1}{np}φ(p)\binom{n}{(n − 1)/p} + \frac{1}{np}C_{n}^{p}.  (8)

Noting that \frac{1}{np}φ(p)\binom{n}{(n−1)/p} = \frac{p−1}{np} \binom{n}{(n−1)/p} = \frac{n(p−1)}{np}C_{(n−1)/p}^{p}, and forcing the n = m case into the summation as φ(1)\binom{pn}{n} = ((p−1)n+1)C_{n}^{p}, we have the (easily simplified) expression

|M̃_{n}^{p}| = (\frac{1}{np} ∑_{m|n} φ(n/m)\binom{pm}{m}) − \frac{(p − 1)n + 1}{np}C_{n}^{p} + \frac{n(p − 1)}{np}C_{(n−1)/p}^{p} + \frac{1}{np}C_{n}^{p}. (9)

4 Acknowledgments

The authors would like to thank the Department of Mathematics & Statistics at Valparaiso University, whose MATH 492 Undergraduate Research in Mathematics course provided the setting under which the research leading to Section 2 of this paper took place.

A On rational non-crossing matchings

As noted in Subsection 2.3, Proposition 1 provides a new combinatorial interpretation for the rational Catalan number C(a, b) as the number non-crossing matchings of type b⃗_{(a,b)} = (⌈\frac{b}{a}⌉−⌈0⌉+1, …, ⌈\frac{ab}{a}⌉−⌈\frac{(a−1)b}{a}⌉+1). Already appearing in the work of Armstrong, Rhoades, and Williams [1] is a distinct combinatorial interpretation of C(a, b) via a class of non-crossing matchings referred to as homogeneous (a, b)-noncrossing partitions. We use this appendix to thoroughly emphasize the differences between these two interpretations.

For relatively prime positive integers a and b, an (a, b)-Dyck path is an integer lattice path from (0, 0) to (b, a) that stays weakly below the line y = \frac{a}{b}x. It was originally shown by Bizley [2] that the number of such (a, b)-Dyck paths is enumerated by C(a, b). Beginning with an (a, b)-Dyck path, Armstrong, Rhoades, and Williams use a “laser construction” to divide the path’s non-terminal lattice points into blocks that partition a+b−1. Lines of slope \frac{a}{b} are drawn southwest from the top of each north step, and all lattice points within each resulting region (with the exception of the point at the top of each laser) are associated with one block.^{2} Note that, even for fixed (a, b), the blocks in their resulting partitions needn’t be consistently sized. For example, homogeneous (5, 8)-noncrossing partitions include elements with block structure {4, 2, 2, 2, 2} and {3, 3, 2, 2, 2} (see Figure 7 of [1]).

Alternatively, our matchings of type b⃗_{(a,b)} represent partitions of a + b and feature blocks whose sizes and ordering are fixed by one’s choice of (a, b). For example, all of our noncrossing matchings of weight b⃗_{(5,8)} feature a block structure of {3, 3, 2, 3, 2}, with those blocks appearing in the stated order when sequenced from left-to-right via their rightmost elements.

Although we omit a formal proof here, one could construct our non-crossing matchings of weight b⃗_{(a,b)} by passing from the associated set-valued tableau to the corresponding lattice path and then applying a modified version of the laser construction. This modified laser construction uses the same lasers, but then identifies the origin point of each laser with the block that lies under that laser. This convention is consistent with the fact that our partitions involve the final point of the (a, b)-Dyck path while the partitions of Armstrong, Rhoades, and Williams do not. See Figure 10 for a comparison of these two approaches.

1 2 3 4 6 7 9 10 5 8 11 12 13 ⇔ ; 1 2 3 4 5 6 7 8 9 10 11 12 13  \begin{matrix}↗ \\ ↘ \end{matrix} 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12

Figure 10: A standard set-valued Young tableaux of density b⃗_{(5,8)}, the corresponding (5, 8)- Dyck path (with lasers in red), and a comparison of the matchings that result from our methodology (TOP) and the methods of Armstrong, Rhoades, and Williams (BOTTOM).

For the context of this paper, our technique is preferable because there does not appear to be a straightforward way to directly associate a homogeneous (a, b)-noncrossing partition with a set-valued tableau (at least not without passing through a partition’s associated (a, b)- Dyck path). This fact makes it difficult to consistently define a notion of jeu de taquin on set-valued tableaux in a way that corresponds to rotation on (a, b)-noncrossing partitions.

2Armstrong, Rhoades, and Williams [1] work with the equivalent set of paths that lie above y = \frac{a}{b}x. This means that their original presentation involves sending lasers northeast from the bottom of each north step.

References

[1] D. Armstrong, B. Rhoades, and N. Williams, Rational associahedra and noncrossing partitions, Electron. J. Combin. 20 (3) (2013), #P54.

[2] M. T. L. Bizley, Derivation of a new formula for the number of minimal lattice paths from (0, 0) to (km, kn) having just t contacts with the line my = nx and having no points above this line; and a proof of Grossman’s formula for the number of paths which may touch but do not rise above this line, J. for the Institute of Actuaries 80 (1954), 55–62.

[3] M. Bodnar and B. Rhoades, Cyclic sieving and rational Catalan theory, Electron. J. Combin. 23 (2) (2016), Paper #P2.4.

[4] M. Bóna, M. Bousquet, G. Labelle, and P. Leroux, Enumeration of m-ary cacti, Adv. in Appl. Math. 24 (2000), 22–56.

[5] A. S. Buch, A Littlewood-Richardson rule for the K-theory of Grassmannians, Acta Math. 189 (2002), 37–78.

[6] P. Drube, Set-valued tableaux & generalized Catalan numbers, Australas. J. Combin. 72 (2018), to appear.

[7] W. Fulton, Young Tableaux, with Application to Representation Theory and Geometry, Cambridge University Press, 1996.

[8] R. W. Goldbach and R. Tijdeman, Pairings of 2n points on a circle, Utilitas Math. 38 (1990), 277–284.

[9] S. Heubach, N. Y. Li, and T. Mansour, Staircase tilings and k-Catalan structures, Discrete Math. 308 (2008), 5954–5964.

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

[11] O. Pechenik, Promotion of increasing tableaux: frames and homomesies, Electron. J. Combin. 24 (3) (2017), #P3.50.

[12] T. K. Petersen, P. Pylyavskyy, and B. Rhoades, Promotion and cyclic sieving via webs, J. Algebraic Combin., 30 (2009), 19–41.

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

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

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

[16] M. Shimozono, A cyclage poset structure for Littlewood-Richardson tableaux, European J. Combin., 22 (2001), 365–393.

[17] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[18] R. P. Stanley, Catalan Numbers, Cambridge University Press, 2015.

[19] J. R. Stembridge, Canonical bases and self-evacuating tableaux, Duke Math. J., 82 (1996), 585–606.

2010 Mathematics Subject Classification: Primary 05A19; Secondary 05C30. Keywords: Young tableau, set-valued Young tableau, non-crossing matching, Catalan number, k-Catalan number, cyclic sieving.

(Concerned with sequences \underline{A002995}, \underline{A054362}, \underline{A054365}, \underline{A054368}, and \underline{A054423}.)

Received October 23 2017; revised versions received May 23 2018; May 24 2018. Published in Journal of Integer Sequences, May 25 2018.

Return to Journal of Integer Sequences home page.