Séminaire Lotharingien de Combinatoire 81 (2020), Article B81h

INTERLACED RECTANGULAR PARKING FUNCTIONS

JEAN-CHRISTOPHE AVAL AND FRANÇOIS BERGERON

Abstract. The aim of this work is to extend the Grossman–Bizley [Scripta Math. 16 (1950), 207–212; J. Inst. Actuar. 80 (1954), 55–62] paradigm that allows the enumeration of Dyck paths in an m × n-rectangle to a general 𝕊_{m} × 𝕊_{n}-module context. We obtain an explicit formula for the the “bi-Frobenius” characteristic of what we call interlaced rectangular parking functions in an m × n-rectangle. These are obtained by labeling the n vertical steps of an m × n-Dyck path by the numbers from 1 to n, together with an independent labeling of its horizontal steps by integers from 1 to m. Our formula specializes to give the Frobenius characteristic of the 𝕊_{n}-module of m × nparking functions in the general situation. Hence, it subsumes the result of Armstrong, Loehr and Warrington of [Ann. Combin. 20 (2016), 21–58], which furnishes such a formula for the special case where m and n are coprime integers.

Contents

Introduction

1. Rectangular Dyck paths  2
2. (m, n)Parking functions  5
3. Frobenius characteristic of the parking function representations  6
4. Bi-Frobenius characteristic  11
5. Further considerations  13
References  14

Introduction

The purpose of this paper is to extend the Grossman–Bizley enumeration formula (see [9, 14]) for the number of Dyck-like paths in an m × n-rectangle to the context of parking functions. These are the south-east lattice paths that start from the north-west corner of the rectangle, end at its south-east corner, and stay below the line between these corners. To each such path we associate a family of parking functions, seen as labelings of the vertical steps of the path. We therefore consider enumeration problems for the global set of such functions, which is called the set of (m, n)-parking functions. More precisely, we obtain explicit formulas for the character (Pólya-enumeration) of the

This work was supported by NSERC-Canada.

𝕊_{n}-module of (m, n)-parking function in the general context. Such formulas have already been established (see [1]) in the special “coprime” case, i.e., when m and n are coprime.

We then extend our approach to get formulas for bi-labeled paths. This means that we independently label south-steps by the numbers 1 to n, and east-steps by the numbers from 1 to m. We give an explicit formula (see 4.3) for the character of the resulting 𝕊_{n} × 𝕊_{m}-module, thus characterizing its decomposition into irreducibles for the joint (commuting) actions of 𝕊_{n} and 𝕊_{m}.

1. Rectangular Dyck paths

An (m, n)-Dyck path is a south-east lattice path, going from (0, n) to (m, 0), which stays below the (m, n)-diagonal, which is the line segment joining (0, n) to (m, 0). See Figure 1 for an example.

[figure: (0,5); (10,0); 7; 6; 3; 0; 0]

Figure 1. The (10, 5)-Dyck path encoded as 76300

We encode such paths as decreasing integer sequences

α = a_{1}a_{2} ⋯ a_{n}, with 0 ≤ a_{k} ≤ (n − k) m/n.

with each a_{k} giving the distance between the y-axis of the (unique) south-step that starts at level k. In other terms, α is an integer partition, with added 0-parts to make it of length n, lying inside the (m, n)-staircase

δ_{m,n} := d_{1}d_{2} ⋯ d_{n}, with d_{k} := ⌊(n − k) m/n⌋.

Hence it makes sense to say that the conjugate path of an (m, n)-path α, denoted by α′, is the (n, m)-path that corresponds to the conjugate partition. As an example, δ_{6,4} = 4310. It is easy to check that δ_{kn,n} = δ_{kn+1,n}. We denote by 𝒟_{m,n}, the set of (m, n)-Dyck paths, and by C_{m,n} its cardinality. It follows from the observation that δ_{kn,n} = δ_{kn+1,n} that we have the set equality

𝒟_{kn,n} = 𝒟_{kn+1,n}.  (1.1)

Examples of values of C_{m,n} = |𝒟_{m,n}| are given in the following table (observe the obvious symmetry in m and n).

\begin{matrix}m \ n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5 \\ 3 & 1 & 2 & 5 & 5 & 7 & 12 & 12 & 15 & 22 \\ 4 & 1 & 3 & 5 & 14 & 14 & 23 & 30 & 55 & 55 \\ 5 & 1 & 3 & 7 & 14 & 42 & 42 & 66 & 99 & 143 \\ 6 & 1 & 4 & 12 & 23 & 42 & 132 & 132 & 227 & 377 \\ 7 & 1 & 4 & 12 & 30 & 66 & 132 & 429 & 429 & 715 \end{matrix}

Observe that it is only when k takes the form k = n − j b, with d = gcd(m, n) and (m, n) = (ad, bd), that we may have (n − k) m/n lying in ℕ. Thus (m, n)-paths α may only return to the diagonal at such positions k. The set of such return positions clearly forms a subset of {1, …, d − 1}, which is encoded in the usual manner^{1} as a composition of d.

If m and n are coprime, the enumeration of (m, n)-Dyck path is given by the long known formula^{2}

