Enumeration of S-omino Towers and Row-Convex k-omino Towers

Alexander M. Haupt Institute of Mathematics Hamburg University of Technology Am Schwarzenberg-Campus 3 21073 Hamburg Germany

                alexander.haupt@tuhh.de

Abstract

We first enumerate a generalization of domino towers that was proposed by Brown, which we call S-omino towers. We establish equations that the generating function must satisfy and then apply the Lagrange inversion formula to find a closed formula for the number of towers. We also show a connection to generalized Dyck paths and describe an explicit bijection. Finally, we consider the set of row-convex k-omino towers, introduced by Brown, and calculate an exact generating function.

1 Introduction

In this paper, we enumerate a generalization of so-called domino towers. Domino towers are two-dimensional structures made out of n dominoes, i.e., rectangular blocks of width 2 and height 1, with the following properties:

1. The dominoes on the bottom level are contiguous, i.e., the row is convex;

2. Every domino above the bottom row is (half) supported on at least one domino in the row below it;

3. No domino lies directly on top of another domino, such as in a brickwork pattern.

Figure 1: Small restricted domino towers for n ∈ {1, 2, 3}.

See Figure 1 for the domino towers with n ∈ {1, 2, 3}. The problem of counting domino towers was first mentioned by Viennot [9, Cor. 4]. Surprisingly, the number of domino towers made up of exactly n blocks is simply 3^{n−1}. Zeilberger showcased the result together with a proof using ordinary generating functions and a bijective proof [10]. The problem also appears as an example in the Handbook of Enumerative Combinatorics [1, p. 25].

In this paper, we drop the restriction that blocks cannot be placed directly on top of another and call the structures unrestricted towers. Brown proved that there are 4^{n−1} unrestricted towers [4, Cor. 2.3]. We give an alternative proof of this fact in Corollary 8 using symbolic methods and a construction called substitution. See Figures 2a and 2b for examples of restricted and unrestricted domino towers.

(a) A restricted domino tower with 8 blocks.

(b) An unrestricted domino tower with 10 blocks.

Figure 2: Examples of domino towers.

In 2016, Brown generalized the problem to unrestricted towers made up of rectangles of width k, which they called k-omino towers [4]. They also introduced a variable b ≥ 1 for the number of blocks in the bottom row. The number of k-omino towers is \binom{kn−1}{n−b}.

Brown also suggests that enumerating towers using rectangles of mixed widths could be interesting for other applications [3, p. 17]. In this paper, we study this generalization by allowing rectangles with any width in a fixed finite list S = (s_{1}, …, s_{m}) of positive integers. We call this set of towers S-omino towers. We additionally fix a list (n_{1}, …, n_{m}), where n_{i} denotes the number of blocks of width s_{i}, and b ≥ 1 the number of blocks in the bottom row. Furthermore, let n := n_{1} + ⋯ + n_{m} ≥ 1 be the total number of blocks as before. We now state the first result of this paper. Note that for S = (k) we, of course, recover the same formula as found by Brown.

Theorem 1. The number of S-omino towers with n blocks of which n_{i} have width s_{i}, and b blocks in the bottom row, which has to be convex, equals

\binom{n}{n_{1}, …, n_{m}}\binom{−1 + ∑ n_{i}s_{i}}{n − b}.

Summing over all b ∈ [n] we get

\binom{n}{n_{1}, …, n_{m}}\binom{−1 + ∑_{i=1}^{m} s_{i}n_{i}}{n − 1} · _{2}F_{1}(1, 1 − n; 1 + ∑_{i=1}^{m}(s_{i} − 1)n_{i}; −1),

where _{2}F_{1} is the Gaussian hypergeometric function.

Note that the heights of the blocks do not change the result, as we will explain in the next section. In particular, setting S = (1, k) for k ≥ 2 corresponds to stacking kominoes horizontally or vertically. In this paper, we assume that S does not contain duplicate entries for ease of notation. However, the methods would work and yield the same formula. Duplicate entries could be interpreted as having multiple distinguishable versions of dominoes with equal width.

At the end of the paper we turn our attention to convex k-omino towers, which are defined as follows:

Definition 2. A tower is called column-convex or row-convex if all its columns or respectively rows are convex. Further, a tower is called convex if it is both column- and row-convex.

In 2016, Brown calculated the generating function for convex towers and asked whether row-convex towers can be enumerated as well [3, p. 17].

Definition 3. Let g(n) be the number of row-convex k-omino towers made up of n kominoes. We also define f_{ℓ}(n) to be the number of row-convex k-omino towers made up of n k-ominoes resting on a platform of width ℓk. In other words, the blocks on the bottom row need to rest on this platform, but the platform does not count towards the number of blocks.

By adapting a method that Privman and Švrakić used in 1988 to calculate so-called fully directed compact lattice animals [7], we calculate the ordinary generating functions G(z) = ∑_{n=0}^{∞} g(n)z^{n} and F_{ℓ}(z) = ∑_{n=0}^{∞} f_{ℓ}(n)z^{n}.

Theorem 4. We have

G(z) = ∑_{ℓ=1}^{∞} z^{ℓ}F_{ℓ}(z),

where

F_{ℓ}(z) = ((1 + kz)T_{1,ℓ} + (kz^{2} − 1)T_{2,ℓ} + (k − 1)z^{3}T_{3,ℓ})/((k − 1)^{2}z^{5}T_{2,3}
+ (1 − (2k − 1)(1 + z)z + k^{2}z^{3})T_{1,2} + (k − 1)((2k − 1)z − 1)z^{3}T_{1,3}),
T_{s,t}(z) = A_{s}B_{t} − A_{t}B_{s},
A_{ℓ}(z) = ∑_{j=0}^{∞} \frac{z^{ℓj}h_{j}}{(z; z)_{j}^{2}} ,

B_{ℓ}(z) = ∑_{j=0}^{∞} \frac{z^{ℓj}h_{j}}{(z; z)_{j}^{2}} (ℓ + ∑_{m=1}^{j} (1 + \frac{2}{1 − z^{m}} − \frac{1}{1 + (k − 1)z^{m}} ) ), and
h_{j}(z) := z^{j(j+1)} ((1 − k)z; z)_{j} .

The structure of the paper is as follows: In Section 2, we will introduce a few ideas and notation, which we need in later sections. In Section 3, we prove Theorem 1 using ordinary generating functions and the Lagrange inversion formula. In Section 4, we will turn the proof into an explicit bijection and show the connection to generalized Dyck paths [8]. Finally, in Section 5, we prove Theorem 4.

2 Representation of towers as sequences

We can think of domino towers as being built by dropping single dominoes one by one straight down from an infinite height. However, there may be multiple ways of building the same tower. However, there is a unique order as described in Lemma 5.

Lemma 5. For any domino tower there is a unique order b_{1}, …, b_{n} of its dominoes with the following properties:

i) The tower can be built by dropping the dominoes straight down from an infinite height in the order b_{1}, …, b_{n};

ii) For all i ∈ [n − 1], the left border of b_{i+1} is strictly to the left of the right border of b_{i}.

Proof. Consider the set of blocks B, which have no other blocks above them, i.e., could be the last block according to condition i). Let b′ be the left-most block in B and b^{⋆} ∈ B be the block, which is dropped last. Suppose, for a contradiction, that b′ ≠ b^{⋆}. Then all blocks after b′ must be strictly to the left of b′. In particular, b^{⋆} is to the left of b′. This contradicts the definition of b′, and therefore b′ is dropped last and we are done by induction on n.

Hence, instead of enumerating towers, we can enumerate valid sequences of x-coordinates of the left borders of blocks b_{1}, …, b_{n}. We fix x_{1} = 0 to keep this sequence unique. For example, ⟨0, 1, 0, 1, −2, −1, −3, −4⟩ is the sequence for the tower in Figure 2a. We now define the set W_{b} and then prove that it contains exactly those sequences of x-coordinates corresponding to domino towers with b blocks in the bottom row.

Definition 6. For b ≥ 1 we define W_{b} to be the set of sequences ⟨x_{1}, …, x_{n}⟩ with the following properties:

i) We have x_{1} = 0;

