Some Properties and Combinatorial Implications of Weighted Small Schröder Numbers

Yu Hin (Gary) Au Department of Mathematics and Statistics University of Saskatchewan Saskatoon, SK S7N 5E6 Canada

                   au@math.usask.ca

Abstract

The n^{th} small Schröder number is s(n) = ∑_{k≥0} s(n, k), where s(n, k) denotes the number of plane rooted trees with n leaves and k internal nodes, each having at least two children. In this manuscript, we focus on the weighted small Schröder numbers s_{d}(n) = ∑_{k≥0} s(n, k)d^{k}, where d is an arbitrary fixed real number. We provide recursive and asymptotic formulas for s_{d}(n), as well as some identities and combinatorial interpretations for these numbers. We also establish connections between s_{d}(n) and several families of Dyck paths.

1 Introduction

1.1 Small Schröder numbers

The small Schröder numbers, denoted s(n) for every n ≥ 1, gives the sequence

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & ⋯ \\ s(n) & 1 & 1 & 3 & 11 & 45 & 197 & 903 & 4279 & ⋯ \end{matrix}

(\underline{A001003} in the On-line Encyclopedia of Integer Sequences (OEIS) [13]). This sequence has been studied extensively and has many combinatorial interpretations (see, for instance, Stanley [16, Exercise 6.39]). We list two below:

• Let T_{n} denote the set of Schröder trees with n leaves, which are plane rooted trees where each internal node has at least 2 children. Then s(n) = |T_{n}| for every n ≥ 1. Figure 1 shows the s(4) = 11 Schröder trees with 4 leaves.

Figure 1: The s(4) = 11 Schröder trees with 4 leaves

• Let P_{n} be the set of small Schröder paths from (0, 0) to (2n − 2, 0), which are lattice paths that

(P1) use only up steps U = (1, 1), down steps D = (1, −1), and flat steps F = (2, 0);

(P2) remain on or above the x-axis;

(P3) do not contain an F step on the x-axis.

Then s(n) = |P_{n}| for every n ≥ 1. Figure 2 lists the s(4) = 11 small Schröder paths from (0, 0) to (6, 0). In this paper, we will use the word consisting of letters U, F, D interchangeably with the path it represents.

To see that |T_{n}| = |P_{n}| for every n ≥ 1, we describe the well-known “walk around the tree” procedure that gives a bijection between T_{n} and P_{n}.

Definition 1. Given a Schröder tree T ∈ T_{n}, construct the path Ψ(T) ∈ P_{n} as follows:

1. Suppose T has q nodes. We perform a preorder traversal of T (i.e., we recursively traverse the tree in the order of root, then its subtrees ordered from left to right), and label the nodes a_{1}, a_{2}, …, a_{q} in that order.

Figure 2: The s(4) = 11 small Schröder paths from (0, 0) to (6, 0)

2. Notice that a_{1} must be the root of T. For every i ≥ 2, define the function ψ(a_{i}) = \begin{cases}U, & if a_{i} is the leftmost child of its parent; \\ D, & if a_{i} is the rightmost child of its parent; \\ F, & otherwise. \end{cases}

3. Define

Ψ(T) = ψ(a_{2})ψ(a_{3}) ⋯ ψ(a_{q}).

Figure 3 illustrates the mapping Ψ for a particular tree. It is not hard to check that Ψ : T_{n} → P_{n} is indeed a bijection.

\begin{aligned}a_{1} ; U^{a_{2}} ; U^{a_{3}} ; F^{a_{4}} ; U^{a_{5}} ; D^{a_{6}} ; D^{a_{7}} ; D^{a_{8}} & & ⟶ \\ & T ∈ T_{5} & & Ψ(T) ∈ P_{5} \end{aligned}

Figure 3: Illustrating the tree-to-path mapping Ψ (Definition 1)

For more historical context, properties, and combinatorial interpretations of the small Schröder numbers, the reader may refer to work by Stanley [15, 16], Shapiro and Sulanke [12], and Gessel [7].

1.2 Weighted small Schröder numbers

Before we describe the weighted small Schröder numbers, let us take a closer look at the Schröder trees T_{n}. Given integers n ≥ 1 and 0 ≤ k < n, let T_{n,k} ⊆ T_{n} be the set of Schröder trees with n leaves and exactly k internal nodes. Furthermore, let s(n, k) = |T_{n,k}|. For instance, Figure 1 shows that s(4, 0) = 0, s(4, 1) = 1, and s(4, 2) = s(4, 3) = 5. Then s(n) = ∑_{k=0}^{n−1} s(n, k), and the numbers s(n, k) produce the following triangle (\underline{A086810} in the OEIS).

s(n, k) k = 0 1 2 3 4 5 ⋯
n = 1  1
2  0 1
3  0 1 2
4  0 1 5 5
5  0 1 9 21 14
6  0 1 14 56 84 42
⋮  ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ...

In general,

s(n, k) = \begin{cases}1, & if n = 1 and k = 0; \\ \frac{1}{n−1} \binom{n−1}{k}\binom{n+k−1}{n}, & if n ≥ 2. \end{cases}

(See, for instance, Geffner and Noy [6, Lemma 1] for a proof.) Next, recall the tree-to-path procedure Ψ from Definition 1. Given T ∈ T_{n,k}, there must be exactly k nodes in T that is each the leftmost child of its parent, and so Ψ(T) would have exactly k up steps. Thus, if we define P_{n,k} ⊆ P_{n} to be the set of small Schröder paths in P_{n} with exactly k up steps, then Ψ is in fact a bijection between T_{n,k} and P_{n,k} for every n and k, and it follows that s(n, k) = |P_{n,k}|. Moreover, observe that s(n, n − 1) counts the number of Schröder paths from (0, 0) to (2n − 2, 0) with n − 1 up steps (and hence n − 1 down steps). These paths must then have no flat steps, and therefore are in fact Dyck paths. Hence, s(n, n − 1) gives the n^{th} Catalan number (\underline{A000108} in the OEIS).

