Combinatorics and Total Positivity

Francesco Brenti^{1} Universitá degli Studi di Perugia Dipartimento di Matematica Via Vanvitelli 1 06123 Perugia, Italy

Abstract

It was first observed in [F. Brenti, Unimodal, log-concave, and Pólya Frequency sequences in Combinatorics, Memoirs Amer. Math. Soc., no. 413 (1989)] that Pólya frequency sequences arise often in combinatorics. In this work we point out that the same is true , more generally, for totally positive matrices, and that there is an intimate connection between them and some generalizations of the classical symmetric functions.

1 Introduction

Total positivity is an important and powerful concept that arises often in various branches of mathematics, statistics, probability, mechanics, economics, and computer science ( see, e.g., [24], and the references cited there). It was first observed in [5] and [6] that Pólya frequency sequences (see §2 for definitions) also arise often in combinatorics. The purpose of the present work is to point out that the same is true , more generally, for totally positive matrices, and that there is an intimate connection between them and some generalizations of the classical symmetric functions.

More precisely, in this paper we show that many of the familiar matrices arising in combinatorics, as well as in the theory of symmetric functions, and many of their generalizations, have remarkable total positivity properties, and that, conversely, any totally positive matrix can be realized as a matrix of generalized complete homogeneous symmetric functions evaluated at nonnegative real numbers. The method that we use to prove these results is completely combinatorial and has its origin in a technique for counting non-intersecting paths in directed graphs first used by Lindström in [26] (though he used it for completely different purposes). This technique was then used by Gessel, Viennot, and others, to solve various enumerative problems (see, e.g., [18], [19]). In this paper we use some variations and generalizations of it.

1This work was carried out while the author was visiting the Mittag-Leffler Institute in Djursholm, Sweden.

The organization of the paper is as follows. In the next section we collect some definitions, notation, and results, that will be used throughout the rest of this work. In section 3 we give a characterization of totally positive matrices in terms of planar digraphs (Theorem 3.1). We then show that any totally positive matrix is a matrix of (suitably defined) generalized complete homogeneous symmetric functions evaluated at nonnegative real numbers (Theorem 3.3), and that any minor of such a matrix is a “generalized flagged Schur function” evaluated at nonnegative real numbers (Theorem 3.5). As consequences of these results we obtain a combinatorial interpretation for any minor of any totally positive matrix as a generating function for certain sets of appropriately weighted column strict tableaux, (thus solving a problem originally posed in [6], §2.2, p. 10), and we obtain a simple proof of a generalization of a result of Stembridge concerning immanants of totally positive matrices. In section 4 we study the total positivity properties of some infinite matrices which depend on three infinite sets of independent variables and on an integer parameter, and which include the matrix of super-Schur functions studied in [10]. In section 5 we apply the results obtained in §4 to matrices of combinatorial interest. We obtain total positivity properties for matrices of q-binomial coefficients, several types of (p, q)-Stirling numbers of both kinds, generalizations of complete homogeneous and elementary symmetric functions, r-associated q-Stirling numbers of the first kind, Delannoy numbers, q-Lah numbers, q-Stirling numbers of type B_{n}, and others. Finally, in section 6 we obtain combinatorial interpretations for the minors of the matrices studied in §4 and thus, in particular, for most of the combinatorial matrices considered in §5 and for any skew super-Schur function (see Corollary 6.4 and the remarks following Corollary 6.5). These combinatorial interpretations are expressed in terms of “dotted t-tableaux”, a notion which is equivalent, when t = 0, to those of a dotted plane partition, P′-tableau, and circled tableau, which were studied in [4], [10], [30], and [37].

2 Notation and Preliminaries

In this section we collect some definitions, notation and results that will be used in the rest of the paper. We let P =^{def} {1, 2, 3, …}, N =^{def} P∪{0}, Q be the set of rational numbers, and R be the set of real numbers; for a ∈ N we let [a] =^{def} {1, 2, …, a} (where [0] =^{def} ∅). The cardinality of a set A will be denoted by |A|, for r ∈ N

we let (\begin{matrix}A \\ r \end{matrix}) =^{def} \{T ⊆ A : |T | = r\}. For i_{1}, …, i_{t} ∈ P we write \{i_{1}, i_{2}, …, i_{t}\}_{<} if

i_{1} < i_{2} < … < i_{t}. For m, n ∈ P with m ≤ n we let [m, n] =^{def} [n] \ [m − 1]. Given T ⊆ [n] there are unique integers r ∈ P, and 1 ≤ a_{1} ≤ a_{2} ≤ … ≤ a_{2r} ≤ n, such that T = ⋃_{i=1}^{r}[a_{2i−1}, a_{2i}] and |a_{2i+1} − a_{2i}| > 1 for i = 1, …, r − 1. We then call the intervals [a_{2i−1}, a_{2i}], i = 1, …, r, the connected components of T. Given a (finite) set T we denote by Π(T) the set of all (set) partitions of T (see, e.g., [35], p.33 for further information about partitions of a set), and by S(T) the set of all bijections from T to itself. For n ∈ P, we let S_{n} =^{def} S([n]). Throughout this work, p and q will denote two independent variables. For n ∈ P we let [n]_{p,q} =^{def} p^{n−1} + q p^{n−2} + q^{2}p^{n−3} + … + q^{n−1}, [n]_{q} =^{def} [n]_{1,q}, and [k]_{p,q} =^{def} 0 if k ≤ 0.

We follow [27], Chap.I, for notation and terminology related to partitions and symmetric functions. In particular, given a partition λ, we denote by λ′ its conjugate, by m_{i}(λ) the number of parts of λ that are equal to i, for i ∈ P, and by s_{λ} (respectively e_{λ}, h_{λ}) the Schur (respectively elementary, complete homogeneous) symmetric function associated to λ. We will usually identify a partition λ = (λ_{1}, …, λ_{r}) with its diagram {(i, j) ∈ P × P : 1 ≤ i ≤ r, 1 ≤ j ≤ λ_{i}}.

We follow [33] for notation and terminology regarding plane partitions. However, we will often need to work with more general objects than skew reverse plane partitions, which we now define. Let λ = (λ_{1}, …, λ_{r}) and μ = (μ_{1}, …, μ_{r}) be two partitions such that μ ⊆ λ. A shifted skew tabloid of shape λ \ μ is an array T = (T_{i,j})_{1≤i≤r, μ_{i}+i≤j≤λ_{i}+i−1} of positive integers (we will sometimes use the notation sh(T) = λ\μ). We denote by T_{i} the i-th row of T, for i = 1, …, r, and we let s(T) =^{def} (T_{1,λ_{1}}, …, T_{r,λ_{r}+r−1}) \ (T_{1,μ_{1}+1}, …, T_{r,μ_{r}+r}) and call s(T) the size of T. We also let

|T | =^{def} ∑_{(i,j)∈sh(T)} T_{i,j}, \overline{T} =^{def} (T_{i,j})_{1≤i≤r, μ_{i}+i+1≤j≤λ_{i}+i−1}, T̃ =^{def} (T_{i,j})_{1≤i≤r, μ_{i}+i≤j≤λ_{i}+i−2},

and T̂ =^{def} ˜ \overline{T}. We call T a shifted skew reverse plane partition if T_{i,j} ≤ T_{i+1,j} and T_{i,j} ≤ T_{i,j+1} whenever both sides of the inequality are defined. We say that T is row strict (respectively, column strict) if T_{i,j} < T_{i,j+1} (respectively, T_{i,j} < T_{i+1,j}) whenever both sides of the inequality are defined. If μ = ∅ then we call T a shifted reverse plane partition of shape λ. Note that we do not require the parts of λ to be distinct. Also note that if both μ and λ have distinct parts then a shifted skew reverse plane partition of shape λ \ μ is just a skew reverse plane partition of shape (λ_{1}, λ_{2} + 1, …, λ_{r} + r − 1) \ (μ_{1}, μ_{2} + 1, …, μ_{r} + r − 1). For brevity, we will often use the word tableau in place of “reverse plane partition”, even though the latter is more common.

An infinite (real) matrix M = (M_{n,k})_{n,k∈N} (where M_{n,k} is the entry in the n-th row and k-th column of M) is said to be totally positive (or, T P, for short) if every minor of M has nonnegative determinant. An infinite (real) sequence {a_{i}}_{i∈N} is said to be a Pólya frequency sequence (or, a P F -sequence, for short) if the infinite matrix A =^{def} (a_{n−k})_{n,k∈N} (where a_{i} =^{def} 0 if i < 0) is totally positive. Given M, {a_{i}}_{i∈N}, and A as above, and {n_{1}, …, n_{r}}_{<}, {k_{1}, …, k_{r}}_{<} ⊆ N (r ∈ P) we will find it convenient to let

M ( \begin{matrix}n_{1}, …, n_{r} \\ k_{1}, …, k_{r} \end{matrix} ) =^{def} det [(M_{n_{i},k_{j}})_{1≤i , j≤r}] ,  (1)

and

\{a_{i}\}_{i∈N} ( \begin{matrix}n_{1}, …, n_{r} \\ k_{1}, …, k_{r} \end{matrix} ) =^{def} A ( \begin{matrix}n_{1}, …, n_{r} \\ k_{1}, …, k_{r} \end{matrix} ) .  (2)

Given a matrix M we will denote by M′ the transpose of M. We will often work with matrices and sequences whose elements are real polynomials over some (usually infinite) set of independent variables x. In this case we will say that such a matrix M = (M_{n,k})_{n,k∈N} (respectively, sequence {a_{i}}_{i∈N}) is x-T P (respectively, x-P F) if (1) (respectively, (2)) is a polynomial with nonnegative coefficients, for all r ∈ P and {n_{1}, …, n_{r}}_{<}, {k_{1}, …, k_{r}}_{<} ⊆ N. Given a sequence of independent variables {x_{i}}_{i∈N} and T ⊆ N we let x_{T} =^{def} ∏_{i∈T} x_{i}. We also let 0 =^{def} (0, 0, 0, …) and 1 =^{def} (1, 1, 1, …).

Let D = (V, A) be a directed graph (or, digraph, for short). We will always assume that D has no loops or multiple edges, so that we can identify the elements of A with ordered pairs (u, v), with u, v ∈ V, u ≠ v. A path in D is a sequence π = u_{1}u_{2} … u_{n} of elements of V such that (u_{i}, u_{i+1}) ∈ A for i = 1, …, n−1, we then say that π goes from u_{1} to u_{n}. We say that D is locally finite if, for every u, v ∈ V, there are only a finite number of paths from u to v. Note that this implies that D is acyclic. We say that D is weighted if there is a function w : A → R, where R is some commutative Q-algebra. If R = R and w((u, v)) ≥ 0 for all (u, v) ∈ A then we call D a nonnegative digraph. Let D = (V, A, w) be a locally finite, weighted, digraph. For a path π = u_{0}u_{1} … u_{k} in D we let

w(π) =^{def} ∏_{i=1}^{k} w(u_{i−1}, u_{i}) ,

and, for u, v ∈ V, we let

P_{D}(u, v) =^{def} ∑_{π} w(π) ,

where the sum is over all paths π in D going from u to v. We adopt the convention that P_{D}(u, u) =^{def} 1 for all u ∈ V (i.e. there is only one path, the empty path, from u to u and its weight is 1). We will usually omit the subscript D when there is no danger of confusion. Given u =^{def} (u_{1}, …, u_{r}), v =^{def} (v_{1}, …, v_{r}) ∈ V^{r} we let

N(u, v) =^{def} ∑_{(π_{1},...,π_{r})} w(π_{1}, …, π_{r}) ,

where w(π_{1}, …, π_{r}) =^{def} ∏_{i=1}^{r} w(π_{i}), and where the sum is over all r-tuples of paths (π_{1}, …, π_{r}) from u to v (i.e., π_{i} is a path from u_{i} to v_{i}, for i = 1, …, r) that are non-intersecting (i.e., π_{i} and π_{j} have no vertices in common if i ≠ j). We say that u and v are compatible if, for every σ ∈ S_{r} \ {Id}, there are no r-tuples of paths from (u_{1}, …, u_{r}) to (v_{σ(1)}, …, v_{σ(r)}) that are non-intersecting. The following fundamental result was first proved by Lindström in [26] and has later found numerous applications in enumerative combinatorics (see, e.g., [18], [19], [31], [38]). We refer the reader to [19], Corollary 2, [38], Theorem1.2, or [26], Lemma 1 for its proof.

Lemma 2.1 Let D = (V, A, w) be a locally finite, weighted digraph and u =^{def} (u_{1}, …, u_{n}), v =^{def} (v_{1}, …, v_{n}) ∈ V^{n} be compatible. Then

N(u, v) = det [(P_{D}(u_{i}, v_{j}))_{1≤i, j≤n}] .

3 Total positivity and lattice paths

Lemma 2.1 shows, in particular, that if D = (V, A, w) is a finite, nonnegative digraph, and (u_{1}, …, u_{n}), (v_{1}, …, v_{n}) ∈ V^{n} are compatible then the matrix

(P_{D}(u_{i}, v_{j}))_{1≤i, j≤n}  (3)

has nonnegative determinant. It is natural to conjecture that under these assumptions this matrix is actually totally positive. This, however, is false. For example, in the digraph D depicted in Figure 1 (where we assume that all the directed edges have weight 1) the triples u =^{def} (u_{1}, u_{2}, u_{3}) and v =^{def} (v_{1}, v_{2}, v_{3}) are compatible but

(P_{D}(u_{i}, v_{j}))_{1≤i,j≤3} = ( \begin{matrix}1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{matrix} )

is not totally positive even though D satisfies all the other hypotheses of Lemma 2.1.

[figure: u_{3}; v_{3}; u_{2}; v_{2}; u_{1}; v_{1}]

Figure 1.

This suggests the following definition. Let D = (V, A) be a digraph and u =^{def} (u_{1}, …, u_{n}), v =^{def} (v_{1}, …, v_{n}) ∈ V^{n}. We say that u and v are fully compatible if (u_{i_{1}}, …, u_{i_{r}}) and (v_{j_{1}}, …, v_{j_{r}}) are compatible for all {i_{1}, …, i_{r}}_{<}, {j_{1}, …, j_{r}}_{<} ⊆ [n] and r ∈ [n]. It is then clear that if D = (V, A, w) is a finite, nonnegative digraph, and (u_{1}, …, u_{n}), (v_{1}, …, v_{n}) ∈ V^{n} are fully compatible then we can apply Lemma 2.1 to every minor of the matrix (3) and thus conclude that it is totally positive. What is surprising, however, is that this actually characterizes totally positive matrices. In fact, we have the following fundamental result. Recall (see, e.g., [24], Chapter 3, §3, p.112) that a matrix (a_{i,j})_{1≤i,j≤n} is called a Jacobi matrix if a_{i,j} = 0 whenever |i − j| > 1.

Theorem 3.1 Let U be an n × n (real) matrix. Then U is totally positive if and only if there exists a planar, finite, nonnegative digraph D = (V, A, w), and u= (u_{1}, …, u_{n}), v = (v_{1}, …, v_{n}) ∈ V^{n} fully compatible, such that