ii) For all i ∈ [n − 1] we have x_{i+1} < x_{i} + 2;

iii) There exists a set D ⊂ [n] containing b numbers 1 = d_{1} < d_{2} < ⋯ < d_{b} such that

a) for all j ∈ [b − 1] we have x_{d_{j+1}} + 2 = x_{d_{j}},

b) for all i ∉ D with i < d_{j+1} we have x_{i} ≥ x_{d_{j}},

c) for all i ∉ D with d_{b} < i we have x_{i} + 2 > min_{j<i} x_{j}.

Proposition 7. The set W_{b} contains exactly the sequences corresponding to domino towers with b blocks in the bottom row. In other words, Lemma 5 always produces a sequence in W_{b} and any sequence in W_{b} corresponds to a valid domino tower.

Proof. Given a tower with b blocks in the bottom row, let b_{1}, …, b_{n} be the order produced by Lemma 5. Let ⟨x_{1}, …, x_{n}⟩ be the x-coordinates of the blocks b_{1}, …, b_{n} with x_{1} = 0. We now show that ⟨x_{1}, …, x_{n}⟩ ∈ W_{b} by checking all properties:

i) We have x_{1} = 0 by definition.

ii) From property ii) in Lemma 5 follows x_{i+1} < x_{i} + 2.

iii) Let D be the set of indices of the blocks in the bottom row of the tower. As the tower has b blocks in the bottom row, we have |D| = b. Order D = {d_{1}, …, d_{b}} as d_{1} < ⋯ < d_{b}.

a) It follows immediately from the properties in Lemma 5 that the rightmost block in the bottom row is always dropped first. Hence we have d_{1} = 1. Similarly, we have that the bottom row must be dropped from right to left. Hence block b_{d_{j+1}} is dropped two units to the left of block b_{d_{j}}, because the bottom row is convex by definition. Hence we have x_{d_{j+1}} + 2 = x_{d_{j}}. See Figure 3 for an illustration.

b) If a block b_{i} is not in the bottom row, dropped before b_{d_{j+1}} and x_{i} < x_{d_{j}}, then we cannot anymore drop b_{d_{j+1}} from an infinite height such that b_{d_{j+1}} reaches the bottom row.

c) If we have x_{i} + 2 ≤ min_{j<i} x_{j}, then block b_{i} falls down to the bottom row. This is not possible if i > d_{b}, as at this point the bottom row is complete.

For the other direction, fix a sequence ⟨x_{1}, …, x_{n}⟩ ∈ W_{b} and consider the structure built by dropping blocks at positions x_{1} to x_{n}. We now show that the structure is a valid domino tower, such that the set D from property iii) contains the indices of blocks which land in the bottom row. Clearly, the first block lands in the bottom row. Properties iii. a) and iii. b) guarantee that the block with index d_{j+1} lands in the bottom row and keeps the row convex. In Figure 3 all blocks with indices strictly between d_{j} and d_{j+1} are dropped to the right of the vertical line. Finally, properties ii) and iii. c) guarantee that all other blocks land on top of a previous block.

\begin{matrix}d_{j} \\ d_{j+1} \\ x_{d_{j}} \\ x_{d_{j+1}} \end{matrix}

Figure 3: Illustration of property iii. a) in Definition 6.

Note that by thinking about sequences of x-coordinates instead of towers, it is now clear that the heights of blocks do not change the number of towers. Only the x-coordinates and order matter. Also note that a tower is restricted if and only if the corresponding sequence does not have repeated consecutive entries. Using this insight we can now explain the relation between restricted and unrestricted towers:

Corollary 8 ([4, Cor. 2.3]). The number of unrestricted domino towers made out of n dominoes is equal to 4^{n−1}.

Proof. Consider the sequences in W := ⋃_{b} W_{b} that have no repeated consecutive entries. We know from the introduction that there are 3^{n−1} such sequences of length n. The corresponding ordinary generating function is therefore f(x) = x + 3x^{2} + 9x^{3} + ⋯ = \frac{x}{1−3x}. Now, if we take such a sequence and replace every entry x_{i} by a sequence x_{i}, …, x_{i} of arbitrary positive length, we get a sequence in W, where repeated consecutive entries are allowed, i.e., a sequence corresponding to an unrestricted tower. This process is reversible: To recover the original sequence, we simply delete repeated consecutive entries. See Figure 4 for an illustration. This is an example of a substitution as defined by Flajolet [5, Def. I.14]. In terms of the generating functions this procedure therefore corresponds to replacing x with x + x^{2} + x^{3} + ⋯ = \frac{x}{1−x}. We can now deduce the generating function for the unrestricted domino towers:

\frac{x}{1 − 3x} ⇝ \frac{\frac{x}{1−x}}{1 − 3 · \frac{x}{1−x}} = \frac{x}{1 − 4x},

from which we can read off the number: 4^{n−1}.

Figure 4: Illustration of the substitution of x with \frac{x}{1−x}. The corresponding sequences are ⟨0, 1, 0, 1, −2, −1, −3⟩ and ⟨0, 1, 0, 1, 1, 1, −2, −2, −2, −2, −1, −3⟩ respectively.

We can generalize sequences W_{b} for S-omino towers by also keeping track of the widths ℓ_{i}. For that we redefine W_{b} as follows:

Definition 9. We define W_{b} to be the set of sequences of pairs ⟨(x_{1}, ℓ_{1}), …, (x_{n}, ℓ_{n})⟩ with n ≥ b with the following properties:

i) We have x_{1} = 0;

ii) For all i ∈ [n − 1] we have x_{i+1} < x_{i} + ℓ_{i};

iii) There exists a set D ⊂ [n] containing b numbers 1 = d_{1} < d_{2} < ⋯ < d_{b} such that

a) for j ∈ [b − 1] we have x_{d_{j+1}} + ℓ_{d_{j+1}} = x_{d_{j}},

b) for all i ∉ D with i < d_{j+1} we have x_{i} ≥ x_{d_{j}},

c) for all i ∉ D with d_{b} < i we have x_{i} + ℓ_{i} > min_{j<i} x_{j}.

Proposition 7 still holds analogously, as 2 was merely replaced by the length of the appropriate block. The purposes of the properties remain exactly the same.

As we want to keep track of how many blocks of each length we have used, we define the weight of a sequence t = ⟨(x_{1}, ℓ_{1}), …, (x_{n}, ℓ_{n})⟩ ∈ W as w(t) := z^{n}y_{ℓ_{1}}y_{ℓ_{2}} ⋯ y_{ℓ_{n}}. Hence, the exponent of y_{ℓ} is the number of pairs in t with second entry equal to ℓ and the exponent of z is the total number of pairs. We define the multivariate ordinary generating function of W_{b} with formal variables z, y_{1}, y_{2}, y_{3}, … as W = ∑_{t∈W} w(t). Lemma 5 now immediately generalizes to:

Lemma 10. Fix s_{i}, n_{i} and b as before. Then there is a bijection between such S-omino towers and elements in W_{b} of weight z^{n} ∏_{i} y_{s_{i}}^{n_{i}}. Furthermore, a tower is restricted if and only if there are no repeated consecutive elements in the corresponding sequence in W_{b}.

Proof. Similarly to Lemma 5, the last element of the sequence must correspond to the leftmost block of the tower, among the blocks that do not have any other blocks vertically above it. The statement follows from induction on n.

We will often need to offset sequences of pairs of the form (x, ℓ) horizontally, so we define

⟨(x_{1}, ℓ_{1}), …, (x_{n}, ℓ_{n})⟩ + α := ⟨(x_{1} + α, ℓ_{1}), …, (x_{n} + α, ℓ_{n})⟩.

Also, we define concatenation of two sequences as follows:

⟨a_{1}, …, a_{n}⟩ ∥ ⟨b_{1}, …, b_{m}⟩ := ⟨a_{1}, …, a_{n}, b_{1}, …, b_{m}⟩.

3 Proof using the Lagrange inversion formula

The main tool we use in this section is the following version of the Lagrange inversion formula [2, Section 2.6]. Here, [x^{n}]G(x) denotes the coefficient of x^{n} in the formal power series G(x).

