Enumeration of Border-Strip Decompositions and Weil-Petersson Volumes

Per Alexandersson Department of Mathematics Royal Institute of Technology SE-100 44 Stockholm Sweden

             per.w.alexandersson@gmail.com

Linus Jordan Department of Mathematics EPFL 1015 Lausanne Switzerland

                linus.jordan@bluewin.ch

Abstract

We describe an injection from border-strip decompositions of certain diagrams to permutations. This allows us to provide enumeration results as well as q-analogues of enumeration formulas. Finally, we use this injection to prove a connection between the number of border-strip decompositions of the n × 2n rectangle and the Weil-Petersson volume of the moduli space of an n-punctured Riemann sphere.

1 Introduction and overview of results

Border-strip tableaux have a rich history, originating with the celebrated Murnaghan-Nakayama rule [5, 6], which provides a combinatorial formula for computing character values in the symmetric group. It is given as a signed sum over border-strip tableaux, but the sign only depends on the border-strip decomposition, i.e., the “unlabeled version” of the tableaux. This motivates us to study border-strip decompositions. Note that there is a hook-formula for enumerating border-strip tableaux given by Fomin and Lulov [2] but less study has been devoted to enumerating border-strip decompositions. Even determining if a region can be tiled by n-strips is non-trivial and sometimes NP-complete, see the papers by Beauquier et al., and Pak [1, 7].

We introduce a family of diagrams called simple diagrams, which have particularly nice properties with respect to enumeration. These diagrams are parameterized by a binary sequence and the strip size. In particular, we show that certain normalized enumerations grow as a polynomial in n — the size of the strips.

We show that border-strip tableaux and border-strip decompositions of simple diagrams are in bijection with certain classes of permutations, see Proposition 13 and Corollary 19. This allows us to study a certain q-analogue of border-strip decompositions which generalize the classical inversion-statistic on permutations. For example, in Corollary 28, we give the formula

∑_{w∈{r,c}^{k}} ∑_{D∈BSD(w,n)} q^{inv(D)} = [n + 1]_{q}^{k}[n]_{q}!

where the first sum is over all binary sequences of length k (defining a simple diagram), and BSD(w, n) is the set of border-strip decompositions with strips of size n and diagram determined by (w, n).

In Proposition 21 we give an efficient way to compute the number of border-strip decompositions of simple diagrams, as a function of n. This allows us to prove that “straighter” simple diagrams admit a larger number of border-strip decompositions, see Theorem 29 and the maximum is attained for rectangles. In contrast, in Proposition 14 we show that whenever n ≥ k, all these diagrams admit the same number of border-strip tableaux.

Finally, we give a new interpretation of the sequence \underline{A115047} in the OEIS. We show that these numbers count tilings of a n × 2n-rectangle with strips of size n, thus providing a new simple combinatorial interpretation of certain Weil-Petersson volumes. We cannot give an intuitive explanation for this curious connection and it invites for further research.

2 Enumeration of border-strip decomposition

We first give simplified definitions of border strip tableaux and decompositions which are sufficient for the purpose of this article — for a thorough background see Richard Stanley’s book [9].

2.1 Preliminaries

A diagram is formally defined as a set of integer coordinates

{(i, j) ∈ ℕ^{2} : μ_{i} ≤ j ≤ λ_{i}},

where λ and μ are integer partitions such that μ_{i} ≤ λ_{i} for all i = 1, 2, . . .. We refer the coordinates in the diagram as boxes. For example, λ = (4, 3, 2, 2, 2), μ = (2, 1, 1) is illustrated as

13 14 22 23 32 41 42 51 52

where ij is written in the box (i, j). A border-strip or strip for short of a diagram is a subset of boxes

(a_{1}, b_{1}), (a_{2}, b_{2}), …, (a_{n}, b_{n})

such that for every i = 1, …, n − 1,

a_{i} = a_{i+1} and b_{i} − 1 = b_{i+1}  or  a_{i} + 1 = a_{i+1} and b_{i} = b_{i+1}.

A tableau T is map T : D → ℕ from a diagram to the set of natural numbers. A tableau is illustrated by writing T (i, j) in the box (i, j). A border-strip tableau^{1} is a tableau T such that rows and columns are weakly increasing and for all i, the set of boxes T^{−1}(i) is a borderstrip. In this paper, we shall only consider border-strip tableaux such that for some m and n,

|T^{−1}(1)| = |T^{−1}(2)| = ⋯ = |T^{−1}(m)| = n and |T^{−1}(j)| = 0 for all j > m.

Hence, each strip of T has size n and T is a border-strip tableau with strip size n. Let BST(D, n) denote the set of border-strip tableaux with strip size n and underlying diagram D. For our purposes, D could be any parameterization of a diagram, in our case we are going to use binary words — see Definition 2 below.

A border-strip decomposition with strip size n is a set-partition of a diagram into borderstrips where all the border-strip are of size n. Analogously, BSD(D, n) denotes the set of border-strip decompositions of the diagram D. Observe that every border strip tableau T in BST(D, n) defines a border-strip decomposition in BSD(D, n), as we shall see in the following example.

Example 1. The following tableau is an element in BST(6 × 5, 5), where 6 × 5 denotes a rectangle of dimension 6 × 5. The corresponding border-strip decomposition with the strips indicated by the colors is shown on the right.

1 1 1 1 2 1 2 2 2 2 3 3 4 4 6 3 4 4 5 6 3 4 5 5 6 3 5 5 6 6  (1)

1Also known as rim-hook tableau.

It is straightforward to verify that for each border-strip decomposition there is at least one border-strip tableau, so we get |BST(D, n)| ≥ |BSD(D, n)| for any diagram D and natural number n. On the other hand, we obtain a border-strip decomposition from a border-strip tableau by “forgetting the numbers” so we have that BST(D, n) = ∅ ⟺ BSD(D, n) = ∅.

