Schröder Coloring and Applications

Daniel Birmajer Nazareth College Rochester, NY 14618 USA

                   abirmaj6@naz.edu

Juan D. Gil Massachusetts Institute of Technology Cambridge, MA 02139 USA

                  jdgil@alum.mit.edu

Juan B. Gil and Michael D. Weiner Penn State Altoona Altoona, PA 16601 USA

                     jgil@psu.edu
                     mdw8@psu.edu

Abstract

We present several bijections, in terms of combinatorial objects counted by the Schröder numbers, that are then used (via coloring of Dyck paths) for the construction and enumeration of rational Schröder paths with integer slope, ordered rooted trees, and simple rooted outerplanar maps. On the other hand, we derive partial Bell polynomial identities for the little and large Schröder numbers, which allow us to obtain explicit enumeration formulas.

1 Introduction

This paper focuses on the little Schröder numbers

1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, …,  (1)

and the role they play for coloring certain combinatorial structures. Consistent with the OEIS, we denote the above sequence by (s_{n})_{n∈ℕ_{0}}. These numbers appeared in a paper by Ernst Schröder [8] from 1870, where he discussed four combinatorial problems regarding parenthesizations. Problem II in [8] lead to (1), and it is now well known that (s_{n})_{n∈ℕ_{0}} enumerates a wide variety of objects, see [10, \underline{A001003}], [11].

Here we rely on the following three interpretations for s_{n} with n ≥ 0:

(path) Number of Schröder paths^{1} from (0, 0) to (n, n) with no D-steps on y = x.

(tree) Number of ordered trees with no vertex of outdegree 1 and having n + 1 leaves.

(poly) Number of dissections of a convex (n + 2)-gon by nonintersecting diagonals.

Our main computational result is Theorem 2, where we give an explicit formula for the evaluation of partial Bell polynomials at s_{0}, s_{1}, s_{2}, . . .. Our proof uses a combinatorial argument that involves integer compositions and (path). In addition, we give a similar formula for when (s_{n})_{n∈ℕ_{0}} is replaced by the sequence (r_{n})_{n∈ℕ_{0}} of large Schröder numbers 1, 2, 6, 22, 90, …, see [10, \underline{A006318}]. These formulas are particularly beneficial when dealing with Bell transformations, as defined by Birmajer, Gil, and Weiner [3].

In Section 3, we consider the set S_{n}(α) of rational Schröder paths with slope α ∈ ℕ, i.e., lattice paths from (0, 0) to (n, αn) with steps E, N, and D, that stay weakly above the line y = αx. We call these paths Fuss-Catalan-Schröder paths. Our main contribution here is a bijective map that provides an algorithm to generate Fuss-Catalan-Schröder paths using classical Schröder paths as building blocks. As a consequence, we obtain a formula for the enumeration of S_{n}(α) by the number of building blocks used for their construction. In the special case when these paths contain the maximal number of blocks of the form D or NE, our formula leads to several sequences listed in the OEIS [10], see Table 1.

Section 4 deals with ordered rooted trees. We consider ordered trees with no vertex of outdegree 1, like in (tree), and use them to construct ordered rooted trees with a given number of generators.^{2} This is achieved by means of a Dyck path insertion algorithm described in the proof of Theorem 8. As a corollary, we obtain a formula for the number of ordered rooted trees with n generators having a prescribed number of nodes of outdegree 1.

Finally, in Section 5, we make a brief excursion into the enumeration of outerplanar maps, cf. [4, 6]. A planar map is a connected graph embedded on the sphere with nonintersecting edges. Such a map is said to be outerplanar if all the nodes lie on one face. We view polygon dissections as biconnected simple outerplanar maps and use (poly), together with certain colored Dyck paths, to generate and count simple outerplanar maps by the number of their biconnected components.

1Lattice paths with steps E = (1, 0), N = (0, 1), and D = (1, 1), staying weakly above y = x.