U = (P_{D}(u_{i}, v_{j}))_{1≤i, j≤n} .

Proof. One direction of the theorem follows immediately from our definitions and Lemma 2.1, as remarked above. So assume that U is totally positive. Then there follows from Theorem 3.5 of [2] and Theorem 4.1 of [14] that there exist t, m ∈ N and matrices W_{1}, …, W_{t+m} such that W_{i} is an n×n upper (respectively lower) triangular, totally positive, Jacobi matrix, for i = 1, …, t (respectively, i = t + 1, …, t + m), and

U = W_{1} … W_{t+m} .  (4)

Let

W_{i} =^{def} [ \begin{matrix}a_{1}^{(i)} & b_{1}^{(i)} & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & ⋯ & a_{n−1}^{(i)} & b_{n−1}^{(i)} \\ 0 & 0 & ⋯ & 0 & a_{n}^{(i)} \end{matrix} ] ,  (5)

for i = 1, …, t, and

W_{i} =^{def} [ \begin{matrix}a_{1}^{(i)} & 0 & ⋯ & 0 & 0 \\ b_{2}^{(i)} & a_{2}^{(i)} & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & ⋯ & b_{n}^{(i)} & a_{n}^{(i)} \end{matrix} ] ,  (6)

for i = t + 1, …, t + m. Note that, since the W_{i}’s are totally positive, a_{i}^{(j)}, b_{i}^{(j)} ≥ 0 for all i and j. Now let D(U) be the weighted digraph on vertex set

V =^{def} [n] × [t + m + 1]

obtained by putting a directed edge from (i, j) to (i + 1, j) with weight a_{j}^{(i)} for (i, j) ∈ [n] × [t + m], and a directed edge from (i, j) to (i + 1, j + 1) (respectively, (i+1, j−1)) with weight b_{j}^{(i)} for (i, j) ∈ [n]×[t] (respectively, (i, j) ∈ [n]×[t+1, t+m]). For example, if n = 4, m = 2, and t = 3, then we obtain the digraph depicted in Figure 2.

[figure: (1,1); (1,2); (1,3); (1,4); (6,1); (6,2); (6,3); (6,4); a_{1}^{(1)}; a_{1}^{(2)}; a_{1}^{(3)}; a_{1}^{(4)}; a_{1}^{(5)}; a_{2}^{(5)}; a_{2}^{(1)}; a_{2}^{(2)}; a_{2}^{(3)}; a_{2}^{(4)}; a_{2}^{(5)}; a_{3}^{(1)}; a_{3}^{(2)}; a_{3}^{(3)}; a_{3}^{(4)}; a_{3}^{(5)}; a_{4}^{(1)}; a_{4}^{(2)}; a_{4}^{(3)}; a_{4}^{(4)}; a_{4}^{(5)}; b_{1}^{(1)}; b_{2}^{(1)}; b_{3}^{(1)}; b_{1}^{(2)}; b_{2}^{(2)}; b_{3}^{(2)}; b_{1}^{(3)}; b_{2}^{(3)}; b_{3}^{(3)}; b_{2}^{(4)}; b_{3}^{(4)}; b_{4}^{(4)}; b_{2}^{(5)}; b_{3}^{(5)}; b_{4}^{(5)}]

Figure 2.

Now let u=^{def} ((1, 1), (1, 2), …, (1, n)) and v=^{def} ((t+m+1, 1), …, (t+m+1, n)). It is clear that D(U) is planar and that u and v are fully compatible. Furthermore, every directed path in D(U) from (1, i) to (t + m + 1, j) (1 ≤ i, j ≤ n) is necessarily of length t + m. By the Transfer Matrix Method (see, e.g., [35], §4.7, Theorem 4.7.1), this implies that P_{D(U)}((1, i), (t + m + 1, j)) equals the ((1, i), (t + m + 1, j)) entry of A^{t+m} where A is the adjacency matrix of the weighted digraph D(U). From our construction of D(U) we see that

A = [ \begin{matrix}0 & W_{1} & 0 & ⋯ & 0 & 0 \\ 0 & 0 & W_{2} & ⋯ & 0 & 0 \\ ⋮ & & & ... & & ⋮ \\ 0 & 0 & 0 & ⋯ & 0 & W_{m+t} \\ 0 & 0 & 0 & ⋯ & 0 & 0 \end{matrix} ]

(in block matrix notation), where we have given the linear ordering (1, 1), (1, 2), …, (1, n), (2, 1), …, (2, n), …, (t + m + 1, 1), …, (t + m + 1, n) to the vertices of D(U). Therefore,

A^{m+t} = [ \begin{matrix}0 & ⋯ & 0 & W_{1} … W_{m+t} \\ 0 & ⋯ & 0 & 0 \\ ⋮ & & ⋮ & ⋮ \\ 0 & ⋯ & 0 & 0 \end{matrix} ]

and hence

(P_{D(U)}((1, i), (t + m + 1, j)))_{1≤i, j≤n} = W_{1} … W_{m+t} = U ,  (7)

as desired. □

The simplicity of the geometry of the digraphs D(U) (cfr. Figure 2) allows us to explicitly describe the generating functions P_{D(U)}((1, i), (t + m + 1, j)), 1 ≤ i, j ≤ n, and thus the entries of U. For this we will find it convenient to embed the digraphs D(U) in a larger digraph and to put independent variables as weights on the edges.

Let X =^{def} (x_{i,j})_{i,j∈N}, and Y =^{def} (y_{i,j})_{i,j∈N} be two infinite matrices of independent variables (or of real numbers). We define a weighted digraph D(X, Y) on vertex set N × N by putting a directed edge from (i, j) to (i + 1, j) (respectively, (i, j + 1)) with weight x_{i+1,j} (respectively, y_{i,j+1}) for all (i, j) ∈ N × N. A portion of D(X, Y) is shown in Figure 3.

[figure: y_{0,1}; y_{0,2}; y_{0,3}; y_{1,1}; y_{1,2}; y_{1,3}; y_{2,1}; y_{2,2}; y_{2,3}; y_{3,1}; y_{3,2}; y_{3,3}; x_{1,0}; x_{1,1}; x_{1,2}; x_{1,3}; x_{2,0}; x_{2,1}; x_{2,2}; x_{2,3}; x_{3,0}; x_{3,1}; x_{3,2}; x_{3,3}]

Figure 3: The digraph D(X, Y).

For n, k ∈ N we let

h_{n,k}(X, Y) =^{def} ∑_{0=i_{0}≤i_{1}≤...≤i_{n}≤i_{n+1}=k} x_{1,i_{1}} … x_{n,i_{n}} y_{0,(i_{0},i_{1}]} y_{1,(i_{1},i_{2}]} … y_{n,(i_{n},i_{n+1}]} , (8)

where y_{i,(j,k]} =^{def} ∏_{j<s≤k} y_{i,s} for i, j, k ∈ N. We also let h_{n,k}(X, Y) =^{def} 0 if either n < 0 or k < 0. We call h_{n,k}(X, Y) the generalized complete homogeneous symmetric function of degrees n and k. Note that h_{n,k}(X, Y) is a homogeneous polynomial of degree n in the x_{i,j}’s and of degree k in the y_{i,j}’s. Furthermore, the complete homogeneous symmetric functions are a specialization of the h_{n,k}(X, Y)’s, since

h_{n,k} ([ \begin{matrix}x_{0} & x_{1} & x_{2} & ⋯ \\ x_{0} & x_{1} & x_{2} & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix} ] , [ \begin{matrix}1 & 1 & 1 & ⋯ \\ 1 & 1 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix} ]) = h_{n}(x_{0}, …, x_{k}) ,

for all n, k ∈ N.

The reason for introducing the polynomials h_{n,k}(X, Y) is that they give a simple way to express the path generating function between any two points of the digraph D(X, Y). Given n, k ∈ N we let S_{(n,k)}(X) =^{def} (x_{n+i,k+j})_{i,j∈N} and S_{(n,k)}(X, Y) =^{def} (S_{(n,k)}(X), S_{(n,k)}(Y)).

Proposition 3.2 Let (i, j), (n, k) ∈ N × N. Then

P_{D(X,Y)}((i, j), (n, k)) = h_{n−i,k−j}(S_{(i,j)}(X, Y)) .  (9)

Proof. We may divide the monomials appearing in the RHS of (8) in two disjoint sets according as to whether i_{n} = k or i_{n} < k. This immediately implies that

h_{n,k}(X, Y) = x_{n,k} h_{n−1,k}(X, Y) + y_{n,k} h_{n,k−1}(X, Y)

for all n, k ∈ N with n + k ∈ P. On the other hand, it is clear from the definition of D(X, Y) that

P_{D(X,Y)}((0, 0), (n, k)) = x_{n,k} P_{D(X,Y)}((0, 0), (n−1, k))+y_{n,k} P_{D(X,Y)}((0, 0), (n, k−1))

for all n, k ∈ N with n + k ∈ P. Since P_{D(X,Y)}((0, 0), (0, 0)) = h_{0,0}(X, Y) = 1, this implies that

P_{D(X,Y)}((0, 0), (n, k)) = h_{n,k}(X, Y)  (10)

for all n, k ∈ N. Now, the definition of D(X, Y) also implies that

P_{D(X,Y)}((i, j), (n, k)) = P_{D(S_{(i,j)}(X,Y))}((0, 0), (n − i, k − j))  (11)

for all (i, j), (n, k) ∈ N × N. Comparing (10) and (11) yields (9), as desired. □

We can now interpret the entries of any totally positive matrix as evaluations of generalized complete homogeneous symmetric functions.

Theorem 3.3 Let U be an n × n (real) matrix. Then U is totally positive if and only if there exist m, t ∈ N and two nonnegative matrices A = (a_{i,j})_{i,j∈N}, and B = (b_{i,j})_{i,j∈N}, with finitely many nonzero entries, such that

U = (h_{t+i−j,m+j−i}(S_{(n+1−i,i)}(A, B)))_{1≤i, j≤n} .  (12)

Furthermore, U is upper (respectively, lower) triangular if and only if m = 0 (respectively, t = 0).

Proof. Suppose first that there exist m, t ∈ N and two matrices A, B as in the statement of the theorem such that (12) holds. Then, by Proposition 3.2,

U = (P_{D(A,B)}((n + 1 − i, i), (t + n + 1 − j, m + j)))_{1≤i, j≤n} .  (13)

But it is easy to see that D(A, B) and the n-tuples ((n, 1), …, (1, n)) and ((t + n, m + 1), …, (t + 1, m + n)) satisfy all the hypotheses of Theorem 3.1, and hence U is totally positive, as claimed.

Conversely, suppose that U is totally positive. It then follows from the proof of Theorem 3.1 that there exist m, t ∈ N and n × n nonnegative matrices W_{1} … W_{m+t} such that (5), (6), and (7) hold. It is then easy to see that we can use the entries of W_{1}, …, W_{m+t} to define two nonnegative matrices A = (a_{i,j})_{i,j∈N} and B = (b_{i,j})_{i,j∈N}, with finitely many nonzero entries, such that

P_{D(A,B)}((n + 1 − i, i), (t + n + 1 − j, m + j)) = P_{D(U)}((1, i), (t + m + 1, j)) (14)

for all 1 ≤ i, j ≤ n, where D(U) has the same meaning as in the proof of Theorem 3.1. The thesis then follows from (7), (14) and (9). Finally, it follows from Theorem 4.1 of [14], that if U is upper (respectively, lower) triangular then we can take m = 0 (respectively, t = 0), in (7), and this completes the proof. □

Note that the preceding theorem explicitly characterizes totally positive matrices. Even though other characterizations of totally positive matrices have appeared before in the literature (see, e.g., [41] where a characterization is given in terms of alternating polytopes), none of these is as simple as the one given above which, in effect, gives an explicit parametrization of the set of all totally positive matrices.

Further evidence of the fact that Theorem 3.3 gives the “right” characterization of totally positive matrices is provided by the comparison with the classical characterization theorem for Pólya frequency sequences obtained by Edrei in 1953 (see, e.g., [17], or [24], Chap. 8, §5, Theorem 5.3). This result, in fact, expresses any element of a Pólya frequency sequence as some “generalized complete homogeneous symmetric function” (more precisely, as a linear combination of super-Schur functions corresponding to one-row shapes) evaluated at nonnegative real numbers (cfr. [24], loc. cit., and [10], §2, eq.(6)).

Besides giving an explicit representation of any totally positive matrix Theorem 3.3 enables us to give a simple combinatorial interpretation of the determinant of any minor of any such matrix. This can be accomplished by analyzing r-tuples of non-intersecting paths in the digraph D(X, Y).

Given a weakly increasing sequence i_{0} ≤ i_{1} ≤ … ≤ i_{n+1} of natural numbers we define its (X, Y)-weight to be

w_{(X,Y)}(i_{0}, …, i_{n+1}) =^{def} x_{1,i_{1}} … x_{n,i_{n}} y_{0,(i_{0},i_{1}]} y_{1,(i_{1},i_{2}]} … y_{n,(i_{n},i_{n+1}]} .

For example, w_{(X,Y)}(0, 0, 0, 2, 4, 5) = x_{1,0} x_{2,0} x_{3,2} x_{4,4} y_{2,1} y_{2,2} y_{3,3} y_{3,4} y_{4,5}.

Given two partitions λ = (λ_{1}, …, λ_{r}) and μ = (μ_{1}, …, μ_{r}) such that μ ⊆ λ and a shifted skew tabloid π =^{def} (π_{i,j})_{1≤i≤r μ_{i}+i≤j≤λ_{i}+i−1} of shape λ \ μ we define its (X, Y)-weight to be

w_{(X,Y)}(π) =^{def} ∏_{i=1}^{r} w_{S_{(μ_{i}+1,0)}(X,Y)}(π_{i}).  (15)

For example, if π is

1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 5 5  (16)

then its (X, Y)-weight (as a shifted skew tabloid of shape (10, 9, 6) \ (3, 1, 0)) is

w_{S_{(4,0)}(X,Y)}(1, 2, 2, 2, 2, 2, 2) w_{S_{(2,0)}(X,Y)}(2, 2, 3, 3, 3, 3, 3, 3) w_{S_{(1,0)}(X,Y)}(3, 4, 4, 4, 5, 5)

= (x_{[5,9],2} y_{4,2})(x_{3,2} x_{[4,8],3} y_{3,3})(x_{[2,4],4} x_{5,5} y_{1,4} y_{4,5}).  (17)

Note that the (X, Y)-weight of π depends on λ and μ and not just on λ \ μ.

Given (a, b), (c, d) ∈ N × N and a directed path τ in D(X, Y) from (a, b) to (c, d) we let

M_{τ}(i) =^{def} max {j : (i, j) ∈ τ}

for a ≤ i ≤ c.