We are now ready to define the sequences that are of our main focus in this manuscript. Given a real number d, we define

s_{d}(n) = ∑_{k=0}^{n−1} s(n, k)d^{k}  (1)

for every integer n ≥ 1. Intuitively, one can interpret assigning a weight of d^{k} to each tree in T_{n,k}, and let s_{d}(n) be the total weight of all trees in T_{n}.

Clearly, s_{1}(n) = s(n), so the above is indeed a generalization of the small Schröder numbers. The following table gives the sequence s_{d}(n) for a few integers d ≥ 2:

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & ⋯ \\ s_{2}(n) & 1 & 2 & 10 & 62 & 430 & 3194 & 24850 & 199910 & ⋯ \\ s_{3}(n) & 1 & 3 & 21 & 183 & 1785 & 18651 & 204141 & 2310447 & ⋯ \\ s_{4}(n) & 1 & 4 & 36 & 404 & 5076 & 68324 & 963396 & 14046964 & ⋯ \end{matrix}

(See \underline{A107841}, \underline{A131763}, and \underline{A131765} for the cases d = 2, 3, and 4, respectively.) While we could not find any literature in which these sequences were the main focus of study, they (especially s_{2}(n)) have made appearances in many areas, such as queuing theory [1], embedded Riordan arrays [2], operads from posets [8], and vorticity equations in fluid dynamics [10]. Chen and Pan [3] also came across these sequences when enumerating a certain family of valley-type weighted Dyck paths, and related these quantities to a variant of generalized large Schröder numbers that is somewhat similar to s_{d}(n). We will make this connection more explicit in Section 4. For other generalizations of small Schröder numbers, see work by Sulanke [18], Schröder [11], Huh and Park [9], and others.

1.3 A roadmap of this paper

In Section 2, we will discuss some basic properties of s_{d}(n) by studying its generating function. We will see that the tools for establishing known formulas for s(n) readily extend to proving analogous results for s_{d}(n). After that, we prove a few identities for s_{d}(n) (Section 3), and describe several families of Dyck paths that are counted by s_{d}(n) (Section 4). Our analysis of the weighted Schröder numbers s_{d}(n) leads to several results regarding Schröder paths and Dyck paths, such as:

• For every n ≥ 1, the number of small Schröder paths in P_{n} with an odd number of up steps and that with an even number of up steps differ by exactly one (Proposition 6);

• For every n ≥ 1, s_{kℓ−1}(n) gives the number of Dyck paths from (0, 0) to (2n − 2, 0) with k possible colors for each up step (U_{1}, …, U_{k}), ℓ possible colors for each down step (D_{1}, …, D_{ℓ}), and avoid peaks of type U_{1}D_{1} (Proposition 13).

We conclude in Section 5 by mentioning some possible future research directions.

2 Basic properties and formulas

Let d be a fixed real number, and consider the generating function y = ∑_{n≥1} s_{d}(n)x^{n}. We first establish a functional equation for y.

Proposition 2. The generating function y = ∑_{n≥1} s_{d}(n)x^{n} satisfies the functional equation

(d + 1)y^{2} − (x + 1)y + x = 0.  (2)

Proof. Let T = ⋃_{n≥1} T_{n} be the set of all Schröder trees, and for each tree T ∈ T we let k(T), n(T) be the number of internal nodes and leaves of T, respectively. Notice that given a tree T ∈ T where n(T) ≥ 2, the root of T must be an internal node with ℓ ≥ 2 subtrees T_{1}, …, T_{ℓ}, so each such tree T uniquely corresponds to some ℓ-tuple of Schröder trees, and there is a natural bijection between the sets T \ T_{1} and ⋃_{ℓ≥2} T^{ℓ}. Also, in this case we have ∑_{j=1}^{ℓ} k(T_{j}) + 1 = k(T) and ∑_{j=1}^{ℓ} n(T_{j}) = n(T). Therefore,

y = ∑_{n≥1} s_{d}(n)x^{n}

= ∑_{T ∈T} d^{k(T)}x^{n(T)}

= ∑_{T ∈T_{1}} d^{k(T)}x^{n(T)} + ∑_{T ∈T \T_{1}} d^{k(T)}x^{n(T)}

= x + ∑_{ℓ≥2} ∑_{T_{1},...,T_{ℓ}∈T} d^{1+∑_{j=1}^{ℓ} k(T_{j})}x^{∑_{j=1}^{ℓ} n(T_{j})}

= x + d ∑_{ℓ≥2} y^{ℓ}

= x + \frac{dy^{2}}{1 − y} ,

which easily rearranges to give (2).

When d ≠ −1, solving for y in (2) (and noting [x^{0}]y = 0) yields

y = \frac{1}{2(d + 1)} (1 + x − \sqrt{1 − (4d + 2)x + x^{2}}) .  (3)

We next use (2) and (3) to prove a recurrence relation for s_{d}(n) that would allow for very efficient computation of these numbers. For the case d = 1, Stanley [15] proved the recurrence

ns(n) = 3(2n − 3)s(n − 1) − (n − 3)s(n − 2), n ≥ 3  (4)

using generating functions. Subsequently, a combinatorial proof using weighted binary trees was given by Foata and Zeilberger [5]. Shortly after, Sulanke [17] also showed that the above recurrence applies for the closely-related large Schröder numbers using Schröder paths. Here, we adapt Stanley’s [15] argument to obtain a similar recurrence relation for s_{d}(n) for all d.

Proposition 3. For every real number d, s_{d}(1) = 1, s_{d}(2) = d, and

ns_{d}(n) = (2d + 1)(2n − 3)s_{d}(n − 1) − (n − 3)s_{d}(n − 2)  (5)

for all n ≥ 3.

Proof. First, s_{d}(1) = 1 and s_{d}(2) = d follows readily from the definition of s_{d}(n). For the recurrence, we start with (2) and differentiate both sides with respect to x to obtain

2(d + 1)yy′ − y − (x + 1)y′ + 1 = 0.