2A generator is a leaf or a node with only one child.

All of our proofs rely on explicit combinatorial bijections that involve building blocks counted by the Schröder numbers. The three applications we discussed in this paper represent just a glimpse of the possible ways Schröder-type objects may be used to construct and enumerate more complex combinatorial classes. For example, s_{n} also counts indecomposable permutations that avoid the patterns 2413 and 3142, and for n ≥ 1, s_{n} gives the number of increasing tableaux of shape (n, n).

In summary, the content of Section 2 provides a toolbox for studying a broad family of sequence transformations of the little and large Schröder numbers.

2 Bell transforms of little Schröder numbers

Birmajer et al. [3] introduced the following family of sequence transformations defined via partial Bell polynomials. Let a, b, c, d be fixed numbers. Given x = (x_{n})_{n∈ℕ}, its Bell transform y = 𝒴_{a,b,c,d}(x) is the sequence defined by

y_{n} = ∑_{k=1}^{n} \frac{1}{n!}[ ∏_{j=1}^{k−1} (an + bk + cj + d)]B_{n,k}(1!x_{1}, 2!x_{2}, …) for n ≥ 1,  (2)

where B_{n,k} denotes the (n, k)-th (exponential) partial Bell polynomial.

For 0 ≤ k ≤ n, we have

B_{n,k}(z_{1}, …, z_{n−k+1}) = ∑_{α∈π(n,k)} \frac{n!}{α_{1}!α_{2}! ⋯} (\frac{z_{1}}{1!} )^{α_{1}} (\frac{z_{2}}{2!} )^{α_{2}} ⋯,

where π(n, k) denotes the set of multi-indices α ∈ ℕ_{0}^{n−k+1} such that

α_{1} + α_{2} + ⋯ = k and α_{1} + 2α_{2} + 3α_{3} + ⋯ = n.

Note that the polynomial B_{n,k} contains as many monomials as the number of partitions of the set [n] = {1, …, n} into k parts.

The definition of 𝒴_{a,b,c,d}(x) suggests the need for a closed formula for B_{n,k}(1!x_{1}, 2!x_{2}, …), which in some cases can be a challenging task. In this section, we will use a combinatorial argument (via colored compositions) to derive a formula for B_{n,k}(1!s_{0}, 2!s_{1}, …), where (s_{n})_{n∈ℕ_{0}} is the sequence of little Schröder numbers.

Let CS_{n,k} be the set of compositions of n with exactly k parts such that part j can take on s_{j−1} colors. In particular, following (path), part j may be labeled with any of the s_{j−1} Schröder paths from (0, 0) to (j − 1, j − 1) with no D-steps on y = x. Using a formula^{3} by Hoggatt and Lind [7], we get

3Written here in terms of Bell polynomials.

#CS_{n,k} = \frac{k!}{n!}B_{n,k}(1!s_{0}, 2!s_{1}, 3!s_{2}, …).  (3)

Lemma 1. The set of Schröder paths from (0, 0) to (n + k − 1, n + k − 1) having exactly k − 1 diagonal steps on the line y = x is in one-to-one correspondence with the set CS_{n+k,k}.

Proof. Given a Schröder path P from (0, 0) to (n + k − 1, n + k − 1) with exactly k − 1 diagonal steps on the line y = x, use these diagonal steps as separators to split P into k Schröder subpaths P_{1}, P_{2}, …, P_{k}, having no D-steps on the line y = x (and ordered such that P_{1} starts at the origin and P_{k} ends at the endpoint of P). Note that a single lattice point is considered a trivial path of length 0. If P_{j} covers a segment on y = x with i_{j} lattice points, we define φ(P) to be the composition (i_{1}, i_{2}, …, i_{k}) of n + k, where part i_{j} is labeled by P_{j}. In other words, the composition φ(P) is an element of the set CS_{n+k,k}.

