SOME COMPOSITION DETERMINANTS

J. M. Brunat^{1∗}, C. Krattenthaler^{2†‡}, A. Lascoux^{3†} and A. Montes^{1∗}

1Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Jordi Girona 1–3, 08034 Barcelona, Spain

                WWW: http://www-ma2.upc.edu/~montes

2Institut Camille Jordan, Université Claude Bernard Lyon-I, 21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France

                WWW: http://igd.univ-lyon1.fr/~kratt

3Institut Gaspard Monge, Université de Marne-la-Vallée, F-77454 Marne-la-Vallée Cedex 2, France

                WWW: http://www-igm.univ-mlv.fr/~al

Abstract. We compute several parametric determinants in which rows and columns are indexed by compositions, where the entries are either products of binomial coefficients or products of powers. These results generalize previous determinant evaluations due to the first and fourth author [SIAM J. Matrix Anal. Appl. 23 (2001), 459–471] and [“A polynomial generalization of the power-compositions determinant,” Linear Multilinear Algebra (to appear)], and they prove two conjectures of the second author [“Advanced determinant calculus: a complement,” preliminary version].

1. Introduction

A composition of a non-negative integer n is a vector (α_{1}, α_{2}, …, α_{k}) of non-negative integers such that α_{1} + α_{2} + ⋯ + α_{k} = n, for some k. For a fixed k, let C(n, k) denote the corresponding set of compositions of n. While working on a problem in global optimisation, two of the authors [1] discovered the following surprising determinant evaluation. It allowed them to show how to explicitly express a multivariable polynomial as a difference of convex functions. In the statement, we use standard multi-index

2000 Mathematics Subject Classification. Primary 05A19; Secondary 05A10 11C20 15A15. Key words and phrases. Binomial determinants, power determinants, compositions, Chu–Vander-

monde summation.

∗Work partially supported by the Ministerio de Ciencia y Tecnología under projects BFM2003-00368 and MTM2004-01728 and by the Generalitat de Catalunya under project 2001 SGR 00224.

†Research partially supported by EC’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe.”

‡Current address: Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna, Austria.

notation: if α = (α_{1}, α_{2}, …, α_{k}) and β = (β_{1}, β_{2}, …, β_{k}) are two compositions, we let

α^{β} := α_{1}^{β_{1}}α_{2}^{β_{2}} ⋯ α_{k}^{β_{k}},

where 0^{0} is interpreted as 1.

Theorem 1. For any positive integers n and k, we have

det_{α,β∈C(n,k)} (α^{β}) = n^{\binom{n+k−1}{k}+k−1} ∏_{i=1}^{n−1} i^{(n−i+1)\binom{n+k−i−1}{k−2}}.  (1.1)

In the preliminary version [5] of [6], the second author observed empirically that there seemed to be a polynomial generalisation of this theorem.

Conjecture 2 ([5, Conjecture 57]). For any positive integers n and k, we have

det_{α,β∈C(n,k)} ((x + α)^{β}) = (kx + n)^{\binom{n+k−1}{k}}n^{k−1} ∏_{i=1}^{n−1} i^{(n−i+1)\binom{n+k−i−1}{k−2}},  (1.2)

where x is a variable, and x + α is short for (x + α_{1}, x + α_{2}, …, x + α_{k}).

Morover, he also worked out a binomial version of this conjecture. Extending our multi-index notation, let

(\begin{matrix}α \\ β \end{matrix}) := \binom{α_{1}}{β_{1}}\binom{α_{2}}{β_{2}} ⋯ \binom{α_{k}}{β_{k}}.

Conjecture 3 ([5, Conjecture 58]). For any positive integers n and k, we have

det_{α,β∈C(n,k)} (\binom{x + α + β}{β}) = \frac{∏_{i=0}^{n−1} (kx + n + k + i)^{\binom{k+i−1}{k−1}}}{∏_{i=1}^{n} i^{\binom{n+k−i−1}{k−1}}} ,  (1.3)

where x is a variable, and x+α+β is short for (x+α_{1}+β_{1}, x+α_{2}+β_{2}, …, x+α_{k} +β_{k}).

In the recent paper [2], the first and fourth author succeeded to prove Conjecture 2. In fact, they established the following multivariable generalisation.

Theorem 4. Let x = (x_{1}, x_{2}, …, x_{k}) be a vector of indeterminates. Then, for any positive integers n and k, we have