Let B be a border-strip, which is a subset of boxes (i, j) (row-index, column-index). It is easy to verify that the set

{j − i : (i, j) ∈ B}

is of the form a, a + 1, …, b for some a < b where b − a + 1 is the number of boxes in B. Define the head, H(B), of a border-strip to be the unique box where j − i is maximal, and its tail, T (B), to be the unique box which minimizes j − i. In (2), the head and tail boxes have been marked.

H ; T  (2)

2.2 Simple diagrams and permutations

In this subsection, we introduce a natural family of diagrams with particularly nice properties. We first describe a bijection between border-strip decompositions of simple diagrams and certain permutations.

Definition 2. A simple diagram is parameterized by (w, n) where w is a finite sequence of elements in {r, c} and n is a natural number. The family of simple diagrams is defined recursively as follows:

• If w = ∅, then (w, n) is the n × n-square.

• The diagram (cw, n) is obtained from (w, n) by adding an additional column of size n on the left, such that the bottom-most square of the new column is in the bottom-most row of (w, n).

• The diagram (rw, n) is obtained from (w, n) by adding an additional row of size n on the bottom such that the left-most square of the new row is in the leftmost column of (w, n).

Let BSD(w, n) denote the set of border-strip decompositions of (w, n) with strips of size n, and BST(w, n) denote the set of border-strip tableaux of (w, n) with strips of size n.

Example 3. The simple diagram determined by (rcrcc, 2) is the diagram on the left below. We can see how (rcrcc, 2) is constructed from the 2 × 2 square by adding successively the blue, red, green, yellow, and gray boxes to a 2 × 2 square.

                                 c c c c c c r r r r    4 5 6 2 3 1  (3)

Given a simple diagram D, the shape (w, n) can be recovered as follows. First, n is given by the smallest number of boxes in a single row, or column. Secondly, k can be found by using the fact that n^{2} + kn is the total number of boxes in the diagram. We then start in the nth square in the bottom-most row of D and follow the outline of the diagram by going right if possible and up otherwise, until k + 1 squares have been visited. The path in the example above is up, right, up right right, which correspond to the word rcrcc.

Definition 4. In a fixed border-strip decomposition, a border-strip B_{a} is above a borderstrip B_{b} if there is a box a of B_{a}, and a box b of B_{b} such that the column index of a is smaller or equal to the column index of b, and the row index of a is smaller or equal to the row index of b. If B_{a} is above B_{b}, we say that B_{b} is below B_{a}.

A border-strip B_{a} is inner to a border-strip B_{b} if there exists a sequence B_{a} = B_{1}, B_{2}, …, B_{k} = B_{b} such that B_{i} is above B_{i+1} for all i = 1, 2, …, k − 1. It means the relation inner is the transitive closure of the relation above. If B_{a} is inner to B_{b}, then B_{b} is outer to B_{a}. Two border strips B_{a} and B_{b} are comparable, if B_{a} is inner or outer to B_{b}.

Remark 5. If B_{1} is above B_{2}, it implies B_{1} must contain a smaller number than B_{2} in any border-strip tableau. This observation proves that the transitive closure of “above” is well-defined.

Example 6. An example of a border-strip decomposition in BSD(ccrcc, 3) is given in (4). The blue strip is above the red one and the red strip is above the yellow one. Hence the blue strip is inner to the yellow strip and the blue and yellow strips are comparable. Note that the blue strip is neither above nor below the yellow strip.

(4)

Definition 7 (Diagonal labeling). For a sequence w of length k, we label the diagonals of the simple diagram (w, n) from n + k to 1, starting from the top right corner as shown in the example below for (crrc, 3):

4 5 6 7 3 4 5 6 1 2 3 4 5 1 2 3 1 2 Lemma 8. Let w be a sequence of length k. Then for any decomposition B ∈ BSD(w, n) there is a unique head in each diagonal from 1 to n+k and the positions of the heads uniquely determine B.

Proof. We show that the positions of the heads uniquely determine the decomposition by processing the diagonals one by one and iteratively prolonging the strips, starting from diagonal n + k.

First, the single box in diagonal n + k must be the head of some strip. For diagonal i with k < i < n + k there is one box more in diagonal i compared to diagonal i + 1. All strips we already encountered have fewer than n boxes and must continue in diagonal i+1. Hence, there is exactly one head in diagonal i. Moreover, the position of the head H in diagonal i determines the continuation of the strips encountered as shown in the following figure:

a ; b ; H c ; d  _{⟶}  a ; b ; H c ; d  (5)

For i ≤ k there is exactly one strip ending in diagonal i + 1. Furthermore, diagonals i and i + 1 have the same size, therefore there must be exactly one head in diagonal i. Once the heads have been placed there are n − 1 boxes left in diagonal i and n − 1 strips which must have a box in diagonal i. Consequently there is at most one way to extend the strips to diagonal i.

The diagonals below diagonal 1 decrease in size by one in each step and it is easy to see that there cannot be any heads below diagonal 1. There is a unique way to extend the partial border-strip decomposition from diagonal 1 to the entire diagram.

Given a border-strip decomposition of a simple diagram, the unique strip with head in diagonal i is referred to as strip i.

Proposition 9. Let (w, n) be a simple diagram with w of length k and B ∈ BSD(w, n). If 1 ≤ i < j ≤ n + k and j − i ≤ n then strip i and strip j in B are comparable.

Proof. The tail of j is at most one diagonal higher than the head of i. From this observation, it follows that the strips must be comparable.