C_{m,n} = \frac{1}{m + n}\binom{m + n}{n}.

Observation (1.1), and a simple calculation, implies that the classical Catalan numbers (or more generally Fuss–Catalan numbers) can be obtained from this.

If m and n have a greatest common divisor d other than 1, the relevant formula is more complicated and seems to have escaped the attention of many until recently. In fact, it appears that it was first stated in 1950 by Grossman [14], and then proved by Bizley [9] in 1954. As we will see more clearly later, it is useful to recast this formula in terms of ring homomorphisms applied to symmetric functions. More specifically, for each fixed coprime pair (a, b), consider the ring homomorphism

θ_{a,b} : Λ ⟶ ℤ

defined by

θ_{a,b}(p_{k}(x)) := \frac{1}{a + b}\binom{ak + bk}{ak},

where x = x_{1}, x_{2}, … is an infinite alphabet, and p_{k}(x) stands for the classical power sum symmetric function of degree k in x. Then, for (m, n) = (ad, bd) with d = gcd(m, n), Grossman–Bizley formula may be very simply written as

1Recall that, to a composition γ = (c_{1}, …, c_{k}), this correspondence associates the set of partial sums S(γ) = {s_{1}, s_{2}, …, s_{k−1}}, where s_{i} = c_{1} + c_{2} + ⋯ + c_{i}, with 1 ≤ i < k.

2which may be obtained by a classical cycle argument maybe due to Dvoretzky and Motzkin (see [12]), or even earlier to Łukasiewicz.

C_{ad,bd} = θ_{a,b}(h_{d}(x)),  (1.2)

where h_{d}(x) stands^{3} for the usual complete homogeneous symmetric function of degree d. Recall that, in generating function format, the link between power sum and complete homogeneous symmetric functions may be expressed as

∑_{d=0}^{∞} h_{d}(x) w^{d} = exp(∑_{k≥1} p_{k}(x) \frac{w^{k}}{k} ).  (1.3)

Hence, in generating function terms, Formula (1.2) may be written as

∑_{d=0}^{∞} C_{ad,bd} w^{d} = exp(∑_{k≥1} \frac{1}{a + b}\binom{ak + bk}{ak} \frac{w^{k}}{k} ).  (1.4)

This will be derived from a more general formula in the sequel (see Proposition 3). Bizley also showed (and we will see in the sequel that this generalizes as well) that the number C′_{ad,bd} of primitive (ad, bd)-Dyck paths is given by

C′_{ad,bd} = θ_{a,b}((−1)^{d−1}e_{d}(x)),  (1.5)

where e_{d}(x) is the elementary symmetric functions of degree d. Recall that primitive paths are those that remain strictly below the diagonal. From this, it easily follows that one can enumerate the set of (m, n)-Dyck paths with returns to the diagonal encoded by a composition γ = (c_{1}, …, c_{k}) of d. These are the (m, n)-Dyck paths that go through the points (a s_{i}, n − b s_{i}), with the notation of Footnote 1. The relevant enumeration formula is then

|𝒟_{γ}^{a/b}| = θ_{a,b}((−1)^{d−k}e_{c_{1}}(x) ⋯ e_{c_{k}}(x)),  (1.6)

where we write 𝒟_{γ}^{a/b} for the set of (m, n)-Dyck paths having returns to the diagonal exactly at the points specified by γ. Clearly, the set 𝒟_{m,n} of all (m, n)-Dyck paths decomposes as the disjoint union^{4}

𝒟_{m,n} = ∑_{γ⊧d} 𝒟_{γ}^{a/b},

where γ ⊧ d means that γ is a composition of d. The set 𝒟′_{m,n} of primitive (ad, bd)-Dyck paths simply corresponds to the case of the one part composition γ = (d), i.e.,

𝒟′_{m,n} = 𝒟_{(d)}^{a/b}.

3We are using Macdonald’s [21] notations here.

4We use summation to denote disjoint union.

2. (m, n)Parking functions

To each (m, n)-Dyck path α = a_{1}a_{2} ⋯ a_{n}, we associate the set 𝒫_{α} of α-parking functions:

𝒫_{α} := {a_{σ(1)}a_{σ(2)} ⋯ a_{σ(n)} | σ ∈ 𝕊_{n}}.

For π ∈ 𝒫_{α}, we also say that α is the shape of π. Observe that α-parking functions may be identified with standard Young tableaux^{5} of skew shape (α + 1^{n})/α, where α + 1^{n} is the partition having parts a_{k} + 1. Indeed, if k sits in row j of (α + 1^{n})/α, then one sets π := b_{1}b_{2} … b_{n}, with b_{k} := a_{j}.

By definition, the symmetric group acts transitively on 𝒫_{α}. Indeed, for π = b_{1}b_{2} ⋯ b_{n} and σ ∈ 𝕊_{n}, this action is defined by

σ · π := b_{σ^{−1}(1)}b_{σ^{−1}(2)} ⋯ b_{σ^{−1}(n)}.

The set of (m, n)-parking functions, denoted by 𝒫_{m,n}, is the set of α-parking functions with α varying in the set of (m, n)-Dyck paths,