det_{α,β∈C(n,k)} ((x + α)^{β}) = (|x| + n)^{\binom{n+k−1}{k}} ∏_{i=1}^{n} i^{(k−1)\binom{n+k−i−1}{k−1}},  (1.4)

where x+α is short for (x_{1}+α_{1}, x_{2}+α_{2}, …, x_{k} +α_{k}), and where |x| = x_{1}+x_{2}+⋯+x_{k}.

The purpose of this paper is to, in some sense, explain the miraculous existence of all these formulae. We do this by introducing further variables, λ_{1}, λ_{2}, …, λ_{k}, in the binomial determinant in (1.3), and by proving an evaluation theorem for the resulting determinant. All the afore-mentioned determinant evaluations are then special cases, respectively limit cases, of this new theorem. To be precise, the main result of this paper is the following determinant evaluation.

Theorem 5. Let x = (x_{1}, x_{2}, …, x_{k}) and λ = (λ_{1}, λ_{2}, …, λ_{k}) be vectors of indeterminates. Then, for any positive integers n and k, we have

det_{α,β∈C(n,k)} (\binom{x + λα}{β}) = (∏_{j=1}^{k} λ_{j})^{\binom{n+k−1}{k}} \frac{_{∏_{ε_{1},...,ε_{k}≥0} ; ε_{1}+···+ε_{k}<n} (n + ∑_{j=1}^{k} (\frac{x_{j}}{λ_{j}} − \frac{ε_{j}}{λ_{j}} ))}{∏_{i=1}^{n} i^{\binom{n+k−i−1}{k−1}}}, (1.5)

where x + λα is short for (x_{1} + λ_{1}α_{1}, x_{2} + λ_{2}α_{2}, …, x_{k} + λ_{k}α_{k}).

Using the elementary property \binom{X}{m} = (−1)^{m}\binom{−X+m−1}{m} of binomial coefficients, we show that an equivalent way to write the same result is as follows.

Theorem 6. Let x = (x_{1}, x_{2}, …, x_{k}) and λ = (λ_{1}, λ_{2}, …, λ_{k}) be vectors of indeterminates. Then, with notation as in Theorem 5, for any positive integers n and k we have

det_{α,β∈C(n,k)} (\binom{x + λα + β}{β}) = (∏_{j=1}^{k} λ_{j})^{\binom{n+k−1}{k}} \frac{_{∏_{ε_{1},...,ε_{k}≥0} ; ε_{1}+···+ε_{k}<n} (n + ∑_{j=1}^{k} (\frac{x_{j} + 1}{λ_{j}} + \frac{ε_{j}}{λ_{j}} ))}{∏_{i=1}^{n} i^{\binom{n+k−i−1}{k−1}}}.

(1.6)

In order to see how Conjecture 3 is implied by these results, it is convenient to first state separately the special cases of Theorems 5 and 6 where all the λ_{i}’s are identical. In that case, the product in the numerator on the right-hand sides of (1.5) and (1.6) can be rearranged by grouping together the factors corresponding to compositions ε = (ε_{1}, ε_{2}, …, ε_{k}) of n − i, which become identical. Taking into account that the number of such compositions is \binom{n−i+k−1}{k−1}, this yields the following two corollaries.

Corollary 7. Let x = (x_{1}, x_{2}, …, x_{k}) be a vector of indeterminates, and let λ be an indeterminate. Then, for any positive integers n and k, we have

det_{α,β∈C(n,k)} (\binom{x + λα}{β}) = λ^{(k−1)\binom{n+k−1}{k}} ∏_{i=1}^{n} (\frac{|x| + (λ − 1)n + i}{i})^{\binom{n+k−i−1}{k−1}} , (1.7)

where x + λα is short for (x_{1} + λα_{1}, x_{2} + λα_{2}, …, x_{k} + λα_{k}), and where |x| = x_{1} + x_{2} + ⋯ + x_{k}, as before.

Corollary 8. Let x = (x_{1}, x_{2}, …, x_{k}) be a vector of indeterminates, and let λ be an indeterminate. Then, with notation as in Corollary 7, for any positive integers n and k we have

det_{α,β∈C(n,k)} (\binom{x + λα + β}{β}) = λ^{(k−1)\binom{n+k−1}{k}} ∏_{i=1}^{n} (\frac{|x| + (λ + 1)n + k − i}{i})^{\binom{n+k−i−1}{k−1}} .

(1.8)

Clearly, Conjecture 3 is the special case of the above corollary where λ = 1 and x_{i} = x for all i.