We notice in Lemma 8 that the positions of the heads of the strips determine the borderstrip decomposition uniquely. The next definition and proposition encodes the placements of the heads as a permutation with certain restrictions, giving an alternative description of border-strip tableaux of simple diagrams. Further down, we add additional restrictions so that the resulting set of permutations is in bijection with the set of border-strip decompositions of simple diagrams.

Definition 10. Define ψ : BST(w, n) → S_{n+k} so that ψ(T) = σ where σ(j) is the diagonal containing the head of the strip labeled with j. Let BSP(w, n) ⊆ S_{n+k} denote the image of BST(w, n) under ψ.

Example 11. Consider the following T ∈ BST(ccc, n). The strip labeled 1 has its head in diagonal 3, thus ψ(T)(1) = 3. The strip labeled 2 has its head in diagonal 2, so ψ(T)(2) = 2.

T = 1 1 1 3 3 4 2 2 2 3 4 4 5 5 5 6 6 6  and  ψ(T) = [3, 2, 5, 6, 1, 4] ∈ S_{6}.  (6)

Proposition 12. The map ψ is injective. In particular, ψ : BST(w, n) → BSP(w, n) is a bijection.

Proof. A permutation σ ∈ BSP(w, n) determines the values of the heads, and thus the set of values of all the boxes in each diagonal. As the entries in diagonals have to be increasing, σ uniquely determine the corresponding border-strip tableau.

Proposition 13. Let w = (w_{1}, …, w_{k}) be a sequence of length k. A permutation σ ∈ S_{n+k} is in BSP(w, n) if and only if for all i with 1 ≤ i ≤ k we have

(a) σ^{−1}(i) < σ^{−1}(n + i) whenever w_{i} = c, and

(b) σ^{−1}(i) > σ^{−1}(n + i) whenever w_{i} = r.

Proof. We construct the tableau T from σ ∈ BSP(w, n) by starting from the last diagonal. By definition, the unique head in diagonal i must have value σ^{−1}(i) in T. If k < i ≤ n + k then diagonal i has one box more than diagonal i + 1 and it is always possible to extend the partial border-strip tableau one diagonal further in a unique fashion as in Lemma 8.

However, when 1 ≤ i ≤ k we need to take w_{i} into consideration. If w_{i} = c then diagonals i and i + 1 are arranged as follows.

We observe that the new strip starting in diagonal i must be above the strip ending in diagonal i + 1 (and starting in diagonal n + i). Hence, it must be filled with a smaller number in T, so we must have σ^{−1}(i) < σ^{−1}(n + i).

If w_{i} = r diagonals i and i + 1 are arranged as follows.

Analogously to the previous argument, the new strip starting in diagonal i must be below strip n + i and thus σ^{−1}(i) > σ^{−1}(n + i).

2.3 Counting border-strip tableaux and decompositions

We now have the necessary setup to obtain some enumerative results.

Proposition 14. For a sequence w of length k ≤ n,

|BST(w, n)| = 2^{−k}(n + k)!.

In particular, the number of border-strip tableaux only depends on the length of the sequence for n ≥ k.

Proof. Recall from Proposition 12 that |BST(w, n)| = |BSP(w, n)|. From conditions (a) and (b) in Proposition 13 we know that the w determines the relative order of the strips i and n + i for every i = 1, 2, …, k. Whenever n ≥ k, these pairs are disjoint. As there are no further restrictions on the (n + k)! possible permutations, |BSP(w, n)| = 2^{−k}(n + k)!.

Proposition 14 cannot be strengthened to the case k > n, as the count |BST(w, n)| in this case might depend on w.

Corollary 15. For every permutation σ ∈ S_{n+k} there is exactly one sequence w of length k such that σ ∈ BSP(w, n). In particular, ψ determines a bijection between {BST(w, n) : w ∈ {r, c}^{k}} and S_{n+k}. Consequently,

∑_{w∈{r,c}^{k}} |BST(w, n)| = (n + k)!.

Proof. From Proposition 12 we know ψ restricted to one sequence w is injective. Proposition 13 shows that a permutation uniquely determines the sequence w, ψ must be injective over the set of all sequences of length k.

On the other hand for any permutation σ ∈ S_{n+k} there is always one sequence w ∈ {r, c}^{k} such that σ ∈ BSP(w, n) as we can find appropriate values for w_{i} from σ^{−1}(i) and σ^{−1}(n+i) together with Proposition 13. Hence ψ is also surjective.

Definition 16 (k-descents). Let σ ∈ S_{n}. We say that i ∈ {1, …, n − 1} is a k-descent of σ if σ(i) − k > σ(i + 1). Let DES_{k}(σ) denote the set of k-descents of σ and let des_{k}(σ) be the number of such k-descents. For example, the 3-descents of the permutation

[2, 4, 10, 5, 6, 3, 8, 1, 7, 9]

are 3 and 7 (marked in bold).

Lemma 17 (Technical lemma). Let T = ψ^{−1}(σ) for some σ ∈ BSP(w, n). The following three statements are equivalent:

(a) The permutation σ has an n-descent.

(b) There is an m such that the strips B_{m} := T^{−1}(m) and B_{m+1} := T^{−1}(m + 1) are not comparable in the sense of Definition 4 and σ(m) > σ(m + 1).

(c) There are two strips B_{x} := T^{−1}(x) and B_{y} := T^{−1}(y) in T such that B_{x} is not comparable to B_{y} in the sense of Definition 4, where x < y and σ(x) > σ(y).

Proof. Recall that σ(x) is simply the diagonal containing the head of B_{x}.