𝒫_{m,n} := ∑_{α∈𝒟_{m,n}} 𝒫_{α}.

It clearly affords a permutation action of 𝕊_{n}, whose orbits are the 𝒫_{α}’s. Obviously, the stabilizer of an (m, n)-Dyck path α (considered as a special (m, n)-parking-function) is the Young subgroup

𝕊_{ρ} := 𝕊_{r_{0}} × 𝕊_{r_{1}} × ⋯ × 𝕊_{r_{m}},

where ρ = ρ(α) := (r_{0}, r_{1}, …, r_{m}), with r_{i} equal to the number of occurrences of i in α. We may as well remove zero parts from ρ(α), since these parts play no role. The result is said to be the riser composition of α. It follows that the number of α-parking functions is given by the multinomial coefficient

|𝒫_{α}| = \binom{n}{ρ(α)} := \frac{n!}{r_{0}! r_{1}! ⋯ r_{k}!},  (2.1)

and thus

|𝒫_{m,n}| = ∑_{α∈𝒟_{m,n}} \binom{n}{ρ(α)}.  (2.2)

If m and n are coprime, (m, n)-parking functions may be seen to give canonical coset representatives of the subgroup H := u ℤ, with u = (1, 1, …, 1), inside the abelian group ℤ_{m}^{n}. Here, elements of ℤ_{m}^{n} correspond to general sequences of length n, with entries between 0 and m − 1, whereas (m, n)-parking functions correspond to the special case for which such a sequence becomes an (m, n)-Dyck path when its entries are sorted (from smallest to largest). Indeed, it may be shown that each coset contains a unique (m, n)-parking function. These considerations have the following consequence.

5naturally using french notation.

Lemma 1 (Armstrong, Loehr, Warrington [1]). For coprime m and n, the number of (m, n)-parking functions is

|𝒫_{m,n}| = m^{n−1}.  (2.3)

If m and n are not coprime, cosets of H will contain up to d (> 0) elements that are (m, n)-parking functions. Exploiting this fact, one can get an analog of Formula (1.2). We will not do this, since this actually follows from a finer result discussed in Section 3. Table 1 gives small explicit values in the general case. From now on, we set (m, n) = (ad, bd) with a and b coprime (thus d = gcd(m, n)).

\begin{matrix}n \ m & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 3 & 3 & 5 & 5 & 7 & 7 & 9 \\ 3 & 1 & 4 & 16 & 16 & 25 & 49 & 49 & 64 \\ 4 & 1 & 11 & 27 & 125 & 125 & 243 & 343 & 729 \\ 5 & 1 & 16 & 81 & 256 & 1296 & 1296 & 2401 & 4096 \\ 6 & 1 & 42 & 378 & 1184 & 3125 & 16807 & 16807 & 35328 \\ 7 & 1 & 64 & 729 & 4096 & 15625 & 46656 & 262144 & 262144 \end{matrix}

Table 1. Number of (m, n)-parking functions

3. Frobenius characteristic of the parking function representations

For a fixed integer composition ρ of n, consider the transitive permutation action of 𝕊_{n} on the set of ρ-set partitions of {1, 2, …, n}. These are the set partitions that have block sizes specified by ρ. One may consider this as a representation of 𝕊_{n}, having dimension equal to the multinomial coefficient

\binom{n}{ρ} = \frac{n!}{ρ_{1}! ρ_{2}! ⋯ ρ_{k}!}.

It is classical that the Frobenius transform^{6} of the character of the resulting 𝕊_{n}-module is h_{ρ}(x) := h_{ρ_{1}}(x)h_{ρ_{2}}(x) ⋯ h_{ρ_{k}}(x). Recall that this means that the coefficients of the Schur function expansion of h_{ρ}(x) correspond to multiplicities of irreducibles.

For a given (m, n)-Dyck path α of height n, the 𝕊_{n}-action on α-parking functions is isomorphic to the action of 𝕊_{n} on ρ-set partitions, with ρ = ρ(α) equal to the risercomposition α. Thus h_{ρ(α)}(x) is the associated Frobenius characteristic.

6We simply say: Frobenius characteristic.

It follows from this that the Frobenius characteristic of the 𝕊_{n}-action on (m, n)-parking functions, which we denote by 𝒫_{m,n}(x), can be calculated as follows

𝒫_{m,n}(x) = ∑_{α∈𝒟_{m,n}} h_{ρ(α)}(x).  (3.1)

As discussed in [1], and borrowing a presentation format inspired by [24], we have the following formulas.

Proposition 2 (Armstrong, Loehr, Warrington). For coprime positive integers m and n, we have

𝒫_{m,n}(x) = \frac{1}{m} ∑_{λ⊢n} m^{ℓ(λ)} \frac{p_{λ}(x)}{z_{λ}}  (3.2)

= \frac{1}{m} ∑_{λ⊢n} s_{λ}(1^{m}) s_{λ}(x)  (3.3)

= ∑_{λ⊢n} \frac{(m − 1) (m − 2) ⋯ (m − ℓ(λ) + 1)}{d_{1}(λ)! ⋯ d_{k}(λ)!} h_{λ}(x),