For example, for n = 5 and k = 4, the path NDEDNENNEEDD corresponds to the composition (3, 4, 1, 1) of 9, where part 3 is labeled by the path NDE and part 4 is labeled by the path NENNEE (see Figure 1).

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

Figure 1: Example of φ for n = 5 and k = 4.

The map φ is clearly bijective. Given a colored composition (i_{1}, …, i_{k}) of n + k, where part i_{j} is labeled by a Schröder path P_{j} with no D-steps on y = x, represent the parts as connected dots on the x-axis, place the labels P_{1}, …, P_{k} on the line y = x above the parts, and connect them with diagonal steps.

As a consequence of Lemma 1, (path), and identity (3), we get

\frac{k!}{(n + k)!}B_{n+k,k}(1!s_{0}, 2!s_{1}, …) = ∑_{m_{1}+···+m_{k}=n} s_{m_{1}} ⋯ s_{m_{k}}.  (4)

Theorem 2. For 1 ≤ k < n, we have

B_{n,k}(1!s_{0}, 2!s_{1}, 3!s_{2}, …) = \frac{n!}{(k − 1)!} ∑_{j=1}^{n−k} \frac{1}{j}\binom{n − k − 1}{j − 1}\binom{n + j − 1}{j − 1}.  (5)

Proof. First of all, note that s_{0} = 1, and for n ≥ 1,

s_{n} = ∑_{j=1}^{n} \frac{1}{j}\binom{n + j}{j − 1}\binom{n − 1}{j − 1}

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

= ∑_{j=1}^{n} \binom{n + j}{j − 1}\frac{(j − 1)!}{n!}B_{n,j}(1!, 2!, …).

Therefore, by a convolution formula given in [3, Section 4],

∑_{m_{1}+···+m_{k}=n}s_{m_{1}} ⋯ s_{m_{k}} = k ∑_{j=1}^{n} \binom{n + j + k − 1}{j − 1}\frac{(j − 1)!}{n!}B_{n,j}(1!, 2!, …)

= ∑_{j=1}^{n} \frac{k}{j} \binom{n − 1}{j − 1}\binom{n + j + k − 1}{j − 1}.

Now, identity (4) implies

\frac{k!}{(n + k)!}B_{n+k,k}(1!s_{0}, 2!s_{1}, …) = ∑_{j=1}^{n} \frac{k}{j} \binom{n − 1}{j − 1}\binom{n + j + k − 1}{j − 1},

and (5) follows by replacing n by n − k.

Using basic properties of the partial Bell polynomials and (5), we get: Corollary 3. If (r_{n})_{n∈ℕ_{0}} is the sequence of large Schröder numbers 1, 2, 6, 22, …, then for 1 ≤ k < n, we have

B_{n,k}(1!r_{0}, 2!r_{1}, 3!r_{2}, …)

= ∑_{ℓ=0}^{k}(−1)^{ℓ}2^{k−ℓ}\binom{n}{ℓ}B_{n−ℓ,k−ℓ}(1!s_{0}, 2!s_{1}, 3!s_{2}, …)

= \frac{n!}{(k − 1)!} ∑_{ℓ=0}^{k} ∑_{j=1}^{n−k} \frac{(−1)^{ℓ}2^{k−ℓ}}{j} \binom{k − 1}{ℓ}\binom{n − k − 1}{j − 1}\binom{n − ℓ + j − 1}{j − 1}.

It is worth noting that some of the most prominent Bell transforms (like the invert [1] and the noncrossing partition [5] transforms) are of the form 𝒴_{a,b,−1,1}(x) with a, b ∈ ℕ_{0}. In such a special case, if s = (s_{n})_{n∈ℕ_{0}} and y = 𝒴_{a,b,−1,1}(s), then (2) becomes

y_{n} = ∑_{k=1}^{n} \binom{an + bk}{k − 1}\frac{(k − 1)!}{n!}B_{n,k}(1!s_{0}, 2!s_{1}, …).