Case (a) ⟹ (b). We have that σ(m)−σ(m+1) > n for some m. Since σ(m) > σ(m+1)+n, we cannot have that B_{m} is adjacent to B_{m+1}. Furthermore, there cannot be a longer sequence of strips B_{m} = B_{i_{1}}, …, B_{i_{ℓ}} = B_{m+1} such that B_{i_{j}} is above B_{i_{j+1}} as the values of these strips must then lie strictly between m and m + 1, which is impossible. Hence, B_{m} is not inner to B_{m+1} and this implies that they are not comparable.

Case (b) ⟹ (c). Just take x = m and y = m + 1.

Case (c) ⟹ (a). Consider the interval of values x, x + 1, …, y and choose x ≤ m < y such that σ(m) − σ(m + 1) is maximized. Suppose σ(m) − σ(m + 1) ≤ n. Then there is a sequence of values i_{1}, …, i_{s} such that

x = i_{1} < i_{2} < ⋯ < i_{s} = y, σ(x) = σ(i_{1}) > σ(i_{2}) > ⋯ > σ(i_{s}) = σ(y),

and for all j we have σ(i_{j})−σ(i_{j+1}) ≤ n. But Proposition 9 implies that the strip with value i_{j} is above the strip with value i_{j+1}. By transitivity, B_{x} must be inner to B_{y} which violates one of the conditions. It follows that σ(m) − σ(m + 1) > n and σ has an n-descent.

We are now ready to characterize a subset of BSP(w, n) which is in bijection with the border-strip decomposition BSD(w, n). Let s_{1}, …, s_{n−1} denote the simple transpositions in S_{n}.

Proposition 18. Suppose w is a sequence of length k, σ ∈ BSP(w, n), and i ∈ DES_{n}(σ). Then the border-strip tableaux ψ^{−1}(s_{i}σ) and ψ^{−1}(σ) have the same border-strip decomposition. Moreover, the sets

BSD(w, n) and {σ ∈ BSP(w, n) : des_{n}(σ) = 0}

are in bijection.

Proof. Let τ := s_{i}σ, T_{σ} := ψ^{−1}(σ), and T_{τ} := ψ^{−1}(τ) be the corresponding border-strip tableaux. First we need to show that τ ∈ BSP(w, n). The only places where τ^{−1} differ from σ^{−1} are τ(i) and τ(i + 1). Now, if j ∈ {1, …, k} then at most one of σ^{−1}(j) and σ^{−1}(n + j) is different from τ^{−1} and the quantities

τ^{−1}(j) − τ^{−1}(n + j) and σ^{−1}(j) − σ^{−1}(n + j)  (7)

are either the same or differ by 1. In particular, the quantities in (7) cannot have opposite signs. Since σ ∈ BSP(w, n), the corresponding inequalities in Proposition 13 are also fulfilled by τ. Hence τ ∈ BSP(w, n) as well. It remains to show that T_{τ} and T_{σ} have the same border-strip decomposition. The only strips in T_{σ} and T_{τ} which have a different number are strip τ(i) and strip τ(i + 1), with a ±1 difference. Therefore, the only pair of strips that has a different relative ordering in T_{τ} is the pair (τ(i), τ(i + 1)). However, since i is an n-descent it does not affect the construction in the proof of Proposition 13 and it follows that T_{σ} and T_{τ} have the same border-strip decomposition.

For the second statement, we use Lemma 17. In order for σ to be free of n-descents, the relative order of the values of all pairs of non-comparable strips is uniquely determined. On the other hand, the relative order of pairs of comparable strips is determined by the shape of the diagram. Since a permutation is uniquely determined by the relative order of all pairs of entries, there is at most one permutation without n-descents in BSP(w, n) with a given border-strip decomposition.

On the other hand, we can always find such a σ by starting from any permutation in BSP(w, n) and repeatedly decrease the number of n-descents until a permutation without n-descents is obtained. This is done by interchanging the values in the non-comparable strips B_{m} and B_{m+1} in Lemma 17 (b).

Corollary 19. Let w ∈ {c, r}^{k}. The set of border-strip decompositions of the simple diagram (w, n) is in bijection with the set of permutations in S_{n+k} such that for each i ∈ [k]

• w_{i} = c ⟹ σ^{−1}(i) < σ^{−1}(n + i),

• w_{i} = r ⟹ σ^{−1}(i) > σ^{−1}(n + i) and

• σ(j) − σ(j + 1) ≤ n for all j ∈ [n + k − 1].

Let BSP^{∗}(w, n) be the subset of permutations in S_{n+k} that fulfill the three conditions in Corollary 19. Hence,

BSP^{∗}(w, n) = {σ ∈ BSP(w, n) : des_{n}(σ) = 0}.

Note that ψ^{−1} gives a bijection from BSP^{∗}(w, n) to BSD(w, n).

Definition 20. For a sequence w ∈ {r, c}^{k} let

f̂_{w}(n) := |BSD(w, n)|\frac{(2k)!}{(n − k)!}.  (8)

Proposition 21. Whenever n ≥ 2k, the function f̂_{w}(n) is equal to

f_{w}(n) := ∑_{τ∈BSP(w,k)}(n + k − des_{k}(τ))_{2k}.  (9)

As a consequence, f̂_{w}(n) is a polynomial in n of degree 2k with integer coefficients when restricted to values n ≥ 2k. Moreover, f_{w}(n) is divisible by the falling factorial (n + 1)_{k+1}.

Proof. We start by assuming that n ≥ 2k. Interpreting permutations in S_{n+k} as sequences of n + k numbers, we note that the first two conditions in Corollary 19 only apply to the relative order of the first and last k elements. Thus, in order to construct a permutation σ in S_{n+k} satisfying the three conditions in Corollary 19, we proceed in three steps.

1. Choose an ordering of the entries {1, 2, …, k} ∪ {n + 1, n + 2, …, n + k}.