Rearranging gives

y′ = \frac{y − 1}{2(d + 1)y − x − 1}.

We also have

2(d + 1)y − x − 1 = −\sqrt{x^{2} − (4d + 2)x + 1}.

This obviously holds when d = −1, and can be derived from (3) for all other values of d. Thus,

y′ = \frac{y − 1}{2(d + 1)y − x − 1} = \frac{y − 1}{−\sqrt{x^{2} − (4d + 2)x + 1}} = \frac{(y − 1)(2(d + 1)y − x − 1)}{x^{2} − (4d + 2)x + 1}

= \frac{2(d + 1)y^{2} − (2d + x + 3)y + x + 1}{x^{2} − (4d + 2)x + 1} = \frac{(x − 2d − 1)y − x + 1}{x^{2} − (4d + 2)x + 1},

where the last equality made use of the fact that (d + 1)y^{2} = (x + 1)y − x from (2). From the above, we obtain the equation

(x^{2} − (4d + 2)x + 1)y′ − (x − 2d − 1)y + x − 1 = 0.  (6)

Since y = ∑_{n≥0} s_{d}(n)x^{n} and y′ = ∑_{n≥0}(n + 1)s_{d}(n + 1)x^{n}, taking the coefficient of x^{n−1} of (6) (for any n ≥ 3) yields

(n − 2)s_{d}(n − 2) − (4d + 2)(n − 1)s_{d}(n − 1) + ns_{d}(n) − s_{d}(n − 2) + (2d + 1)s_{d}(n − 1) = 0,

which can be rearranged to give the desired recurrence (5).

We remark that one can also obtain a combinatorial proof for (5) by extending Foata and Zeilberger’s [5] combinatorial proof of the recurrence for the special case d = 1. Therein, they interpreted the small Schröder number s(n) as counting binary trees with n leaves where each internal node either has label 1 or 2, and nodes with label 2 must have a right subtree that is not a leaf. Now if we assign each such tree T to have weight d^{k_{1}(T)}(d + 1)^{k_{2}(T)} (where k_{1}(T), k_{2}(T) denote the number of internal nodes of T with label 1 and 2, respectively), then one can prove (5) by equating the total weight of the trees on both sides of the Foata– Zeilberger bijection.

Next, we look into the asymptotic behavior of s_{d}(n). The asymptotic formula for s_{1}(n) is well known — see, for instance, Flajolet and Sedgewick [4, p. 474]. Here, we extend that formula to one that applies for all positive d.

Proposition 4. For every real number d > 0, as n → ∞,

s_{d}(n) ∼ (\frac{(\sqrt{d + 1} − \sqrt{d}) · d^{1/4}}{2(d + 1)^{3/4}π^{1/2}} ) · n^{−3/2} · (2d + 1 + 2\sqrt{d^{2} + d})^{n} .

Proof. We follow the template given by Flajolet and Sedgewick [4, Theorem VI.6, p. 404] to prove our claim. First, recall that y = ∑_{n≥1} s_{d}(n)x^{n} satisfies the functional equation y = xϕ(y) where ϕ(y) = \frac{1−y}{1−(d+1)y}. We need to verify the following analytic conditions for ϕ:

H_{1}: ϕ is a nonlinear function that is analytic at 0 with ϕ(0) ≠ 0 and [z^{n}]ϕ(z) ≥ 0 for all n ≥ 0.

H_{2}: Within the open disc of convergence of ϕ at 0, |z| < R, there exists a (then necessarily unique) positive solution s to the characteristic equation ϕ(s) = sϕ′(s).

Notice that, expanding ϕ(z), we obtain

ϕ(z) = \frac{1 − z}{1 − (d + 1)z} = 1 + ∑_{n≥1} ((d + 1)^{n} − (d + 1)^{n−1}) z^{n} = 1 + d ∑_{n≥1}(d + 1)^{n−1}z^{n},

and so H_{1} holds for all d > 0. For H_{2}, the radius of convergence of ϕ(z) (which is a geometric series) is obviously R = \frac{1}{d+1}. Now since ϕ′(z) = \frac{d}{(1−(d+1)z)^{2}} , solving ϕ(s) = sϕ′(s) yields one

solution s = 1 − \sqrt{\frac{d}{d+1}}, which lies in (0, R) given d > 0. Thus, H_{2} holds as well. Hence, it follows that

s_{d}(n) ∼ \sqrt{\frac{ϕ(s)}{2ϕ′′(s)}} · \frac{ρ^{n}}{\sqrt{πn^{3}}} ,  (7)

where ρ = \frac{ϕ(s)}{s}. It is not hard to check that

ϕ(s) = \frac{1}{\sqrt{d + 1}(\sqrt{d + 1} − \sqrt{d})},
ϕ′′(s) = \frac{2(d + 1)}{\sqrt{d} (\sqrt{d + 1} − \sqrt{d})^{3}} ,

ρ = 2d + 1 + 2\sqrt{d^{2} + d}.

Substituting these expressions into (7) and simplifying gives the desired result.

In particular, from Proposition 4 we obtain that the sequence s_{d}(n) has growth rate

lim_{n→∞} \frac{s_{d}(n + 1)}{s_{d}(n)} = ρ = 2d + 1 + 2\sqrt{d^{2} + d} ∈ (4d + 1, 4d + 2)

for all d > 0.

3 Some identities and implications

In this section, we prove several identities related to s_{d}(n) and describe their combinatorial implications. We will first focus on two special sequences s_{−1/2}(n) and s_{−1}(n), then prove an identity that seems to have a natural connection with large Schröder numbers.

3.1 The case d = −1/2

Notice that in the recurrence (5), the coefficient of s_{d}(n − 1) vanishes when d = −\frac{1}{2}. In this case, we obtain the following sequence:

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & ⋯ \\ s_{−1/2}(n) & 1 & −\frac{1}{2} & 0 & \frac{1}{8} & 0 & −\frac{2}{32} & 0 & \frac{5}{128} & 0 & −\frac{14}{512} & 0 & \frac{42}{2048} & ⋯ \end{matrix}