Proposition 11 (The Lagrange inversion formula [2]). Let Y (x) = xΦ(Y), where Φ(Y) is a power series such that Φ(0) ≠ 0. Then for any power series g(Y) and n ≥ 1 we have

[x^{n}]g(Y) = \frac{1}{n}[y^{n−1}]g′(y)(Φ(y))^{n}.

We prove an immediate corollary:

Corollary 12. Let Y (x) = xΦ(Y), where Φ(Y) is a power series such that Φ(0) ≠ 0. Then for any power series h(Y) and n ≥ 1 we have

[x^{n}]x\frac{dY}{dx} h(Y) = [y^{n−1}]h(y)(Φ(y))^{n}.

Proof. Let g(Y) = ∫ h(Y)dY and apply Proposition 11 on g.

[x^{n}]x\frac{dY}{dx} h(Y)

= n · [x^{n}] ∫ \frac{dY}{dx} h(Y)dx

= n · [x^{n}] ∫ h(Y)dY

= [y^{n−1}]h(y)(Φ(y))^{n}.

The idea of the proof is to relate W_{b} to other sets of sequences.

Definition 13. We define U_{⋆} to be the set of sequences of pairs ⟨(x_{1}, ℓ_{1}), …, (x_{n}, ℓ_{n})⟩ with n ≥ 1 with the following properties:

i) We have x_{1} = 0;

ii) For all i > 1 we have x_{i} ≥ 1 and x_{i} < x_{i−1} + ℓ_{i−1}.

We also define U_{1} := Seq_{≥1}(U_{⋆}), the set of sequences that are a concatenation of at least one sequence in U_{⋆}. For convenience we similarly define U := Seq_{≥0}(U_{⋆}) = {⟨⟩} ∪ U_{1}, which also contains the empty sequence.

Lemma 14. Let ⟨(x_{1}, ℓ_{1}), …, (x_{n}, ℓ_{n})⟩ ∈ U_{⋆}. Then there is exactly one choice of indices d_{1}, …, d_{ℓ_{1}} such that

• we have 2 = d_{1} ≤ d_{2} ≤ ⋯ ≤ d_{ℓ_{1}} = n + 1 and

• for all j ∈ [ℓ_{1} − 1] the subsequence ⟨(x_{d_{j}}, ℓ_{d_{j}}), …, (x_{d_{j+1}−1}, ℓ_{d_{j+1}−1})⟩ − α_{j} ∈ U, where α_{j} := ℓ_{1} − j. In particular, if d_{j} < d_{j+1}, then x_{d_{j}} = α_{j}.

Proof. Define the indices d_{j}^{⋆} := min{i ≥ 2 : x_{i} ≤ α_{j}}, where d_{j}^{⋆} = n + 1 if such an i does not exist. We now prove by induction on j that d_{j+1} = d_{j+1}^{⋆} is the unique choice for indices that satisfy the conditions in the lemma. Clearly, for j = 1 we are done, because d_{1} = 2 = d_{1}^{⋆}. Similarly, we have d_{ℓ_{1}} = n + 1 = d_{ℓ_{1}}^{⋆} for j = ℓ_{1} − 1. Now for j ∈ [ℓ_{1} − 2] we can assume the induction hypothesis for j − 1, i.e., that d_{j} = d_{j}^{⋆}. For a contradiction, we consider the cases d_{j+1} > d_{j+1}^{⋆} and d_{j+1} < d_{j+1}^{⋆} separately:

1. If d_{j+1} > d_{j+1}^{⋆} ≥ d_{j}^{⋆} = d_{j}, then by definition of d_{j+1}^{⋆} we have x_{d_{j+1}^{⋆}} ≤ α_{j+1}. However, by definition of U_{⋆} and the fact that ⟨(x_{d_{j}}, ℓ_{d_{j}}), …, (x_{d_{j+1}−1}, ℓ_{d_{j+1}−1})⟩ − α_{j} ∈ U we have x_{d_{j+1}^{⋆}} ≥ α_{j} = α_{j+1} + 1, a contradiction.

2. If d_{j+1} < d_{j+1}^{⋆}, then by definition of d_{j+1}^{⋆} we have x_{d_{j+1}} > α_{j+1}. However, for k := max{p : d_{p} = d_{j+1}} we have d_{k} < d_{k+1} and therefore x_{d_{j+1}} = x_{d_{k}} = α_{k} ≤ α_{j+1}, a contradiction.

Hence d_{j+1} = d_{j+1}^{⋆} and we are done by induction on j.

Example 15. The sequence ⟨(0, 4), (3, 2), (3, 2), (1, 2), (2, 2)⟩ ∈ U_{⋆} corresponds to the tower in Figure 5. The indices d_{i} in this example are: d_{1} = 2, d_{2} = 4, d_{3} = 4 and d_{4} = 6. We have ⟨(3, 2), (3, 2)⟩ − 3 ∈ U drawn in violet, ⟨⟩ − 2 ∈ U, and finally ⟨(1, 2), (2, 2)⟩ − 1 ∈ U drawn in red.

Figure 5: Illustration of Example 15.

We have just shown that every sequence in U_{⋆} can be built by concatenating ⟨(0, ℓ)⟩ with ℓ − 1 sequences in U, offset by ℓ − 1, ℓ − 2, …, 1 respectively and that this construction is unique. Similarly, every sequence in U_{1} can be constructed uniquely using ℓ sequences in U. This motivates the following proposition.

Lemma 16. Let u ∈ U be non-empty. Define ℓ and n such that the first element of u is (0, ℓ) and n = |u|. Then u satisfies the following two properties:

i) There exists a unique pair (x, y) with x ∈ U_{⋆} and y ∈ U such that u = x ∥ y.

ii) There is exactly one choice of indices d_{1}, …, d_{ℓ+1} such that

• we have 2 = d_{1} ≤ ⋯ ≤ d_{ℓ+1} = n + 1 and

• we have u = ⟨(0, ℓ)⟩ ∥ (c_{ℓ−1} + ℓ − 1) ∥ (c_{ℓ−2} + ℓ − 2) ∥ ⋯ ∥ (c_{0} + 0), where c_{0}, …, c_{ℓ−1} in U with |c_{ℓ−i}| = d_{i+1} − d_{i}.

Proof. For part i) suppose that u = ⟨(x_{1}, ℓ_{1}), …, (x_{n}, ℓ_{n})⟩. There are two cases:

1. Suppose that ∀i > 1 x_{i} ≥ 1. In this case u ∈ U_{⋆}. Note that x must be non-empty by definition and if y were non-empty its first element would be (0, ℓ′) for some ℓ′. Hence (u, ⟨⟩) is the unique pair (x, y) such that u = x ∥ y.

2. Suppose that there exists i > 1 with x_{i} = 0 and let i^{⋆} > 1 be the minimal such i. In this case u ∉ U_{⋆}. Hence y cannot be empty and needs to start with (0, ℓ′) for some ℓ′ by definition. By definition of U_{⋆} we must have |x| < i^{⋆}. Hence the pair (⟨(x_{1}, ℓ_{1}), …, (x_{i^{⋆}−1}, ℓ_{i^{⋆}−1})⟩, ⟨(x_{i^{⋆}}, ℓ_{i^{⋆}}), …, (x_{n}, ℓ_{n})⟩) is the unique pair (x, y) such that u = x ∥ y.

This completes the proof of part i). We now prove part ii). By part i) there exists a unique pair (x, y) with x ∈ U_{⋆}, y ∈ U and u = x ∥ y. By Lemma 14 there is exactly one choice of indices d_{1}, …, d_{ℓ} such that 2 = d_{1} ≤ ⋯ ≤ d_{ℓ} = |x| + 1 and for all j ∈ [ℓ − 1] we have c_{ℓ−j} := ⟨(x_{d_{j}}, ℓ_{d_{j}}), …, (x_{d_{j+1}−1}, ℓ_{d_{j+1}−1})⟩ − ℓ + j ∈ U. Also define c_{0} := y and d_{ℓ+1} := n + 1. Then we have

x = ⟨(0, ℓ)⟩ ∥ (c_{ℓ−1} + ℓ − 1) ∥ (c_{ℓ−2} + ℓ − 2) ∥ ⋯ ∥ (c_{1} + 1)