We can then use (5) to conclude:

Corollary 4. If s = (s_{n})_{n∈ℕ_{0}}, then the Bell transform 𝒴_{a,b,−1,1}(s) is given by

y_{n} = \frac{1}{n}\binom{(a + b)n}{n − 1} + ∑_{k=1}^{n−1} ∑_{j=1}^{n−k} \frac{1}{j}\binom{an + bk}{k − 1}\binom{n − k − 1}{j − 1}\binom{n + j − 1}{j − 1}.

3 Fuss-Catalan-Schröder paths

For a ∈ ℕ and c = (c_{1}, c_{2}, …) with c_{j} ∈ ℕ_{0}, let us consider the set of Dyck words of semilength (a + 1)n created from strings of the form P_{0} = “d ” and P_{j} = “u^{(a+1)j}d^{j}” for j = 1, …, n, such that each maximal (a + 1)j-ascent substring u^{(a+1)j} may be colored in c_{j} different ways. Consistent with the notation used in [2], we denote this set by 𝔇_{n}^{c}(a, 1).

Let SP_{n}^{∧} denote the set of Schröder paths from (0, 0) to (n, n) that lie strictly above the diagonal y = x except for the diagonal path from (0, 0) to (1, 1). Moreover, let σ σ σ be the sequence that enumerates SP_{n}^{∧}. In particular, σ_{1} = 2 since the two paths D and NE from (0, 0) to (1, 1) both fit the above description, and σ_{2}, σ_{3}, σ_{4}, …, is precisely the sequence of large Schröder numbers 2, 6, 22, 90, 394, …, see [10, \underline{A006318}]. For j ≥ 1, σ_{j} = 2s_{j−1}.

Recall that S_{n}(α) denotes the set of Fuss-Catalan-Schröder paths with slope α ∈ ℕ.

Theorem 5. For every n ∈ ℕ, we have

#S_{n}(α) = #𝔇_{n}^{σ σ σ}(α − 1, 1).

In other words, there is a bijection between Fuss-Catalan-Schröder paths from (0, 0) to (n, αn) and Dyck paths of semilength αn whose ascent lengths are multiples of α, and where an αjascent may be labeled in σ_{j} ways and is always followed by at least j down-steps.

Proof. We will give an explicit bijective map ξ : S_{n}(α) → 𝔇_{n}^{σ σ σ}(α − 1, 1).

Given a Fuss-Catalan-Schröder path P ∈ S_{n}(α), walk the path from (n, αn) to (0, 0) and construct a colored Dyck path Q ∈ 𝔇_{n}^{σ σ σ}(α − 1, 1) as follows:

• if at a point (a, b) on P followed by a D-step, add an α-ascent followed by one downstep to the path Q, color the ascent by the one-step path D (i.e., ), and move to the point (a − 1, b − 1) on P; • if at a point (a, b) followed by a horizontal step, draw a line of slope 1 from that point

to the next point of the form (a − j, b − j) where the line intersects the path P. The path P_{j} between these two points is a Schröder path in SP_{j}^{∧}. Add to the path Q an αj-ascent followed by j down-steps, color that ascent by P_{j}, and move to the point (a − j, b − j) on P;

• if at a point (a, b) followed by a vertical step, add a down-step to the path Q and move to the point (a, b − 1) on P.

We continue this process until (0, 0) has been reached. The path Q = ξ(P) created by means of the above algorithm is by construction a Dyck path in 𝔇_{n}^{σ σ σ}(α − 1, 1). Note that a return to the line y = αx on P corresponds to a return to the x-axis on the Dyck path. For an example, see Figure 2.

\begin{matrix}P_{1} \\ P_{2} \\ P_{3} \\ ξ \end{matrix}  ^{\begin{matrix}P_{1} \\ P_{2} \\ P_{3} \end{matrix}}

Figure 2: Example for α = 2 and n = 4.