2. Choose the positions of the entries {1, 2, …, k} ∪ {n + 1, n + 2, …, n + k}.

3. Choose an ordering of the entries {k + 1, …, n}.

Note that as n ≥ 2k, the unions in the first two steps above are disjoint. Not every choice here will fulfill the conditions in Corollary 19 — we shall see below which ones are valid. For a choice in the first step, two things might happen.

a) There is some pair (i, i + n) in the wrong order — violating one of the first two conditions. In this case we do not have a border-strip tableau, and thus no borderstrip composition for this choice.

b) All pairs (i, i + n) have the correct order. In this case, the ordering of the 2k entries

{1, 2, …, k} ∪ {n + 1, n + 2, …, n + k}

fulfills the conditions (after standardization!) of being a permutation τ ∈ BSP(w, k). Notice the use of k and not n here as strip-size.

Now we need to ensure that there are no n-descents in the final permutation. If there are no k-descents in τ in step b) above, then there are no n-descents either. Otherwise, we need to insert another number after every k-descent of τ. This means we only have \binom{n+k−des_{k}(τ)}{2k} valid choices in step (2). The last step always has (n − k)! valid choices as the order on {k + 1, …, n} does not matter. It follows that whenever n ≥ 2k, the function f̂_{w}(n) is given by

f̂_{w}(n) = \frac{(2k)!}{(n − k)!} ∑_{τ∈BSP(w,k)} \binom{n + k − des_{k}(τ)}{2k}(n − k)!

= ∑_{τ∈BSP(w,k)}(n + k − des_{k}(τ))_{2k}.

This function is obviously a polynomial of degree 2k. Furthermore, since des_{k}(τ) is between 0 and k − 1 it follows that (n + k − des_{k}(τ))_{2k} is divisible by (n + 1)_{k+1}.

Corollary 22. We have the enumeration

|BSD(rc, n)| = (n + 1)!(3n + 2)/12 whenever n ≥ 2.

Proof. Using Proposition 21, we know that |BSD(rc, n)| can be expressed as (n−2)!f̂_{rc}(n)/4!. Since we know that f̂_{rc}(n) is a polynomial in n for n ≥ 4, it suffices to verify the formula for the first few values of n.

The sequence a_{n+1} = (n + 1)!(3n + 2)/12 appears \underline{A227404} in the OEIS, where a_{n} count the total number of inversions in all permutations in S_{n} consisting of a single cycle. For example, the permutations (123) and (132) have four inversions in total, giving a_{3} = 4. We have not managed to find an explicit bijection that shows this correspondence.

2.4 Inversions and q-analogues

Definition 23 (Inversions). Two border strips B_{1} and B_{2} in a decomposition form an inversion if and only if the following three conditions are fulfilled:

• The intersection

{j − i : (i, j) ∈ B_{1}} ∩ {j − i : (i, j) ∈ B_{2}}

is non-empty. Equivalently, there is a diagonal as in Definition 7 that intersects both B_{1} and B_{2}.

• B_{1} is inner to B_{2}, and

• H(B_{1}) > H(B_{2}).

We prove in Corollary 25 that this definition generalizes the notion of inversions of permutations in a natural manner.

Lemma 24. Let σ ∈ BSP^{∗}(w, n), with B_{σ} := ψ^{−1}(σ) being the corresponding border-strip decomposition. Then the strips i and j in B_{σ} with i < j form an inversion if and only if j − i < n and σ^{−1}(i) > σ^{−1}(j).

Proof. If j − i ≥ n they do not have an element on the same diagonal, and by definition do not form an inversion. If j − i < n they share an element on the same diagonal and if σ^{−1}(i) > σ^{−1}(j) then strip j is above strip i and they form an inversion.

Given a border-strip decomposition B, let inv(B) denote the total number of inversions in B. Furthermore, for σ ∈ S_{n+k} let

inv_{n}(σ) := {(i, j) : 0 < j − i < n and σ^{−1}(i) > σ^{−1}(j)}.

The q-analogue of BSD(w, n) is defined as

|BSD(w, n)|_{q} := ∑_{B∈BSD(w,n)} q^{inv(B)}  (10)

and by Lemma 24 we have that

|BSD(w, n)|_{q} = ∑_{σ∈BSP^{∗}(w,n)} q^{inv_{n}(σ)}.  (11)

Corollary 25. The q-analogue of the n × n-square, |BSD(∅, n)|_{q}, satisfies the identity

∑_{B∈BSD(∅,n)} q^{inv(B)} = [n]_{q}!.

Proof. From Proposition 13 we know every permutation in S_{n} is in BSP^{∗}(∅, n). From Proposition 18, we know every border-strip tableau correspond to a unique border-strip decomposition. From Lemma 24 we can then deduce that the q-analogue is given by [n]_{q}!.

Corollary 26. We have the following q-analogue for BSD(c, n):

∑_{B∈BSD(c,n)} q^{inv(B)} = [n − 1]_{q}! ∑_{i=1}^{n} iq^{i−1}.

Proof. We get a permutation corresponding to a decomposition by placing 1 and n + 1 (i.e., choose σ^{−1}(1) and σ^{−1}(n + 1)), and then choose the order of 2, …, n. This choice gives [n − 1]_{q}! and the possible positions of 1 and n + 1 give ∑_{i=1}^{n} iq^{i−1}, as 1 has to be before n + 1 for it to be a border-strip tableau. Note that there cannot be any n-descents and therefore the number of border-strip tableaux is equal to the number of decompositions.

Proposition 27. If w is a sequence of a simple diagram, then

|BSD(cw, n)| + |BSD(rw, n)| = (n + 1)|BSD(w)|.