where d_{i}(λ) is the number of parts of size i in λ and z_{λ} = ∏_{i≥1} i^{d_{i}(λ)d_{i}(λ)!}.

From (3.3), we may calculate that the respective multiplicities of the trivial and the sign representation in 𝒫_{m,n} are given (as expected) by

\frac{1}{m} h_{n}(1^{m}) = \frac{1}{m + n} \binom{m + n}{n},  and  \frac{1}{m} e_{n}(1^{m}) = \frac{1}{m} \binom{m}{n},

since these occur as coefficients of s_{n}(x) and s_{1^{n}}(x), respectively. More generally, the other multiplicities may be obtained using the classical evaluation (involving hook lengths)

s_{λ}(1^{m}) = ∏_{(i,j)∈λ} \frac{m + i − j}{(λ_{j} − i) + (λ′_{i} − j) + 1}.

It is also worth recalling that the sign-twisted version^{7} of 𝒫_{n,n}(x) is the Frobenius characteristic of the space of “diagonal harmonics” [15].

Formula for the non-coprime case. To get formulas for the non-coprime case, we generalize (1.2) in a natural manner as below. Once again, we assume that (m, n) = (ad, bd) with (a, b) coprime, and consider γ a composition of d. We adapt our notations from Section 1 to parking functions. Consequently, we write 𝒫_{γ}^{a/b} for the set of (ad, bd)- parking function whose underlying path lies in the set 𝒟_{γ}^{a/b}:

𝒫_{γ}^{a/b} := ∑_{α∈𝒟_{γ}^{a/b}} 𝒫_{α}.

7This simply means that we replace p_{k}(x) by (−1)^{k−1}p_{k}(x) in (3.2).

Likewise, 𝒫′_{m,n} is the set of primitive (m, n)-parking functions, i.e., those whose underlying paths only touch the diagonal at both ends. Maintaining our previous conventions, we set

𝒫_{γ}^{a/b}(x) := ∑_{α∈𝒟_{γ}^{a/b}} h_{ρ(α)}(x), and 𝒫′_{m.n}(x) := ∑_{α∈𝒟′_{m,n}} h_{ρ(α)}(x).

In the same spirit as previously, we consider a ring homomorphism Θ_{a,b} : Λ ⟶ Λ that sends degree d homogeneous symmetric functions to degree n = bd homogeneous symmetric functions. Just as before, this homomorphism is characterized by its effect on the algebraic generators p_{k}(x), setting

Θ_{a,b}(p_{k}(x)) := \frac{1}{a} ∑_{λ⊢ak}(ak)^{ℓ(λ)} \frac{p_{λ}(x)}{z_{λ}},

For a degree d symmetric function f_{d}(x), we also write f_{d}^{a/b}(x) for the image of f_{d}(x) under the homomorphism Θ_{a,b}, i.e.,

f_{d}^{a/b}(x) := Θ_{a,b}(f_{d}(x)).  (3.4)

The following proposition extends the approach of Bizley (see [9]) for the enumeration of (m, n)-Dyck paths to the (m, n)-parking function Frobenius characteristic. Its proof makes use of the notion of rank of points along (m, n)-paths, which is simply defined as

rank(x, y) := m y + n x.

Proposition 3. Let (m, n) = (ad, bd), with a and b coprime, and consider γ =(c_{1}, …, c_{k}) a composition of d. Then we have

𝒫_{m,n}(x) = Θ_{a,b}(h_{d}(x)),  (3.5)
𝒫′_{m,n}(x) = Θ_{a,b}((−1)^{d−1}e_{d}(x)),  (3.6)
𝒫_{γ}^{a/b}(x) = Θ_{a,b}((−1)^{d−k}e_{c_{1}}(x) ⋯ e_{c_{k}}(x)).  (3.7)

Proof. The proof is essentially an adaptation of Bizley’s original proof, integrating symmetric functions arguments.

For the purpose of our argument, we consider the set ℬ_{m,n} of all south-east lattice paths going from (0, n) to (m, 0), which end with an east-step (without any condition relative to the diagonal). We think of these as length m + n “words” in the letters y and x, which encode the successive steps, with y standing for a south-step and x for an east-step. Thus, the paths in ℬ_{m,n} bijectively correspond to all possible words containing n copies of y and m copies of x, with final letter equal to x. It clearly follows that the number of such words/paths is

|ℬ_{m,n}| = \binom{m + n − 1}{n}.  (3.8)

We bijectively label the n south-steps of such paths with the integers 1 to n, just as we earlier did for parking functions. This is to say that labels decrease along consecutive south-steps. The resulting set of labeled paths is denoted by ℒ_{m,n}. The symmetric group 𝕊_{n} acts on ℒ_{m,n} by permuting labels, and the Frobenius characteristic of this (permutation) action is

∑_{α∈ℬ_{m,n}} h_{ρ(α)}(x) = ∑_{λ⊢n}(m)^{ℓ(λ)} \frac{p_{λ}(x)}{z_{λ}} = a p_{d}^{a/b}(x).  (3.9)