with |c_{ℓ−j}| = d_{j+1} − d_{j} and |c_{0}| = |y| = n − |x| = d_{ℓ+1} − d_{ℓ}. As u = x ∥ y, the result follows.

We also define two other sets of sequences X and V.

Definition 17. We define X_{ℓ} to be the set of sequences

X_{ℓ} := {u − α : 0 ≤ α < ℓ and u ∈ U_{⋆} and u starts with (0, ℓ)}.

Let X := ⋃_{ℓ∈ℕ} X_{ℓ} be the union over all possible lengths ℓ. Further, we define V to be the minimal set with the following properties:

i) We have ⟨⟩ ∈ V;

ii) The set V is closed under the following procedure:

a) Pick any ℓ ∈ ℕ; b) Pick any elements v ∈ V and x ∈ X_{ℓ} starting with, say, (−α, ℓ);

c) Then x ∥ (v − α) ∈ V.

Remark 18. To aid readability of the following arguments, we now describe the towers corresponding to the sets of sequences W_{b}, U_{⋆}, U_{1}, U, X_{ℓ}, X and V informally.

The sequences in W_{b} correspond to the towers we want to enumerate: Towers with b blocks in the bottom row as introduced in Section 1.

The sequences in U_{⋆} correspond to towers with a single block in the bottom row with left edge at x = 0, and no other block crossing the vertical line x = 1. See Figure 6a for an example.

The sequences in U_{1} correspond to towers with a single block in the bottom row with left edge at x = 0, and no other block crossing the vertical line x = 0. See Figure 6b for an example. The set of sequences U equals U_{1} but including an empty tower with 0 blocks.

You can think of sequences in X_{ℓ} as towers in U_{⋆} with a base of length ℓ lying on top of a unit-length platform. The platform is fixed between 0 and 1 and its position relative to the base block corresponds to α in Definition 17. See Figure 6c for an example. The set X is simply the union over all possible lengths of the base.

Similarly to X, you can think of sequences in V as towers in W_{1} with their base lying on top of a unit-length platform. See Figure 6d for an example.

0 1 2 3 4 5 6

(a) The tower corresponding to ⟨(0, 3), (2, 2), (1, 2), (1, 3)⟩ ∈ U_{⋆}.

0 1 2 3 4 5 6

(b) The tower corresponding to

⟨(0, 2), (1, 3), (2, 2), (2, 2), (0, 2)⟩ ∈ U_{1}.

\begin{matrix}−2 \\ −1 \\ 0 \\ 1 \\ 2 \\ 3 \end{matrix}

(c) The tower corresponding to ⟨(−2, 4), (1, 2), (−1, 2), (0, 2)⟩ ∈ X_{4}.

\begin{matrix}−3 \\ −2 \\ −1 \\ 0 \\ 1 \\ 2 \\ 3 \end{matrix}

(d) The tower corresponding to ⟨(−1, 3), (0, 3), (−3, 3), (−1, 2)⟩ ∈ V.

Figure 6: Towers corresponding to sequences in U_{⋆}, U_{1}, X_{4} and V.

Lemma 19. The set W_{b} is related to X and V as follows:

i) For all b ≥ 2 we have a weight-preserving bijection W_{b} ↔ U_{1} × W_{b−1}; ii) We have a weight-preserving bijection W_{1} ↔ U_{⋆} × V.

Proof. Consider any element ⟨(x_{1}, ℓ_{1}), …, (x_{n}, ℓ_{n})⟩ ∈ W_{b}. For b ≥ 2 we know from Definition 9 that there exists an index 1 < d_{2} = min{i ≥ 2 : x_{i} < 0} such that we have

⟨(x_{1}, ℓ_{1}), …, (x_{d_{2}−1}, ℓ_{d_{2}−1})⟩ ∈ U_{1} and ⟨(x_{d_{2}}, ℓ_{d_{2}}), …, (x_{n}, ℓ_{n})⟩ + ℓ_{d_{2}} ∈ W_{b−1}. For b = 1 we let d = min{i ≥ 2 : x_{i} ≤ 0} and d = n + 1 if such an i does not exist. Then

⟨(x_{1}, ℓ_{1}), …, (x_{d−1}, ℓ_{d−1})⟩ ∈ U_{⋆} and ⟨(x_{d}, ℓ_{d}), …, (x_{n}, ℓ_{n})⟩ ∈ V.

In both cases the function has an inverse: Concatenate both parts back together. Example 20. The sequence ⟨(0, 2), (1, 2), (2, 2), (−2, 2), (−1, 2), (−3, 2), (−4, 2)⟩ ∈ W_{2} corresponds to the tower in Figure 7. We have ⟨(0, 2), (1, 2), (2, 2)⟩ ∈ U_{1} drawn in blue, ⟨(−2, 2), (−1, 2)⟩ + 2 ∈ U_{⋆} drawn in violet, and finally ⟨(−3, 2), (−4, 2)⟩ + 2 ∈ V drawn in red.

Figure 7: Illustration of Example 20.

Using the same weights as for W, let U, U_{1}, U_{⋆}, X_{ℓ}, X and V be the multivariate ordinary generating functions of U, U_{1}, U_{⋆}, X_{ℓ}, X and V respectively. Theorem 21. The ordinary generating functions satisfy the following equations:

a) U = 1 + U_{1} and U_{1} = U_{⋆} · U = ∑_{ℓ∈ℕ} zy_{ℓ}U^{ℓ}

b) X_{ℓ} = ℓzy_{ℓ}U^{ℓ−1}, X = ∑_{ℓ∈ℕ} X_{ℓ}, and V = 1 + X · V

c) W_{b} = U_{⋆} · V · U_{1}^{b−1}

d) z \frac{dU_{1}}{dz} = U_{1} + X · z \frac{dU_{1}}{dz}

e) z \frac{dU_{1}}{dz} = U_{1} · V

f) (1 + U_{1}) · W_{b} = U_{1}^{b−1}z \frac{dU_{1}}{dz} Proof. Parts a), b) and c) follow from Lemma 16, Definition 17 and Lemma 19 respectively. For d) note that z \frac{dU_{1}}{dz} is the ordinary generating function of ΘU_{1}, i.e., the set U_{1}, where one element is marked. We can define ΘU_{1} := {(u, k) : u ∈ U_{1}, k ∈ [|u|]}. We now describe a bijection f between ΘU_{1} and U_{1} + X × ΘU_{1}. Let (u, k) ∈ ΘU_{1}. Now note that there are two cases:

1. For k = 1 we simply define f((u, k)) := u ∈ U_{1};

2. For k ≥ 2 we know that by Lemma 16 there exists ℓ ∈ ℕ and sequences c_{0}, …, c_{ℓ−1} ∈ U and 2 = d_{1} ≤ ⋯ ≤ d_{ℓ+1} = n + 1 such that

u = ⟨(0, ℓ)⟩ ∥ (c_{ℓ−1} + ℓ − 1) ∥ (c_{ℓ−2} + ℓ − 2) ∥ ⋯ ∥ (c_{0} + 0),

where |c_{ℓ−i}| = d_{i+1} − d_{i}. As k ≥ 2, there exists exactly one p ∈ [ℓ] such that d_{p} ≤ k < d_{p+1}. Hence (c_{ℓ−p}, k − d_{p} + 1) ∈ ΘU_{1}. Let

x = ⟨(−ℓ + p, ℓ)⟩ ∥ (c_{ℓ−1} + p − 1) ∥ ⋯ ∥ (c_{ℓ−p+1} + 1)
∥ (c_{ℓ−p−1}) ∥ ⋯ ∥ (c_{0} − ℓ + p + 1).

Then x ∈ X_{ℓ}. We define f((u, k)) = (x, (c_{ℓ−p}, k − d_{p} + 1)) ∈ X × ΘU_{1}. This function is invertible, because x stores the variable p, which enables us to undo the shifts and reinsert c_{ℓ−p} into u at the correct position.

For e), note that from b) and d) follows ΘU_{1} = U_{1} × Seq_{≥0}(X) = U_{1} × V. Finally f) follows from a), c) and e).