Furthermore, this relation extends to the following q-analogue:

|BSD(cw, n)|_{q} + |BSD(rw, n)|_{q} = [n + 1]_{q}|BSD(w)|_{q}.

Proof. If we fix the positions of the heads in (w, n), the new head in (cw, n) must be above the strip it replaces, where as in (rw, n) it must be below. Together, this gives n + 1 choices to complete the partial decomposition to a BSD of (w, n). If, in (cw, n) or in (rw, n), we place the new head in position i of the diagonal, the new strip forms an inversion with all i − 1 strips above it. This proves the q-analogue.

Corollary 28. We can enumerate the total number of border-strip decompositions for all sequences of length k:

∑_{w∈{r,c}^{k}} |BSD(w, n)| = (n + 1)^{k}n!

and this relation extends to the q-analogue

∑_{w∈{r,c}^{k}} ∑_{B∈BSD(w,n)} q^{inv(B)} = [n + 1]_{q}^{k}[n]_{q}!.  (12)

Proof. It suffices to show the q-analogue. We proceed by induction over k. The base case k = 0 is given by Corollary 25. We then have

∑_{w∈{r,c}^{k}} |BSD(w, n)|_{q} = ∑_{w∈{r,c}^{k−1}} |BSD(rw, n)|_{q} + ∑_{w∈{r,c}^{k−1}} |BSD(cw, n)|_{q}

= [n + 1]_{q} ∑_{w∈{r,c}^{k−1}} |BSD(w, n)|_{q}

= [n + 1]_{q} ([n + 1]_{q}^{k−1}[n]_{q}!)

= [n + 1]_{q}^{k}[n]_{q}!

where the second equality is due to Proposition 27, and the third equality is our induction hypothesis. This completes the proof.

For n = k − 1, (12) gives the sequence a(n) = (n + 1)^{n−1}n!, which is \underline{A066319}. This sequence also show up in the work of Weist [10, Thm. 5.4]. Let K_{n,n+1} be the complete bipartite graph with n sources and n + 1 sinks. There are a(n) spanning trees such that every source has exactly 2 incident edges. As a(n) is also related to computing the Euler characteristic of certain moduli spaces, we ask if it perhaps is related to what we discuss in Section 3 below.

For a sequence w, let C_{w} be the total number of c’s in w, R_{w} be the total number of r’s in w and hor(w) := C_{w} − R_{w}. For example,

C_{rcrcc} = 3, R_{rcrcc} = 1 and hor(rcrcc) = 3 − 2 = 1.

Intuitively, hor(w) measures how “horizontal” the diagram is, and | hor(w)| is smaller for “straigher” shapes. The following theorem shows that straighter diagrams admit a larger number of decompositions, in a precise sense:

Theorem 29. If v and w are sequences of length k and | hor(v)| < | hor(w)|, then

|BSD(v, n)| < |BSD(w, n)| for n sufficiently large.

In fact,

\frac{|BSD(w, n)| − |BSD(v, n)|}{(n − k)!} = O(n^{2k−1}).

Proof. From Proposition 21, we know that for sufficiently large n, we have that

f̂_{v}(n) := |BSD(w, n)|\frac{(2k)!}{(n − k)!} = ∑_{σ∈BSP(v,k)}(n + k − des_{k}(σ))_{2k}.

From Proposition 14 we know that |BSP(v, k)| = (2k)!/2^{2k}. It then follows that

f̂_{v}(n) = \frac{(2k)!}{2^{k}}n^{2k} + αn^{2k−1} + l.o.t and f̂_{w}(n) = \frac{(2k)!}{2^{k}}n^{2k} + βn^{2k−1} + l.o.t.

Our goal is to prove that α < β. For a fixed permutation σ ∈ BSP(v, k), its contribution to α is given by

∑_{i=0}^{2k−1}(k − des_{k}(σ) − i) = 2k^{2} − k(2k − 1) − 2k des_{k}(σ) = k − 2k des_{k}(σ).

Hence, by summing over all permutations,

α = k|BSP(v, k)| − 2k ∑_{σ∈BSP(v,k)} des_{k}(σ).

As |BSP(v, k)| does not depend on v, the only part depending on v is

J_{v} := ∑_{σ∈BSP(v,k)} des_{k}(σ),

and it suffices to prove that J_{v} increases as | hor(v)| decreases.

To do this, we count the number of permutations where b + k is a k−descent with a, for 1 ≤ a < b ≤ k fixed (i.e., we have …, b + k, a, … in the permutation). To create such a permutation, we can choose the order of all elements different from a, b, a + k, b + k in any way respecting the orders of pairs σ(i), σ(i + k), which gives (2k − 4)!/2^{k−2} choices. Then we must choose the order of the three blocks a + k, (b + k)a, b. If a + k and b are on the same side of (b + k)a, this gives two possibilities, otherwise there is only one way. We observe a + k and b are on the same side if and only if v_{a} ≠ v_{b}. Finally, we can chose the position of the three blocks a + k, b, (b + k)a, which gives \binom{2k}{3} choices. So the number of permutations where b + k is a k-descent with a is exactly

\begin{cases}2\binom{2k}{3}(2k − 4)!/2^{k−2}, & if v_{a} ≠ v_{b}; \\ \binom{2k}{3}(2k − 4)!/2^{k−2}, & otherwise. \end{cases}

Recall C_{v} is the number of c’s in v and R_{v} is the number of r’s in v. The previous argument implies

J_{v} = \binom{2k}{3}\frac{(2k − 4)!}{2^{k−2}} [\binom{C_{v}}{2} + 2C_{v}R_{v} + \binom{R_{v}}{2}] .

Since R_{v} = k − C_{v} it follows that