For every n ≥ 1, let c(n) = \frac{1}{n} \binom{2n−2}{n−1} denote the n^{th} Catalan number. It is easy to check that c(1) = 1, and that

c(n) = \frac{2(2n − 3)}{n}c(n − 1)  (8)

for all n ≥ 2. Using this recurrence of c(n) and Proposition 3, we prove the following:

Proposition 5. For every integer m ≥ 1, s_{−1/2}(2m + 1) = 0 and s_{−1/2}(2m) = \frac{(−1)^{m}}{2^{2m−1}} c(m).

Proof. We prove our claim by induction on m. First, in the case of d = −\frac{1}{2}, (5) reduces to

s_{−1/2}(n) = \frac{−(n − 3)}{n}s_{−1/2}(n − 2).  (9)

Thus, s_{−1/2}(3) = 0s_{−1/2}(1) = 0. From there on, since s_{−1/2}(2m+1) is a multiple of s_{−1/2}(2m− 1) for all m ≥ 1, we obtain that s_{−1/2}(2m + 1) = 0 for all m ≥ 1.

Next, we establish the claim for s_{−1/2}(2m). When m = 1,

s_{−1/2}(2) = −\frac{1}{2} = \frac{(−1)^{1}}{2^{2−1}} c(1),

so the base case holds. For the inductive step, notice that

s_{−1/2}(2m) = \frac{−(2m − 3)}{2m}s_{−1/2}(2m − 2)

= \frac{−(2m − 3)}{2m} (\frac{(−1)^{m−1}}{2^{2m−3}} c(m − 1))

= \frac{(−1)^{m}}{2^{2m−1}} (\frac{2(2m − 3)}{m}c(m − 1))

= \frac{(−1)^{m}}{2^{2m−1}} c(m),

where the last equality follows from (8). This finishes our proof.

We will return to the quantity s_{−1/2}(n) subsequently in Section 4.

3.2 The case d = −1

Next, we turn to the case when d = −1. In this case, (2) gives

y = \frac{x}{1 + x} = ∑_{n≥1}(−1)^{n−1}x^{i},

and so s_{−1}(n) = (−1)^{n−1} for every n ≥ 1. Since s_{−1}(n) = ∑_{k≥0} s(n, k)(−1)^{k} by definition, we have shown the following:

Proposition 6. For every integer n ≥ 1,

∑_{k odd} s(n, k) = ∑_{k even} s(n, k) + (−1)^{n}.

Proposition 6 implies that, for every n, the number of trees in T_{n} with an odd number of internal nodes and that with an even number of internal nodes differ by exactly one. Likewise, in terms of small Schröder paths, we now know that the number of paths in P_{n} with an odd number of up steps is exactly one away from that with an even number of up steps. This leads to the following consequence, which might be folklore but we could not find a mention of it in the literature:

Corollary 7. The small Schröder number s(n) is odd for all n ≥ 1.

Corollary 7 further implies that, for all odd, positive integers d and for all n ≥ 1, s_{d}(n) is odd (since then d^{k} is odd for all k ≥ 0, and so s_{d}(n) would be a sum of an odd number of odd quantities). Likewise, we obtain that for all n ≥ 2, the n^{th} large Schröder number (which is twice the n^{th} small Schröder number) is congruent to 2 (mod 4).

While we have already described a very short algebraic proof to Proposition 6, we will also provide a simple combinatorial proof.

↕  ↕  ↕  ↕  ↕

Figure 4: Illustrating our combinatorial proof of Proposition 6. Paths on the first (resp., second) row have an odd (resp., even) number of up steps.

Consider the set of paths P_{n} for a fixed n, and observe that Q = U^{n−1}D^{n−1} (i.e., the path consisting of n − 1 up steps followed by n − 1 down steps) is the only path in P_{n} that contains neither a flat step F nor a valley DU. Then, for every path P ∈ P_{n} \{Q}, we define the path α(P) as follows:

(1) If the first valley in P occurs before the first flat step, we write P = P_{1}DUP_{2} where P_{1} does not contain a flat step, and define α(P) = P_{1}F P_{2}.

(2) Otherwise, the first flat step occurs before the first valley. In this case, we write P as P_{1}F P_{2} where P_{1} does not contain an instance of DU, and define α(P) = P_{1}DUP_{2}.

Figure 4 illustrates the mapping α on paths in P_{4}. It is easy to see that α is an involution on P_{n} \ {Q}. Since the number of up steps in P and in α(P) always differ by exactly one, Proposition 6 follows (again).

3.3 Connection to large Schröder numbers

Here, we prove another identity for s_{d}(n), and briefly discuss a version of weighted large Schröder numbers that is analogous to s_{d}(n). We first have the following:

Proposition 8. For every real number d ≠ −1 and every integer n ≥ 2,

s_{d}(n) = \frac{(−1)^{n−1}d}{d + 1}s_{−d−1}(n).

Proof. Recall the generating function y = ∑_{n≥1} s_{d}(n)x^{n}. We can rewrite (2) as the functional

equation y = x (\frac{1−y}{1−(d+1)y}), apply Lagrange inversion, and obtain that

s_{d}(n) = [x^{n}]y = \frac{1}{n}[y^{n−1}] (\frac{1 − y}{1 − (d + 1)y} )^{n}

= \frac{1}{n}[y^{n−1}] (∑_{i≥0} \binom{n}{i}(−1)^{i}y^{i}) (∑_{j≥0} \binom{n + j − 1}{n − 1}(d + 1)^{j}y^{j})

= \frac{1}{n} (∑_{i≥0}(−1)^{i}\binom{n}{i}\binom{2n − i − 2}{n − 1}(d + 1)^{n−i−1}) .

Since \binom{2n−i−2}{n−1} = 0 when i > n − 1, the sum could simply run from i = 0 to i = n − 1. Moreover, by re-indexing the sum using j = n − i − 1, we have