Proposition 3.4 Let r ∈ P and {a_{1}, …, a_{r}}_{>}, {b_{1}, …, b_{r}}_{<}, {c_{1}, …, c_{r}}_{>}, {d_{1}, …, d_{r}}_{<} ⊆ P. Then there is a bijection between r-tuples of non-intersecting paths in D(X, Y) from ((a_{1}, b_{1}), …, (a_{r}, b_{r})) to ((c_{1}, d_{1}), …, (c_{r}, d_{r})) and column strict shifted skew tableaux of shape (c_{1} + 1, …, c_{r} + 1) \ (a_{1} − 1, …, a_{r} − 1) and size (d_{1}, …, d_{r}) \ (b_{1}, …, b_{r}). Furthermore, if (τ_{1}, …, τ_{r}) and π correspond under the above bijection then

w_{D(X,Y)}(τ_{1}, …, τ_{r}) = w_{(X,Y)}(π) .

Proof. Let (τ_{1}, …, τ_{r}) be an r-tuple of non-intersecting paths in D(X, Y) from ((a_{1}, b_{1}), …, (a_{r}, b_{r})) to ((c_{1}, d_{1}), …, (c_{r}, d_{r})) (so that τ_{i} goes from (a_{i}, b_{i}) to (c_{i}, d_{i}),

for i = 1, …, r). Let π =^{def} (π_{i,j})_{1≤i≤r, a_{i}+i−1≤j≤c_{i}+i} where

π_{i,j} =^{def} M_{j−i}(τ_{i})  (18)

for 1 ≤ i ≤ r, a_{i} − 1 ≤ j − i ≤ c_{i} (where M_{a_{i}−1}(τ_{i}) =^{def} b_{i}, for i = 1, …, r). For each i ∈ [r] we then clearly have that

b_{i} = π_{i,a_{i}+i−1} ≤ π_{i,a_{i}+i} ≤ … ≤ π_{i,c_{i}+i} = d_{i} .  (19)

Furthermore, for i ∈ [r − 1], τ_{i} and τ_{i+1} are non-intersecting, if and only if

M_{k−1}(τ_{i+1}) > M_{k}(τ_{i})  (20)

for all a_{i} ≤ k ≤ c_{i+1}. Since it is clear from (19) that π_{i,a_{i}+i−1} < π_{i+1,a_{i}+i−1} and π_{i,c_{i+1}+i+1} < π_{i+1,c_{i+1}+i+1}, we conclude from (18) and (20) that π is column strict.

Conversely, let π = (π_{i,j})_{1≤i≤r, a_{i}+i−1≤j≤c_{i}+i} be a column strict tableau satisfying (19). It is clear that then, for each i ∈ [r], there is a unique path τ_{i} from (a_{i}, b_{i}) to (c_{i}, d_{i}) such that (18) holds for all a_{i} + i ≤ j ≤ c_{i} + i, namely,

τ_{i} =^{def} ⋃_{j=a_{i}}^{c_{i}}{(j, k) : π_{i,j+i−1} ≤ k ≤ π_{i,j+i}} .  (21)

Since π is column strict, this implies that (20) holds for all i ∈ [r − 1], a_{i} ≤ k ≤ c_{i+1} + 1, and this, as remarked above, implies that τ_{i} and τ_{i+1} are non-intersecting, for i = 1, …, r − 1.

Finally, if π and (τ_{1}, …, τ_{r}) correspond under the above bijection then, from (21) and our definitions, we conclude that

w_{D(X,Y)}(τ_{i}) = ∏_{j=a_{i}}^{c_{i}} y_{j,(π_{i,j+i−1},π_{i,j+i}]} ∏_{j=a_{i}}^{c_{i}−1} x_{j+1,π_{i,j+i}}
= w_{S_{(a_{i},0)} (X,Y)}(π_{i}) ,

for i = 1, …, r, and the thesis follows. □

We illustrate the above proposition with an example. Let π be the shifted skew column strict tableau of shape (10, 9, 6)\(3, 1, 0) given in (16). Then the corresponding triple of non-intersecting paths (τ_{1}, τ_{2}, τ_{3}) in D(X, Y) from ((4, 1), (2, 2), (1, 3)) to ((9, 2), (8, 3), (5, 5)) is depicted in Figure 4.

[figure: (4,1); (2,2); (9,2); (1,3); (8,3); (5,5)]

Figure 4.

Their weight is

w_{D(X,Y)}(τ_{1}, τ_{2}, τ_{3}) = (y_{4,2}x_{[5,9],2}) (x_{3,2}y_{3,3}x_{[4,8],3}) (y_{1,4}x_{[2,4],4}y_{4,5}x_{5,5}) ,

which is in accordance with (17).

We can now interpret any minor of any totally positive matrix as a “generalized flagged Schur function”. In particular, this gives a combinatorial interpretation to any such minor, thus also providing an answer to a general question first raised in [6] (see, §2.2, p.10).

Theorem 3.5 Let U be an n × n totally positive matrix and m, t, A, and B as in the statement of Theorem 3.3. Let r ∈ [n], and {m_{1}, …, m_{r}}_{<}, {k_{1}, …, k_{r}}_{<} ⊆ [n]. Then

U ( \begin{matrix}m_{1}, …, m_{r} \\ k_{1}, …, k_{r} \end{matrix} ) = ∑_{π} w_{(A,B)}(π)

where the sum is over all column strict skew tableaux π of shape (t+n+2−k_{1}, …, t+ n+1−k_{r}+r)\(n−m_{1}, …, n−m_{r}+r−1) and size (m+k_{1}, …, m+k_{r})\(m_{1}, …, m_{r}).

Proof. By Theorem 3.3 and Proposition 3.2 we have that

U = (P_{D(A,B)}((n + 1 − i, i), (t + n + 1 − j, m + j)))_{1≤i,j≤n}.

Since D(A, B) satisfies the hypotheses of Lemma 2.1, and u =^{def} ((n, 1), …, (1, n)), and v =^{def} ((t + n, m + 1), …, (t + 1, m + n)) are fully compatible we conclude that

U ( \begin{matrix}m_{1}, …, m_{r} \\ k_{1}, …, k_{r} \end{matrix} ) = ∑_{(τ_{1},...,τ_{r})} w_{D(A,B)}(τ_{1}, …, τ_{r})

where the sum is over all r-tuples (τ_{1}, …, τ_{r}) of non-intersecting paths in D(A, B) from ((n + 1 − m_{1}, m_{1}), …, (n + 1 − m_{r}, m_{r})) to ((t + n + 1 − k_{1}, m + k_{1}), …, (t + n + 1 − k_{r}, m + k_{r})). The thesis now follows from Proposition 3.4. □

Besides enabling us to give a combinatorial interpretation to any minor of any totally positive matrix Theorems 3.1 and 3.3 have also other applications to the theory of totally positive matrices. For example, the following fundamental fact (usually proved using the classical Cauchy-Binet identity, see, e.g., [24], Chap. 0, p.1) is an immediate consequence of Theorem 3.1, (and its proof).

Corollary 3.6 Let U and V be two n × n totally positive matrices. Then U V is totally positive. □

Another application is to the computation of immanants of totally positive matrices. Recall (see, e.g., [21], Definition 1.1) that given an n×n matrix U =^{def} (U_{i,j})_{1≤i, j≤n} and a partition λ of n the immanant of U corresponding to λ is defined by

Imm_{λ}(U) =^{def} ∑_{σ∈S_{n}} χ^{λ}(σ)U_{1,σ(1)} …, U_{n,σ(n)} ,  (22)

where χ^{λ} is the irreducible character of S_{n} corresponding to the partition λ. Recently there has been a revived interest on immanants (especially of totally positive matrices) and several conjectures have been made and proved about them (see, e.g., [21], [22], [39], [40], and [23], for further information). Proposition 3.2 enables us to use a combinatorial construction first introduced in [21] to prove the following result.

Theorem 3.7 Let n, m, t ∈ N and

U =^{def} (h_{t+i−j, m+j−i}(S_{(n+1−i,i)}(X, Y)))_{1≤i, j≤n} .

Then

Imm_{λ}(U) ∈ N[X, Y] ,

for all partitions λ of n.

Proof. By Proposition 3.2 we have that

U = (P_{D(X,Y)}(u_{i}, v_{j}))_{1≤i, j≤n}  (23)

where u_{i} =^{def} (n + 1 − i, i), and v_{i} =^{def} (t + n + 1 − i, m + i), for i = 1, …, n. For σ ∈ S_{n} let C_{σ} be the set of all n-tuples of paths (τ_{1}, …, τ_{n}) such that τ_{i} is a directed path from u_{i} to v_{σ(i)}, for i = 1, …, n. Then from (22) and (23) we have that

Imm_{λ}(U) = ∑_{σ∈S_{n}} χ^{λ}(σ) ∏_{i=1}^{n} P_{D(X,Y)}(u_{i}, v_{σ(i)})
= ∑_{σ∈S_{n}} χ^{λ}(σ) ∑_{τ∈C_{σ}} w_{D(X,Y)}(τ)
= ∑_{τ∈C} χ^{λ}(σ_{τ}) w_{D(X,Y)}(τ) ,

where C =^{def} ⋃_{σ∈S_{n}} C_{σ} and, for τ ∈ C, σ_{τ} is the unique element of S_{n} such that τ ∈ C_{σ_{τ}}. Therefore,

Imm_{λ}(U) = ∑_{α∈M(X,Y)} α ∑_{τ∈M_{α}} χ^{λ}(σ_{τ}) = ∑_{α∈M(X,Y)} α χ^{λ} ( ∑_{τ∈M_{α}} σ_{τ} ) , (24)

where M(X, Y) is the set of all monomials (of finite degree) in the variables x_{i,j} and y_{i,j}, i, j ∈ N, and M_{α} =^{def} {τ ∈ C : w_{D(X,Y)}(τ) = α}, for α ∈ M(X, Y). Now

fix α =^{def} ∏_{i,j≥0} x_{i,j}^{α_{i,j}} y_{i,j}^{β_{i,j}} ∈ M(X, Y) where α_{i,j}, β_{i,j} ∈ N for all i, j ∈ N. We claim

that

∑_{τ∈M_{α}} σ_{τ} = c T_{J_{1}} … T_{J_{r}}  (25)

for some r ∈ N, where J_{1}, …, J_{r} are subintervals of [n], c ≥ 0, and, for any J ⊆ [n],

T_{J} =^{def} ∑_{σ∈S(J)} σ ,

(where we consider S(J) as a subgroup of S_{n} in the obvious way). In fact, let D̃_{α}(X, Y) be the directed planar graph obtained from D(X, Y) by replacing the edge from (i − 1, j) (respectively, (i, j − 1)) to (i, j) by α_{i,j} (respectively, β_{i,j}) edges, each having weight x_{i,j} (respectively, y_{i,j}), for all (i, j) ∈ N × N. It is then clear that

∑_{τ∈M̃_{α}} σ_{τ} = ∏_{i,j≥0}(α_{i,j})! (β_{i,j})! ∑_{τ∈M_{α}} σ_{τ}  (26)

where M̃_{α} = ⋃_{σ∈S_{n}} M̃_{α,σ} and M̃_{α,σ} is the set of all n-tuples of edge-disjoint paths (τ_{1}, …, τ_{n}) in D̃_{α}(X, Y) from (u_{1}, …, u_{n}) to (v_{σ(1)}, …, v_{σ(n)}) such that w_{D̃_{α}(X,Y)}(τ) = α. For τ ∈ M̃_{α} and 0 ≤ γ ≤ t + m, γ ∉ [t + m − 1], let (x_{i}^{(γ)}, y_{i}^{(γ)}) be the point of intersection of τ_{i} (considered as a continuous curve) with the line x + y = γ + n + 1, and σ_{τ}^{(γ)} be the unique permutation of S_{n} such that

x_{σ_{τ}^{(γ)}(1)}^{(γ)} < … < x_{σ_{τ}^{(γ)}(n)}^{(γ)} .

Note that σ_{τ}^{(0)} =Id, σ_{τ}^{(t+m)} = σ_{τ} and σ_{τ}^{(γ)} = σ_{τ}^{(δ)} for all a − 1 < γ, δ < a, and a ∈ [t+m]. Furthermore, it is clear from the geometry of D̃_{α}(X, Y) that if a ∈ [t+m−1] and a − 1 < γ < a, then

( ∏_{i=1}^{a+n}(b_{i} − b_{i−1})!) ∑_{τ∈M̃_{α}} σ_{τ}^{(γ+1)} = ( ∏_{i=1}^{a+n} T_{(b_{i−1},b_{i}]}) ∑_{τ∈M̃_{α}} σ_{τ}^{(γ)} ,  (27)

where b_{i} =^{def} ∑_{j=1}^{i}(α_{i,a+n+1−i} + β_{i,a+n+1−i}) for i = 0, …, a + n, and this, by (26),

proves (25) as claimed. But it was proved by Greene (see, [22], Theorem 1.3) that

χ^{λ}(T_{J}) ≥ 0

for any partition λ and any subinterval J ⊆ [n]. Thus the thesis follows from (24), and (25). □

As an immediate consequence of Theorems 3.3 and 3.7 we obtain the following result which was first conjectured, and then proved, by Stembridge (see [39], Conjecture 2.2, and [40], Corollary 3.3).

Corollary 3.8 Let U be an n × n totally positive matrix, and λ be a partition of n. Then Imm_{λ}(U) ≥ 0. □

4 The method of invariant digraphs

Even though Theorems 3.1 and 3.3 completely characterize the class of totally positive matrices and have, as we have seen, several interesting and non-trivial consequences, their interest is mainly theoretical and they are difficult to apply in practice. In fact, given a totally positive matrix U it is usually hard to determine the parameters and the weights of the corresponding digraph D(U) constructed in the proof of Theorem 3.1 (or, equivalently, the integers t, m and matrices A, B appearing in the statement of Theorem 3.3). Conversely, given some parameters t, m, A, and B, the matrix U defined by (12) will usually lack any simple combinatorial meaning except that given by (13). So the usefulness of Theorems 3.1 and 3.3 as tools for proving the total positivity property of particular matrices is limited.

However, there are other total positivity results that can be deduced from Lemma 2.1 and which, though less powerful than Theorems 3.1 and 3.3, are easier to apply and still powerful enough to yield the total positivity of many interesting matrices arising from algebraic and enumerative combinatorics.

Let D = (N × N, A, w) be a, locally finite, weighted digraph. Recall (see [10], §2) that D is weakly y-invariant if

P_{D}((0, m) , (n, k)) = P_{D}((0, 0) , (n, k − m))  (28)

for all m, n, k ∈ N with k ≥ m, and that D is y-invariant if the map S_{y} : D → D defined by

S_{y}((n, k)) =^{def} (n, k + 1)

for all (n, k) ∈ N × N is an isomorphism between D and S_{y}(D) (as weighted digraphs). The following theorem appears in [10] (see Theorem 2.1) and its proof is an easy consequence of (28) and of Lemma 2.1. We restate it here for completeness and because we will use it repeatedly.