\binom{C_{v}}{2} + 2C_{v}R_{v} + \binom{R_{v}}{2} = \binom{k}{2} + C_{v}R_{v}

which increases as | hor(v)| decreases. This implies the theorem.

Conjecture 30. The function f_{w}(n) uniquely determines w up to isometry of the diagram w, i.e., up to exchanging r and c and reversing the sequence.

Note that for fixed k, the polynomials (in n) {(n + k − i)_{2k}}_{i=0}^{k−1} are linearly independent. They span the same space as

\{\frac{(n + i)_{2k}}{(2k)!} \}_{i=1}^{k} = \{\binom{n + i}{2k}\}_{i=1}^{k}

and the latter collection of polynomials can be seen to be linearly independent.

As a consequence, given f_{w}(n), which is a sum over permutations in BSP(w, k), for any i we can extract the number of permutations σ ∈ BSP(w, k) with des_{k}(σ) = i. Hence, the conjecture is reduced to determining if the multi-set of des_{k}-values of the elements in BSP(w, k) uniquely determines w up to isometry.

In particular, if the number of terms without k-descents is different, the polynomial is also different, so we can formulate the stronger conjecture that |BSD(w, k)| uniquely determines a sequence w of length k up to isometry.

3 A connection with the Weil-Petersson volume

We let c^{n} denote the simple shape which is a rectangle of width 2n and height n. It follows from Corollary 19 that the set BSD(c^{n}, n) is in bijection with the set of permutations of {x_{1}, …, x_{n}, y_{1}, …, y_{n}} such that x_{i} appears before y_{i} for all i, and we do not have …, x_{i}, y_{j}, … (consecutive), such that i > j.

Lemma 31 (Adaptation of Xiang [11]). The cardinality of BSD(c^{n}, n) is given by the formula

|BSD(c^{n}, n)| = ∑_{p⊢n}(−1)^{|p−1|} \frac{1}{m!}\binom{|p|}{p}\binom{|p + 1|}{p + 1},  (13)

where m = (m_{1}, m_{2}, …, m_{k}) and m_{i} is the multiplicity of i in p, and we use the notation p±1 := (p_{1} ±1, …, p_{k} ±1) and |p| = p_{1} +⋯+p_{k}. Note that \binom{|p|}{p} and \binom{|p+1|}{p+1} are multinomial coefficients.

Proof. For a permutation σ ∈ S_{2n} corresponding to a border-strip tableau, let Γ_{σ} be the graph on the vertex set [n] with edge set

{(σ(i) − n, σ(i + 1)) : σ(i) − n > σ(i + 1)}.

Let G be the set of graphs obtained from such border-strip tableaux. Let E be \binom{[n]}{2}, that is, the set of all possible edges on the vertex set [n] and let G(e_{1}, …, e_{r}) ⊆ G be the set of graphs that include the edges {e_{1}, …, e_{r}} ⊆ E. We have that elements in BSP^{∗}(c^{n}, n) are in bijection with G(∅), and Proposition 18 tells us that

|BSD(c^{n}, n)| = G \ (⋃_{r=1}^{n} ⋃_{e_{1},...,e_{r}∈E} G(e_{1}, …, e_{r})) .

Using the inclusion-exclusion principle, it follows that

|BSD(c^{n}, n)| = |BST(c^{n}, n)| − ∑_{e_{1}∈E} |G(e_{1})| + ∑_{e_{1},e_{2}∈E} |G(e_{1}, e_{2})| − · · · .

We then observe that these graphs are characterized by the connected components induced by the forced edges e_{1}, …, e_{r}, determining an integer partition p of n. Furthermore, the sign in the above formula only depends on the number of forced edges, which is equal to |p − 1|, so we can transform this into a sum over all partitions of n. Given a partition p ⊢ n, the number of graphs with component sizes p_{1}, p_{2}, …, p_{k} is given by \frac{1}{m!} \binom{|p|}{p}, with m given as above. Claim: Let e_{1}, e_{2}, …, e_{r} be fixed edges such that the component sizes are given by p. Then

G(e_{1}, …, e_{r}) = \binom{|p + 1|}{p + 1}.

Proof: Suppose Γ_{σ} ∈ G(e_{1}, …, e_{r}) has a component (i_{1}, i_{2}, …, i_{j}), in increasing order. From Proposition 13, we know σ^{−1}(i_{s}) < σ^{−1}(i_{s} + n) for all 1 ≤ s ≤ j, and for (i_{1}, i_{2}, …, i_{j}) to be connected, we need i_{s} + n to form an n-descent with i_{s−1} for all 1 < s ≤ j i.e., σ^{−1}(i_{s} + n) = σ^{−1}(i_{s−1}) − 1.

Together these two statements imply that σ, has the following structure:

σ^{−1}(i_{j}) < σ^{−1}(i_{j} + n) ⋖ σ^{−1}(i_{j−1}) < σ^{−1}(i_{j−1} + n) ⋖ ⋯
⋯ < σ^{−1}(i_{3} + n) ⋖ σ^{−1}(i_{2}) < σ^{−1}(i_{2} + n) ⋖ σ^{−1}(i_{1}) < σ^{−1}(i_{1} + n)

where a ⋖ b means that a + 1 = b. Thus, we have j + 1 blocks,

[σ^{−1}(i_{j})], [σ^{−1}(i_{s+1} + n) ⋖ σ^{−1}(i_{s})] for s = 1, …, j − 1 and [σ^{−1}(i_{1} + n)]

which need to appear in order, but there is no further restriction. The number of Γ_{σ} with component sizes determined by p is therefore \binom{|p+1|}{p+1}, which concludes the proof.

Let us now dive into a completely different part of mathematics. We shall not use the following definition and we omit many details. The important part is Theorem 32 further down.