The map ξ is reversible. Given a Dyck path Q ∈ 𝔇_{n}^{σ σ σ}(α−1, 1), construct a path P ∈ S_{n}(α) as follows. Walk the Dyck path Q from right to left. For every down-step that is not part of a block P_{j} = u^{αj}d^{j} on Q, add an N-step to P, and for every block P_{j}, add to P the Schröder path labeling the corresponding αj-ascent on P_{j}.

The above bijection provides an algorithm to generate Fuss-Catalan-Schröder paths using classical Schröder paths as building blocks.

By [2, Theorem 2], the number of elements in 𝔇_{n}^{σ σ σ}(α − 1, 1) having exactly k peaks is given by

\binom{(α − 1)n + k}{k − 1}\frac{(k − 1)!}{n!}B_{n,k}(1!σ_{1}, 2!σ_{2}, …)

= \binom{(α − 1)n + k}{k − 1}\frac{(k − 1)!}{n!}B_{n,k}(1!(2s_{0}), 2!(2s_{1}), …)

= \binom{(α − 1)n + k}{k − 1}\frac{(k − 1)!}{n!}2^{k}B_{n,k}(1!s_{0}, 2!s_{1}, …).

Corollary 6. There are

\frac{2^{n}}{n} \binom{αn}{n − 1} = \frac{2^{n}}{(α − 1)n + 1}\binom{αn}{n}  (6)

paths in S_{n}(α) containing n paths from SP_{1}^{∧} (i.e., paths of the form D or NE).

Table 1 shows a few terms of the sequence (6) for α = 1, …, 5.

Slope α  \frac{2^{n}}{(α−1)n+1} \binom{αn}{n}  OEIS
1  2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, …  \underline{A000079}
2  2, 8, 40, 224, 1344, 8448, 54912, 366080, …  \underline{A151374}
3  2, 12, 96, 880, 8736, 91392, 992256, 11075328, …  \underline{A153231}
4  2, 16, 176, 2240, 31008, 453376, 6888960, 107707392, …  \underline{A217360}
5  2, 20, 280, 4560, 80960, 1520064, 29680640, 596593920, … \underline{A217364}

Table 1: Number of paths in S_{n}(α) having n subpaths from SP_{1}^{∧}.

Corollary 7. If 1 ≤ k < n, the number of paths in S_{n}(α) that can be built with exactly k elements of SP^{∧} = ⋃_{n} SP_{n}^{∧} is given by

2^{k}\binom{(α − 1)n + k}{k − 1} ∑_{j=1}^{n−k} \frac{1}{j}\binom{n − k − 1}{j − 1}\binom{n + j − 1}{j − 1}.

Finally, for the cardinality of S_{n}(α), we can use [9, Theorem 2.9] to deduce the simple formula

#S_{n}(α) = \frac{1}{αn + 1} ∑_{ℓ=0}^{n} \binom{αn + 1}{n − ℓ}\binom{αn + ℓ}{ℓ}.

4 Ordered rooted trees

In this section, we use the interpretation (tree) to generate and count ordered rooted trees with n generators (leaves or nodes of outdegree 1).

Let ST_{n} be the set of ordered trees with no vertex of outdegree 1 and having n+1 leaves. Thus #ST_{n} = s_{n}. Note that every tree in ST_{n} has n + 1 generators.

Let T_{n} be the set of ordered rooted trees with n generators. Our next result shows that every element of T = ⋃_{n} T_{n} can be uniquely constructed from elements of the set ST = ⋃_{n} ST_{n} via a Dyck path insertion algorithm.

n = 0  n = 1  n = 2

n = 3

Table 2: Elements of ST_{n} for n = 0, 1, 2, 3.

Theorem 8. The set of ordered rooted trees with n generators is in one-to-one correspondence with the set of Dyck paths of semilength n whose ascents of length j, for j = 1, …, n, may be colored in s_{j−1} different ways.