Theorem 4.1 Let D be a locally finite, weighted digraph on vertex set N × N. Assume that D is planar and weakly y-invariant. Let {n_{1}, …, n_{r}}_{<}, {k_{1}, …, k_{r}, m}_{<} ⊆ N, and n ∈ N. Then

(P_{D}((0, 0), (n, k)))_{n,k∈N} ( \begin{matrix}n_{1}, …, n_{r} \\ k_{1}, …, k_{r} \end{matrix} ) = N(u_{1}, v_{1}) ,  (29)

and

\{P_{D}((0, 0), (n, k))\}_{k∈N} ( \begin{matrix}n_{1}, …, n_{r} \\ k_{1}, …, k_{r} \end{matrix} ) = N(u_{2}, v_{2}) ,

where u_{1} = ((0, m−k_{1}), …, (0, m−k_{r})), v_{1} = ((n_{1}, m), …, (n_{r}, m)), u_{2} = ((0, n_{1}), …, (0, n_{r})), and v_{2} = ((n, k_{1}), …, (n, k_{r})). □

From this we immediately deduce the following total positivity result.

Corollary 4.2 Let D be a locally finite, nonnegative, digraph on vertex set N × N. Assume that D is planar and weakly y-invariant. Let M = (M_{n,k})_{n,k∈N} be the infinite matrix defined by

M_{n,k} =^{def} P_{D}((0, 0) , (n, k))  (30)

for (n, k) ∈ N × N. Then: i) M is totally positive;

ii) every row of M is a PF sequence. □

We can now define and study a class of infinite matrices which posses many remarkable total positivity properties and which includes many familiar matrices arising in enumerative and algebraic combinatorics as well as in the theory of symmetric functions. Let x =^{def} {x_{n}}_{n∈N}, y =^{def} {y_{n}}_{n∈N}, and z =^{def} {z_{n}}_{n∈N} be three sequences of independent variables. We will adopt the convention that x_{n} =^{def} y_{n} =^{def} z_{n} =^{def} 0 if n < 0.

Theorem 4.3 Let t ∈ N. Define a matrix M = (M_{n,k})_{n,k∈N} by

M_{n,k} = z_{n} M_{n−t,k−1} + y_{n} M_{n−1−t,k−1} + x_{n} M_{n−1,k}  (31)

if n + k ∈ P (where M_{n,k} =^{def} 0 if either n < 0 or k < 0), and M_{0,0} =^{def} 1. Then:

i) M is (x, y, z)-totally positive;

ii) every row of M is an (x, y, z)-PF sequence.

Proof. We construct a weighted digraph D(t) on N × N as follows. We put an edge from (n − t, k − 1) (respectively, (n − 1 − t, k − 1), (n − 1, k)) to (n, k) with weight z_{n} (respectively, y_{n}, x_{n}) for all (n, k) for which (n − t, k − 1) (respectively, (n − 1 − t, k − 1) , (n − 1, k)) is in N × N. Clearly, D(t) is planar and y-invariant, and

M_{n,k} = P_{D(t)}((0, 0), (n, k)) ,  (32)

so the thesis follows from Theorem 4.1. □

In what follows we will always denote by M_{t}(x, y, z) the matrix defined in the preceding theorem. Note that the columns of M_{t}(x, y, z) are not, in general, (x, y, z) − P F, as simple examples show. Also note that the matrices M_{t}(x, y, z) include the matrix of super-Schur functions studied in [10], as is shown by the next result, whose proof follows immediately from (32) and Proposition 2.2 of [10]. Given a partition λ, we denote by s_{λ}(x/y) the super-Schur function corresponding to λ in the variables x and y (we refer the reader to [3], [4], [10], or [15], for the definition and further information about super-Schur functions).

Proposition 4.4 We have that

(s_{(k)}(x_{1}, …, x_{n}/y_{1}, …, y_{n}))_{n,k∈N} = M_{0}(1, y, {0, x_{1}, x_{2}, …}) .□

The matrix M_{0}(x, y, z) has an additional total positivity property. Given an infinite matrix M =^{def} (M_{n,k})_{n,k∈N} and t ∈ N, we let

L_{t}(M) =^{def} (M_{n−kt,k})_{n,k∈N}  (33)

(where M_{n,k} =^{def} 0 if either n < 0 or k < 0). So L_{0}(M) = M, L_{t}(L_{r}(M)) = L_{t+r}(M), and the k-th column of L_{t}(M) equals the kth-column of M preceded by a string of kt zeros.

Theorem 4.5 Let t ∈ N. Then

L_{t}(M_{0}(x, y, z)′)

is (x, y, z)-totally positive.

Proof. Construct a weighted digraph D′(t) on N × N as follows. Put an edge from (n, k − 1) (respectively, (n − 1, k − t − 1), (n − 1, k − t)) to (n, k) with weight z_{n} (respectively, y_{n}, x_{n}) for all (n, k) for which (n, k −1) (respectively, (n−1, k −t−1), (n − 1, k − t)) is in N × N. A portion of the digraph D′(1) is shown in Figure 5.

[figure: (0,0); (0,1); (1,0); z_{0}; z_{0}; z_{0}; z_{0}; x_{1}; x_{1}; x_{1}; x_{1}; y_{1}; y_{1}; y_{1}; z_{1}; z_{1}; z_{1}; z_{1}; x_{2}; x_{2}; x_{2}; x_{2}; y_{2}; y_{2}; y_{2}; z_{2}; z_{2}; z_{2}; z_{2}; x_{3}; x_{3}; x_{3}; x_{3}; y_{3}; y_{3}; y_{3}; z_{3}; z_{3}; z_{3}; z_{3}; x_{4}; x_{4}; x_{4}; x_{4}; y_{4}; y_{4}; y_{4}; z_{4}; z_{4}; z_{4}; z_{4}]

Figure 5: The digraph D′(1).

Clearly, D′(t) is planar and y-invariant, and it follows from (31) and (33) that

L_{t}(M_{0}(x, y, z)′)′ = (P_{D′(t)}((0, 0), (n, k)))_{n,k∈N} ,  (34)

so the thesis follows from Theorem 4.1. □

Note that it is not true, in general, that if an infinite matrix M is totally positive then L_{t}(M) is totally positive. For example,

M = ( \begin{matrix}1 & 1 & 0 & ⋯ \\ 1 & 1 & 0 & ⋯ \\ 2 & 2 & 0 & ⋯ \\ 0 & 0 & 0 & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix} )

is totally positive, but L_{1}(M) is not.

The matrix L_{t}(M_{0}(x, y, z)′) can also be described directly by a simple linear recurrence analogous to (31).

Proposition 4.6 Let t ∈ N, and L =^{def} L_{t}(M_{0}(x, y, z)′). Then the entries L_{n,k} of L satisfy the recurrence relation

L_{n,k} = x_{k} L_{n−t,k−1} + y_{k} L_{n−1−t,k−1} + z_{k} L_{n−1,k} ,  (35)

for n + k ∈ P (where L_{n,k} =^{def} 0 if either n < 0 or k < 0), with the initial condition

L_{0,0} =^{def} 1. □

There are some simple relations that hold among the matrices M_{t}(x, y, z) which deserve to be mentioned. Their verification is left to the reader.

Proposition 4.7 For t ∈ N we have that:

i) M_{t}(x, y, 0) = M_{t+1}(x, 0, y);

ii) L_{1}(M_{0}(x, 0, y)′) = M_{0}(0, x, y)′. □

We close this section by remarking that other interesting classes of x-totally positive matrices can be obtained by “manipulating” the matrices M_{t}(x, y, z) suitably. We give one such example below.

Theorem 4.8 Let {a_{n}}_{n∈N}, {b_{n}}_{n∈N}, {α_{n}}_{n∈N}, {β_{n}}_{n∈N} be sequences of polynomials in N[x]. Define a matrix R =^{def} (R_{n,k})_{n,k∈N} by

R_{n,k} = (a_{n} + b_{n} α_{k})R_{n−1,k} + b_{n}β_{k}R_{n−1,k−1}  (36)

for n + k ∈ P (where a_{n} = b_{n} = α_{k} = β_{k} = R_{n,k} = 0 if either n < 0 or k < 0), and R_{0,0} =^{def} 1. Then R is x-totally positive.

Proof. Let M =^{def} M_{0}({a_{n}}_{n∈N}, {b_{n}}_{n∈N}, 0) and L =^{def} M_{0}(0, {β_{n}}_{n∈N}, {α_{n}}_{n∈N})′. By

Theorem 4.3 we know that L and M are x−T P. We claim that R = ML (note that M and L are both lower triangular, so that ML is well defined). We will prove this by showing that the entries of ML satisfy the recursion (36), with the same initial condition. In fact, using (31) and (35), we see that

(ML)_{n,k} = ∑_{j=0}^{n} M_{n,j} L_{j,k}
= ∑_{j=0}^{n−1} M_{n−1,j}(a_{n}L_{j,k} + b_{n}L_{j+1,k})
= a_{n}(ML)_{n−1,k} + b_{n}(α_{k}(ML)_{n−1,k} + β_{k} , (ML)_{n−1,k−1}) ,

and since (ML)_{0,0} = M_{0,0} L_{0,0} = 1, the claim follows. But it follows immediately from the Cauchy-Binet formula (see, e.g., [24], p. 1) that the product of two x−T P matrices is again x − T P and the thesis follows. □

5 Applications to combinatorics

The results obtained in the preceding section have numerous applications to combinatorics and to the theory of symmetric functions. In this section we look in detail at these applications. In many cases we obtain new results, in others we obtain simple and unified proofs of known results.

Our first application is to a natural common generalization of the elementary and complete homogeneous symmetric functions. Let t ∈ N and x =^{def} (x_{0}, x_{1}, …) be a sequence of independent variables. For k ∈ P and n ∈ N we let

e_{k}^{(t)}(x_{0}, …, x_{n}) =^{def} ∑_{i_{1},...,i_{k}} x_{i_{1}} … x_{i_{k}}  (37)

where the sum is over all i_{1}, …, i_{k} ∈ [n] such that i_{j+1} − i_{j} ≥ t for all 0 ≤ j ≤ k − 1, (where i_{0} =^{def} 0). We also let e_{0}^{(t)}(x_{0}, …, x_{n}) =^{def} 1 for all n ∈ N. So, for example, e_{k}^{(t)}(x_{0}, …, x_{n}) = 0 unless n ≥ k t, and e_{3}^{(2)}(x_{0}, …, x_{7}) = x_{3}x_{5}x_{7} +x_{2}x_{5}x_{7} +x_{2}x_{4}x_{7} + x_{2}x_{4}x_{6}. Also, it is clear that

e_{k}^{(0)}(x_{0}, …, x_{n}) = h_{k}(x_{0}, …, x_{n}) ,  (38)

and

e_{k}^{(1)}(x_{0}, …, x_{n}) = e_{k}(x_{1}, …, x_{n}) ,  (39)

for all k, n ∈ N.

Theorem 5.1 Let t ∈ N, and E_{t}(x) =^{def} (e_{k}^{(t)}(x_{0}, …, x_{n}))_{n,k∈N}. Then:

i) E_{t}(x) is x − T P;

ii) every row of E_{t}(x) is x − P F.

Proof. It follows immediately from our definitions that

e_{k}^{(t)}(x_{0}, …, x_{n}) = x_{n}e_{k−1}^{(t)}(x_{0}, …, x_{n−t}) + e_{k}^{(t)}(x_{0}, …, x_{n−1}) ,

for all n, k ∈ N with n + k ∈ P. Therefore

E_{t}(x) = M_{t}(1, 0, x) ,  (40)

and the thesis follows from Theorem 4.3. □

For t = 0, 1 part i) of the preceding theorem was first proved by Sagan (see [31], Theorem 5.4), while part ii) is then a consequence of the well known Jacobi-Trudi identity, (see, e.g., [27], Chap. I, §5, eqs. (5.4) and (5.5)).

There is another generalization of the elementary symmetric functions which also possesses interesting total positivity properties. For t, k ∈ P, and n ∈ N, let

a_{k}^{(t)}(x_{1}, …, x_{n}) =^{def} ∑_{i_{1},...,i_{k}} x_{i_{1}} … x_{i_{k}}  (41)

where the sum is over all 1 ≤ i_{1} < … < i_{k} ≤ n such that i_{j} ≡ j (mod t) for j = 1, …, k. We also let a_{0}^{(t)}(x_{1}, …, x_{n}) =^{def} 1, for all n ∈ N. So, for example, a_{2}^{(2)}(x_{1}, …, x_{6}) = x_{1}x_{2} +x_{1}x_{4} +x_{1}x_{6} +x_{3}x_{4} +x_{3}x_{6} +x_{5}x_{6}, a_{k}^{(t)}(x_{1}, …, x_{n}) = 0 unless n ≥ k, and a_{k}^{(t)}(x_{1}, …, x_{n}) = a_{k}^{(t)}(x_{1}, …, x_{n−1}) if n ≢ k (mod t). Also note that

a_{k}^{(1)}(x_{1}, …, x_{n}) = e_{k}(x_{1}, …, x_{n})

for all n, k ∈ N.

Theorem 5.2 Let t ∈ P, and A_{t}(x) =^{def} (a_{n−tk}^{(t)}(x_{1}, …, x_{n}))_{k,n∈N}. Then:

i) A_{t}(x) is x-T P;

ii) every row of A_{t}(x) is x-P F.

Proof. Note that it follows from our definitions that if n ≡ k (mod t) and x_{i_{1}} … x_{i_{k}} is a monomial appearing on the RHS of (41) with i_{k} < n, then i_{k} ≤ n − t (since n − t + 1, …, n − 1 ≢ k (mod t)). Therefore

a_{k}^{(t)}(x_{1}, …, x_{n}) = x_{n}a_{k−1}^{(t)}(x_{1}, …, x_{n−1}) + a_{k}^{(t)}(x_{1}, …, x_{n−t}) ,

if n ≡ k (mod t). Hence

a_{n−tk}^{(t)}(x_{1}, …, x_{n}) = x_{n} a_{n−1−tk}^{(t)}(x_{1}, …, x_{n−1}) + a_{n−t−t(k−1)}^{(t)}(x_{1}, …, x_{n−t}) ,

for all n, k ∈ N with n + k > 0. This shows that

A_{t}(x) = M_{t}(x, 0, 1) ,  (42)

and the thesis follows from Theorem 4.3.□

We now concentrate on more concrete combinatorial applications. For n, k ∈ N we denote by S[n, k]_{p,q} and c[n, k]_{p,q} the (p, q)-Stirling numbers of the second and first kind, respectively. These are defined inductively by letting

S_{p,q}[n, k] = p^{k−1} S_{p,q}[n − 1, k − 1] + [k]_{p,q} S_{p,q}[n − 1, k] ,

and

c_{p,q}[n, k] = p^{n} c_{p,q}[n − 1, k − 1] + q[n − 1]_{q} c_{p,q}[n − 1, k] ,