Proof of Theorem 1. We consider the multivariate power series W_{b} in z, y_{1}, y_{2}, y_{3}, … as a power series in z with coefficients in the ring of multivariate formal power series in y_{1}, y_{2}, y_{3}, … and use Corollary 12:

[z^{n}]W_{b} = [z^{n}]z \frac{dU_{1}}{dz} \frac{U_{1}^{b−1}}{1 + U_{1}}

= [u^{n−1}]\frac{u^{b−1}}{1 + u}( ∑_{i∈[m]} y_{s_{i}}(1 + u)^{s_{i}})^{n}

= [u^{n−b}]\frac{1}{1 + u}( ∑_{i∈[m]} y_{s_{i}}(1 + u)^{s_{i}})^{n}.

Now we also fix the number of occurrences of length s_{i} to be n_{i}:

[y_{s_{1}}^{n_{1}} ⋯ y_{s_{m}}^{n_{m}}][z^{n}]W_{b} = [y_{s_{1}}^{n_{1}} ⋯ y_{s_{m}}^{n_{m}}][u^{n−b}]\frac{1}{1 + u}( ∑_{i∈[m]} y_{s_{i}}(1 + u)^{s_{i}})^{n}

= [u^{n−b}]\frac{1}{1 + u}\binom{n}{n_{1}, …, n_{m}} ∏_{i=1}^{m}(1 + u)^{s_{i}n_{i}}

= [u^{n−b}]\binom{n}{n_{1}, …, n_{m}}(1 + u)^{−1+∑_{i=1}^{m} s_{i}n_{i}}

= \binom{n}{n_{1}, …, n_{m}}\binom{−1 + ∑_{i=1}^{m} s_{i}n_{i}}{n − b}.

Now, summing over all b ∈ [n] we can express the total number of S-omino towers for given (n_{1}, …, n_{m}) in terms of the Gaussian hypergeometric function _{2}F_{1}:

[z^{n}y_{s_{1}}^{n_{1}} ⋯ y_{s_{m}}^{n_{m}}] ∑_{b=1}^{n} W_{b}

= ∑_{b=1}^{n} \binom{n}{n_{1}, …, n_{m}}\binom{−1 + ∑_{i=1}^{m} s_{i}n_{i}}{n − b}

= \binom{n}{n_{1}, …, n_{m}}\binom{−1 + ∑_{i=1}^{m} s_{i}n_{i}}{n − 1} ∑_{b=0}^{n−1} \frac{(n − 1)!(−n + ∑_{i=1}^{m} s_{i}n_{i})!}{(n − 1 − b)!(b − n + ∑_{i=1}^{m} s_{i}n_{i})!}

= \binom{n}{n_{1}, …, n_{m}}\binom{−1 + ∑_{i=1}^{m} s_{i}n_{i}}{n − 1} ∑_{b=0}^{n−1} \frac{(1)_{b}(1 − n)_{b}}{(1 − n + ∑_{i=1}^{m} s_{i}n_{i})_{b}} \frac{(−1)^{b}}{b!}

= \binom{n}{n_{1}, …, n_{m}}\binom{−1 + ∑_{i=1}^{m} s_{i}n_{i}}{n − 1} · _{2}F_{1}(1, 1 − n; 1 + ∑_{i=1}^{m}(s_{i} − 1)n_{i}; −1).

This completes the proof of Theorem 1.

Remark 22. We can find closed formulas for the other sets analogously. For example, for s := ∑ n_{i}s_{i} we have

[y_{s_{1}}^{n_{1}} ⋯ y_{s_{m}}^{n_{m}}][z^{n}]V = \binom{s}{n_{1}, …, n_{m}, s − n}

and

[y_{s_{1}}^{n_{1}} ⋯ y_{s_{m}}^{n_{m}}][z^{n}]U = \frac{1}{s + 1}\binom{s + 1}{n_{1}, …, n_{m}, s + 1 − n}.

Therefore, the number of sequences in U for m = 1, n_{1} = n, s_{1} = 2 is given by the Catalan numbers – sequence \underline{A000108} in the On-line Encyclopedia of Integer Sequences [11].

4 Bijective proof

In this section, we give an explicit bijection between U and generalized Dyck paths and then extend it to a bijection between W_{b} and D_{W_{b}}.

Definition 23. We define the weighted set of generalized Dyck paths D_{U} as the set of all integer sequences ⟨u_{1}, u_{2}, …, u_{N}⟩ with the following properties:

i) We have ∀i ∈ [N] u_{i} ≥ −1;

ii) We have ∀j ∈ [N] ∑_{i<j} u_{i} ≥ 0;

iii) We have ∑_{i∈[N]} u_{i} = −1.

We define the weight function to be

w(⟨u_{1}, u_{2}, …, u_{N}⟩) := ∏_{i∈[N]} \begin{cases}zy_{u_{i}+1}, & if u ≥ 0; \\ 1, & if u = −1. \end{cases}

From the properties above, it follows that any sequence in D_{U} satisfies u_{N} = −1 and ∑_{i∈[N−1]} u_{i} = 0. We include the fixed −1 at the end of each sequence for later convenience. Also note that Rukavicka gave a different definition of generalized Dyck paths [8]. They also consider paths with flaws, which allows the path to fall below 0. When disregarding the fixed −1 at the end of our sequence, our definition corresponds to Dyck paths with 0 flaws as defined by Rukavicka. See Figure 8 for the correspondence between the two definitions: Every −1 corresponds to a vertical step of length 1 and every u_{i} ≥ 1 corresponds to a horizontal step of length u_{i}. Note that our definition allows us to have u_{i} = 0 which would correspond to a horizontal step of length 0.

\begin{matrix}2 \\ −1 \\ 2 \\ −1 \\ −1 \\ −1 \\ 1 \\ −1 \\ −1 \end{matrix}

Figure 8: Correspondence between the sequence ⟨2, −1, 2, −1, −1, −1, 1, −1, −1⟩ ∈ D_{U} on the left and a Dyck path with 0 flaws as defined by Rukavicka on the right.

Lemma 24. We have a weight-preserving bijection f_{U} between U and D_{U}.

Proof. We define f_{U}(⟨⟩) := ⟨−1⟩ and given a sequence u = ⟨(x_{1}, ℓ_{1}), …, (x_{n}, ℓ_{n})⟩ ∈ U_{1}, we define

f_{U}(u) := ( ∥_{p=1}^{n−1} ⟨ℓ_{p} − 1, \underbrace{−1, −1, …, −1}_{x_{p}+ℓ_{p}−1−x_{p+1} times}⟩) ∥ ⟨ℓ_{n} − 1, \underbrace{−1, −1, …, −1}_{x_{n}+ℓ_{n} times}⟩.

Note that f_{U} is clearly weight-preserving, as for every pair (x, ℓ) ∈ u we have got exactly one copy of ℓ − 1 in f_{U}(u), both of which account for the same weight: zy_{ℓ}.

We now show f_{U}(u) ∈ D_{U} by checking all three properties of sequences in D_{U}. For that let ⟨u_{1}, …, u_{N}⟩ = f_{U}(u).

i) By definition we have ∀i u_{i} ≥ −1.

ii) Let k_{1} < k_{2} < ⋯ < k_{n} ∈ [N] be all indices with u_{k_{m}} ≥ 0. By construction of f_{U}(u) it is enough to show property ii) for each j = k_{m}. We have

∑_{i<k_{m}} u_{i} = ∑_{p<m}((ℓ_{p} − 1) − 1 · (x_{p} + ℓ_{p} − 1 − x_{p+1}))

= ∑_{p<m}(−1 · (x_{p} − x_{p+1}))

= x_{m} − x_{1} = x_{m}

≥ 0.

iii) Finally, we have

∑_{i∈[N]} u_{i} = ∑_{p<n} ((ℓ_{p} − 1) − 1 · (x_{p} + ℓ_{p} − 1 − x_{p+1})) + (ℓ_{n} − 1) − 1 · (x_{n} + ℓ_{n})

= ∑_{p<n}(−1 · (x_{p} − x_{p+1})) − x_{n} − 1

= −1.