Proof. Let 𝔇_{n}^{s}(1, 0) be the set of Dyck paths of semilength n colored by the little Schröder numbers. Because of (tree), we can consider 𝔇_{n}^{s}(1, 0) to be the set of Dyck paths of semilength n with each j-ascent associated with a tree in ST_{j−1}.

We will define a map ψ : 𝔇_{n}^{s}(1, 0) → T_{n} that requires a notion of traversing an ordered tree. When traversing a tree, we stick to the ordering of leaf nodes that would be acquired when performing in-order depth-first search.

Suppose we have a path P ∈ 𝔇_{n}^{s}(1, 0) with k peaks. For 1 ≤ i ≤ k, let G_{i} denote the ordered tree associated with the ith ascent of the Dyck path. Starting at the first ascent of P, we construct the ordered tree ψ(P) as follows. We start at the root of the tree G_{1}. Suppose that the first ascent of the Dyck path is followed by a j_{1}-descent. Then, we traverse G_{1} from the root until we reach the j_{1}th leaf. At that point, we add an edge between the j_{1}th leaf of G_{1} and the root of the tree G_{2} corresponding to the second ascent. Suppose that the second ascent is followed by a j_{2}-descent. From the node that was formerly the j_{1}th leaf from the root (and which is no longer a leaf), we continue to traverse the augmented tree until we reach the j_{2}th leaf from that node.

This algorithm will always result in an ordered tree with n generators. Note that since P has n up steps, and since every j-ascent corresponds to an ordered tree with j leaves (and no other generators), there are n leaves total in the trees G_{1}, …, G_{k}. Every leaf in a tree G_{i} either becomes a leaf in the final tree, or it becomes a node with a single child. Thus the final tree ψ(P) has exactly n generators.

An example that illustrates the above construction is given in Figure 3.

The inverse map from T_{n} to 𝔇_{n}^{s}(1, 0) is straightforward. Given G ∈ T_{n}, we construct a

\begin{matrix}G_{1} \\ G_{2} \\ G_{3} \\ G_{4} \\ ψ \end{matrix}  \begin{matrix}G_{1} \\ G_{2} \\ G_{3} \\ G_{4} \end{matrix}

Figure 3: Example for n = 7.

Schröder colored Dyck path as follows. Starting at the root of G, we first identify the largest subgraph of G with the same root that is an ordered tree with no vertex of outdegree 1. We call this subgraph G_{1}. Once G_{1} has been specified, we count the number of leaves of G_{1}. If G_{1} has j leaves, then we begin the Dyck path with a j-ascent and label that first ascent with G_{1}. Then, we traverse G_{1} until we find a leaf of G_{1} that corresponds to a node of outdegree 1 in G. If this leaf is the j_{1}th leaf checked, then we add a j_{1}-descent to the Dyck path. Then, to find the next ascent, we identify the ordered tree G_{2} rooted at the child of the node corresponding to the j_{1}th leaf of G_{1}. This process continues until the tree G has been completely traversed.

This algorithm gives a Dyck path in 𝔇_{n}^{s}(1, 0). Indeed, every generator in G is counted as both an ascent and a descent, so the path ψ^{−1}(G) has semilength n. Moreover, every j-ascent corresponds to one of the s_{j−1} possible ordered trees with j leaves and no nodes of outdegree 1. Finally, note that the ascent corresponding to a generator of the ordered tree is always added to the path before the descent corresponding to the same generator is added to the path.

Corollary 9. As a consequence of [2, Theorem 2] and Theorem 8, we get

#T_{n} = #𝔇_{n}^{s}(1, 0) = 1 + ∑_{k=1}^{n−1} ∑_{j=1}^{n−k} \frac{1}{j}\binom{n}{k − 1}\binom{n − k − 1}{j − 1}\binom{n + j − 1}{j − 1}.

This gives the sequence 1, 2, 7, 32, 166, 926, 5419, 32816, …, see [10, \underline{A108524}].