To see this, observe that the stabilizer of an orbit of ℒ_{m,n} (which corresponds to some fixed underlying path α) is the Young subgroup 𝕊_{r_{1}} × 𝕊_{r_{2}} × ⋯ × 𝕊_{r_{j}}, where ρ(α) = (r_{1}, r_{2}, …, r_{j}), and that the action is the action induced by the trivial action of 𝕊_{r_{1}} × 𝕊_{r_{2}} × ⋯ × 𝕊_{r_{j}}. The second equality in (3.9) is by definition (3.4). The first equality may be derived from the Cauchy identity [11] as follows. Let y = y_{1}, y_{2}, … denote a (second) infinite alphabet. We have

∏_{i=1}^{∞} ∏_{j=1}^{∞} \frac{1}{1 − x_{i}y_{j}} = ∑_{λ} h_{λ}(x)h_{λ}(y) = ∑_{λ} \frac{1}{z_{λ}} p_{λ}(x)p_{λ}(y).  (3.10)

Setting the first m variables y_{j} to t and the other ones to 0 in (3.10), and then taking the coefficient of t^{n}, we obtain

∑_{λ⊢n} h_{λ}(x)\binom{m}{m_{1}, …, m_{n}, m − ℓ(λ)} = ∑_{λ⊢n} \frac{1}{z_{λ}} p_{λ}(x)m^{ℓ(λ)},  (3.11)

with λ = (1^{m_{1}}, 2^{m_{2}}, …). The left-hand side of (3.11) is precisely ∑_{α∈ℬ_{m,n}} h_{ρ(α)}(x).

We next consider highest rank points along a path α in ℬ_{m,n}. Namely, these are the points (i, j) on the path for which rank(i, j) reaches its maximal value. To simplify our discussion, we remove the point (m, 0) from those considered. Clearly, a path α may have more than one highest rank point, but the number of such points is at most d. We denote by ℬ_{m,n}^{t} (respectively 𝒟_{m,n}^{t}) the subset of ℬ_{m,n} (respectively 𝒟_{m,n}) consisting of paths with exactly t highest points.

We then consider cyclic permutations of α = ℓ_{1} ⋯ ℓ_{m+n} (where either ℓ_{i} = x or ℓ_{i} = y) in the following sense. Choosing any occurrence of x in α, say at ℓ_{i}, we cut the path after this x, and build a new word β by switching the two resulting components of α:

α = ℓ_{1} ⋯ ℓ_{i} ℓ_{i+1} ⋯ ℓ_{m+n} ↦ β = ℓ_{i+1} ⋯ ℓ_{m+n} ℓ_{1} ⋯ ℓ_{i}.

Observe that the number of highest rank points is invariant under such cyclic permutations, and that these highest rank points can be brought to the diagonal by some cyclic permutation. Moreover, the riser-composition of α is cyclically preserved. Hence, the Frobenius characteristic is left unchanged, and it equals h_{ρ(α)}(x) for both the action of 𝕊_{n} on labelings with underlying path α or β. Figure 2 illustrates the notion of highest point (two in this case, represented by blue dots) and the procedure of cyclic permutation (the cut ℓ_{i} appears as a black cross).

[figure: (0,5); (10,0); •; •; (0,5); (10,0); •; •]

Figure 2. Cyclic permutation of an element of ℬ_{10,5} with 2 highest points

The key point is the following: the cyclic permutation allows us to build a bijection

𝒟_{m,n}^{t} × [m] ⟶^{∼} ℬ_{m,n}^{t} × [t].  (3.12)

Consider (α, j) ∈ 𝒟_{m,n}^{t} × [m]. By cutting α after its j-th east step, and performing the corresponding cyclic permutation, we get an element γ of ℬ_{m,n}^{t}. We may keep track of the final point of α, which corresponds to one of the t highest points of γ (call it h). The reverse bijection consists in applying the cyclic permutation to γ in position h: we get back α, and we keep track of the final point of γ as the index j.

Now recall from our hypothesis that (m, n) = (ad, bd) with (a, b) coprime. Denote by 𝒫_{ad,bd}^{t}(x) the Frobenius characteristic of the parking functions associated with (ad, bd)- Dyck paths having exactly t contact points with the diagonal. From bijection (3.12), we get that ∑_{t=1}^{d}(da/t) 𝒫_{ad,bd}^{t}(x) is the Frobenius characteristic of ℒ_{ad,bd}. Consequently, because of (3.9) and after simplification, we obtain

∑_{t=1}^{d} \frac{1}{t} 𝒫_{ad,bd}^{t}(x) = \frac{1}{d} p_{d}^{a/b}(x).  (3.13)

Since the case t = 1 of 𝒫_{ad,bd}^{t}(x) corresponds to the Frobenius characteristic of the primitive (ad, bd)-Dyck path, we clearly have

𝒫_{ad,bd}^{t}(x) = ∑_{γ⊧_{t}d} 𝒫′_{ac_{1},bc_{1}}(x) 𝒫′_{ac_{2},bc_{2}}(x) ⋯ 𝒫′_{ac_{t},bc_{t}}(x),  (3.14)

