USING THE JACOBI-TRUDI FORMULA TO

COMPUTE STIRLING DETERMINANTS

Tewodros Amdeberhan and Shalosh B. Ekhad

PART I: Theory

The unsigned Stirling numbers of the first kind \left[{n \atop k}\right] enumerate permutations of n elements with k disjoint cycles. They also arise as coefficients of the rising factorial, i.e.,

x(x + 1)(x + 2) ⋯ (x + n − 1) = ∑_{k=0}^{n} \left[{n \atop k}\right] x^{k}.

The Stirling numbers of the second kind \left\{{n \atop k}\right\} enumerate the number of ways to partition a set of n objects into k non-empty subsets. They also arise as coefficients of the falling factorial, i.e.,

\frac{x^{k}}{x(x − 1)(x − 2) ⋯ (x − k)} = ∑_{n=1}^{∞} \left\{{n \atop k}\right\}x^{n}.

Assume a and b to be non-negative integers. Our specific interest lies in computing the determinants of the following n × n matrices

M_{n}(a, b) = (\left[{i + a \atop j + b}\right])_{1≤i,j≤n}  and  N_{n}(a, b) = (\left\{{i + a \atop j + b}\right\})_{1≤i,j≤n} .

Denote β_{n}(a, b) = det(M_{n}(a, b)) and γ_{n}(a, b) = det(N_{n}(a, b)). Let [a] = {1, 2, …, a} be the integer interval. Given a partition λ, the Schur functions can be given by

s_{λ}(ξ_{1}, …, ξ_{a}) = \begin{matrix}det & (ξ_{i}^{λ_{j}+a−j}) & 1≤i,j≤a \\ det & (ξ_{i}^{a−j}) & 1≤i,j≤a \end{matrix} .

We are now ready to state our results.

Theorem 1. For a, b, n ∈ ℤ_{≥0} and b ≤ a, the sequence β_{n}(a, b) has a rational generating function, in the variable q, with linearly factored denominator having the form

∏_{\begin{matrix}i_{1}<i_{2}<···<i_{b} \\ i_{1},i_{2},...,i_{b}∈[a] \end{matrix}} (1 − \frac{a!}{i_{1}i_{2} ⋯ i_{b}} q) .

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 05A10, 05A15, 05E05, 11B65.

Theorem 2. Denote (n^{c}) = (n, n, …, n) ⊢ cn to be a partition of cn. Then, we have

β_{n}(a, b) = s_{(n^{a−b})}(1, 2, …, a)  and  γ_{n}(a, b) = s_{((a−b)^{n}}(1, 2, …, a)).

Proof. First, observe that the Stirling numbers of the first and second kinds are the respective specializations of e_{m} and h_{m}. Both assertions follow from the Jacobi-Trudi and Nägelsbach-Kostka identities

s_{λ}(ξξξ) = det(e_{λ′_{j}+j−i}(ξξξ))_{1≤i,j≤n} = det(h_{λ_{j}+j−i}(ξξξ))_{1≤i,j≤n},

where λ′ is the conjugate partition to λ and e_{m}(ξξξ), h_{m}(ξξξ) are the elementary and the complete homogeneous symmetric functions, respectively. □

Theorem 3. Let A_{i} = (−1)^{a−i} · \frac{i^{a}}{a!} \binom{a}{i}, for i ∈ [a]. Then, we have the ”explicit” expressions

β_{n}(a + b, b) = (−1)^{\binom{a}{2}} ∑_{1≤i_{1}<···<i_{a}≤a+b} ∏_{ℓ=1}^{a} A_{i_{ℓ}} · ∏_{\begin{matrix}ℓ_{u}<ℓ_{v} \\ ℓ_{u},ℓ_{v}∈\{i_{1},...,i_{a}\} \end{matrix}}(i_{ℓ_{u}} − i_{ℓ_{v}})^{2} · ∏_{ℓ=1}^{a} i_{ℓ}^{n−a+1} = γ_{a}(n + b, b).

Remark. R. Stanley informed the first author that our identity for special case β_{n}(a + 1, a) looks like its should be equivalent to Exercise 7.4 in [2] (see also references therein).

PART II: Computations

Using the Jacobi-Trudi formula mentioned in Theorem 2 in Part I (Eq. (I.3.5) in [1], page 41) we computed explicit expressions for β_{n}(a, b), and also the explicit generating functions ∑_{n=0}^{∞} β_{n}(a, b)q^{n} (that are always rational functions of q), for all 10 ≥ n ≥ a ≥ b ≥ 0.

The output file is

  https://sites.math.rutgers.edu/~zeilberg/tokhniot/oStirlingDet1.txt

It was generated by executing the command

  Paper1(10,n,q):

in the Maple package accompanying this article, that can be gotten from

  https://sites.math.rutgers.edu/~zeilberg/tokhniot/StirlingDet.txt

References

[1] Ian G. Macdonald, Symmetric Functions and Hall Polynomials, second edition, Clarendon Press, Oxford, 1995..

[2] R. P. Stanley, Enumerative combinatorics, Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, Cambridge, 1999. xii+581 pp.

Tewodros Amdeberhan, Department of Mathematics, Tulane University, New Orleans, LA, 70118,

USA. Email: tamdeber@tulane.edu

Shalosh B. Ekhad (c/o D. Zeilberger) Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: ShaloshBEkhad@gmail.com

June 17, 2022