Moreover, the number of trees in T_{n} having exactly k − 1 nodes of outdegree 1 is equal to the number of paths in 𝔇_{n}^{s}(1, 0) having k peaks. This number is given by

\binom{n}{k − 1}\frac{(k − 1)!}{n!}B_{n,k}(1!s_{0}, 2!s_{1}, …),

which for 1 ≤ k < n can be written as

\binom{n}{k − 1} ∑_{j=1}^{n−k} \frac{1}{j}\binom{n − k − 1}{j − 1}\binom{n + j − 1}{j − 1}.

5 Outerplanar maps

Recall that if s is the sequence (s_{n})_{n∈ℕ_{0}}, 𝔇_{n}^{s}(1, 1) denotes the set of Dyck paths of semilength 2n created from down-steps and blocks of the form P_{j} = “u^{2j}d^{j}” for j = 1, …, n, such that each 2j-ascent may be colored in s_{j−1} different ways.

In this section, we use the interpretation (poly) for the little Schröder numbers to generate and count simple outerplanar maps using polygon dissections (seen as biconnected outerplanar maps) put together according to the elements of 𝔇_{n}^{s}(1, 1).

Let B_{n} be the set of biconnected (nonseparable) rooted outerplanar maps with n + 2 vertices. Note that B_{0} consists of the single map , and for n ≥ 1, every element of B_{n} can be seen as a dissection of a convex (n + 2)-gon by nonintersecting diagonals. Therefore, #B_{n} = s_{n}. For example, B_{1} consists of a single triangle and B_{2} contains the three possible dissections of a square:

By default, we will assume that the elements of B_{n} are rooted at the base of the polygon such that the root face is the outer face.

Theorem 10. The set M_{n} of simple outerplanar maps with n + 1 vertices is in one-to-one correspondence with the set 𝔇_{n}^{s}(1, 1).

Proof. We will establish a bijective map ϕ : M_{n} → 𝔇_{n}^{s}(1, 1) that relies on the decomposition of a planar map into biconnected components. Given a map M ∈ M_{n} with k biconnected components, we construct a Dyck path P = ϕ(M) as follows. Starting at the root vertex v_{0} of M, we walk counterclockwise around M, visiting all of its vertices. We let B_{1}, …, B_{k} be the biconnected components of M, numbered in the order they are visited, and assume that B_{j} has i_{j} + 1 vertices, 1 ≤ i_{j} ≤ n for every j. While at v_{0}, add a 2i_{1}-ascent to P followed by i_{1} down-steps and walk to the next vertex of M (second vertex of the root edge). For each subsequent vertex we visit on B_{1}, add a down-step to P until we reach the first vertex on B_{2}. At that point, we add a 2i_{2}-ascent to P followed by i_{2} down-steps, and move to the next vertex. We then continue adding down-steps to P until we reach the first vertex of the next component of M. When visiting a vertex of a biconnected component that has already been visited, we add a down-step to P. This process ends after we have visited all vertices of M and reach v_{0} again. We then label/color the k maximal ascents of P with the corresponding biconnected maps B_{1}, …, B_{k}, and obtain an element of 𝔇_{n}^{s}(1, 1) with k peaks. An example of the above construction is shown in Figure 4.

The inverse map is clear. Given a Dyck path P ∈ 𝔇_{n}^{s}(1, 1) with k maximal ascents of lengths 2i_{1}, …, 2i_{k}, colored by biconnected rooted maps B_{1}, …, B_{k}, we construct an outerplanar map as follows. Let M_{1} = B_{1} and let v_{0} be the root vertex of B_{1}. If the first ascent of P is followed by j_{1} down-steps, we walk around M_{1} (starting at v_{0}) until we reach

\begin{matrix}B_{1} \\ B_{2} \\ B_{3} \\ ϕ \end{matrix}  \begin{matrix}B_{1} \\ B_{2} \\ B_{3} \end{matrix}