Therefore f_{U}(u) ∈ D_{U}. The inverse of above function can be described as follows: Fix any sequence v = ⟨u_{1}, …, u_{N}⟩ ∈ D_{U}. Let k_{1} < k_{2} < ⋯ < k_{n} ∈ [N] be all indices with u_{k_{m}} ≥ 0. Note that this determines the value of n. Define f^{−1}(v) := ⟨(x_{1}, ℓ_{1}), …, (x_{n}, ℓ_{n})⟩ with x_{m} := ∑_{i<k_{m}} u_{i} and ℓ_{m} := u_{k_{m}} + 1 for all m ∈ [n]. We now check both properties of sequences in U:

i) We have x_{1} = ∑_{i<1} u_{i} = 0.

ii) For all m > 1 we have x_{m} = ∑_{i<k_{m}} u_{i} ≥ 0, by definition of D_{U}. Also we have

x_{m} − x_{m−1} = ∑_{k_{m−1}≤i<k_{m}} u_{i}
= u_{k_{m−1}} − 1 · (k_{m} − k_{m−1} − 1)
< u_{k_{m−1}} + 1 = ℓ_{m−1}.

Therefore f^{−1}(v) ∈ U.

As we have proven Theorem 21 bijectively, we already know how we can relate sequences in V and W with sequences in U. We now reuse the ideas from the previous section and replace U with D_{U}. Also, we use Raney’s lemma [6] instead of the Lagrange inversion formula.

Lemma 25 (Version of Raney’s lemma). For any sequence of integers ⟨a_{1}, …, a_{m}⟩ with a_{i} ≥ −1 and ∑ a_{i} = −1, there exists exactly one r ∈ [m] with the property that all proper partial sums, or in other words, the totals of all proper prefixes, of ⟨a_{r+1}, …, a_{m}, a_{1}, …, a_{r}⟩ are nonnegative. Note that we must have a_{r} = −1, of course, as a_{r+1} +⋯+a_{m} +a_{1} +⋯+a_{r−1} ≥ 0, but ∑ a_{i} = −1.

We now generalize the idea from Dyck paths to the following sets V and W:

Definition 26. Define

D_{V} := {⟨u_{1}, u_{2}, …, u_{N}⟩ : ∀i u_{i} ≥ −1 and ∑_{i∈[N]} u_{i} = −1 and u_{N} = −1} and

D_{W_{b}} := {⟨u_{1}, u_{2}, …, u_{N}⟩ : ∀i ∈ [b] u_{i} ≥ 0 and ∑_{i∈[N]} u_{i} = −b and u_{N} = −1},

where the weight of a sequence is w(⟨u_{1}, u_{2}, …, u_{N}⟩) := ∏_{i∈[N]} \begin{cases}zy_{u_{i}+1}, & if u ≥ 0; \\ 1, & if u = −1. \end{cases}

We can easily enumerate elements in V and W_{b} with given weight.

Lemma 27. Fix a weight w = z^{n} ∏_{i∈[m]} y_{s_{i}}^{n_{i}} with n = ∑_{i∈[m]} n_{i} and let s = ∑_{i∈[m]} n_{i}s_{i}. Then the number of elements in D_{V} with weight w equals

\binom{s}{n_{1}, n_{2}, …, n_{m}, s − n}.

Also, the number of elements in D_{W_{b}} with weight w equals

\binom{n}{n_{1}, …, n_{m}}\binom{s − 1}{n − b}.

Proof. For the first part, note that every element in D_{V} with weight w has s − n + 1 copies of −1 and total length N = s + 1. The number of sequences follows from the fact that only u_{N} is fixed to be −1.

For the second part, note that every element in D_{W_{b}} with weight w has s − n + b copies of −1 and total length N = s + b. We have u_{N} = −1 and u_{i} ≠ −1 for i ∈ [b]. The number of elements in D_{W_{b}} follows by first considering the order and then the position of the non-negative integers.

Corollary 28. Define

D_{Y} := {(v, k) : v = ⟨u_{1}, u_{2}, …, u_{N}⟩ ∈ D_{U} and k ∈ [N] and u_{k} = −1},

which can be thought of as the set of sequences in D_{U}, where one copy of −1 is marked. Then there is a bijection f_{V_{2}} between D_{Y} and D_{V}.

Proof. Let f_{V_{2}} be the following bijection: Take an element (v, k) ∈ D_{Y} and let f_{V_{2}}((v, k)) := ⟨u_{k+1}, …, u_{N}, u_{1}, …, u_{k}⟩ ∈ D_{V}. In other words, we have moved the marked element of an element in D_{Y} to the end by doing a cyclic rotation of the sequence. This can be undone using Raney’s lemma.

Lemma 29. We have a weight-preserving bijection f_{V_{1}} between V and D_{Y}. Hence, f_{V} := f_{V_{2}} ∘ f_{V_{1}} is a weight-preserving bijection between V and D_{V}.

Proof. We construct an explicit bijection f_{V_{1}} : V → D_{Y} as follows. First, let f_{V_{1}}(⟨⟩) := (⟨−1⟩, 1) and now consider any non-empty v ∈ V. Then by definition ∃ℓ ∈ ℕ, α ∈ {0, …, ℓ− 1}, x ∈ X_{ℓ}, v′ ∈ V, where x starts with (−α, ℓ), such that v = x ∥ (v′ − α). By definition of X_{ℓ} and Lemma 14 we can find c_{1}, …, c_{ℓ−1} ∈ U such that x = (⟨(0, ℓ)⟩ ∥ c_{ℓ−1} + ℓ − 1 ∥ c_{ℓ−2} + ℓ − 2 ∥ ⋯ ∥ c_{1} + 1) − α. Hence we have

v = (⟨(0, ℓ)⟩ ∥ c_{ℓ−1} + ℓ − 1 ∥ c_{ℓ−2} + ℓ − 2 ∥ ⋯ ∥ c_{1} + 1 ∥ v′) − α.

Let (u, k) := f_{V_{1}}(v′). We define k′ := k + 1 + |f_{U}(c_{ℓ−1})| + ⋯ + |f_{U}(c_{α+1})| and

f_{V_{1}}(v) := (⟨ℓ − 1⟩ ∥ f_{U}(c_{ℓ−1}) ∥ ⋯ ∥ f_{U}(c_{α+1}) ∥ u ∥ f_{U}(c_{α}) ∥ ⋯ ∥ f_{U}(c_{1}), k′).

Note that k′ is chosen such that the marked element in u remains marked.

Lemma 30. We have a weight-preserving bijection f_{W} between W_{b} and D_{W_{b}}.

Proof. From Lemma 19 we know that we can split an element w ∈ W_{b} into two parts. For b = 1 we have w = u ∥ v, where u ∈ U_{⋆} and v ∈ V. We define f_{W} (w) := f_{U}(u) ∥ f_{V} (v). For b ≥ 2 we have w = u ∥ w′ − ℓ, where u ∈ U_{1}, w′ ∈ W_{b−1} and u starts with (0, ℓ). Here we could choose to define f_{W} (w) := f_{U}(u) ∥ f_{W} (w′), but it would change the definition of D_{W} and make its enumeration more complicated. So we instead proceed as follows: Let f_{W} (w′) = ⟨a_{1}, …, a_{n}⟩. Then define f_{W} (w) := ⟨a_{1}, …, a_{b−1}⟩ ∥ f_{U}(u) ∥ ⟨a_{b}, …, a_{n}⟩. We can undo the function in both cases, as we know that the sequence f_{U}(u) sums to −1. The bijection f_{W} is weight-preserving, because f_{U} and f_{V} are.

We would like to conclude the section by providing examples of the bijection and show how the sequences are related to the towers described in Remark 18. Figure 9 shows the idea of the bijection for D_{U}. The labels on the blocks correspond to the order of Lemma 5. The different colors correspond to the decomposition from Lemma 16.

As U corresponds to towers with no overhang to the left, the sequences in D_{U} are Dyck paths. To deal with overhang we use Lemma 29 to mark an element −1 in the sequences.

\begin{matrix}1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 1 \\ 1 \\ 2 \\ −1 \\ −1 \\ 0 \\ −1 \\ −1 \\ 1 \\ 1 \\ −1 \\ −1 \\ −1 \end{matrix}