s_{d}(n) = \frac{1}{n} (∑_{j=0}^{n−1}(−1)^{n−j−1}\binom{n}{n − j − 1}\binom{2n − (n − j − 1) − 2}{n − 1}(d + 1)^{j})

= (−1)^{n−1} (∑_{j=0}^{n−1} \frac{1}{n}\binom{n}{j + 1}\binom{n + j − 1}{n − 1}(−d − 1)^{j}) .

Now notice that

\frac{1}{n}\binom{n}{j + 1}\binom{n + j − 1}{n − 1} = \frac{1}{n − 1} (\binom{n − 1}{j}\binom{n + j − 1}{n} + \binom{n − 1}{j + 1}\binom{n + j}{n})
= s(n, j) + s(n, j + 1).

Hence, we have

s_{d}(n) = (−1)^{n−1} ∑_{j=0}^{n−1}(s(n, j) + s(n, j + 1))(−d − 1)^{j}

= (−1)^{n−1} (∑_{j=0}^{n−1} s(n, j)(−d − 1)^{j} − \frac{1}{d + 1} ∑_{j=0}^{n−1} s(n, j + 1)(−d − 1)^{j+1})

= (−1)^{n−1} \frac{d}{d + 1}s_{−d−1}(n),

finishing the proof of our claim. Note that in the second equality above we used the fact that s(n, 0) = s(n, n) = 0 for all n ≥ 2, as well as the assumption that d ≠ −1.

Notice that Proposition 8 rearranges to (−1)^{n−1}s_{−d−1}(n) = \frac{d+1}{d}s_{d}(n) (for d ≠ 0, −1), and that we encountered the expression s(n, j) + s(n, j + 1) in its proof. We note that these quantities have a natural connection with the large Schröder numbers. For every integer n ≥ 1, we define the set of large Schröder paths \overline{P}_{n} to be the set of lattice paths from (0, 0) to (2n−2, 0) that satisfy properties (P1) and (P2) (but not necessarily (P3)) in the definition of small Schröder paths. Thus, P_{n} is a subset of \overline{P}_{n} for every n. Figure 5 illustrates the large Schröder paths in \overline{P}_{4} that do not belong to P_{4}.

Figure 5: The 11 large Schröder paths in \overline{P}_{4} \ P_{4}

Let \overline{s}(n) = |\overline{P}_{n}|. Then \overline{s}(n) gives the large Schröder numbers (\underline{A006318} in the OEIS):

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & ⋯ \\ \overline{s}(n) & 1 & 2 & 6 & 22 & 90 & 394 & 1806 & 8558 & ⋯ \end{matrix}

It is well known that \overline{s}(n) = 2s(n) for every n ≥ 2. To see this, consider a path P ∈ \overline{P_{n}} \ P_{n}, and write P = P_{1}F P_{2} where P_{1} is chosen maximally so that it does not contain a flat step on the x-axis. Then it is easy to show that the mapping β : \overline{P}_{n} \ P_{n} → P_{n} where β(P) = P_{1}UP_{2}D is a bijection, thus showing that |\overline{P}_{n}| = 2|P_{n}|. Moreover, notice that β(P) has exactly one more up step than P. Thus, if we let \overline{P}_{n,k} denote the set of paths in \overline{P}_{n} with exactly k up steps, then we have

\overline{P}_{n,k} = P_{n,k} ∪ \{P : β(P) ∈ P_{n,k+1}\} .

The sets P_{n,k} and \{P : β(P) ∈ P_{n,k+1}\} are obviously disjoint. Thus, if we let \overline{s}(n, k) = |\overline{P}_{n,k}|, we have

\overline{s}(n, k) = s(n, k) + s(n, k + 1)

for every n ≥ 2 and every k ∈ {0, …, n − 1}. Furthermore, given a real number d, if we define the weighted large Schröder number \overline{s}_{d}(n) = ∑_{k=0}^{n−1} \overline{s}(n, k)d^{k}, then we see that

\overline{s}_{d}(n) = ∑_{k=0}^{n−1} \overline{s}(n, k)d^{k} = ∑_{k=0}^{n−1}(s(n, k) + s(n, k + 1))d^{k} = \frac{d + 1}{d}s_{d}(n).

Thus, Proposition 8 can be written as simply

\overline{s}_{d}(n) = (−1)^{n−1}s_{−d−1}(n)

for all d ≠ 0, −1 and n ≥ 2. We will revisit Proposition 8 from the perspective of Dyck paths in the next section.

4 Describing s_{d}(n) in terms of Dyck paths

We next discuss several families of Dyck paths that are counted by s_{d}(n). Recall that a Dyck path is a small Schröder path with only up and down steps (i.e., no flat steps). Let D_{n} be the set of Dyck paths that starts at (0, 0) and ends at (2n − 2, 0). (Equivalently, D_{n} = P_{n,n−1}.) Also, it will be convenient to have the following notation for our subsequent discussion: Given a path P ∈ P_{n}, let

• U(P), F (P), and D(P) respectively denote the number of up, flat, and down steps in P;

• V (P) denote the number of valleys (i.e., occurrences of DU) in P;

• K(P) denote the number of peaks (i.e., occurrences of UD) in P; • U_{V} (P) (resp., D_{V} (P)) denote the number of up (resp., down) steps in P that is not

contained in a valley;

• U_{K}(P) (resp., D_{K}(P)) denote the number of up (resp., down) steps in P that is not contained in a peak.

Recently, Chen and Pan [3] studied the following notion of weighted Catalan numbers: Given real numbers a and b, define

c_{a,b}^{V}(n) = ∑_{P ∈D_{n}} a^{U_{V} (P)}b^{V (P)}.  (10)

Then c_{1,1}^{V}(n) gives the ordinary Catalan numbers c(n). Interestingly, c_{a,b}^{V}(n) also coincides with s_{d}(n) for certain choices of a and b.

Proposition 9. For every real number d and integer n ≥ 1,