Theorem 4 is also implied by Theorem 5. To see this, we shall show that, by extracting the highest homogeneous component in (1.5) (this could also be realised by an appropriate limit), we obtain the following corollary.

Corollary 9. Let x = (x_{1}, x_{2}, …, x_{k}) and λ = (λ_{1}, λ_{2}, …, λ_{k}) be vectors of indeterminates. Then, with notation as in Theorem 5, for any positive integers n and k we have

det_{α,β∈C(n,k)} ((x + λα)^{β}) = (∏_{j=1}^{k} λ_{j})^{\binom{n+k−1}{k}} (n + ∑_{j=1}^{k} \frac{x_{j}}{λ_{j}} )^{\binom{n+k−1}{k}} ∏_{i=1}^{n} i^{(k−1)\binom{n+k−i−1}{k−1}}. (1.9)

The corresponding special case where all the λ_{i}’s are identical is the following.

Corollary 10. Let x = (x_{1}, x_{2}, …, x_{k}) be a vector of indeterminates, and let λ be an indeterminate. Then, with notation as in Corollary 7, for any positive integers n and k we have

det_{α,β∈C(n,k)} ((x + λα)^{β}) = λ^{(k−1)\binom{n+k−1}{k}} (|x| + λn)^{\binom{n+k−1}{k}} ∏_{i=1}^{n} i^{(k−1)\binom{n+k−i−1}{k−1}}.  (1.10)

Clearly, Theorem 4 is the special case λ = 1 of this corollary.

In the next section, we give proofs of Theorems 5 and 6, and of Corollary 9 (and, thus, of Corollaries 7, 8 and 10 also). In contrast to the inductive procedure in [1, 2] that was used in the original proofs of Theorems 1 and 4, our proof is based on the “identification of factors” technique (see [4, Sec. 2.4]). As it turns out, the crucial identity in our proof is the multivariate version of the Chu–Vandermonde summation formula (see Lemma 11). Finally, in the last section, we derive analogues of Theorems 5 and 6, and of Corollary 9 for the subdeterminants in which we restrict the rows and columns to compositions of n with exactly k positive summands.

2. The proofs

Lemma 11. Let x = (x_{1}, x_{2}, …, x_{k}) be a vector of indeterminates, and let n and k be non-negative integers. Then

∑_{δ∈C(n,k)} \binom{x}{δ} = ∑_{δ_{1}+···+δ_{k}=n} \binom{x}{δ} = \binom{|x|}{n}.

Proof. The Chu–Vandermonde summation formula (see e.g. [3, Sec. 5.1, (5.27)]) reads

∑_{r=0}^{s} \binom{M}{r}\binom{N}{s − r} = \binom{M + N}{s}.

On the basis of this formula, the assertion of the lemma is easily proved by induction on k. □

Proof of Theorem 5. We prove the theorem by the identification of factors method described in [4, Sec. 2.4]. For convenience, let us write M(n, k) for the matrix of which we want to compute the determinant, that is,

M(n, k) = (\binom{x + λα}{β})_{α,β∈C(n,k)} .

Step 1. The term

T (n, k, x, λ, ε) := n ∏_{j=1}^{k} λ_{j} + ∑_{t=1}^{k} x_{t}_{∏_{j=1}^{k} ; j≠t}λ_{j} − ∑_{t=1}^{k} ε_{t}_{∏_{j=1}^{k} ; j≠t}λ_{j}

divides det M(n, k) for any composition ε ∈ C(n − i, k), 1 ≤ i ≤ n. (It should be noted that T (n, k, x, λ, ε) is the factor corresponding to ε_{1}, ε_{2}, …, ε_{k} in the product in the numerator on the right-hand side of (1.5), up to multiplication by ∏_{j=1}^{k} λ_{j}.) To prove this assertion, we find a vector in the kernel of

M(n, k)|_{T (n,k,x,λ,ε)=0}.  (2.1)

This kernel lives in the free vector space generated by the compositions in C(n, k). Given δ ∈ C(n, k), let us denote the corresponding element (“unit vector”) in this vector space by e_{δ}. Then we claim that the vector

v_{ε} := ∑_{δ∈C(i,k)} (∑_{t=1}^{k} \frac{δ_{t}}{λ_{t}} ) \binom{δ + ε}{δ}e_{δ+ε}  (2.2)

is in the kernel of the matrix (2.1). To see this, we calculate, using Lemma 11 and the notation u_{t} = (0, …, 0, 1, 0, …, 0) (with the 1 in position t),