Figure 9: Illustration of the bijection f_{U} with the element ⟨1, 1, 2, −1, −1, 0, −1, −1, 1, 1, −1, −1, −1⟩ ∈ D_{U}.

\begin{matrix}2 \\ −1 \\ −1 \\ −1 \end{matrix} ; (a) (⟨2, −1, −1, −1⟩, 3) ∈ D_{Y}.  \begin{matrix}1 \\ 2 \\ −1 \\ −1 \\ −1 \\ −1 \end{matrix} ; (b) (⟨1, 2, −1, −1, −1, −1⟩, 4) ∈ D_{Y}.

Figure 10: Illustration of the bijection f_{V_{1}}.

The position of the marked element then determines the overhang to the left. See Figures 10 and 11 for an illustration, where the marked element is colored dark blue. Figure 10 shows two examples of the bijection f_{V_{1}}, where in Figure 10b the result of Figure 10a is used.

Figure 11 shows a complete example of f_{V}. Note that the result from Figure 10b is used.

Finally, see Figure 12 for an example of the bijection between W_{2} and D_{W_{2}}. The violet blocks are in U, the blue blocks in U_{⋆} and the red blocks in V. Note that the result of f_{V_{2}} applied to Figure 10b is used.

5 Row-convex k-omino towers

In this section, we consider row-convex k-omino towers, as defined in Definition 2. By conditioning on the width of the bottom row, we see that f and g are related by the equation

g(n) = ∑_{ℓ=1}^{n} f_{ℓ}(n − ℓ), or equivalently G(z) = ∑_{ℓ=1}^{∞} z^{ℓ}F_{ℓ}(z).

\begin{matrix}1 \\ 1 \\ −1 \\ −1 \\ 1 \\ 2 \\ −1 \\ −1 \\ −1 \\ −1 \\ −1 \\ −1 \\ 1 \\ 1 \\ −1 \\ −1 \\ 1 \\ 2 \\ −1 \\ −1 \end{matrix}

Figure 11: Illustration of the bijection f_{V} := f_{V_{2}} ∘ f_{V_{1}} with the element ⟨−1, −1, 1, 1, −1, −1, 1, 2, −1, −1⟩ ∈ D_{V}.

\begin{matrix}1 \\ 1 \\ 1 \\ −1 \\ −1 \\ 1 \\ −1 \\ −1 \\ −1 \\ −1 \\ −1 \\ 1 \\ 2 \\ −1 \\ −1 \end{matrix}

Figure 12: Illustration of the bijection f_{W} with the element ⟨1, 1, 1, −1, −1, 1, −1, −1, −1, −1, −1, 1, 2, −1, −1⟩ ∈ D_{W_{2}}.

To improve readability, from now on we write F_{ℓ}(z) as F_{ℓ} and similarly for G(z) and h_{n}(z), α(z) and β(z) which are yet to be introduced. If the platform has width kℓ and the bottom row consists of i blocks, then there are (ℓ + 2 − i)k − 1 positions the blocks in the row above could take such that the row is convex and they do not fall off the sides. This can be seen by an argument similar to the one given by Brown [3, Prop. 2.5]. We immediately find the recurrence:

f_{ℓ}(n) = ∑_{i=1}^{ℓ+1} ((ℓ + 2 − i)k − 1)f_{i}(n − i), for n ≥ 1, where we define  (1)
f_{ℓ}(0) = 1 and f_{ℓ}(n) = 0, for n < 0.

We now simplify this recurrence relation of f and rewrite it in terms of the generating functions F_{ℓ}.

Lemma 31. The generating functions F_{ℓ} satisfy the following recurrence relation and boundary conditions:

F_{ℓ+2} − 2F_{ℓ+1} + F_{ℓ} = z^{ℓ+2}F_{ℓ+2} + (k − 1)z^{ℓ+3}F_{ℓ+3},  (2)
\begin{aligned}F_{1} & = 1 + (2k − 1)zF_{1} + (k − 1)z^{2}F_{2}, \\ F_{2} & = 1 + (3k − 1)zF_{1} + (2k − 1)z^{2}F_{2} + (k − 1)z^{3}F_{3}. \end{aligned}  (3)

Proof. First, we calculate

f_{ℓ+1}(n) − f_{ℓ}(n) = (k − 1)f_{ℓ+2}(n − ℓ − 2) + k ∑_{i=1}^{ℓ+1} f_{i}(n − i)

and then use this result twice as follows:

f_{ℓ+2}(n) − 2f_{ℓ+1}(n) + f_{ℓ}(n)
= (f_{ℓ+2}(n) − f_{ℓ+1}(n)) − (f_{ℓ+1}(n) − f_{ℓ}(n))
= (k − 1)f_{ℓ+3}(n − ℓ − 3) + f_{ℓ+2}(n − ℓ − 2).

The corresponding recurrence in terms of F_{ℓ} is

F_{ℓ+2} − 2F_{ℓ+1} + F_{ℓ}

= ∑_{n=0}^{∞} (f_{ℓ+2}(n) − 2f_{ℓ+1}(n) + f_{ℓ}(n))z^{n}

= ∑_{n=0}^{∞} (f_{ℓ+2}(n − ℓ − 2) + (k − 1)f_{ℓ+3}(n − ℓ − 3))z^{n}

= z^{ℓ+2}F_{ℓ+2} + (k − 1)z^{ℓ+3}F_{ℓ+3}.

The boundary conditions are obtained by setting ℓ = 1 and ℓ = 2 in (1).

To solve the recurrence (2), we first guess that there is a solution of the form

∑_{j=0}^{∞} \frac{z^{ℓj}h_{j}(z)}{(z; z)_{j}^{2}}

and then determine an h_{j}(z) such that the recurrence relation holds. Here, (a; q)_{n} = ∏_{i=0}^{n−1}(1 − aq^{i}) denotes the q-Pochhammer symbol. That this method works is not surprising: In 1988, Privman and Švrakić successfully found an exact generating function for fully directed compact lattice animals using this approach [7]. The two problems are related, Figure 13: Illustration of the bijection between restricted rowconvex domino towers and fully directed compact lattice animals

as there is a bijection between fully directed compact lattice animals and restricted rowconvex domino towers. The number of dominoes in the bottom row maps to the number of compact sources of the directed animal. For an illustration of this bijection see Figure 13.

After adapting their method we end up with two solutions A_{ℓ} and B_{ℓ}, which we now check:

Lemma 32. Two solutions of (2) are:

A_{ℓ} := ∑_{j=0}^{∞} \frac{z^{ℓj}h_{j}}{(z; z)_{j}^{2}} and

B_{ℓ} := ∑_{j=0}^{∞} \frac{z^{ℓj}h_{j}}{(z; z)_{j}^{2}} (ℓ + ∑_{m=1}^{j} (1 + \frac{2}{1 − z^{m}} − \frac{1}{1 + (k − 1)z^{m}} )), where
h_{j} := z^{j(j+1)} ((1 − k)z; z)_{j} .

Proof. First, we calculate the ratio

\frac{h_{j}}{h_{j−1}} = \frac{z^{j(j+1)}}{z^{(j−1)j}} \frac{∏_{i=1}^{j}(1 − (1 − k)z^{i})}{∏_{i=1}^{j−1}(1 − (1 − k)z^{i})} = z^{2j}(1 + (k − 1)z^{j}).

Then we show that the recurrence holds

A_{ℓ+2} − 2A_{ℓ+1} + A_{ℓ}

= ∑_{j=0}^{∞} \frac{h_{j}}{(z; z)_{j}^{2}} (z^{(ℓ+2)j} − 2z^{(ℓ+1)j} + z^{ℓj})

= ∑_{j=1}^{∞} \frac{h_{j−1} (z^{2j} + (k − 1)z^{3j})}{(z; z)_{j}^{2}}z^{ℓj} (1 − z^{j})^{2}

= ∑_{j=1}^{∞} \frac{h_{j−1} (z^{(ℓ+2)j} + (k − 1)z^{(ℓ+3)j})}{(z; z)_{j−1}^{2}}