s_{d}(n) = c_{d,d+1}^{V}(n).

Proof. Given a path P ∈ D_{n}, let S ⊆ {1, …, V (P)} be an arbitrary subset of the valleys of P. Define the function f_{S} : D_{n} → P_{n} such that f_{S}(P) is the path obtained from replacing every valley not in S by a flat step F. Observe that by this construction, the resulting path f_{S}(P) is a small Schröder path with U_{V} (P) + |S| up steps.

Now observe that, for every path P ∈ D_{n},

d^{U_{V} (P)}(d + 1)^{V (P)} = ∑_{S⊆{1,...,V (P)}} d^{U_{V} (P)+|S|} = ∑_{S⊆{1,...,V (P)}} d^{U(f_{S}(P))}  (11)

Also, every path Q ∈ P_{n} can be written as f_{S}(P) for a unique choice of P ∈ D_{n} and subset S (namely, let P be the path with all flat steps in Q replaced by valleys, and let S be the set of valleys in P that are valleys in Q). Thus, if we sum over all paths in D_{n} on both sides of (11), we obtain

c_{d,d+1}^{V}(n) = ∑_{P ∈D_{n}} d^{U_{V} (P)}(d + 1)^{V (P)} = ∑_{Q∈P_{n}} d^{U(Q)} = s_{d}(n).

We remark that Proposition 9 also follows from a result of Chen and Pan [3, eq. (1.15)] and our discussion in Section 3.3 showing that \overline{s}_{d}(n) = \frac{d+1}{d}s_{d}(n). Also, notice that when d is a positive integer, we obtain that s_{d}(n) counts the number of ways to construct a Dyck path from (0, 0) to (2n − 2, 0) where each valley can be painted one of d + 1 colors, and each up step that does not belong to a valley can be painted one of d colors. Moreover, it is obvious that

c_{−1,0}^{V}(n) = ∑_{P ∈D_{n}}(−1)^{U_{V} (P)}(0)^{V (P)} = (−1)^{n−1}

for every n ≥ 1, since the only Dyck path in D_{n} with no valleys is the path U^{n−1}D^{n−1}. Thus, in the case of d = −1, Proposition 9 implies Proposition 6.

Next, we show that c_{a,b}^{V}(n) can be related to s_{d}(n) even when b ≠ a + 1.

Corollary 10. For every integer n ≥ 1 and all real numbers a, b where a ≠ b,

c_{a,b}^{V}(n) = (b − a)^{n−1}s_{a/(b−a)}(n).

Proof.

c_{a,b}^{V}(n) = ∑_{P ∈D_{n}} a^{U_{V} (P)}b^{V (P)}

= (b − a)^{n−1} ∑_{P ∈D_{n}} (\frac{a}{b − a})^{U_{V} (P)} (\frac{a}{b − a} + 1)^{V (P)}

= (b − a)^{n−1}c_{a/(b−a),a/(b−a)+1}^{V}(n)

= (b − a)^{n−1}s_{a/(b−a)}(n).

Note that the second equality follows from the fact that U_{V} (P) + V (P) = U(P) = n − 1 for all P ∈ D_{n}.

Corollary 10 readily implies that certain families of small Schröder paths and Dyck paths have the same size. For instance:

Corollary 11. For all integers m, n ≥ 1, both of the following quantities are equal to m^{n−1}s_{1/m}(n):

(i) the number of small Schröder paths in P_{n} where each flat step can be painted one of m colors;

(ii) the number of Dyck paths in D_{n} where each valley can be painted one of m + 1 colors.

Proof. From Corollary 10, we obtain that

m^{n−1}s_{1/m}(n) = c_{1,m+1}^{V}(n),

showing (ii). For (i),

m^{n−1}s_{1/m}(n) = m^{n−1} ∑_{P ∈P_{n}}(1/m)^{U(P)}1^{F (P)} = ∑_{P ∈P_{n}} m^{F (P)},

since U(P) + F (P) = n − 1 for every P ∈ P_{n}. This finishes the proof.

We next study another variant of weighted Catalan numbers that, as we shall see, is equal to c_{a,b}^{V}(n). Given real numbers a and b, define

c_{a,b}^{K}(n) = ∑_{P ∈D_{n}} a^{K(P)}b^{U_{K}(P)}.

Then we have the following:

Proposition 12. For all real numbers a, b and integer n ≥ 1

c_{a,b}^{V}(n) = c_{a,b}^{K}(n).

Proof. Observe that for every Dyck path P ∈ D_{n}, V (P) = K(P) − 1. Also, since U(P) = U_{K}(P) + K(P) = U_{V} (P) + V (P), it follows that U_{V} (P) = U_{K}(P) + 1. Hence,

c_{a,b}^{K}(n) = ∑_{P ∈D_{n}} a^{K(P)}b^{U_{K}(P)}

= ∑_{P ∈D_{n}} a^{V (P)+1}b^{U_{V} (P)−1}

= \frac{a}{b}c_{b,a}^{V}(n)

= \frac{a}{b}(a − b)^{n−1}s_{b/(a−b)}(n).

Note that the last equality follows from Corollary 10. Next, let d = \frac{b}{a−b}, then −d − 1 = \frac{a}{b−a}. Thus, by Proposition 8 (and Corollary 10 again),

\frac{a}{b}(a − b)^{n−1}s_{b/(a−b)}(n) = \frac{a}{b}(a − b)^{n−1} \frac{(−1)^{n−1} · \frac{b}{a−b}}{\frac{a}{a−b}} s_{a/(b−a)}(n)
= (b − a)^{n−1}s_{a/(b−a)}(n)
= c_{a,b}^{V}(n),

as desired.