where the sum is over length t compositions γ = (c_{1}, c_{2}, …, c_{t}) of d. In other terms, if we set

𝒫′_{a,b}(x; z) := ∑_{j=1}^{∞} 𝒫′_{aj,bj}(x) z^{j},

then 𝒫_{ak,bk}^{t}(x) is the coefficient of z^{k} in (𝒫′_{a,b}(x; z))^{t}. We may thus argue that Equation (3.13) says that \frac{1}{k} p_{k}^{a/b}(x) is the coefficient of z^{k} in log(1/(1 − 𝒫′_{a,b}(x; z)), so that

𝒫′_{a,b}(x; z) = 1 − exp ( − ∑_{k=1}^{∞} p_{k}^{a/b}(x) z^{k}/k)  (3.15)

= Θ_{a,b} (∑_{d=1}^{∞}(−1)^{d−1}e_{d}(x) z^{d}) ,  (3.16)

which is equivalent to (3.6), which in turn readily implies (3.7). Clearly,

𝒫_{ad,bd}(x) = ∑_{t>0} 𝒫_{ak,bk}^{t}(x),

so that

𝒫_{a,b}(x; z) = \frac{1}{1 − 𝒫′_{a,b}(x; z)} = exp ( ∑_{k=1}^{∞} p_{k}^{a/b}(x) z^{k}/k)  (3.17)

= Θ_{a,b} (∑_{d=0}^{∞} h_{d}(x) z^{d}) ,  (3.18)

which concludes the proof of Proposition 3. □

For example, for any coprime a and b, we get

𝒫_{2a,2b}(x) = \frac{1}{2a}h_{2b}[2a x] + \frac{1}{2} (\frac{1}{a}h_{b}[a x])^{2} ,

𝒫′_{2a,2b}(x) = \frac{1}{2a}h_{2b}[2a x] − \frac{1}{2} (\frac{1}{a}h_{b}[a x])^{2} ,

which give the Frobenius characteristic that correspond to (2a, 2b)-Dyck paths and primitive (2a, 2b)-Dyck paths, respectively. The notation h_{n}[m x] refers to the well-known plethystic substitution (see for example [19]). To get explicit formulas for the number of (m, n)-parking functions, we need simply compute the scalar product ⟨𝒫_{m,n}(x), h_{1}^{n}(x)⟩. Likewise for 𝒫′_{m,n} or 𝒫_{γ}^{a/b}.

4. Bi-Frobenius characteristic

As before, let (m, n) = (ad, bd) with a and b coprime. We can now consider the “riser-step“ bi-Frobenius characteristic of (m, n)-parking function, which may be defined/calculated to be

𝒫_{m,n}(x, y) := ∑_{α∈𝒟_{m,n}} h_{ρ(α)}(x) h_{ρ(α′)}(y),  (4.1)

where, as before, y = y_{1}, y_{2}, … stands for another denumerable alphabet of variables. Hence, α(x) encodes the “riser structure” of α, whereas α′(y) encodes its “step structure” (which are the risers of the conjugate path α′). Clearly this bi-Frobenius characteristic affords the symmetry

𝒫_{m,n}(x, y) = 𝒫_{n,m}(y, x).  (4.2)

Once again, there is a Bizley-like formula for 𝒫_{m,n}(x, y), which subsumes (up to some calculations) all of our previous results. This formula is the subject of the following theorem.

Theorem 4. For coprime positive integers a and b, we have

∑_{d=0}^{∞} 𝒫_{ad,bd}(x, y) z^{d} = exp(∑_{k≥1} p_{k}^{a/b}(x, y)z^{k}/k),  (4.3)

where we set

p_{k}^{a/b}(x, y) := ∑_{j=1}^{k} \frac{k}{j} ∑_{ρ⊧_{j}bk, σ⊧_{j}ak} h_{ρ}(x) h_{σ}(y),  (4.4)

and where, as before, we write ρ ⊧_{j} n to say that ρ is a composition of n having j parts.

Proof. The proof of Theorem 4 uses a refinement of the argument used to prove Proposition 3. We introduce the set 𝒞_{m,n} of lattice paths in ℬ_{m,n} with the additional condition that they start with a south step. By definition, corners of a south-east lattice path are the points that lie between an east-step and a following south-step. We consider (m, n)-Dyck paths α having t highest points and j corners, and modify the argument of Proposition 3 by restricting cuts to points that lie at one of the j corners. In the same way as (3.12), we get a bijection

𝒟_{m,n}^{t,j} × [j] ⟶^{∼} 𝒞_{m,n}^{t,j} × [t],  (4.5)

where the superscripts t, j indicate a restriction to paths with exactly t highest points and j corners.

Set

𝒫_{m,n}^{t,j}(x, y) := ∑_{α∈𝒟_{m,n}^{j,j}} h_{ρ(α)}(x) h_{ρ(α′)}(y).

Bijection (4.5) implies

\frac{1}{t}𝒫_{m,n}^{t,j}(x, y) = \frac{1}{j} ∑_{ρ⊧_{j}n, σ⊧_{j}m} h_{ρ}(x) h_{σ}(y).

Summing both sides over j (writing (m, n) as (ad, bd)), we obtain

∑_{t=1}^{d} \frac{1}{t} 𝒫_{ad,bd}^{t}(x, y) = ∑_{j=1}^{d} \frac{1}{j} ∑_{ρ⊧_{j}bd, σ⊧_{j}ad} h_{ρ}(x) h_{σ}(y) = \frac{1}{d} p_{d}^{a/b}(x, y).  (4.6)

Then (4.3) is deduced from (4.6) just as (3.15) was deduced from (3.13). □

An alternate formula for p_{k}^{a/b}(x, y), which involves much less terms, is easily seen to be

p_{k}^{a/b}(x, y) := k ∑_{j=1}^{k} \frac{1}{j} ∑_{μ⊢_{j}bk, ν⊢_{j}ak} \binom{j}{λ(μ)}\binom{j}{λ(ν)}h_{μ}(x) h_{ν}(y).  (4.7)

The second sum is now over j-part partitions, with λ(μ) denoting the partition of j that indicates the multiplicities of the parts of μ (likewise for ν), and \binom{j}{λ( .)} stands for the corresponding multinomial coefficient. Hence, the above formula is simply obtained by collecting the compositions that have the same parts, up to re-ordering, in (4.4).

Observe that we get back Proposition 3 from Theorem 4 if we take the usual symmetric function scalar product with h_{n}(y) on each side of (4.6). Indeed, we first recall that this scalar product is such that

⟨h_{μ}(y), h_{n}(y)⟩ = 1,

for any partition (or composition) of n. This implies that ⟨−, h_{n}(y)⟩ is a ring homomorphism. Hence, we need only prove that

⟨p_{k}^{a/b}(x, y), h_{n}(y)⟩ = k ∑_{j=1}^{k} \frac{1}{j} ∑_{μ⊢_{j}bk, ν⊢_{j}ak} \binom{j}{λ(μ)}\binom{j}{λ(ν)}h_{ρ}(x)  (4.8)

reduces to

p_{k}^{a/b}(x) = \frac{1}{a} ∑_{λ⊢bk}(ak)^{ℓ(λ)} \frac{p_{λ}(x)}{z_{λ}}.  (4.9)

This is obtained as follows. The right-hand side of (4.8) is equal to

k ∑_{t,j} \frac{1}{j} ∑_{γ∈𝒞_{m,n}^{t,j}} h_{ρ(γ)}(x),

whereas the right-hand side of (4.9) is equal to

\frac{k}{m} ∑_{γ∈ℬ_{m,n}} h_{ρ(γ)}(x).

Because of bijections (3.12) and (4.5), these two expressions are equal (and equal to k ∑_{t} \frac{1}{t} ∑_{α∈𝒟_{m,n}^{t}} h_{ρ(γ)}(x)).

5. Further considerations

Extensions of these considerations, linked to several interesting questions (see [3, 4, 7, 16, 17]), take into account parameters on parking functions such as “area” and “dinv”. To formulate the analogous results, one needs to work with an algebra of operators on symmetric functions isomorphic to the elliptic Hall algebra studied in [10, 13, 23]. In this framework, the homomorphism Θ_{a,b} sends a symmetric function to an operator on symmetric functions. In turn, formulas are obtained by applying the resulting operator to the symmetric function 1.

In this light, it is worth observing that the image under Θ_{a,b} of other symmetric functions gives rise to significant formulas. The interesting feature of these formulas is that their Schur function expansion has positive integer coefficients. It is usual to say that they are “Schur-positive”. This is the case for hook Schur functions^{8} s_{(k|j)}(x), for which we can easily show h-positivity of Θ_{a,b}((−1)^{j}s_{(k|j)}(x)), which implies Schurpositivity. Indeed, one easily verifies that the symmetric function (−1)^{j}s_{(k|j)}(x) expands with positive integer coefficients in the basis (−1)^{|μ|−ℓ(μ)} e_{μ}(x); and we have seen that Θ_{a,b}((−1)^{j−1}e_{j}(x)) expands with positive integer coefficients in the basis h_{ν}(x). Hence, application of the homomorphism Θ_{a,b} to (−1)^{j}s_{(k|j)}(x) gives rise to an h-positive expression. This expression is also Schur-positive, since any h_{ν}(x) is.

Extensive experiments suggest that, for all μ, Θ_{a,b}((−1)^{ι(μ)}s_{μ}(x)) is Schur-positive, where ι(μ) is the number of cells (i, j) of the diagram of μ, such that j > i. Moreover, all of this seems to carry over to the study of the bi-Frobenius characteristic. An intriguing question is to expand the elliptic Hall algebra techniques to cover these bi-Frobenius characteristic. The hope is that this would lead to more explicit formulas for three parameter expressions such as

∑_{α∈𝒟_{m,n}} q^{area(α)}α(x; t)α′(y; r),  (5.1)

were α(x; t) is an LLT-polynomial calculated using the dinv-statistic on (m, n)-parking functions (see [7] for more details on all this):

α(x; t) := ∑_{π𝒫_{α}} t^{dinv(π)} s_{co(π)}(x),

where co(π) is a composition that encodes “descents” of the parking function π. Recall that composition-indexed Schur functions may be defined by a suitable adaptation of the Jacobi–Trudi identity. Up to a sign-twist, Expression (5.1) specializes to the right-hand side of (4.1). It is known that the LLT-polynomial α(x; t) is Schur-positive.

References

[1] D. Armstrong, N. Loehr, and G. Warrington, Rational parking functions and Catalan numbers, Ann. Combin. 20 (2016), 21–58.

[2] D. Armstrong, B. Rhoades, and V. Reiner, Parking spaces, Adv. Math. 269 (2015), 647–706.

[3] C. Athanasiadis, Generalized Catalan numbers, Weyl groups and arrangements of hyperplanes, Bull. London Math. Soc. 36 (2004), 294–302.

[4] J.-C. Aval, F. Bergeron, and A. Garsia, Combinatorics of labelled parallelogram polyominoes, J. Combin. Theory, Ser. A 132 (2015), 32–57.

[5] F. Bergeron, Algebraic Combinatorics and Coinvariant Spaces, CMS Treatise in Mathematics, CMS and A.K. Peters, 2009.

[6] F. Bergeron, Multivariate diagonal coinvariant spaces for complex reflection groups, Adv. Math. 239 (2013), 97–108.

8We use here the Frobenius notation, hence the relevant hook shape has a part of size k + 1, and j parts of size 1.

[7] F. Bergeron, E. Leven, A. Garsia, and G. Xin, Compositional (km, kn)-shuffle conjectures, International Math. Res. Notices, Volume 2016, Issue 14, 4229–4270.

[8] F. Bergeron, A.M. Garsia, M. Haiman, and G. Tesler, Identities and positivity conjectures for some remarkable operators in the theory of symmetric functions, Methods Appl. Anal. 6 (1999), 363–420.

[9] 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 and a proof of Grossman’s formula for the number of paths which may touch but do not rise above this line, J. Inst. Actuar. 80 (1954), 55–62.

[10] I. Burban, and O. Schiffmann, On the Hall algebra of an elliptic curve, I, Duke Math. J. 161 (2012), 1171–1231.

[11] A. L. Cauchy, Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu’elles renferment, J. École Polytechnique 10 (1815), 29–112.

[12] A. Dvoretzky and Th. Motzkin, A problem of arrangements, Duke Math. J. 14 (1947), 305– 313.

[13] E. Gorsky and A. Negut, Refined knot invariants and Hilbert scheme, J. Math. Pures Appl., 104 (2015), 403–435.

[14] H. D. Grossman, Fun with lattice points: paths in a lattice triangle, Scripta Math. 16 (1950), 207–212.

[15] J. Haglund, The q, t-Catalan Numbers and the Space of Diagonal Harmonics, AMS University Lecture Series, Amer. Math. Soc., R.I., 2008. (Get PDF at http://www.math.upenn.edu/∼jhaglund/)

[16] J. Haglund, M. Haiman, N. Loehr, J. Remmel, and A. Ulyanov, A combinatorial formula for the character of the diagonal coinvariants, Duke Math. J. 126 (2005), 195–232.

[17] J. Haglund, J. Morse, and M. Zabrocki, A compositional shuffle conjecture specifying touch points of the Dyck path, Canad. J. Math. 64 (2012), 822–844.

[18] M. Haiman, Vanishing theorems and character formulas for the Hilbert scheme of points in the plane, Invent. Math. 149 (2002), 371–407.

[19] M. Haiman, Combinatorics, symmetric functions, and Hilbert schemes, Current Developments in Math. 1 (2002), 39–111.

[20] T. Koshy, Catalan Numbers with Applications, Oxford University Press, 2009.

[21] I. G. Macdonald, Symmetric Functions and Hall Polynomials, second ed., Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York, 1995.

[22] B. Rhoades, Parking structures: Fuss analogs, J. Algebraic Combin. 40 (2014), 417–473.

[23] O. Schiffmann and E. Vasserot, The elliptic Hall algebra and the K-theory of the Hilbert scheme of A^{2}, Duke Math. J. 162 (2013), 279–366.

[24] R.P. Stanley, Parking functions and noncrossing partitions, The Wilf Festschrift volume, Electron. J. Combin. 4, no. 2 (1997), Art. #R20.

[25] R.P. Stanley, Hyperplane arrangements parking functions and tree inversions, in Mathematical Essays in Honor of Gian-Carlo Rota (B. Sagan and R. Stanley, eds.), Birkhäuser, 1998, pp. 359–375.

[26] N. von Fuß, Solutio quaestionis quot modis polygonum n laterum in polygona m laterum per diagonales resolvi queat, Nova acta academiae scientiarum imperialis petropolitanae IX (1795), 243–251.

LaBRI, CNRS, Université de Bordeaux, 351 cours de la Libération, 33405 Talence, France.

Email address: aval@labri.fr

Département de Mathématiques, UQAM, C.P. 8888, Succ. Centre-Ville, Montréal, H3C 3P8, Canada.

Email address: bergeron.francois@uqam.ca