if n + k ∈ P (with the convention that S_{p,q}[n, k] =^{def} c_{p,q}[n, k] =^{def} 0 if either n < 0 or k < 0), and S_{p,q}[0, 0] =^{def} c_{p,q}[0, 0] =^{def} 1. (We refer the reader to [42] and [29] for combinatorial interpretations and further information about these polynomials). It then follows immediately from these definitions and from the definition of M_{t}(x, y, z) (see (31)) that

(S_{p,q}[n + 1, k + 1])_{n,k∈N} = M_{0}(0, {p^{n}}_{n∈N}, {[n + 1]_{p,q}}_{n∈N})′ ,

and

(c_{p,q}[n + 1, k + 1])_{n,k∈N} = M_{0}({q[n]_{q}}_{n∈N}, {p^{n+1}}_{n∈N}, 0) .

The next result is therefore an immediate consequence of Theorems 4.3 and 4.5.

Corollary 5.3 Let S(p, q) =^{def} (S_{p,q}[n + 1, k + 1])_{n,k∈N}, C(p, q) =^{def} (c_{p,q}[n + 1, k + 1])_{n,k∈N}, and t ∈ N. Then:

i) L_{t}(S(p, q)) and L_{t}(C(p, q)′) are (p, q) − T P;

ii) every column of S(p, q) is (p, q) − P F;

iii) every row of C(p, q) is (p, q) − P F. □

We can also obtain easily the main total positivity properties of various matrices of q-binomial coefficients. For n, k ∈ N we let

[\begin{matrix}n \\ k \end{matrix}]_{q} =^{def} ∏_{i=1}^{k} \frac{(1 − q^{n−i+1})}{(1 − q^{i})} .  (43)

The following result first appeared in [31], (see Corollary 5.5 and §6).

Corollary 5.4 Let F (q) =^{def} ([\begin{matrix}n+k \\ k \end{matrix}]_{q})_{n,k∈N}, and t ∈ N. Then:

i) L_{t}(F (q)) is q − T P;

ii) every column of F (q) is q − P F.

Proof. It follows easily from (43) that

[\begin{matrix}n+k \\ n \end{matrix}]_{q} = [\begin{matrix}n+k−1 \\ n−1 \end{matrix}]_{q} + q^{n} [\begin{matrix}n+k−1 \\ n \end{matrix}]_{q}

for n + k ∈ P. Hence

F (q) = M_{0}(1, 0, {q^{n}}_{n∈N})′ ,

and the thesis follows from Theorems 4.3 and 4.5. □

Note that L_{1}(F (q)) is the usual matrix of q-binomial coefficients ([\begin{matrix}n \\ k \end{matrix}]_{q})_{n,k∈N}. The fact that, for a fixed q ≥ 0, L_{1}(F (q)) and L_{2}(F (q)) are totally positive matrices was first proved by Karlin in [24].

There are countless generalizations and analogs of Stirling, q-Stirling, and (p, q)- Stirling numbers of both kinds existing in the literature, and many of them can be obtained by suitably specializing and combining the matrices M_{t}(x, y, z). We give below some of the most interesting such examples.

For n, k ∈ N let \overline{S}[n, k]_{p,q}, Ŝ[n, k]_{p,q}, and S̃[n, k]_{p,q} be the (p, q)-Stirling numbers of the second kind defined in §6 of [32] (to which we refer the reader for their definition). (Note that what we denote by \overline{S}[n, k]_{p,q} is denoted by S[n, k]_{p,q} in §6 of [32]). We then have the following result.

Theorem 5.5 Let \overline{S}(p, q) =^{def} (\overline{S}[n + 1, k + 1]_{p,q})_{n,k∈N}, Ŝ(p, q) =^{def} (Ŝ[n + 1, k + 1]_{p,q})_{n,k∈N}, S̃(p, q) =^{def} (S̃[n + 1, k + 1]_{p,q})_{n,k∈N}, and t ∈ N. Then:

i) L_{t}(\overline{S}(p, q)), L_{t}(Ŝ(p, q)), and L_{t}(S̃(p, q)) are (p, q) − T P;

ii) every column of \overline{S}(p, q), Ŝ(p, q), and S̃(p, q) is (p, q) − P F.

Proof. Theorems 6.1 and 6.2 of [32] imply that

\overline{S}(p, q) = M_{0}(0, 1, \{1 + pq[k]_{p,q}\}_{k∈N})′ ,
Ŝ(p, q) = M_{0}(0, {q^{k}}_{k∈N}, {[k + 1]_{p,q}}_{k∈N})′ ,

and

S̃(p, q) = M_{0}(0, {q^{k}}_{k∈N}, {q^{k} + p[k]_{qp}}_{k∈N})′ ,

so the thesis follows from Theorems 4.3 and 4.5. □

For n, k ∈ N let S_{B}(n, k; q) be the q-Stirling number of the second kind of type B_{n} defined in §3 of [11]. These may also be defined by

S_{B}(n, k; q) = ∑_{i=k}^{n} (\begin{matrix}n \\ i \end{matrix}) q^{n−i}(1 + q)^{i} S(i, k) ,  (44)

and have the property that S_{B}(n, k; 0) = S(n, k), while k! S_{B}(n, k; 1) equals the number of k-dimensional faces of the Coxeter complex of type B_{n} (see [11], §3, and [16], for further details). We then have the following result.

Theorem 5.6 Let S_{B}(q) =^{def} (S_{B}(n, k; q))_{n,k∈N}, and t ∈ N. Then:

i) L_{t}(S_{B}(q)) is q-TP;

ii) every column of S_{B}(q) is q-PF.

Proof. It follows from (44) (see also eq. (47) of [11]) that

S_{B}(n, k; q) = (1 + q) S_{B}(n − 1, k − 1; q) + (k(1 + q) + q) S_{B}(n − 1, k; q)

for all n, k ∈ N with n + k > 0. Hence

S_{B}(q) = M_{0}(0, (1 + q)1, {k(1 + q) + q}_{k∈N})′

and the thesis follows from Theorems 4.3 and 4.5. □

We now consider q-analogues of the r-associated Stirling numbers. These, to the best of our knowledge, have never been considered before in the literature.

For n, k, r ∈ P let D_{r}(n, k) be the set of all σ ∈ S_{n} that have exactly k cycles, each of size ≥ r, and D_{r}(n) =^{def} ⋃_{k≥1} D_{r}(n, k). Note that |D_{1}(n, k)| is just the signless Stirling number of the first kind c(n, k), while |D_{2}(n, k)| is the number of derangements of S_{n} having k cycles, (these numbers are sometimes called the Jordan numbers, see, e.g., [12]). The numbers |D_{r}(n, k)| are usually called the signless rassociated Stirling numbers of the first kind (see, e.g., [13], p. 257, Ex. 7, for further information about these numbers).

Let σ ∈ D_{r}(n, k). We say that σ is written in r-normal form if:

i) each cycle is written with its r-th smallest element first;

ii) the cycles are written in increasing order of their first elements.

The r-normal representation of σ is the word a_{1} … a_{n} obtained from the r-normal form of σ by erasing all the parentheses. An r-inversion of σ is an inversion in the r-normal representation of σ (i.e., a pair (a_{i}, a_{j}) such that a_{i} > a_{j} and i < j). We denote by inv_{r}(σ) the number of r-inversions of σ. For example, if σ = (316)(789)(245), then (524)(631)(978) is its 3-normal form, 524631978 its 3-normal representation, and inv_{3}(σ) = 13. By contrast, its 2-normal form is (316)(452)(897), and hence inv_{2}(σ) = 10.

We define the r-associated signless q-Stirling numbers of the first kind by letting

c_{r}[n, k]_{q} =^{def} ∑_{σ∈D_{r}(n,k)} q^{inv_{r}(σ)} ,

for n, k ∈ P, and c_{r}[n, 0]_{q} = c_{r}[0, n]_{q} = δ_{0,n} for n ∈ N. Clearly, c_{1}[n, k]_{q} = c[n, k]_{q}, where c[n, k]_{q} denotes a q-Stirling number of the first kind as defined, e.g., in [25]. We then have the following result. Given a (finite) set T and a partition λ of |T | we denote by S(T, λ) the set of all elements of S(T) of cycle-type λ.

Theorem 5.7 Let r, n, k ∈ P. Then

c_{r}[n, k]_{q} = [n − 1]_{q} c_{r}[n − 1, k]_{q} + q^{r−1} ∏_{i=1}^{r−1}[n − i]_{q} c_{r}[n − r, k − 1]_{q} ,

(where c_{r}[n, k]_{q} =^{def} 0 if either n < 0 or k < 0).

Proof. Let σ ∈ D_{r}(n, k), and assume that σ is written in r-normal form. There are two possible cases.

If n is in a cycle of size ≥ r + 1 then the permutation obtained by deleting n from the disjoint cycle decomposition of σ, call it σ̂, is in D_{r}(n − 1, k), and it follows from our definition of the r-normal form that the r-normal representation of σ̂ is obtained from that of σ by deleting n. Hence inv_{r}(σ) = inv_{r}(σ̂) + n − 1 − i where i is the number of elements to the left of n in the r-normal representation of σ. Furthermore, for fixed i ∈ [n − 1], the map σ ↦ σ̂ is a bijection between those σ ∈ D_{r}(n, k) for which n is in a cycle of size ≥ r + 1 and has i elements to its left in the r-normal representation of σ, and D_{r}(n − 1, k).

If n is in a cycle of size r, call it C, then, since σ is in r-normal form, C must be the rightmost cycle of σ. Therefore the r-normal representation of σ|_{[n]\C} (respectively, σ|_{C}) is obtained from that of σ by deleting the last r (respectively, the first n − r) elements in the r-normal representation of σ. Hence

inv_{r}(σ) = inv_{r}(σ|_{[n]\C}) + inv_{r}(σ|_{C}) + ∑_{i=1}^{r−1}[(n − a_{i}) − (r − i)] ,

where \{a_{1}, …, a_{r−1}, n\}_{<} are the elements of C. Furthermore, for fixed A ∈ (\begin{matrix}[n] \\ r \end{matrix}), n ∈ A, the map σ ↦ (σ|_{[n]\A}, σ|_{A}) gives a bijection between those σ ∈ D_{r}(n, k) for which the elements of A are a cycle of size r and D_{r}(n − r, k − 1) × S(A, (r)). Therefore

c_{r}[n, k]_{q} = ∑_{i=1}^{n−1} ∑_{σ∈D_{r}(n−1,k)} q^{inv_{r}(σ)+n−1−i}
+ ∑_{1≤a_{1}<...<a_{r−1}≤n−1} ∏_{i=1}^{r−1} q^{n−a_{i}−r+i} ∑_{σ∈D_{r}(n−r,k−1)} q^{inv_{r}(σ)} ∑_{τ∈S([r],(r))} q^{inv _{r}(τ)}
= [n − 1]_{q} c_{r}[n − 1, k]_{q}
+ ∑_{n−r≥b_{1}≥...≥b_{r−1}≥0} ∏_{i=1}^{r−1} q^{b_{i}} c_{r}[n − r, k − 1]_{q} ∑_{σ∈S_{r−1}} q ^{inv(σ)+r−1}

and the thesis follows from Proposition 1.3.19 and Corollary 1.3.10 of [35]. □ The following result is new even for q = 1.

Corollary 5.8 Let r ∈ P, and D_{r}(q) =^{def} (c_{r}[n, k]_{q})_{n,k∈N}. Then:

i) D_{r}(q) is q-T P;

ii) every row of D_{r}(q) is q-P F.

Proof. Theorem 5.7 shows that

D_{r}(q) = M_{r} ({[n − 1]_{q}}_{n∈N}, 0, {q^{r−1} ∏_{i=1}^{r−1}[n − i]_{q}}_{n∈N})

so the thesis follows from Theorem 4.3. □

We should mention that other total positivity properties of the matrix D_{2}(1) appear in [6] (see Theorem 6.7.2).

Part ii) of Corollary 5.8 has a nice application to unimodality. Recall that a sequence {a_{0}, a_{1}, …, a_{d}} (of real numbers) is called log-concave if a_{i}^{2} ≥ a_{i−1}a_{i+1} for i = 1, …, d − 1, and is said to be unimodal if there exists an index 0 ≤ j ≤ d such that a_{i} ≤ a_{i+1} for i = 0, …, j − 1 and a_{i} ≥ a_{i+1} for i = j, …, d − 1. We say that a polynomial ∑_{i=0}^{d} a_{i} x^{i} is log-concave (respectively, unimodal) if the sequence {a_{0}, a_{1}, …, a_{d}} has the corresponding property. It is well known that if ∑_{i=0}^{d} a_{i} t^{i} is a polynomial with nonnegative coefficients and with only real zeros, then the sequence {a_{0}, a_{1}, …, a_{d}} is log-concave and unimodal, (see, e.g., [13], Thm. B, p.270). Unimodal sequences arise often in combinatorics, algebra, and geometry, and we refer the reader to [36] for an excellent survey.

The following result is an immediate consequence of part ii) of Corollary 5.8 and of Theorem 2.2.4 of [6] (see also [24], Chap. 8, §3, Corollary 3.1). For σ ∈ S_{n} we denote by c(σ) the number of cycles of σ.

Corollary 5.9 For n, r ∈ P, the polynomial

∑_{σ∈D_{r}(n)} x^{c(σ)}

has only real zeros. In particular, it is log-concave and unimodal. □

For r = 1 the preceding result is well known (see, e.g., [35], Proposition 1.3.4) while for r = 2 it was first proved by R. Canfield (private communication). Corollary 5.9 is by no means an isolated result, similar results relating unimodality and permutation enumeration appear, e.g., in [7], §4, [8], §6, and [9].

It is natural to expect that the analogues of Theorem 5.7 and Corollary 5.8 will hold for suitable q-analogues of the r-associated Stirling numbers of the second kind. While this may be true, we have only been able to obtain the analogue of Theorem 5.7. Since the definition and the result are new, and they may very well have applications to total positivity, we present them here. For n, k, r ∈ P, let Π_{r}([n], k) be the set of all π ∈ Π([n]) that have exactly k blocks, each of size ≥ r. Given π = {B_{1}, …, B_{k}} ∈ Π_{r}([n], k) we say that π is written in r-normal form

if a_{1,r} < a_{2,r}, < … < a_{k,r} where {a_{i,1}, …, a_{i,r}, …}_{<} =^{def} B_{i}, for i = 1, …, k. An

r-inversion of π is a pair (b, a_{i,p}) such that b > a_{i,p}, 1 ≤ p ≤ r, and b ∈ B_{j} with j < i. We denote by inv_{r}(π) the number of r-inversions of π. For example, if r = 2 and π = 15/726/348 then the 2-normal form of π is 348/15/267, and inv_{2}(π) = 9. We define the r-associated q-Stirling numbers of the second kind by letting

S_{r}[n, k]_{q} =^{def} ∑_{π∈Π_{r}([n],k)} q^{inv_{r}(π)} ,  (45)