We remark that Proposition 12 can also be proven combinatorially. Given a Schröder tree T ∈ T_{n}, let f(T) denote the tree obtained from reflecting T along a vertical line. In other words, we reverse the left-to-right order of the subtrees of every internal node of the given tree T. Then Ψ(f(T)) (where Ψ is the tree-to-path mapping described in Definition 1) would also be a small Schröder path in P_{n}. Since both Ψ and f are bijective, it follows that the mapping γ : P_{n} → P_{n} where γ(P) = Ψ(f(Ψ^{−1}(P))) is also bijective, and so γ also give a bijection on D_{n} ⊆ P_{n}. From there, it is not hard to see that for every P ∈ D_{n}, K(P) = U_{V} (γ(P)) and U_{K}(P) = V (γ(P)). Hence, it follows that

c_{a,b}^{K}(n) = ∑_{P ∈D_{n}} a^{K(P)}b^{U_{K}(P)} = ∑_{P ∈D_{n}} a^{U_{V} (γ(P))}b^{V (γ(P))} = c_{a,b}^{V}(n).

We next point out how Propositions 5 and 8 in Section 3 can be alternatively shown using the connections between s_{d}(n), c_{a,b}^{V}(n), and c_{a,b}^{K}(n) established above. First, we revisit Proposition 5 and the sequence s_{−1/2}(n). For every integer n ≥ 2 and k ∈ {0, …, n − 1}, define

c(n, k) = \frac{1}{n − 1}\binom{n − 1}{k − 1}\binom{n − 1}{k},

and let c(1, 0) = 1. These are known as the Narayana numbers (\underline{A090181} in the OEIS), and c(n, k) counts the number of Dyck paths in D_{n} with exactly k peaks.

c(n, k) k = 0 1 2 3 4 5 ⋯
n = 1  1
2  0 1
3  0 1 1
4  0 1 3 1
5  0 1 6 6 1
6  0 1 10 20 10 1
⋮  ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ...

If we define the generating function

C_{d}(x) = ∑_{n≥1} ∑_{k≥0} c(n, k)d^{k}x^{n},

then it is not hard to check that C_{d}(x) satisfies the functional equation

C_{d}(x)^{2} + (dx − x − 1)C_{d}(x) + x = 0.

(See, for instance, Stanley [16, Exercise 6.36b] for the details of the derivation.) Solving the above gives

C_{d}(x) = \frac{1 + x − dx − \sqrt{(dx − x − 1)^{2} − 4x}}{2}.

When d = −1, 1, this specializes to

C_{−1}(x) = \frac{1 + 2x − \sqrt{1 + 4x^{2}}}{2} , C_{1}(x) = \frac{1 − \sqrt{1 − 4x}}{2}.

Obviously, C_{1}(x) is the generating function for the ordinary Catalan numbers, and so [x^{n}]C_{1}(x) = c(n) for every n ≥ 1. Also notice that C_{1}(−x^{2}) = C_{−1}(x) − x. Putting things together, we see that, for every n ≥ 2,

2^{n−1}s_{−1/2}(n) = c_{−1,1}^{K}(n) = ∑_{P ∈D_{n}}(−1)^{K(P)} = ∑_{k=0}^{n−1} c(n, k)(−1)^{k}

= [x^{n}]C_{−1}(x) = [x^{n}]C_{1}(−x^{2})

= \begin{cases}0, & if n is odd; \\ c(n/2), & if n ≡ 0 (mod 4); \\ −c(n/2), & if n ≡ 2 (mod 4), \end{cases}

which aligns with Proposition 5. Moreover, the fact that 2^{n−1}s_{−1/2}(n) = c_{−1,1}^{K}(n) also implies that

2^{n−1}s_{−1/2}(n) = ∑_{k even} c(n, k) − ∑_{k odd} c(n, k)

for all n ≥ 1. Thus, we see that given a fixed length, the number of Dyck paths with an odd number of peaks and that with an even number of peaks are either identical, or differ by a Catalan number. This produces the following two sequences:

n  1 2 3 4 5 6 7 8 9 10 ⋯
|{P ∈ D_{n} : K(P) is even}| 1 0 1 3 7 20 66 217 715 2424 ⋯
|{P ∈ D_{n} : K(P) is odd}| 0 1 1 2 7 22 66 212 715 2438 ⋯

These two sequences, with the terms for n = 1 removed, give \underline{A071688} and \underline{A071684} in the OEIS, respectively.

Next, we re-consider Proposition 8. Notice that for every real number m ≠ 1,

c_{m,1}^{K}(n) = ∑_{P ∈D_{n}} m^{K(P)} = m ∑_{P ∈D_{n}} m^{V (P)} = mc_{1,m}^{V}(n).

Thus, applying Corollary 10 and substituting d = \frac{1}{m−1}, we obtain

mc_{1,m}^{V}(n) = m(m − 1)^{n−1}s_{1/(m−1)}(n) = (\frac{d + 1}{d}) d^{−(n−1)}s_{d}(n)

Likewise, we also have

c_{m,1}^{K}(n) = (1 − m)^{n−1}s_{m/(1−m)}(n) = (−1)^{n−1}d^{−(n−1)}s_{−d−1}(n),

which yields a proof of Proposition 8 for all cases where d ≠ 0.

Finally, inspired by David Scambler’s comments in the OEIS, we show how s_{d}(n) counts families of Dyck paths with certain forbidden peak types. Scambler claimed (in \underline{A107841}, slightly paraphrased here) that s_{2}(n) counts the number of Dyck paths from (0, 0) to (2n − 2, 0) with 3 types of up steps U_{1}, U_{2}, U_{3}, one type of down step D, and avoid U_{1}D. Similarly, he commented (\underline{A131763}) that s_{3}(n) gives the number of Dyck paths from (0, 0) to (2n − 2, 0) with two types of up steps U_{1}, U_{2}, two types of down steps D_{1}, D_{2}, and avoid U_{1}D_{1}. Independently, Geffner and Noy [6, Theorem 3] showed that s(n) counts the number of Dyck paths in D_{n} with one type of up step U, two types of down steps D_{1}, D_{2}, and avoid UD_{1}. We show that a generalization of these statements follow readily from our findings above.