The Weil-Petersson volume, Vol_{W P} (·), is defined as

Vol_{W P} (M) := \frac{1}{(n − 3)!} ∫_{M} ∧^{n−3}(ω_{M}),

where ωM is the Weil-Petersson symplectic form on the manifold M. A special type of manifold is M_{0,n}, which denotes the moduli space of an n-punctured Riemann sphere, that is

M_{0,n} := {(z_{1}, …, z_{n}) ∈ ℂ̂^{n} : z_{i} ≠ z_{j}}/S_{n} × PSL(2, ℂ)

and S_{n} acts by permuting variables, and PSL(2, ℂ) acts as a linear fractional transformation.

Theorem 32 (Zograf [12]). The Weil-Petersson volume of the moduli space of an n-punctured Riemann sphere M_{0,n} is given by the formula

Vol_{W P} (M_{0,n}) = \frac{π^{2(n−3)}v_{n}}{n!(n − 3)!}, for n ≥ 4,

where the sequence (v_{n})_{n=3}^{∞} is defined via the recursion

v_{3} = 1,  v_{n} = \frac{1}{2} ∑_{i=1}^{n−3} \frac{i(n − i − 2)}{n − 1}\binom{n − 4}{i − 1}\binom{n}{i + 1}v_{i+2}v_{n−i},  n ≥ 4.  (14)

This sequence shows up as \underline{A115047} in the OEIS [8], see Kaufmann, Manin, and Zagier [3] and Matone [4] for more background. In the paper by Kauffman et al., [3] the following relationship is shown.

Proposition 33. Let the sequence v_{n} be defined as in (14). Then

v_{n} = ∑_{k=1}^{n−3} \frac{(−1)^{n−3−k}}{k!} ∑_{\begin{matrix}m_{1},...,m_{k}>0 \\ m_{1}+···+m_{k}=n−3 \end{matrix}} \binom{n − 3}{m_{1}, …, m_{k}}\binom{n − 3 + k}{m_{1} + 1, …, m_{k} + 1}.

We are now ready to prove the following connection between the sequence v(n) and border-strip decompositions.

Theorem 34. Let a(n) be defined inductively by a(0) = 1 and

a(n) = \frac{1}{2} ∑_{i=1}^{n} \frac{i(n − i + 1)}{(n + 2)}\binom{n − 1}{i − 1}\binom{n + 3}{i + 1}a(i − 1)a(n − i)  (15)

and let v_{n} be given as in (14). Then a(n) = v_{n+3} = |BSD(c^{n}, n)|.

Proof. The first equality, v_{n+3} = a(n) follows from comparing (14) and (15). It is a straightforward calculation to verify that they are equal. To get the second identity, note that we can get the formula in Proposition 33 from Equation (13) by replacing integer partitions with integer compositions, and then refining the sum over the number of parts, denoted by k in Proposition 33.

4 Further directions

Given the connection with Euler characteristics of moduli spaces mentioned after Corollary 28, and the connection with moduli spaces in Theorem 34, is there a generalization of this mysterious connection? For example, there are formula for the volumes of surfaces of other genus; see Matone [4].

Another interesting direction is to consider the q-analogue of border-strip tableaux rather than decompositions.

5 Acknowledgments

The authors are thankful for the observation made by Ziqing Xiang [11]. We also thank Richard Stanley for pointing out the work by Igor Pak [7], and Justin Troyka for pointing out an error in an earlier draft. We are also grateful for the comments by the anonymous referee.

P. A. is funded by the Knut and Alice Wallenberg Foundation (2013.03.07).

References

[1] D. Beauquier, M. Nivat, E. Remila, and M. Robson, Tiling figures of the plane with two bars, Comput. Geom. 5 (1995), 1–25.

[2] S. Fomin and N. Lulov, On the number of rim hook tableaux, J. Math. Sci. (N.Y.) 87 (1997), 4118–4123.

[3] R. Kaufmann, Y. Manin, and D. Zagier, Higher Weil-Petersson volumes of moduli spaces of stable n-pointed curves, Comm. Math. Phys. 181 (1996), 763–787.

[4] M. Matone, Multi-instanton measure from recursion relations in N = 2 supersymmetric Yang-Mills theory, J. High Energy Phys. 04 (2001), 0–41.

[5] F. Murnaghan, The characters of the symmetric group, Amer. J. Math. 59 (1937), 739–753.

[6] T. Nakayama, On some modular properties of irreducible representations of a symmetric group. I and II, Japan J. Math. 17 (1940), 165–184, 411–423.

[7] I. Pak, Ribbon tile invariants, Trans. Amer. Math. Soc. 352 (2000), 5525–5562.

[8] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2019. Available

at https://oeis.org.

[9] R. P. Stanley, Enumerative Combinatorics:, Volume 2, Cambridge University Press, 1st edition, 2001.

[10] T. Weist, On the Euler characteristic of Kronecker moduli spaces, J. Algebraic Combin. 38 (2012), 567–583.

[11] Z. Xiang, Rim hook decomposition and volume of moduli spaces, MathOverflow.

https://mathoverflow.net/q/294267 (version: 2018-03-03).

[12] P. Zograf, The Weil-Petersson volume of the moduli spaces of punctured spheres, Cont. Math. 150 (1993), 367–372.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 97N70, 05A05. Keywords: border-strip decomposition, permutation, q-analogue, Weil-Petersson volume, rectangular shape.

(Concerned with sequences \underline{A066319}, \underline{A115047}, and \underline{A227404}.)

Received May 28 2018; revised version received June 10 2019. Published in Journal of Integer Sequences, June 28 2019.

Return to Journal of Integer Sequences home page.