for n, k ∈ P, and S_{r}[n, 0]_{q} = S_{r}[0, n]_{q} = δ_{0,n} for all n ∈ N. Clearly S_{1}[n, k]_{q} = S[n, k]_{q}, where S[n, k]_{q} denotes a q-Stirling number of the second kind as defined, e.g., in [28], and S_{r}[n, k]_{1} is the r-associated Stirling number of the second kind as defined, e.g., in [13], p. 221, Ex. 7. The next result shows that (45) is a very natural q-analogue of the r-associated Stirling numbers of the second kind (cfr. [13], p. 222, Ex. 7).

Theorem 5.10 Let r, n, k ∈ P. Then

S_{r}[n, k]_{q} = [k]_{q^{r}} S_{r}[n − 1, k]_{q} + [\begin{matrix}n−1 \\ r−1 \end{matrix}]_{q} S_{r}[n − r, k − 1]_{q} ,

(where S_{r}[n, k]_{q} =^{def} 0 if either n < 0 or k < 0).

Proof. Let π = {B_{1}, …, B_{k}} ∈ Π_{r}([n], k) and assume that π is written in r-normal form. Let i ∈ [k] be such that n ∈ B_{i}. There are two possible cases.

If |B_{i}| ≥ r + 1 then π̂ =^{def} {B_{1}, …, B_{i} \ {n}, …, B_{k}} is a partition in Π_{r}([n − 1], k)

and π̂ is still in r-normal form, so that inv_{r}(π) = inv_{r}(π̂) + r(k − i). Furthermore, for fixed i ∈ [k], the map π ↦ π̂ is a bijection between those π ∈ Π_{r}([n], k) for which the i-th block (in the r-normal form of π) has size ≥ r + 1 and contains n, and Π_{r}([n − 1], k).

If |B_{i}| = r then (since π is in r-normal form), i = k. Let {a_{1}, …, a_{r−1}, n}_{<} =^{def} B_{k}. Then π′ =^{def} {B_{1}, …, B_{k−1}} is a partition in Π_{r}([n] \ B_{k}, k − 1) in r-normal form, and

inv_{r}(π) = inv_{r}(π′) + ∑_{i=1}^{r−1}[(n − a_{i}) − (r − i)] .

Furthermore, for fixed {a_{1}, …, a_{r−1}}_{<} ⊆ [n − 1], the map π ↦ π′ is a bijection between those π for which {a_{1}, …, a_{r−1}, n} is a block of π, and Π_{r}([n] \ {a_{1}, …, a_{r−1}, n}, k − 1). Therefore

S_{r}[n, k]_{q} = ∑_{i=1}^{k} ∑_{π∈Π_{r}([n−1],k)} q^{inv_{r}(π)+r(k−i)}

+ ∑_{1≤a_{1}<...<a_{r−1}≤n−1} ∏_{i=1}^{r−1} q^{n−a_{i}−r+i} ∑_{π∈Π_{r}([n−r],k−1)} q^{inv_{r}(π)}
= [k]_{q^{r}} S_{r}[n − 1, k]_{q} + S_{r}[n − r, k − 1] ∑_{n−r≥b_{1}≥...≥b_{r−1}≥0} ∏_{i=1}^{r−1} q^{b_{i}} ,

and the result follows from Proposition 1.3.19 of [35]. □

We now consider some generalizations of the q-Stirling numbers which, to the best of our knowledge, have never been considered before in the literature, even for q = 1. For n, k ∈ P, let C(n, k) =^{def} D_{1}(n, k). Given σ ∈ C(n, k) we let S(σ) =^{def} {min(C_{1}), …, min(C_{k})} where C_{1}, …, C_{k} are the cycles of σ. For n, k, t ∈ P, we let C^{(t)}(n, k) be the set of all σ ∈ C(n, k) such that all the connected components of S(σ) which do not contain n have size which is a multiple of t. We then let

c^{(t)}[n, k]_{q} =^{def} ∑_{σ∈C^{(t)}(n,k)} q^{inv(σ)} ,  (46)

(where inv (σ) =^{def} inv_{1}(σ)), and c^{(t)}[n, 0]_{q} = c^{(t)}[0, n]_{q} = δ_{0,n} for all n ∈ N. For example, C^{(2)}(5, 3) = {(134)(2)(5), (143)(2)(5), (13)(24)(5), (14)(23)(5), (1)(234)(5), (1)(243)(5)}, and c^{(2)}[5, 3]_{q} = 1 + 2q + 2q^{2} + q^{3}. Note that C^{(1)}(n, k) = C(n, k) and hence

c^{(1)}[n, k]_{q} = c[n, k]_{q} ,

for all n, k ∈ N.

Proposition 5.11 Let t ∈ P. Then the polynomials c^{(t)}[n, k]_{q} defined by (46) satisfy the recurrence relation

c^{(t)}[n, k]_{q} = \{ \begin{matrix}c^{(t)}[n − 1, k − 1]_{q} + [n − 1]_{q} c^{(t)}[n − 1, k]_{q}, & if k ≡ 0 (mod t), \\ c^{(t)}[n − 1, k − 1]_{q}, & otherwise, \end{matrix} (47)

for n, k ∈ P.

Proof. Note first that if σ ∈ C^{(t)}(n, k) and n ∈ S(σ) then σ_{|[n−1]} ∈ C^{(t)}(n − 1, k − 1) and the map σ ↦ σ_{|[n−1]} is a bijection. Therefore

∑_{{σ∈C^{(t)}(n,k): n∈S(σ)}} q^{inv(σ)} = c^{(t)}[n − 1, k − 1]_{q} ,  (48)

for all n, k ∈ P. On the other hand, if σ ∈ C^{(t)}(n, k) and n ∉ S(σ) (and this, by our definitions, can only happen if k ≡ 0 (mod t)) then removing n from σ yields a permutation σ̃ ∈ C^{(t)}(n−1, k). Conversely, given σ̃ ∈ C^{(t)}(n−1, k) we can insert n in one of the cycles of σ̃ in n − 1 ways to obtain permutations σ_{1}, …, σ_{n−1} ∈ C^{(t)}(n, k) such that n ∉ S(σ_{i}), σ̃_{i} = σ̃, and inv(σ_{i}) = inv(σ) + i − 1 for i = 1, …, n − 1. Therefore

∑_{{σ∈C^{(t)}(n,k):n∉S(σ)}} q^{inv(σ)} = [n − 1]_{q} c^{(t)}[n − 1, k]_{q} ,  (49)

if k ≡ 0 (mod t), and n ∈ P. Summing (48) and (49) we obtain the first equality in (47). Now if k ≢ 0 (mod t) and σ ∈ C^{(t)}(n, k) then |S(σ)| ≢ 0 (mod t) and hence n ∈ S(σ). Therefore (48) is equivalent with the second equality in (47), when k ≢ 0 (mod t). □

The following result gives the main total positivity properties of the polynomials c^{(t)}[n, k]_{q} defined by (46).

Theorem 5.12 Let t ∈ P, and C_{t}(q) =^{def} (c^{(t)}[n + 1, (k + 1)t]_{q})_{n,k∈N}. Then:

i) C_{t}(q) is q-T P;

ii) every row of C_{t}(q) is q-P F.

Proof. It follows immediately from Proposition 5.11 that

c^{(t)}[n, k]_{q} = c^{(t)}[n − t, k − t]_{q} + [n − 1]_{q} c^{(t)}[n − 1, k]_{q} ,

if n ∈ P, and k ≡ 0 (mod t). Therefore

c^{(t)}[n, kt]_{q} = c^{(t)}[n − t, (k − 1) t]_{q} + [n − 1]_{q} c^{(t)}[n − 1, k t]_{q} ,

for all n, k ∈ P. This shows that

C_{t}(q) = M_{t}({[n]_{q}}_{n∈N}, 0, 1) ,  (50)

and the thesis follows from Theorem 4.3. □

In the case t = 1 part ii) of the preceding theorem was first explicitly noted in [31] (see §6), part i) is new even for t = 1.

An analogous construction can be made for set partitions. For n, k ∈ P let Π([n], k) =^{def} Π_{1}([n], k). Given π =^{def} {B_{1}, …, B_{k}} ∈ Π([n], k) we let S(π) =^{def} {min (B_{1}), …, min (B_{k})}. We will always assume that π is written in 1-normal form (so that min(B_{1}) < … < min (B_{k})). For n, k, t ∈ P, we let Π^{(t)}([n], k) be the set of all π ∈ Π([n], k) such that all the connected components of S(π) which do not contain n have size which is a multiple of t. We then let

S^{(t)}[n, k]_{q} =^{def} ∑_{π∈Π^{(t)}([n],k)} q^{inv(π)} ,  (51)

(where inv (π) =^{def} inv_{1}(π)). For example, Π^{(3)}([4], 3) = {14/2/3, 1/24/3, 1/2/34} and S^{(3)}[4, 3]_{q} = 1 + q + q^{2}. We also let S^{(t)}[n, 0]_{q} = S^{(t)}[0, n]_{q} = δ_{0,n} for all n ∈ N. Note that Π^{(1)}([n], k) = Π([n], k) and hence

S^{(1)}[n, k]_{q} = S[n, k]_{q}

for all n, k ∈ N.

The proof of the following result is analogous to that of Proposition 5.11 and is therefore omitted.

Proposition 5.13 Let t ∈ P. Then the polynomials S^{(t)}[n, k]_{q} defined by (51) satisfy the recurrence relation

S^{(t)}[n, k]_{q} = \{ \begin{matrix}S^{(t)}[n − 1, k − 1]_{q} + [k]_{q} S^{(t)}[n − 1, k]_{q}, & if k ≡ 0 (mod t), \\ S^{(t)}[n − 1, k − 1]_{q}, & otherwise, \end{matrix} (52)

for n, k ∈ P. □

We can now prove the analogue of Theorem 5.12 for the polynomials defined by (51).

Theorem 5.14 Let t ∈ P, and S_{t}(q) =^{def} (S^{(t)}[n + 1, (k + 1)t]_{q})_{n,k∈N}. Then:

i) S_{t}(q) is q-T P;

ii) every column of S_{t}(q) is q-P F.

Proof. It follows immediately from Proposition 5.13 that

S^{(t)}[n, k]_{q} = S^{(t)}[n − t, k − t]_{q} + [k]_{q} S^{(t)}[n − 1, k]_{q} ,

if n ∈ P, and k ≡ 0 (mod t). Therefore

S^{(t)}[n, kt]_{q} = S^{(t)}[n − t, (k − 1)t]_{q} + [kt]_{q} S^{(t)}[n − 1, kt]_{q} ,

for all n, k ∈ P. This shows that

S_{t}(q) = L_{t}(M_{0}(1, 0, {[(k + 1)t]_{q}}_{k∈N})′) ,

and the thesis follows from Theorems 4.3 and 4.5. □

For t = 1 the preceding result was first proved by Sagan (see [31], Corollary 5.5, and §6).

Besides matrices arising from the enumeration of set partitions and permutations subject to various restrictions and according to various statistics there are many other matrices of combinatorial interest which can be obtained by specializing and combining the matrices M_{t}(x, y, z) and that possess interesting total positivity properties. We shall just mention a few examples.

For n, k ∈ N let D(n, k) be the Delannoy number. This can be defined by

D(n, k) =^{def} ∑_{i=0}^{k} (\begin{matrix}k \\ i \end{matrix}) (\begin{matrix}n+k−i \\ k \end{matrix}) ,  (53)

(see, e.g., [13], p.81). We then have the following result.

Corollary 5.15 Let D =^{def} (D(n, k))_{n,k∈N}, and t ∈ N. Then:

i) L_{t}(D) is totally positive;

ii) every row of D is a P F -sequence.

Proof. It is well known (see, e.g., [13], p. 81), and also easy to see from (53), that

D(n, k) = D(n − 1, k) + D(n − 1, k − 1) + D(n, k − 1)

for n + k ∈ P (where D(n, k) =^{def} 0 if either k < 0 or n < 0). Hence

D = M_{0}(1, 1, 1)′ ,  (54)

and the thesis follows from Theorems 4.3 and 4.5. □

Note that equations (53) and (54) can be used to define several q-analogues of the Delannoy numbers for which the q-analogue of Corollary 5.15 holds. We don’t know if any of these q-analogues have been previously considered in the literature, but we will not pursue this line of investigation here.

For our next application we assume some familiarity with the basic terminology of the theory of hyperplane arrangements as presented, e.g., in [43].

Corollary 5.16 For k, n ∈ N let a(n, k) be the number of regions into which n hyperplanes in general position divide R^{k}, and A =^{def} (a(n, k))_{n,k∈N}. Then:

i) A is totally positive;

ii) every row of A is a P F -sequence.

Proof. It is well known (see, e.g., [43], Chap. 5, §E, eq. (5.7)) that

a(n, k) = ∑_{i=0}^{k} (\begin{matrix}n \\ i \end{matrix}) ,

for n, k ∈ N. It then follows from this (and is also easy to see directly, see, e.g., [13], p. 72, Ex. 2) that

a(n, k) = a(n − 1, k) + a(n − 1, k − 1),

for all n, k ∈ P, and a(n, 0) = a(0, n) = 1 for n ∈ N. Hence

A = M_{0}(1, 1, {1, 0, 0, …}) ,

and the thesis follows from Theorem 4.3. □

It would be interesting to obtain a geometric interpretation for the matrices

M_{0}(1, 1, \{\underbrace{1, …, 1}_{n}, 0, 0, …\})

for n ≥ 2.

We define the signless q-Lah numbers by

L[n, k]_{q} =^{def} \frac{n!}{k!} ∑_{i=1}^{k}(−1)^{k−i} (\begin{matrix}k \\ i \end{matrix}) (\begin{matrix}n+iq−1 \\ n \end{matrix})  (55)

for n, k ∈ N. For q ∈ P the L[n, k]_{q} were first defined and studied in [1] where they arose from a problem in statistics and where they are called the associated Lah numbers. Using (55) it is easy to see that L[n, k]_{q} reduces to the absolute value of the ordinary Lah number L(n, k) (as defined, e.g., in [13], p.135) when q = 1. The following result is new even in the case q = 1.

Theorem 5.17 Let L(q) =^{def} (L[n, k]_{q})_{n,k∈N}, then L(q) is q-TP.

Proof. It is proved in [1] that L[n + 1, k]_{q} = (kq + n) L[n, k]_{q} + q L[n, k − 1] for all n, k ∈ N, with L[0, 0]_{q} =^{def} 1. Hence taking b_{n} = 1, β_{n} = q, α_{n} = nq, a_{n+1} = n for n ∈ N and a_{0} = 0 in Theorem 4.8 yields the desired result. □

6 Combinatorial interpretations

The results in §4 show not only the (x, y, z)-total positivity of the matrices M_{t}(x, y, z), but also give a combinatorial interpretation of their minors in terms of non-intersecting paths in the digraphs D(t). These combinatorial interpretations, however, are not very explicit. Our goal in this section is to show how one can obtain more explicit combinatorial interpretations. The technique that we use is a generalization of the one used in [10].