coefficient of e_{α} in M(n, k) · v_{ε} = ∑_{δ∈C(i,k)} \binom{x + λα}{δ + ε} (∑_{t=1}^{k} \frac{δ_{t}}{λ_{t}} ) \binom{δ + ε}{δ}

= \binom{x + λα}{ε} ∑_{t=1}^{k} ∑_{|δ|=i} \frac{δ_{t}}{λ_{t}} \binom{x + λα − ε}{δ}

= \binom{x + λα}{ε} ∑_{t=1}^{k} \frac{1}{λ_{t}} (x_{t} + λ_{t}α_{t} − ε_{t}) ∑_{|δ|=i} \binom{x + λα − ε − u_{t}}{δ − u_{t}}

= \binom{x + λα}{ε} (n + ∑_{t=1}^{k} (\frac{x_{t}}{λ_{t}} − \frac{ε_{t}}{λ_{t}} )) \binom{|x + λα| − (n − i) − 1}{i − 1}.

Since i ≥ 1, the occurrence of the factor in the middle implies

M(n, k)|_{T (n,k,x,λ,ε)=0} · v_{ε} = 0.

Step 2. Comparison of degrees. By inspection, the (total) degree in the x_{i}’s and λ_{i}’s of the determinant on the left-hand side of (1.5) is at most n · |C(n, k)| = n\binom{n+k−1}{n}. On the other hand, the degree in the x_{i}’s and λ_{i}’s of the right-hand side of (1.5) is equal to k\binom{n+k−1}{k} = n\binom{n+k−1}{n}.

Since the degree bound on the determinant is the same as the degree of the right-hand side of (1.5), the determinant must be equal to the right-hand side up to a possible multiplicative constant which is independent of the x_{i}’s and λ_{i}’s. We conclude that

det_{α,β∈C(n,k)} (\binom{x + λα}{β}) = const(n, k) (∏_{j=1}^{k} λ_{j})^{\binom{n+k−1}{k}}

×_{∏_{ε_{1},...,ε_{k}≥0} ; ε_{1}+···+ε_{k}<n} (n + ∑_{j=1}^{k} (\frac{x_{j}}{λ_{j}} − \frac{ε_{j}}{λ_{j}} )), (2.3)

where const(n, k) is independent of x and λ.

Step 3. Computation of the multiplicative constant. If we set x_{i} = 0 and λ_{i} = 1 for all i, then the determinant on the left-hand side of (1.5) becomes triangular with 1s on the diagonal. Thus, we obtain that

1 = const(n, k)_{∏_{ε_{1},...,ε_{k}≥0} ; ε_{1}+···+ε_{k}<n} (n − ∑_{j=1}^{k} ε_{j}) = const(n, k) ∏_{i=1}^{n} i^{|C(n−i,k)|}.

This implies that

const(n, k) = ∏_{i=1}^{n} i^{−\binom{n+k−i−1}{k−1}},

completing the proof of the theorem. □

Proof of the equivalence of Theorem 5 and 6. If we replace λ_{i} by −λ_{i} and x_{i} by −x_{i} −1 for all i in (1.5), and then use the identity \binom{X}{m} = (−1)^{m}\binom{−X+m−1}{m}, then we obtain

det_{α,β∈C(n,k)} ((−1)^{n}\binom{x + λα + β}{β}) =

= (−1)^{k\binom{n+k−1}{k}} (∏_{j=1}^{k} λ_{j})^{\binom{n+k−1}{k}} \frac{_{∏_{ε_{1},...,ε_{k}≥0} ; ε_{1}+···+ε_{k}<n} (n + ∑_{j=1}^{k} (\frac{x_{j} + 1}{λ_{j}} + \frac{ε_{j}}{λ_{j}} ))}{∏_{i=1}^{n} i^{\binom{n+k−i−1}{k−1}}}.  (2.4)

Except for the signs, this is exactly (1.6). However, we have

n · |C(n, k)| + k\binom{n + k − 1}{k} = n\binom{n + k − 1}{k − 1} + k\binom{n + k − 1}{k} = 2\frac{(n + k − 1)!}{(k − 1)! (n − 1)!}.

Since this is an even number, the signs in (2.4) do indeed cancel. □

Proof of Corollary 9. The right-hand and left-hand sides of (1.5) are both polynomials in the λ_{i}’s and the x_{i}’s. As we already observed in Step 2 of the first proof of Theorem 5, the (total) degree in the λ_{i}’s and the x_{i}’s of the determinant on the left-hand side is equal to