Proposition 13. Given integers k, ℓ ≥ 1, let D_{k,ℓ}(n) denote the number of ways to construct Dyck paths from (0, 0) to (2n − 2, 0) using k types of up steps U_{1}, …, U_{k} and ℓ types of down steps D_{1}, …, D_{ℓ}, while avoiding peaks of the type U_{1}D_{1}. Then

D_{k,ℓ}(n) = s_{kℓ−1}(n).

for every n ≥ 1.

Proof. Notice that D_{k,ℓ}(n) can be reinterpreted as the number of Dyck paths where

• each of the K(P) peaks of P is assigned kℓ − 1 colors (since there are a total of kℓ types of possible peaks, 1 of which is forbidden);

• each of the U_{K}(P) up steps not contained in a peak is assigned one of k colors;

• each of the D_{K}(P) down steps not contained in a peak is assigned one of ℓ colors.

Hence, we obtain that

D_{k,ℓ}(n) = ∑_{P ∈D_{n}} k^{U_{K}(P)}(kℓ − 1)^{K(P)}ℓ^{D_{K}(P)}

= ∑_{P ∈D_{n}}(kℓ)^{U_{K}(P)}(kℓ − 1)^{K(P)}

= c_{kℓ−1,kℓ}^{K}(n)

= c_{kℓ−1,kℓ}^{V}(n) = s_{kℓ−1}(n).

Note that the second equality above is due to U_{K}(P) = D_{K}(P) for every Dyck path P, and the last two equalities are due to Propositions 9 and 12, respectively.

Note that the above argument can be easily extended to cases where more than 1 of the kℓ possible peak types are forbidden. More precisely, one could show that the number of Dyck paths from (0, 0) to (2n − 2, 0) with k types of up steps, ℓ types of down steps, with p of the kℓ peak types forbidden, is c_{kℓ−p,kℓ}^{K}(n) = p^{n−1}s_{(kℓ−p)/p}(n).

5 Concluding remarks

In this manuscript, we looked at s_{d}(n), a natural generalization of the small Schröder numbers that had made cameos in a number of contexts but was never the main focus of study until now. We also saw that the study of s_{d}(n) led to implications for familiar combinatorial objects such as Schröder paths and Dyck paths.

We remark that there are many natural combinatorial interpretations of s_{d}(n) that we have yet to mention. For instance, as we have seen with Schröder trees and small Schröder paths, any combinatorial interpretation of s(n, k) readily extends to a corresponding set of objects counted by s_{d}(n) for positive integers d. For another example, it is known [14] that s(n, k) counts the number of ways to subdivide the regular (n + 1)-gon into k regions using non-crossing diagonals. Therefore, s_{d}(n) gives the number of ways to subdivide the regular (n + 1)-gon using non-crossing diagonals, with each of the regions colored one of d colors.

Other interpretations of s(n, k) (e.g., in terms of standard Young tableaux [14], and loopless outerplanar maps [6]) can be extended similarly, and it is possible that s_{d}(n) — or other generalizations of related integer sequences — can lend new perspectives to solving combinatorial problems involving these familiar quantities.

Figure 6: The s_{2}(3) = 10 ways to 2-color subdivisions of a square

6 Acknowledgments

Finally, we express our gratitude to Neil J. A. Sloane and the numerous contributors to the On-Line Encyclopedia of Integer Sequences for developing and curating such a valuable resource for mathematical discovery.

References

[1] J. Abate and W. Whitt, Integer sequences from queuing theory, J. Integer Sequences 13 (2010), Article 10.5.5.

[2] P. Barry, Embedding structures associated with Riordan arrays and moment matrices, Int. J. Comb. 2014 (2014) Article ID 301394.

[3] Z. Chen and H. Pan, Identities involving weighted Catalan, Schröder and Motzkin paths, Adv. Appl. Math. 86 (2017), 81–98.

[4] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[5] D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence, J. Combin. Theory Ser. A 80 (1997), 380–384.

[6] I. Geffner and M. Noy, Counting outerplanar maps, Electron. J. Combin. 24 (2017), 1–8.

[7] I. Gessel, Schröder numbers, large and small, 2009. Available at http://people.

   brandeis.edu/~gessel/homepage/slides/schroder.pdf.

[8] S. Giraudo, Operads from posets and Koszul duality, European J. Combin. 56 (2016), 1–32.

[9] J. Huh and S. Park, Generalized small Schröder numbers, Electron. J. Combin. 22 (3) (2015), 3–14.

[10] F. Lam, Integral invariance and non-linearity reduction for proliferating vorticity scales in fluid dynamics, 2013. Available at https://arxiv.org/abs/1311.6395.

[11] J. Schröder, Generalized Schröder numbers and the rotation principle, J. Integer Sequences 10 (2007), Article 07.7.7.

[12] L. W. Shapiro and R. A. Sulanke, Bijections for the Schröder numbers, Math. Mag. 73 (2000), 369–376.

[13] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2020. Available

    at https://oeis.org.

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

[15] R. P. Stanley, Hipparchus, Plutarch, Schröder, and Hough, Amer. Math. Monthly 104 (1997), 344–350.

[16] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Studies in Advanced Mathematics, 1999.

[17] R. A. Sulanke, Bijective recurrences concerning Schröder paths, Electron. J. Combin. 5 (1998), Article R47.

[18] R. A. Sulanke, Generalizing Narayana and Schröder numbers to higher dimensions, Electron. J. Combin. 11 (2004), Article R54.

2010 Mathematics Subject Classification: Primary 05A15. Secondary 05A16, 05A19.

Keywords: Schröder number, Schröder path, Catalan number, Dyck path, Narayana number, plane rooted tree.

(Concerned with sequences \underline{A000108}, \underline{A001003}, \underline{A006318}, \underline{A071684}, \underline{A071688}, \underline{A086810}, \underline{A090181}, \underline{A107841}, \underline{A131763}, and \underline{A131765}.)

Received May 2 2020; revised version received December 23 2020. Published in Journal of Integer Sequences, December 28 2020.

Return to Journal of Integer Sequences home page.