Let λ = (λ_{1}, …, λ_{r}) and μ = (μ_{1}, …, μ_{r}) (r ∈ P) be two partitions such that μ ⊆ λ, and α, β ∈ Z. A shifted skew (α, β)-tableau of shape λ \ μ is an array π = (π_{i,j})_{1≤i≤r, μ_{i}+i≤j≤λ_{i}+i−1} of positive integers such that π_{i,j} ≤ π_{i,j+1} + α and π_{i,j} ≤ π_{i+1,j} + β whenever both sides of these inequalities are defined. Note that a (0, 0)-tableau is just a reverse plane partition, while a (0, −1)-tableau is a column strict reverse plane partition.

We will often need to distinguish (i.e. to root) some of the entries of an (α, β)- tableau π. We will do this by “dotting” (i.e., by putting a dot on top of) these entries. We will then call these entries the dotted entries of π, and call the resulting array a rooted (α, β)-tableau. The next definition is fundamental for this section. Let t ∈ N, and λ, μ be two partitions as above, a shifted skew dotted t-tableau of shape λ \ μ is a rooted shifted skew (−t, t)-tableau π = (π_{i,j})_{1≤i≤r,μ_{i}+i≤j≤λ_{i}+i−1} of shape λ \ μ such that:

i) π_{i,j} < π_{i,j+1} − t if π_{i,j+1} is dotted;

ii) π_{i,j} < π_{i+1,j} + t if π_{i,j} is not dotted;

whenever both sides of these inequalities are defined. For example,

˙1 ˙7 9 ˙12 ˙1 ˙4 6 8 ˙13 ˙3 6 8 ˙11 ˙14  (56)

is a shifted skew dotted 2-tableau of shape (8, 7, 7) \ (4, 2, 2).

Given two (possibly) dotted integers we will write a ≐ b to indicate that they are equal as dotted integers, and a = b if they are only equal as integers (so that, for example, 2 = ˙2, 2 ≐ 2, ˙2 ≐ ˙2). We will also write (a + b)^{·} instead of the more

cumbersome \overbrace{a + b}^{·}. Given a sequence d =^{def} (d_{1}, d_{2}, …) of integers and t ∈ N we let S_{t}(d) =^{def} (d_{t+1}, d_{t+2}, …), S =^{def} S_{1}, and Σ_{t}(d) =^{def} ∑_{i=0}^{t−1} S_{i}(d), (so that Σ_{1}(d) = d and Σ_{0}(d) = 0).

Given a shifted skew dotted t-tableau π as above we let, for r ∈ P,

m_{r}(π) =^{def} |{(i, j) ∈ sh(π) : π_{i,j} = r}|,

ṁ_{r}(π) =^{def} |{(i, j) ∈ sh(π) : π_{i,j} ≐ ṙ}|,

and

m(π) =^{def} (m_{1}(π), m_{2}(π), …),

ṁ(π) =^{def} (ṁ_{1}(π), ṁ_{2}(π), …).

We then define the weight of π to be

w(π) =^{def} x^{s(π)′−Σ_{t}(m(π̄))−S_{t}(ṁ(π̄))} y^{ṁ(π̂)}z^{m(π)−ṁ(π)} ,  (57)

(recall that s(π) is the size of π). For example, if π is the shifted skew dotted 2-tableau given in (56) then

m(π) = (2, 0, 1, 1, 0, 2, 1, 2, 1, 0, 1, 1, 1, 1, 0, 0, …),
ṁ(π) = (2, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, …),
Σ_{2}(m(π̄)) = (0, 0, 1, 1, 2, 3, 3, 3, 1, 1, 2, 2, 2, 1, 0, 0, …),

and

w(π) = x_{1} x_{2} x_{3}^{2} x_{8} x_{9} y_{3} y_{6} y_{10} z_{5}^{2} z_{7}^{2} z_{8} .  (58)

We are now ready to state and prove one of the main results of this section. Given a directed path τ in D(t) from (a, b) to (c, d) we let

R_{τ}(i) =^{def} max {j : (j, i) ∈ τ},

and

L_{τ}(i) =^{def} min {j : (j, i) ∈ τ},

for b ≤ i ≤ d.

Theorem 6.1 Let (a_{1}, b_{1}), …, (a_{r}, b_{r}), (c_{1}, d_{1}), …, (c_{r}, d_{r}) ∈ N × N be such that a_{1} ≤ … ≤ a_{r}, b_{1} ≥ … ≥ b_{r}, c_{1} ≤ … ≤ c_{r}, and d_{1} ≥ … ≥ d_{r}. Then there is a weight preserving bijection between r-tuples of non-intersecting paths in D(t) from ((a_{1}, b_{1}), …, (a_{r}, b_{r})) to ((c_{1}, d_{1}), …, (c_{r}, d_{r})) and shifted skew dotted t-tableaux of shape (d_{1} + 2, …, d_{r} + 2) \ (b_{1}, …, b_{r}) in which the i-th row has largest part ≐ (c_{i} + t + 2)^{·} and smallest part ≐ (a_{i} + 1)^{·}, for i = 1, …, r.

Proof. Let (τ_{1}, …, τ_{r}) be a set of non-intersecting paths in D(t) from ((a_{1}, b_{1}), …, (a_{r}, b_{r})) to ((c_{1}, d_{1}), …, (c_{r}, d_{r})) (so that τ_{i} goes from (a_{i}, b_{i}) to (c_{i}, d_{i}), for i = 1, …, r). Let

π_{i,j} =^{def} L_{τ_{i}}(j − i) + 1  (59)

for 1 ≤ i ≤ r, b_{i} ≤ j − i ≤ d_{i} + 1 (where L_{τ_{i}}(d_{i} + 1) =^{def} c_{i} + t + 1, for i = 1, …, r). Now let π =^{def} (π_{i,j})_{1≤i≤r, b_{i}+i≤j≤d_{i}+i+1} and dot π_{i,j} if and only if either j = b_{i} + i or j = d_{i} + i + 1 or the step reaching (L_{τ_{i}}(j − i), j − i) is a (t + 1, 1) step. Then