n · |C(n, k)| = n\binom{n + k − 1}{k − 1} = k\binom{n + k − 1}{k},

and the degree in the λ_{i}’s and the x_{i}’s of the expression on the right-hand side is exactly the same value. Therefore, if we extract the homogeneous parts in the λ_{i}’s and the x_{i}’s of degree k\binom{n+k−1}{k} in (1.5), we obtain

det_{α,β∈C(n,k)} (\frac{(x + λα)^{β}}{β!} ) = (∏_{j=1}^{k} λ_{j})^{\binom{n+k−1}{k}} \frac{_{∏_{ε_{1},...,ε_{k}≥0} ; ε_{1}+···+ε_{k}<n} (n + ∑_{j=1}^{k} \frac{x_{j}}{λ_{j}} )}{∏_{i=1}^{n} i^{\binom{n+k−i−1}{k−1}}},

where β! = ∏_{i=1}^{k} β_{i}!, or, equivalently,

det_{α,β∈C(n,k)} ((x + λα)^{β}) = (∏_{j=1}^{k} λ_{j})^{\binom{n+k−1}{k}} \frac{(n + ∑_{j=1}^{k} \frac{x_{j}}{λ_{j}} )^{∑_{i=0}^{n−1} |C(i,k)|}}{∏_{i=1}^{n} i^{\binom{n+k−i−1}{k−1}}} ( ∏_{β∈C(n,k)} β!).

Since

∑_{i=0}^{n−1} |C(i, k)| = ∑_{i=0}^{n−1} \binom{i + k − 1}{k − 1} = \binom{n + k − 1}{k},

the only missing piece for the proof of the corollary is the verification of the identity

∏_{β∈C(n,k)} β! = ∏_{β_{1}+···+β_{k}=n} β_{1}! ⋯ β_{k}! = ∏_{i=1}^{n} i^{k\binom{n+k−i−1}{k−1}}.  (2.5)

This can, for example, be done by induction on n + k, by using the obvious recurrence

Π(n, k) = ∏_{i=0}^{n} (i!^{|C(n−i,k−1)|}Π(n − i, k − 1)) ,

where

Π(n, k) = ∏_{β_{1}+···+β_{k}=n} β_{1}! ⋯ β_{k}!.

□

3. Determinants for compositions with only positive parts

Let C^{∗}(n, k) denote the set of all compositions of n with exactly k positive summands. Then we have the following theorem.

Theorem 12. Let x = (x_{1}, x_{2}, …, x_{k}) and λ = (λ_{1}, λ_{2}, …, λ_{k}) be vectors of indeterminates. Then, for any positive integers n and k, n ≥ k, we have

det_{α,β∈C^{∗}(n,k)} (\binom{x + λα}{β}) = (∏_{j=1}^{k} λ_{j})^{\binom{n−1}{k}} (∏_{i=1}^{k} ∏_{j=1}^{n−k+1} (\frac{x_{i} + λ_{i}j}{j} )^{\binom{n−j−1}{k−2}})

× \frac{_{∏_{ε_{1},...,ε_{k}≥0} ; ε_{1}+···+ε_{k}<n−k} (n + ∑_{j=1}^{k} (\frac{x_{j} − 1}{λ_{j}} − \frac{ε_{j}}{λ_{j}} ))}{∏_{i=1}^{n} i^{\binom{n−i−1}{k−1}}}. (3.1)

Proof. Let 1 be the k-vector with all entries equal to 1. The mapping C^{∗}(n, k) → C(n − k, k) defined by α = (α_{1}, …, α_{k}) ↦ α − 1 = (α_{1} − 1, …, α_{k} − 1) is bijective. Thus, we have

det_{α,β∈C^{∗}(n,k)} (\binom{x + λα}{β}) = det_{α,β∈C^{∗}(n,k)} (\binom{x + λ + λ(α − 1)}{β − 1 + 1})

= det_{α,β∈C(n−k,k)} (\binom{x + λ + λα}{β + 1})

= det_{α,β∈C(n−k,k)} (\binom{x + λ − 1 + λα}{β} ∏_{i=1}^{k} \frac{x_{i} + λ_{i} + λ_{i}α_{i}}{β_{i} + 1} )