= ∑_{j=0}^{∞} \frac{h_{j} (z^{(ℓ+2)(j+1)} + (k − 1)z^{(ℓ+3)(j+1)})}{(z; z)_{j}^{2}}

= z^{ℓ+2}A_{ℓ+2} + (k − 1)z^{ℓ+3}A_{ℓ+3}.

Similarly, we can prove that B_{ℓ} is a solution. The interested reader can find the detailed calculation for this in the appendix.

We have yet to find a solution that satisfies the boundary conditions. A suitable linear combination of A_{ℓ} and B_{ℓ}, however, does the trick. In general, setting F_{ℓ} = αA_{ℓ} + βB_{ℓ} and solving the simultaneous equations c_{1}F_{1} + c_{2}F_{2} + c_{3}F_{3} = 1 and d_{1}F_{1} + d_{2}F_{2} + d_{3}F_{3} = 1 for α and β yields after some algebra:

α = ( − (c_{1} − d_{1})B_{1} − (c_{2} − d_{2})B_{2} − (c_{3} − d_{3})B_{3})/d,
β = ((c_{1} − d_{1})A_{1} + (c_{2} − d_{2})A_{2} + (c_{3} − d_{3})A_{3})/d, where
d = (c_{1}A_{1} + c_{2}A_{2} + c_{3}A_{3})(d_{1}B_{1} + d_{2}B_{2} + d_{3}B_{3})
− (c_{1}B_{1} + c_{2}B_{2} + c_{3}B_{3})(d_{1}A_{1} + d_{2}A_{2} + d_{3}A_{3}).

Now setting

c_{1} = 1 − (2k − 1)z,  c_{2} = −(k − 1)z^{2},  c_{3} = 0,
d_{1} = −(3k − 1)z,  d_{2} = 1 − (2k − 1)z^{2},  d_{3} = −(k − 1)z^{3}

as in (3) and plugging α and β into F_{ℓ} = αA_{ℓ} + βB_{ℓ} yields the result of Theorem 4. Remark 33. Note that for k = 1 the sequence (g(n))_{n≥1} = 1, 2, 4, 8, 15, … is given by sequence \underline{A001523}. It also counts the weakly unimodal compositions of n. Similarly, f_{ℓ}(n) counts the number of unimodal ℓ-tuples of positive integers summing to n + ℓ. For example the sequence (f_{3}(n))_{n≥0} is given by sequence \underline{A000212}. For k = 2, the sequence (g(n))_{n≥1} = 1, 4, 16, 61, 225, … is given by sequence \underline{A338531} in the On-line Encyclopedia of Integer Sequences [11].

6 Comments and open questions

1. One might reconsider the restricted problem. Using a substitution similar to the one mentioned in Corollary 8, we can deduce the generating function for the restricted case, by replacing zy_{i} with \frac{zy_{i}}{1+zy_{i}}. However, is it possible to find a direct way of enumerating the generating function of restricted towers and a closed formula for its coefficients?

2. In this paper, we have counted S-omino towers and row-convex towers. Is it possible to combine the two ideas and count row-convex S-omino towers?

7 Acknowledgments

I would like to thank my supervisor Anusch Taraz and Julian Großmann for many helpful comments and suggestions regarding both content and presentation.

Additional thanks go to the anonymous referee for carefully reading the manuscript and their many valuable comments.

Appendix

For the sake of completeness, we show that B_{ℓ} is a solution to (2). B_{ℓ+2} − 2B_{ℓ+1} + B_{ℓ}

= ∑_{j=0}^{∞} \frac{h_{j}}{(z; z)_{j}^{2}} ((ℓ + 2)z^{(ℓ+2)j} − 2(ℓ + 1)z^{(ℓ+1)j} + ℓz^{ℓj}

+ (z^{(ℓ+2)j} − 2z^{(ℓ+1)j} + z^{ℓj}) ∑_{m=1}^{j} (1 + \frac{2}{1 − z^{m}} − \frac{1}{1 + (k − 1)z^{m}} ) )

= ∑_{j=1}^{∞} \frac{h_{j}}{(z; z)_{j}^{2}} z^{ℓj} (1 − z^{j})^{2} (2 + ℓ − \frac{2}{1 − z^{j}} + ∑_{m=1}^{j} (1 + \frac{2}{1 − z^{m}} − \frac{1}{1 + (k − 1)z^{m}} ) )

= ∑_{j=1}^{∞} \frac{h_{j−1} (z^{(ℓ+2)j} + (k − 1)z^{(ℓ+3)j})}{(z; z)_{j−1}^{2}}(2 + ℓ − \frac{2}{1 − z^{j}}

+ ∑_{m=1}^{j} (1 + \frac{2}{1 − z^{m}} − \frac{1}{1 + (k − 1)z^{m}} ) )

= ∑_{j=1}^{∞} \frac{h_{j−1} (z^{(ℓ+2)j} + (k − 1)z^{(ℓ+3)j})}{(z; z)_{j−1}^{2}}(3 + ℓ − \frac{1}{1 + (k − 1)z^{j}}

+∑_{m=1}^{j−1}(1 + \frac{2}{1 − z^{m}} − \frac{1}{1 + (k − 1)z^{m}} ))

= ∑_{j=1}^{∞} \frac{h_{j−1}}{(z; z)_{j−1}^{2}} ((ℓ + 2)z^{(ℓ+2)j} + (k − 1)(ℓ + 3)z^{(ℓ+3)j}

+ (z^{(ℓ+2)j} + (k − 1)z^{(ℓ+3)j}) ∑_{m=1}^{j−1} (1 + \frac{2}{1 − z^{m}} − \frac{1}{1 + (k − 1)z^{m}} ) )

= ∑_{j=0}^{∞} \frac{h_{j}}{(z; z)_{j}^{2}} ((ℓ + 2)z^{(ℓ+2)(j+1)} + (k − 1)(ℓ + 3)z^{(ℓ+3)(j+1)}

+ (z^{(ℓ+2)(j+1)} + (k − 1)z^{(ℓ+3)(j+1)}) ∑_{m=1}^{j} (1 + \frac{2}{1 − z^{m}} − \frac{1}{1 + (k − 1)z^{m}} ) )

= z^{ℓ+2}B_{ℓ+2} + (k − 1)z^{ℓ+3}B_{ℓ+3}.

References

[1] F. Ardila, Algebraic and geometric methods in enumerative combinatorics, in M. Bóna, ed., Handbook of Enumerative Combinatorics, CRC Press, 2015, pp. 3–172.

[2] H. Prodinger, Analytic Methods, in M. Bóna, ed., Handbook of Enumerative Combinatorics, CRC Press, 2015, pp. 173–252.

[3] T. M. Brown, Convex domino towers, J. Integer Sequences 20 (2017), Article 17.3.1.

[4] T. M. Brown, On the enumeration of k-omino towers, Discrete Math. 340 (2017), 1319–1326.

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

[6] I. M. Gessel, Lagrange inversion, J. Combin. Theory Ser. A 144 (2016), 212–249.

[7] V. Privman and N. M. Švrakić, Exact generating function for fully directed compact lattice animals, Phys. Rev. Lett. 60 (1988), 1107–1109.

[8] J. Rukavicka, On generalized Dyck paths, Electron. J. Combin. 18 (2011), Article P40.

[9] G. Viennot, Problèmes combinatoires posés par la physique statistique, Astérisque 121-122 (1985), 225–246.

[10] D. Zeilberger, The amazing 3^{n} theorem and its even more amazing proof [Discovered by Xavier G. Viennot and his École Bordelaise gang], Personal J. of Shalosh B. Ekhad and

Doron Zeilberger, 2012. Available at https://sites.math.rutgers.edu/~zeilberg/
mamarim/mamarimhtml/bordelaise.html.

[11] N. J. A. Sloane, ed., The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2020.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: domino, bijection, convex polyomino, Lagrange inversion.

(Concerned with sequences \underline{A000108}, \underline{A001523}, \underline{A000212}, and \underline{A338531}.)

Received November 1 2020; revised versions received November 9 2020; February 10 2021; February 15 2021. Published in Journal of Integer Sequences, February 16 2021.

Return to Journal of Integer Sequences home page.