π_{i,j+1} − π_{i,j} ≥ \{ \begin{matrix}t + 1 & if π_{i,j+1} is dotted, \\ t, & otherwise \end{matrix}

for 1 ≤ i ≤ r, b_{i} + i ≤ j ≤ d_{i} + i, and π_{i,b_{i}+i} ≐ (a_{i} + 1)^{·}, π_{i,d_{i}+i+1} ≐ (c_{i} + t + 2)^{·}, for i = 1, …, r. Furthermore, τ_{i} and τ_{i+1} are non-intersecting if and only if

R_{τ_{i}}(j) < L_{τ_{i+1}}(j)  (60)

for all b_{i} ≤ j ≤ d_{i+1}. But, by our definitions,

R_{τ_{i}}(j) = \{ \begin{matrix}L_{τ_{i}}(j + 1) − t − 1, & if π_{i,j+i+1} is dotted, \\ L_{τ_{i}}(j + 1) − t, & otherwise, \end{matrix}  (61)

for b_{i} ≤ j ≤ d_{i}. Hence we conclude from (59), (60), and (61) that

π_{i,j} < \{ \begin{matrix}π_{i+1,j} + t + 1, & if π_{i,j} is dotted, \\ π_{i+1,j} + t, & otherwise, \end{matrix}  (62)

for b_{i} + i + 1 ≤ j ≤ d_{i+1} + i + 1. Now, if b_{i} > b_{i+1}, then π_{i,b_{i}+i} = L_{τ_{i}}(b_{i}) + 1 = a_{i} + 1 ≤ a_{i+1} + 1 < π_{i+1,b_{i}+i} + t + 1. Furthermore, if d_{i} > d_{i+1}, then π_{i,d_{i+1}+i+2} ≤ c_{i} + t + 2 ≤ c_{i+1} + t + 2 < c_{i+1} + 2t + 3 = π_{i+1,d_{i+1}+i+2} + t + 1 and, if π_{i,d_{i+1}+i+2} is not dotted, then d_{i+1} + i + 2 < d_{i} + i + 1 and hence π_{i,d_{i+1}+i+2} ≤ π_{i,d_{i}+i+1} − t − 1 = c_{i} + 1 < c_{i+1} + 2t + 2 = π_{i+1,d_{i+1}+i+2} + t + 1. Hence (62) holds also for j = b_{i} + i (if b_{i} > b_{i+1}) and for j = d_{i+1} + i + 2 (if d_{i} > d_{i+1}), and this shows that π is a shifted skew dotted t-tableau, as desired.

Conversely, let π =^{def} (π_{i,j})_{1≤i≤r, b_{i}+i≤j≤d_{i}+i+1} be a shifted skew dotted t-tableau such that π_{i,b_{i}+i} ≐ (a_{i} + 1)^{·}, and π_{i,d_{i}+i+1} ≐ (c_{i} + t + 2)^{·}, for i = 1, …, r. Now fix i ∈ [r] and let

R_{i,j} =^{def} \{ \begin{matrix}π_{i,j+i+1} − t − 2, & if π_{i,j+i+1} is dotted, \\ π_{i,j+i+1} − t − 1, & otherwise, \end{matrix}

for b_{i} ≤ j ≤ d_{i}, and

τ_{i} =^{def} ⋃_{j=b_{i}}^{d_{i}}{(k, j) : π_{i,j+i} − 1 ≤ k ≤ R_{i,j}} .  (63)

It is then clear that τ_{i} is a path in D(t) from (a_{i}, b_{i}) to (c_{i}, d_{i}), for i = 1, …, r. Now, since π is a dotted t-tableau we know that (62) holds for all b_{i}+i+1 ≤ j ≤ d_{i+1}+i+1. This implies that

R_{τ_{i}}(j) = R_{i,j} < π_{i+1,j+i+1} − 1 = L_{τ_{i+1}}(j) ,

for all b_{i} ≤ j ≤ d_{i+1}, and this, as remarked above, implies that τ_{i} and τ_{i+1} are non-intersecting, as desired.

Furthermore, if (τ_{1}, …, τ_{r}) and π correspond under the above bijection then, by (63), we have that, for i ∈ [r],

w(τ_{i}) = \frac{1}{y_{c_{i}+t+1}} ∏_{j=b_{i}}^{d_{i}} x_{[π_{i,j+i},R_{i,j}]} ∏_{j∈[b_{i}+i+1,d_{i}+i]\π̇_{i}} z_{π_{i,j}−1} ∏_{j∈π̇_{i}} y_{π_{i,j}−1}
= \frac{1}{y_{c_{i}+t+1}} ∏_{j∈π̇_{i}} x_{[π_{i,j−1},π_{i,j}−t−1)} y_{π_{i,j}−1} ∏_{j∈[b_{i}+i+1,d_{i}+i+1]\π̇_{i}} x_{[π_{i,j−1},π_{i,j}−t)} z_{π_{i,j}−1}

where π̇_{i} =^{def} {j ∈ [b_{i} + i + 1, d_{i} + i + 1] : π_{i,j} is dotted}, and the thesis follows. □

We illustrate the preceding theorem with an example. Let t = 2, (a_{1}, a_{2}, a_{3}, b_{1}, b_{2}, b_{3}, c_{1}, c_{2}, c_{3}, d_{1}, d_{2}, d_{3}) = (0, 0, 2, 4, 2, 2, 8, 9, 10, 6, 5, 5) and π be the shifted skew dotted 2-tableau given in (56). Then the three non-intersecting paths (τ_{1}, τ_{2}, τ_{3}) in D(2), from ((0, 4), (0, 2), (2, 2)) to ((8, 6), (9, 5), (10, 5)), corresponding to π are those depicted in Figure 6 and

w(τ_{1}, τ_{2}, τ_{3}) = x_{[1,3]} y_{6} z_{8} y_{3} x_{[8,9]} z_{5} z_{7} y_{10} x_{3} z_{5} z_{7} ,

which is in accordance with (58).

Figure 6.

[figure: (0,2); (0,4); (2,2); (10,5); (9,5); (8,6)]

Since we also wish to give a combinatorial interpretation to the minors of the matrices L_{t}(M_{0}(x, y, z)′) we will need the analogue of Theorem 6.1 for the digraph D′(t) (cfr. the proof of Theorem 4.5). Since D′(t) is the transpose of D(t) Theorem 6.1 implies that we can encode r-tuples of non-intersecting paths in D′(t) by shifted skew dotted t-tableaux. However, transposition does not preserve the weights of D(t) and D′(t). Therefore, we will need to introduce a second kind of weight on shifted skew dotted t-tableaux which will correspond to the weighting that D(t) inherits from D′(t) by transposition.

Let π =^{def} (π_{i,j})_{1≤i≤r, μ_{i}+i≤j≤λ_{i}+i−1} be a shifted skew dotted t-tableau of shape (λ_{1}, …, λ_{r}) \ (μ_{1}, …, μ_{r}). For k ∈ N we let

d_{k}(π) =^{def} |{i ∈ P : (i, i + k) ∈ sh(π)},

ḋ_{k}(π) =^{def} |{i ∈ P : π_{i,i+k} is dotted }|,

T_{k}(π) =^{def} ∑_{i=1}^{d_{k}(π)} π_{i,i+k},

and

d(π) =^{def} (d_{0}(π), d_{1}(π), …),

ḋ(π) =^{def} (ḋ_{0}(π), ḋ_{1}(π), …),

T (π) = (T_{0}(π), T_{1}(π), …).

We then define the transpose weight of π to be

w′(π) =^{def} x^{d(π)−ḋ(π)} y^{ḋ(π̂)} z^{S(T (π̄)−ḋ(π̄)−t d(π̄))−T (π̃)}.

For example, if π is the shifted skew dotted 2-tableau given in (56) then

d(π) = (0, 0, 2, 2, 3, 3, 3, 1, 0, 0, …),
ḋ(π) = (0, 0, 2, 1, 1, 2, 2, 1, 0, 0, …),
T (π̄) = (0, 0, 0, 10, 14, 26, 36, 12, 0, 0, …),

and

w′(π) = x_{3} x_{4}^{2} x_{5} x_{6} y_{3} y_{5}^{2} z_{2} z_{4}^{3} z_{5}^{2}.  (64)

We can now state and prove the analogue of Theorem 6.1 for the digraph D′(t).

Theorem 6.2 Let (a_{1}, b_{1}), …, (a_{r}, b_{r}), (c_{1}, d_{1}), …, (c_{r}, d_{r}) ∈ N × N be such that a_{1} ≤ … ≤ a_{r}, b_{1} ≥ … ≥ b_{r}, c_{1} ≤ … ≤ c_{r}, and d_{1} ≥ … ≥ d_{r}. Then there is a bijection between r-tuples of non-intersecting paths in D′(t) from ((a_{1}, b_{1}), …, (a_{r}, b_{r})) to ((c_{1}, d_{1}), …, (c_{r}, d_{r})) and shifted skew dotted t-tableaux of shape (c_{r} + 2, …, c_{1} + 2)\(a_{r}, …, a_{1}) in which the i-th row has largest part ≐ (d_{r+1−i} +t+2)^{·} and smallest part ≐ (b_{r+1−i} + 1)^{·}, for i = 1, …, r. Furthermore, if (τ_{1}, …, τ_{r}) and π correspond under the above bijection, then w(τ_{1}, …, τ_{r}) = w′(π).

Proof. Since D′(t) is the transpose of D(t) (as digraphs, not as weighted digraphs), transposition gives a bijection between r-tuples of non-intersecting paths as in the statement of the theorem and r-tuples of non-intersecting paths in D(t) from ((b_{r}, a_{r}), …, (b_{1}, a_{1})) to ((d_{r}, c_{r}), …, (d_{1}, c_{1})); hence the first part of the theorem follows from Theorem 6.1.

Now, if (τ_{1}, …, τ_{r}) and π correspond under this composite bijection then, by (63), we have that, for i = 1, …, r,

τ_{r+1−i} = ⋃_{j=a_{r+1−i}}^{c_{r+1−i}}{(j, k) : π_{i,j+i} − 1 ≤ k ≤ R_{i,j}},

where

R_{i,j} =^{def} \{ \begin{matrix}π_{i,j+i+1} − t − 2, & if π_{i,j+i+1} is dotted, \\ π_{i,j+i+1} − t − 1, & otherwise, \end{matrix}

for a_{r+1−i} ≤ j ≤ c_{r+1−i}. Therefore,

w(τ_{r+1−i}) = \frac{1}{y_{c_{r+1−i}+1}} ∏_{j=a_{r+1−i}}^{c_{r+1−i}} z_{j}^{|[π_{i,j+i},R_{i,j}]|} ∏_{j∈[a_{r+1−i}+i+1,c_{r+1−i}+i]\π̇_{i}} x_{j−i} ∏_{j∈π̇_{i}} y_{j−i}

= \frac{∏_{j∈π̇_{i}}z_{j−i−1}^{|[π_{i,j−1},π_{i,j}−t−1)|} y_{j−i}}{y_{c_{r+1−i}+1}} ∏_{j∈[a_{r+1−i}+i+1,c_{r+1−i}+i+1]\π̇_{i}} z_{j−i−1}^{|[π_{i,j−1},π_{i,j}−t−1]|} x_{j−i}

where π̇_{i} =^{def} {j ∈ [a_{r+1−i} + i + 1, c_{r+1−i} + i + 1] : π_{i,j} is dotted }, and the thesis follows. □

We briefly illustrate the preceding theorem with an example. Let (a_{1}, a_{2}, a_{3}, b_{1}, b_{2}, b_{3}, c_{1}, c_{2}, c_{3}, d_{1}, d_{2}, d_{3}) = (2, 2, 4, 2, 0, 0, 5, 5, 6, 10, 9, 8) and π be the shifted skew dotted 2-tableau given in (56). Then the triple of non-intersecting paths in D′(2) corresponding to π under the composite bijection described in Theorem 6.2 is the one obtained by transposing the three paths depicted in Figure 6. The weight of these transposed paths, in D′(2), is

(z_{2}x_{3}x_{4}y_{5})(y_{3}x_{4}x_{5}z_{5}^{2})(z_{4}^{3}y_{5}x_{6}),

which is in accordance with (64).

Note that the preceding theorem shows that the transpose weight of π is also the weight, defined by (57), of a suitably defined “conjugate” of π. However, we have no need for this fact here, and we wanted to have an explicit description of this transpose weight and for this reason we have chosen to define it directly.

We are now ready to prove the three main results of this section. Their proofs follow immediately from Theorems 4.1, 6.1, and 6.2, and from equations (32) and (34).

Corollary 6.3 Let t ∈ N, {n_{1}, …, n_{r}}_{<}, {k_{1}, …, k_{r}}_{<} ⊆ N and m ∈ P, m > k_{r}. Then

M_{t}(x, y, z) ( \begin{matrix}n_{1}, …, n_{r} \\ k_{1}, …, k_{r} \end{matrix} ) = ∑_{π} x^{s(π)′−Σ_{t}(m(π̄))−S_{t}(ṁ(π̄))} y^{ṁ(π̂)}z^{m(π)−ṁ(π)}

where the sum is over all shifted skew dotted t-tableaux π of shape (m + 2, …, m + 2) \ (m − k_{1}, …, m − k_{r}) in which the i-th row has smallest part ≐ ˙1 and largest part ≐ (n_{i} + t + 2)^{·}, for i = 1, …, r. □

Corollary 6.4 Let t ∈ N, {m_{1}, …, m_{r}}_{>}, {k_{1}, …, k_{r}}_{>} ⊆ N, and n ∈ P. Then

\{M_{t}(x, y, z)_{n,k}\}_{k∈N} ( \begin{matrix}m_{r}, …, m_{1} \\ k_{r}, …, k_{1} \end{matrix} ) = ∑_{π} x^{s(π)′−Σ_{t}(m(π̄))−S_{t}(ṁ(π̄))} y^{ṁ(π̂)}z^{m(π)−ṁ(π)}

where the sum is over all skew dotted t-tableaux π of shape (k_{1} + 2, …, k_{r} + r + 1) \ (m_{1}, …, m_{r} + r − 1) in which every row has smallest part ≐ ˙1 and largest part ≐ (n + t + 2)^{·}. □

Corollary 6.5 Let t ∈ N, {n_{1}, …, n_{r}}_{>}, {k_{1}, …, k_{r}}_{>} ⊆ N, and m ∈ P, m > n_{1}. Then

L_{t}(M_{0}(x, y, z)′) ( \begin{matrix}n_{r}, …, n_{1} \\ k_{r}, …, k_{1} \end{matrix} ) = ∑_{π} x^{d(π)−ḋ(π)} y^{ḋ(π̂)} z^{S(T (π̄)−ḋ(π̄)−t d(π̄))−T (π̃)}

where the sum is over all shifted dotted t-tableaux π of shape (k_{1} + 2, …, k_{r} + 2) in which the i-th row has largest part ≐ (m + t + 2)^{·} and smallest part ≐ (m − n_{i} + 1)^{·}, for i = 1, …, r. □

Note that, by Proposition 4.4, Corollary 6.4 gives, when t = 0, x = 1, and z_{0} = 0, a combinatorial interpretation for the super-Schur function (in the variables z_{1}, …, z_{n}/y_{1}, …, y_{n}) corresponding to the skew shape (m − m_{r} + 1, …, m − m_{1} +r)\(m−k_{r} +1, …, m−k_{1} +r), (where m ≥ max {m_{1}, k_{1}}). This combinatorial interpretation is different from (and simpler than) the one given in Theorem 3.4 of [10], and reduces, when {k_{1}, …, k_{r}}_{>} = {r, …, 2, 1}, to the one given in [34] (see eq. (11)). Also note that in this case Corollary 6.5 reduces to Theorem 3.3 of [10].

Using the preceding three results it is easy to give combinatorial interpretations to the minors of almost all of the matrices considered in the preceding section. For example, consider the minors associated to the matrix E_{t}(x) defined in Theorem 5.1. The next two results follow from Corollaries 6.3, and 6.4 and from (40).

Corollary 6.6 Let t ∈ N, {n_{1}, …, n_{r}}_{<}, {k_{1}, …, k_{r}}_{<} ⊆ N, and m ∈ P, m > k_{r}. Then

E_{t}(x) ( \begin{matrix}n_{1}, …, n_{r} \\ k_{1}, …, k_{r} \end{matrix} ) = ∑_{π} x^{m(π̂)},

where the sum is over all shifted skew (−t, t−1)-tableaux π of shape (m+2, …, m+ 2) \ (m − k_{1}, …, m − k_{r}) and size (n_{1} + t + 1, …, n_{r} + t + 1) \ (1^{r}). □

Corollary 6.7 Let t ∈ N, {m_{1}, …, m_{r}}_{>}, {k_{1}, …, k_{r}}_{>} ⊆ N, and n ∈ P. Then

\{e_{k}^{(t)}(x_{0}, …, x_{n})\}_{k∈N} ( \begin{matrix}m_{r}, …, m_{1} \\ k_{r}, …, k_{1} \end{matrix} ) = ∑_{π} x^{m(π)},

where the sum is over all skew (−t, t − 1)-tableaux π of shape (k_{1}, …, k_{r} + r − 1) \ (m_{1}, …, m_{r} + r − 1) with entries ≤ n + 1 and ≥ t + 1. □

It is easy to see that, when t = 0, 1, the preceding corollaries reduce to Corollaries 5.1, 5.2, 5.3, and 5.4 of [10]. In particular, Corollary 6.7 reduces to the Jacobi-Trudi identity (see, e.g., [27], Chap. I, §5, eqs. (5.4) and (5.5)).

In a similar way, combining Corollaries 6.3, 6.4, and 6.5 with the various specializations of the matrices M_{t}(x, y, z)and L_{t}(M_{0}(x, y, z)′) considered in section 5 it is not hard to obtain explicit combinatorial interpretations for the minors of all these specializations. It is then possible to use appropriate bijections to get “natural” combinatorial interpretations (in the sense of [10], §5) analogous to those appearing in §§5,6,7, and 8 of [10]. We leave this task to the interested reader. Acknowledgements. I would like to thank Curtis Greene, Richard Stanley, John Stembridge, Bernd Sturmfels, and Michelle Wachs for some useful conversations, and the Institut Mittag-Leffler for hospitality and financial support during the preparation of this work.

References

[1] J. C. Ahuja and E. A. Enneking, Concavity property and a recurrence relation for associated Lah numbers, Fibonacci Quart., 17 (1979), 158-161.

[2] T. Ando, Totally positive matrices, Linear Algebra Appl., 90 (1987), 165-219.

[3] A. B. Balantekin and I. Bars, Representations of supergroups, J. Math. Phys., 22 (1981), 1810-1818.

[4] A. Berele and A. Regev, Hook Young diagrams with applications to combinatorics and to representations of Lie superalgebras, Adv. in Math., 64 (1987), 118-175.

[5] F. Brenti, Unimodal, log-concave, and Pólya Frequency sequences in Combinatorics, Ph. D. Dissertation, Massachusetts Institute of Technology, May 1988.

[6] F. Brenti, Unimodal, log-concave, and Pólya Frequency sequences in Combinatorics, Memoirs Amer. Math. Soc., no. 413 (1989).

[7] F. Brenti, Unimodal polynomials arising from symmetric functions, Proc. Amer. Math. Soc., 108(1990), 1133-1141.

[8] F. Brenti, Log-concavity and combinatorial properties of Fibonacci Lattices, Europ. J. Combinatorics, 12(1991), 459-476 .

[9] F. Brenti, Permutation enumeration, symmetric functions, and unimodality, Pacific J. Math., 157(1993), 1-28.

[10] F. Brenti, Determinants of super-Schur functions, lattice paths, and dotted plane partitions, Adv. in Math., 98(1993), 27-64.

[11] F. Brenti, q-Eulerian polynomials arising from Coxeter groups, Europ. J. Combinatorics, submitted.

[12] L. Carlitz, Note on the numbers of Jordan and Ward, Duke Math. J. 38 (1971), 783-790.

[13] L. Comtet, Advanced Combinatorics, Reidel, Dordrecht/Boston, 1974.

[14] C. W. Cryer, Some properties of totally positive matrices, Linear Algebra Appl., 15(1976), 1-25.

[15] P. H. Dondi and P. D. Jarvis, Diagram and superfield techniques in the classical superalgebras, J. Phys., A 14 (1981), 547-563.

[16] I. Dolgachev and V. Lunts, A character formula for the representation of a Weyl group in the cohomology of the associated toric variety, J. Algebra, to appear.

[17] A. Edrei, Proof of a conjecture of Schoenberg on the generating function of a totally positive sequence, Canadian J. Math., 5 (1953), 86-94.

[18] I. Gessel and G. Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math., 58 (1985), 300-321.

[19] I. Gessel and G. Viennot, Determinants, paths, and plane partitions, preprint.

[20] H. W. Gould, The q-Stirling numbers of the first and second kinds, Duke Math. J., 28 (1961), 281-289.

[21] I. P. Goulden and D. M. Jackson, Immanants of combinatorial matrices, J. Algebra, 148 (1992), 305-324.

[22] C. Greene, Proof of a conjecture on immanants of the Jacobi-Trudi matrix, Linear Algebra Appl., to appear.

[23] M. Haiman, Hecke algebra characters and immanant conjectures, J. Amer. Math. Soc., submitted.

[24] S. Karlin, Total Positivity, vol.1, Stanford University Press, 1968.

[25] P. Leroux, Reduced matrices and q-log concavity properties of q-Stirling numbers, J. Combin. Theory Ser. A, 54 (1990), 64-84.

[26] B. Lindström, On the vector representations of induced matroids, Bull. London Math. Soc., 5 (1973), 85-90.

[27] I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, New York/London, 1979.

[28] S. C. Milne, Restricted growth functions, rank row matchings of partition lattices, and q-Stirling numbers, Adv. in Math., 43 (1982), 173-196.

[29] J. Remmel and M. Wachs, in preparation.

[30] B. E. Sagan, Shifted tableaux, Schur Q-functions and a conjecture of R. Stanley, J. Combin. Theory Ser. A, 45 (1987), 62-103.

[31] B. E. Sagan, Log concave sequences of symmetric functions and analogs of the Yacobi-Trudi determinants, Trans. Amer. Math. Soc., 329 (1992), 795-812.

[32] B. E. Sagan, A maj statistic for set partitions, Europ. J. Combinatorics, 12 (1991), 69-79.

[33] R. Stanley, Theory and application of plane partitions, Parts 1, 2, Stud. Appl. Math., 50 (1971), 167-188, 259-279.

[34] R. Stanley, Unimodality and Lie superalgebras, Studies in Applied Math., 72 (1985), 263-281.

[35] R. Stanley, Enumerative Combinatorics , vol.1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.

[36] R. Stanley, Log-concave and unimodal sequences in Algebra, Combinatorics and Geometry, Annals of the New York Academy of Sciences, 576 (1989), 500-534.

[37] J. R. Stembridge, Shifted tableaux and the projective representations of symmetric groups, Adv. in Math., 74 (1989), 87-134.

[38] J. R. Stembridge, Non-intersecting paths, pfaffians and plane partitions, Adv. in Math., 83 (1990), 96-131.

[39] J. R. Stembridge, Some conjectures for immanants, Canad. J. Math., to appear.

[40] J. R. Stembridge, Immanants of totally positive matrices are nonnegative, Bull. London Math. Soc., 23 (1991), 422-428.

[41] B. Sturmfels, Totally positive matrices and cyclic polytopes, Linear Algebra Appl., 107(1988), 275-281.

[42] M. Wachs and D. White, p,q-Stirling numbers and set partition statistics, J. Combin. Theory Ser. A, 56(1991), 27-46.

[43] T. Zaslavsky, Facing up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes, Memoirs Amer. Math. Soc., no.154 (1975).