= ( ∏_{α∈C(n−k,k)} ∏_{i=1}^{k} \frac{x_{i} + λ_{i}(α_{i} + 1)}{α_{i} + 1}) det_{α,β∈C(n−k,k)} (\binom{x + λ − 1 + λα}{β}) .

In the product, a ratio (x_{i} + λ_{i}(j + 1))/(j + 1) appears as many times as there are compositions in C(n − k − j, k − 1), i.e., \binom{n−j−2}{k−2} times. Thus,

∏_{α∈C(n−k,k)} ∏_{i=1}^{k} \frac{x_{i} + λ_{i}(α_{i} + 1)}{α_{i} + 1} = ∏_{i=1}^{k} ∏_{j=0}^{n−k} (\frac{x_{i} + λ_{i}(j + 1)}{j + 1})^{\binom{n−j−2}{k−2}}

= ∏_{i=1}^{k} ∏_{j=1}^{n−k+1} (\frac{x_{i} + λ_{i}j}{j} )^{\binom{n−j−1}{k−2}} .

Substituting this and using Theorem 5 with n replaced by n − k and x replaced by x + λ − 1 to evaluate the determinant, we obtain the desired formula. □

By replacing λ_{i} by −λ_{i} and x_{i} by −x_{i} −1 for all i in (3.1), and then using the identity \binom{X}{m} = (−1)^{m}\binom{−X+m−1}{m}, we obtain the following equivalent form of Theorem 12.

Theorem 13. Let x = (x_{1}, x_{2}, …, x_{k}) and λ = (λ_{1}, λ_{2}, …, λ_{k}) be vectors of indeterminates. Then, for any positive integers n and k, n ≥ k, we have

det_{α,β∈C^{∗}(n,k)} (\binom{x + λα + β}{β}) = (∏_{j=1}^{k} λ_{j})^{\binom{n−1}{k}} (∏_{i=1}^{k} ∏_{j=1}^{n−k+1} (\frac{x_{i} + λ_{i}j + 1}{j})^{\binom{n−j−1}{k−2}})

× \frac{_{∏_{ε_{1},...,ε_{k}≥0} ; ε_{1}+···+ε_{k}<n−k} (n + ∑_{j=1}^{k} (\frac{x_{j} + 2}{λ_{j}} + \frac{ε_{j}}{λ_{j}} ))}{∏_{i=1}^{n} i^{\binom{n−i−1}{k−1}}}. (3.2)

Extracting the highest homogeneous component in Theorem 12, we obtain the following analogue of Corollary 10.

Corollary 14. Let x = (x_{1}, x_{2}, …, x_{k}) and λ = (λ_{1}, λ_{2}, …, λ_{k}) be vectors of indeterminates. Then, for any positive integers n and k, n ≥ k, we have

det_{α,β∈C^{∗}(n,k)} ((x + λα)^{β}) = (∏_{j=1}^{k} λ_{j})^{\binom{n−1}{k}} (∏_{i=1}^{k} ∏_{j=1}^{n−k+1} (x_{i} + λ_{i}j)^{\binom{n−j−1}{k−2}})

× (_{∏_{ε_{1},...,ε_{k}≥0} ; ε_{1}+···+ε_{k}<n−k} (n + ∑_{j=1}^{k} \frac{x_{j}}{λ_{j}} )) ∏_{i=1}^{n−k} i^{(k−1)\binom{n−i−1}{k−1}}. (3.3)

References

[1] J. M. Brunat and A. Montes, The power-compositions determinant and its application to global optimization, SIAM J. Matrix Anal. Appl. 23 (2001), 459–471.

[2] J. M. Brunat and A. Montes, A polynomial generalization of the power-compositions determinant, Linear Multilinear Algebra (to appear); available at http://www-ma2.upc.edu/~montes/.

[3] R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, Massachusetts, 1989.

[4] C. Krattenthaler, Advanced determinant calculus, Séminaire Lotharingien Combin. 42 (1999) (“The Andrews Festschrift”), Article B42q, 67 pp.

[5] C. Krattenthaler, Advanced determinant calculus: a complement, preliminary version;

   arXiv:math.CO/0503507v1.

[6] C. Krattenthaler, Advanced determinant calculus: a complement, Linear Algebra Appl. 411 (2005), 68–166.

Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Jordi Girona 1–3, 08034 Barcelona, Spain.

Institut Camille Jordan, Université Claude Bernard Lyon-I, 21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France.

Institut Gaspard Monge, Université de Marne-la-Vallée, F-77454 Marne-la-Vallée Cedex 2, France.