Figure 4: Example for n = 6 and k = 3.

the (j_{1} − i_{1} + 1)th vertex on M_{1}. We call that vertex v_{1} and merge it with the root vertex of B_{2} to create a rooted outerplanar map M_{2} with the same root edge as M_{1}. This extended map has now i_{1} + i_{2} + 1 vertices. We then repeat the process starting now at v_{1}. After all coloring biconnected maps have been used as extensions (traversing P from left to right), the resulting rooted outerplanar map M_{k} will be an element of M_{n}. We let ϕ^{−1}(P) = M_{k}.

Corollary 11. By Theorem 10, the number of outerplanar maps in M_{n} having exactly k biconnected components is equal to the number of paths in 𝔇_{n}^{s}(1, 1) having k peaks. Thus, by [2, Theorem 2], this number is given by

\binom{n + k}{k − 1}\frac{(k − 1)!}{n!}B_{n,k}(1!s_{0}, 2!s_{1}, …),  (7)

which for 1 ≤ k < n can be written as

\binom{n + k}{k − 1} ∑_{j=1}^{n−k} \frac{1}{j}\binom{n − k − 1}{j − 1}\binom{n + j − 1}{j − 1}.

Note that if k = n, then (7) becomes \frac{1}{n} \binom{2n}{n−1} = C_{n}, and we recover the known fact that planted trees are counted by the Catalan numbers.

Corollary 12. For n ≥ 1 we have

#M_{n} = \frac{1}{n}\binom{2n}{n − 1} + ∑_{k=1}^{n−1} ∑_{j=1}^{n−k} \frac{1}{j}\binom{n + k}{k − 1}\binom{n − k − 1}{j − 1}\binom{n + j − 1}{j − 1}.

This gives the sequence 1, 3, 13, 67, 381, 2307, 14589, 95235, …, see [10, \underline{A064062}].

References

[1] M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Algebra Appl. 226/228 (1995), 57–72.

[2] D. Birmajer, J. B. Gil, P. R. W. McNamara, and M. D. Weiner, Enumeration of colored Dyck paths via partial Bell polynomials, Lattice path combinatorics and applications, 155–165, Dev. Math. 58, Springer, Cham, 2019.

[3] D. Birmajer, J. B. Gil, and M. D. Weiner, A family of Bell transformations, Discrete Math. 342 (2019), no. 1, 38–54.

[4] N. Bonichon, C. Gavoille, and N. Hanusse, Canonical decomposition of outerplanar maps and application to enumeration, coding and generation, J. Graph Algorithms Appl. 9 (2005), no. 2, 185–204.

[5] D. Callan, Sets, lists and noncrossing partitions, J. Integer Seq. 11 (2008), no. 1, Article 08.1.3.

[6] I. Geffner and M. Noy, Counting outerplanar maps, Electron. J. Combin. 24 (2) (2017), #P2.3.

[7] V. E. Hoggatt and D. A. Lind, Fibonacci and binomial properties of weighted compositions, J. Combin. Theory 4 (1968), 121–124.

[8] E. Schröder, Vier kombinatorische Probleme, Z. Math. Phys. 15 (1870), 361–376.

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

[10] N. J. A. Sloane et al., The On-line Encyclopedia of Integer Sequences, 2020. Available

at https://oeis.org/.

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

2020 Mathematics Subject Classification: Primary 05A19; Secondary 05A10, 05C05, 11B83. Keywords: Schröder number, Bell polynomial, lattice path, rooted tree, outerplanar map.

(Concerned with sequences \underline{A000079}, \underline{A001003}, \underline{A006318}, \underline{A064062}, \underline{A108524}, \underline{A151374}, \underline{A153231}, \underline{A217360}, and \underline{A217364}.)

Received August 4 2019; revised version received December 24 2019; December 21 2020. Published in Journal of Integer Sequences, ??????.

Return to Journal of Integer Sequences home page.