Séminaire Lotharingien de Combinatoire 59 (2008), Article B59d

COUNTING MULTIDERANGEMENTS BY EXCEDANCES

CHAK-ON CHOW

Abstract. We consider the enumeration of multiderangements of a multiset n = {1^{n_{1}}, 2^{n_{2}}, …, m^{n_{m}}} by the number of excedances. We prove several properties, including the invariance under permutations of {n_{1}, n_{2}, …, n_{m}}, the symmetry, recurrence relations, the real-rootedness, and a combinatorial expansion, of the generating function d_{n}(x) of multiderangements by excedances, thus generalizing the corresponding results for the classical derangements. By a further extension, the generating function for multipermutations by numbers of excedances and fixed points is also given.

1. Introduction

In [3] Brenti considered a class of derangement polynomials defined for n ⩾ 1 by

d_{n}(x) = ∑_{w∈𝒟_{n}} x^{e(w)},

and conjectured that d_{n}(x) has only real zeros, where e(w) = #{i ∈ [n] : w_{i} > i} is the number of excedances of w = w_{1}w_{2} ⋯ w_{n} ∈ 𝔖_{n} and 𝒟_{n} is the set of derangements in 𝔖_{n}. Brenti remarked in [4] that this conjecture had been settled by E. Rodney Canfield (unpublished). A published proof of this conjecture later appeared in the work of Zhang [16, 17] which involved the recurrence relation for the d_{n}(x)’s, namely,

(1)  d_{n+1}(x) = nx[d_{n}(x) + d_{n−1}(x)] + x(1 − x)d′_{n}(x).

There are a number of possible lines of generalizations of the above mentioned results. For instance, one may consider generalizations to other Coxeter families. See, e.g., [5] for the type B case. Another line of generalization, which is the focus of this work, is to consider multiderangements. Let n = {1^{n_{1}}, 2^{n_{2}}, …, m^{n_{m}}} be a multiset and n := n_{1} + ⋯ + n_{m}. A multipermutation w = w_{1}w_{2} ⋯ w_{n} of n is called a multiderangement if w_{i} ≠ p_{i} for i = 1, 2, …, n, where the word δ(w) = p_{1}p_{2} ⋯ p_{n} is the nondecreasing rearrangement of w. An integer i ∈ [n] is an excedance of w = w_{1}w_{2} ⋯ w_{n} if w_{i} > p_{i}. Denote by exc(w) := {i ∈ [n]: w_{i} > p_{i}} the excedance set, and by e(w) := # exc(w) the number of excedances, of w. Every multiderangement w = w_{1}w_{2} ⋯ w_{n}, regarded as a multipermutation of n, can be represented by the two-line representation \binom{δ(w)}{w} or by the one-line representation w_{1}w_{2} ⋯ w_{n}. For further details on multipermutations, their representations, cycle factorizations and related algorithms, see [7]. Denote by 𝒟(n) the set of all multiderangements of n.

2000 Mathematics Subject Classification. 05A05, 05A15.

Key words and phrases. Multisets, multiderangements, excedances, symmetric functions.

\begin{matrix}\{n_{1}, n_{2}, …, n_{m}\} & d_{n}(x) \\ \{1, 1\} & x \\ \{1, 1, 1\} & x + x^{2} \\ \{2, 2\} & x^{2} \\ \{2, 1, 1\} & 2x^{2} \\ \{1, 1, 1, 1\} & x + 7x^{2} + x^{3} \\ \{2, 2, 1\} & 2x^{2} + 2x^{3} \\ \{2, 1, 1, 1\} & 6x^{2} + 6x^{3} \\ \{1, 1, 1, 1, 1\} & x + 21x^{2} + 21x^{3} + x^{4} \\ \{3, 3\} & x^{3} \\ \{3, 2, 1\} & 3x^{3} \\ \{3, 1, 1, 1\} & 6x^{3} \\ \{2, 2, 2\} & x^{2} + 8x^{3} + x^{4} \\ \{2, 2, 1, 1\} & 4x^{2} + 21x^{3} + 4x^{4} \\ \{2, 1, 1, 1, 1\} & 14x^{2} + 56x^{3} + 14x^{4} \\ \{1, 1, 1, 1, 1, 1\} & x + 51x^{2} + 161x^{3} + 51x^{4} + x^{5} \end{matrix}

Table 1. d_{n}(x) for n = 2, 3, …, 6.

The generating function of multiderangements by excedances is defined as

d_{n}(x) = ∑_{w∈𝒟(n)} x^{e(w)} = ∑_{k⩾0}Θ(n, k)x^{k},

where Θ(n, k) = #{w ∈ 𝒟(n) : e(w) = k}. The goal of this work is to establish several properties of d_{n}(x). In the next section, we prove the invariance under permutations of {n_{1}, n_{2}, …, n_{m}}, and the symmetry, of d_{n}(x). In Section 3, we compute the recurrence relations which d_{n}(x) satisfies. In Section 4, we prove the real-rootedness of d_{n}(x) from which we deduce the unimodality and log-concavity of the coefficients of d_{n}(x). In Section 5, we give a combinatorial expansion of d_{n}(x), which parallels the one for d_{n}(x). In the final section, we extend the generating function to the one counting multipermutations by the numbers of excedances and fixed points.

2. Basic properties

We establish some basic properties of d_{n}(x) in this section. The first few non-zero d_{n}(x)’s are listed in Table 1. If n_{1} = n_{2} = ⋯ = n_{m} = 1, then n = {1, 2, …, m} so that d_{n}(x) = d_{m}(x), whose properties are known [3, 16, 17].

Property 2.1. The following hold:

(i) If max_{1⩽i⩽m} n_{i} > n/2, then 𝒟(n) = ∅ so that d_{n}(x) ≡ 0.

(ii) If n_{i} = n/2 for some i ∈ [m], then d_{n}(x) = \binom{n/2}{n_{1},...,n_{i−1},n_{i+1},...,n_{m}}x^{n/2}.

(iii) Let n = {1^{n_{1}}, 2^{n_{2}}, …, m^{n_{m}}} and n′ = {1^{n_{i_{1}}}, 2^{n_{i_{2}}}, …, m^{n_{im}}} be two multisets such that (i_{1}, i_{2}, …, i_{m}) is a permutation of (1, 2, …, m). Then d_{n}(x) ≡ d_{n′}(x).

Properties 2.1(i)–(ii) are easily proved. Using MacMahon’s Master Theorem [9, p. 97– 98], Askey and Ismail [1] showed that (2)

∑_{n_{1},...,n_{m}⩾0}d_{n}(x)x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}} = \frac{1}{1 − xe_{2} − (x + x^{2})e_{3} − ⋯ − (x + x^{2} + ⋯ + x^{m−1})e_{m}} ,

where e_{i} (2 ⩽ i ⩽ m) is the ith elementary symmetric function in the commuting indeterminates x_{1}, …, x_{m}. See [13, Chapter 7] for the definitions of undefined terms concerning symmetric functions. The identity (2) was also obtained by Kim and Zeng using their U- and V -decompositions of derangements [8] and Foata’s factorization of multipermutations [6, 7]. Again by using MacMahon’s Master Theorem, Zeng enumerated in [15] multipermutations and multiderangements by the numbers of cycles and excedances.

Property 2.1(iii) is implicit in (2). To wit, recall that [13, Proposition 7.4.1] if λ ⊢ n, then

(3)  e_{λ} = ∑_{μ⊢n} M_{λ,μ}m_{μ},

where e_{λ} is the elementary symmetric function indexed by λ, m_{μ} the monomial symmetric function indexed by μ, M_{λ,α} the number of (0, 1)-matrices A = (a_{ij})_{i,j⩾1} with row sum vector row(A) = λ and column sum vector col(A) = α, and α = (α_{1}, α_{2}, …) a weak composition of n. Expanding the right side of (2), we have

(4) ∑_{n_{1},...,n_{m}⩾0}d_{n}(x)x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}

= 1 + ∑_{l⩾1}(∑_{k=2}^{m}(x + x^{2} + ⋯ + x^{k−1})e_{k})^{l}

= 1 + ∑_{l⩾1} ∑_{2⩽k_{1},...,k_{l}⩽m} e_{k_{1}} ⋯ e_{k_{l}} ∏_{j=1}^{l}(x + x^{2} + ⋯ + x^{k_{j}−1})

= 1 + ∑_{l⩾1} ∑_{2⩽k_{1},...,k_{l}⩽m} ∑_{μ⊢k_{1}+···+k_{l}} M_{(k_{1},...,k_{l}),μ}m_{μ} ∏_{j=1}^{l}(x + x^{2} + ⋯ + x^{k_{j}−1}),

where the last equality follows from (3). Since m_{μ} is a sum of distinct permutations of monomials x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}} having μ equal to the weakly decreasing rearrangement of its exponents, equating the coefficients of x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}, we have that d_{n}(x) ≡ d_{n′}(x), where n′ is a multiset obtained by a permutation of n.

If n_{j} = n/2 for some j ∈ [m], then n_{i} ⩽ n/2 for all i ∈ [m] so that max_{1⩽i⩽m} n_{i} = n/2

and Property 2.1(ii) implies that d_{n}(x) is symmetric of degree n − max_{1⩽i⩽m} n_{i} and with

center of symmetry at n/2. This symmetry result actually holds for arbitrary multiset n = {1^{n_{1}}, 2^{n_{2}}, …, m^{n_{m}}} such that max_{1⩽i⩽m} n_{i} ⩽ n/2. See Proposition 2.3 below.

We need some notations and results from [7] for the proof of Proposition 2.3.

Let A be a totally order alphabet and A^{∗} be the free monoid generated by A. A word w = w_{1}w_{2} ⋯ w_{n} ∈ A^{∗} is said to be dominated if w_{1} > w_{i} for i = 2, 3, …, n. Let w and w′ be A-words of the same length. The two-row matrix \binom{w′}{w} is called a flow. If w′ is a rearrangement of w, then \binom{w′}{w} is called a circuit. Denote by δw := w_{2}w_{3} ⋯ w_{n}w_{1} the cyclic shift of the word w = w_{1}w_{2} ⋯ w_{n}. A circuit c is said to be dominated if it is of the form \binom{δw}{w} for some dominated word w. If c = \binom{δw}{w} is a dominated circuit, then let F c := F w, the first letter of w. A dominated circuit factorization of a circuit c is a sequence (d_{1}, d_{2}, …, d_{r}) of dominated circuits with the property that c = d_{1}d_{2} ⋯ d_{r} and F d_{1} ⩽ F d_{2} ⩽ ⋯ ⩽ F d_{r}. The next result is due to Foata [7, Theorem 10.4.1].

Theorem 2.2. Every nonempty circuit admits exactly one dominated circuit factorization.

For instance, for the word w = 31514226672615, its nondecreasing rearrangement δ(w) = 11122234556667 and the circuit \binom{δ(w)}{w} admits the following dominated circuit factorization:

\binom{δ(w)}{w} = ( \begin{matrix}1 & 1 & 1 & 2 & 2 & 2 & 3 & 4 & 5 & 5 & 6 & 6 & 6 & 7 \\ 3 & 1 & 5 & 1 & 4 & 2 & 2 & 6 & 6 & 7 & 2 & 6 & 1 & 5 \end{matrix} )

= (\begin{matrix}1 & 1 & 2 & 3 \\ 3 & 1 & 1 & 2 \end{matrix}) (\begin{matrix}4 & 2 & 2 & 6 \\ 6 & 4 & 2 & 2 \end{matrix}) (\begin{matrix}6 \\ 6 \end{matrix}) (\begin{matrix}5 & 1 & 6 \\ 6 & 5 & 1 \end{matrix}) (\begin{matrix}5 & 7 \\ 7 & 5 \end{matrix}) .

Observe that the columns of the dominated circuits in the factorization are precisely those of \binom{δ(w)}{w}, and that in each dominated circuit

(\begin{matrix}a_{i} & a_{i−1} & ⋯ & a_{j−1} & a_{j−2} & ⋯ & a_{1} & a_{0} \\ a_{0} & a_{i} & ⋯ & a_{j} & a_{j−1} & ⋯ & a_{2} & a_{1} \end{matrix}) ,

each (vertical) occurrence of excedance corresponds to a (horizontal) occurrence of descent. It is clear that each dominated circuit is uniquely determined by the bottom word of the circuit. Thus, when we talk about dominated circuits in the sequel, we mean the bottom word of the circuit. Moreover, reversing the bottom word turns descents into non-descents, hence excedances into non-excedances, and vice versa.

Proposition 2.3. For each multiset n = {1^{n_{1}}, 2^{n_{2}}, …, m^{n_{m}}}, d_{n}(x) is a symmetric polynomial of degree n − max_{1⩽i⩽m} n_{i} and with center of symmetry at n/2 if it is not iden-

tically zero.

Proof. Let w ∈ 𝒟(n). Denote by (d_{1}, d_{2}, …, d_{r}) the dominated circuit factorization of w. For i = 1, 2, …, r, let d̃_{i} be the dominated circuit obtained by cyclic permutation of the reversal of d_{i}. Let w̃ ∈ 𝒟(n) be the multiderangement whose dominated circuit factorization is (d̃_{1}, d̃_{2}, …, d̃_{r}). By the remark preceding the present proposition, we have e(w̃) = n−e(w). The map Φ: 𝒟(n) ⟶ 𝒟(n) defined by Φ(w) = w̃ for w ∈ 𝒟(n) is thus a bijection sending 𝒟(n) onto itself such that e(Φ(w)) = e(w̃) = n − e(w). This establishes the symmetry of d_{n}(x).

That d_{n}(x) has center of symmetry at n/2 is clear.

It remains to prove that deg d_{n}(x) = n − max_{1⩽i⩽m} n_{i}. By virtue of Property 2.1(iii),

we may assume that n_{1} ⩾ n_{2} ⩾ ⋯ ⩾ n_{m} so that n_{1} = max_{1⩽i⩽m} n_{i}. To show that

deg d_{n}(x) = n − n_{1}, we demonstrate explicitly a w ∈ 𝒟(n) with e(w) = n − n_{1}. Let w be the word obtained by concatenating n_{2} copies of 2’s, n_{3} copies of 3’s, …, n_{m} copies of m’s, and n_{1} copies of 1’s. Also, let δ(w) = p_{1}p_{2} ⋯ p_{n} be the nondecreasing rearrangement of w. Since n_{1} ⩾ n_{2} ⩾ ⋯ ⩾ n_{m}, it is clear that w_{i} ≠ p_{i} for all i ∈ [n] so that w ∈ 𝒟(n) with the first n − n_{1} positions being excedances and the remaining n_{1} positions non-excedances. □

It is worth mentioning that in the classical derangement case, i.e., n = {1, 2, …, m}, the (unique) derangement w ∈ 𝒟(n) with e(w) = m − 1 is w = 23 ⋯ m1; also, the bijection Φ: 𝒟(n) ⟶ 𝒟(n) in the above proof is precisely the inversion map Φ(w) = w^{−1}.

3. Recurrence relations

We derive in this section the recurrence relations for d_{n}(x). The multi-analogue of (1) is the following.

Proposition 3.1. Let n = {1^{n_{1}}, 2^{n_{2}}, …, m^{n_{m}}}. The polynomial d_{n}(x) satisfies

(5) d_{n+e_{m+1}}(x) = x[n_{1}d_{n−e_{1}}(x) + ⋯ + n_{m}d_{n−e_{m}}(x)] + nxd_{n}(x) + x(1 − x)d′_{n}(x)

and for j = 1, 2, …, m,

(n_{j} + 1)d_{n+e_{j}}(x) = x[n_{1}d_{n−e_{1}}(x) + ⋯ + n_{j−1}d_{n−e_{j−1}}(x) + n_{j+1}d_{n−e_{j+1}}(x) (6)

+ ⋯ + n_{m}d_{n−e_{m}}(x)] + [(n − n_{j})x − n_{j}]d_{n}(x) + x(1 − x)d′_{n}(x),

where n + e_{j} (respectively n − e_{j}) denotes the multisets obtained from n by adjoining an additional copy (respectively by removing a copy) of the letter j.

Proof. There are three cases to consider.

Case 1: Let w = w_{1} ⋯ w_{n}w_{n+1} ∈ 𝒟(n + e_{m+1}). Since w_{n+1} ≠ m + 1 and m + 1 occurs only once in w, there exists exactly one i ∈ [n] such that w_{i} = m + 1. It is clear that i is an excedance of w. Consider the word w′ = w_{1} ⋯ w_{i−1}w_{n+1}w_{i+1} ⋯ w_{n}(m + 1) obtained by swapping the ith and the (n + 1)st letters of w. If w_{n+1} ≠ p_{i}, then w_{1} ⋯ w_{i−1}w_{n+1}w_{i+1} ⋯ w_{n} ∈ 𝒟(n) and

e(w) = e(w_{1} ⋯ w_{i−1}w_{n+1}w_{i+1} ⋯ w_{n}) + χ(i ∉ exc(w_{1} ⋯ w_{i−1}w_{n+1}w_{i+1} ⋯ w_{n})),

where χ(P) = 1 if P is true, and 0 otherwise. If w_{n+1} = p_{i}, then w_{1} ⋯ w_{i−1}w_{i+1} ⋯ w_{n} ∈ 𝒟(n−e_{p_{i}}) and e(w) = e(w_{1} ⋯ w_{i−1}w_{i+1} ⋯ w_{n})+1, where n−e_{p_{i}} is the multiset obtained from n by removing one copy of the p_{i}th type element. Putting pieces together, we have

d_{n+e_{m+1}}(x) = ∑_{i=1}^{n} ∑_{w∈𝒟(n)} x^{e(w)+χ(i∉exc(w))} + ∑_{i=1}^{n} ∑_{w∈𝒟(n−e_{p_{i}})} x^{e(w)+1}

= ∑_{w∈𝒟(n)}[e(w)x^{e(w)} + (n − e(w))x^{e(w)+1}] + ∑_{i=1}^{n} ∑_{w∈𝒟(n−e_{p_{i}})} x^{e(w)+1}

= xd′_{n}(x) + nxd_{n}(x) − x^{2}d′_{n}(x) + x ∑_{i=1}^{n} d_{n−e_{p_{i}}}(x)

= x[n_{1}d_{n−e_{1}}(x) + ⋯ + n_{m}d_{n−e_{m}}(x)] + nxd_{n}(x) + x(1 − x)d′_{n}(x).

Case 2: Consider now the case that j = m. Let w = w_{1} ⋯ w_{n}w_{n+1} ∈ 𝒟(n + e_{m}). There exist i_{1}, …, i_{n_{m}+1} ∈ [n − n_{m}] such that w_{i_{1}} = ⋯ = w_{i_{nm+1}} = m. It is clear that i_{1}, …, i_{n_{m}+1} are excedances of w. For i ∈ {i_{1}, …, i_{n_{m}+1}}, consider the word w_{1} ⋯ w_{i−1}w_{n+1}w_{i+1} ⋯ w_{n}m obtained by swapping the ith and the (n + 1)st letters of w. If w_{n+1} ≠ p_{i}, then w_{1} ⋯ w_{i−1}w_{n+1} w_{i+1} ⋯ w_{n} ∈ 𝒟(n) and

e(w) = e(w_{1} ⋯ w_{i−1}w_{n+1}w_{i+1} ⋯ w_{n}) + χ(i ∉ exc(w_{1} ⋯ w_{i−1}w_{n+1}w_{i+1} ⋯ w_{n})).

If w_{n+1} = p_{i}, then w_{1} ⋯ w_{i−1}w_{i+1} ⋯ w_{n} ∈ 𝒟(n − e_{p_{i}}) and e(w) = e(w_{1} ⋯ w_{i−1} w_{i+1} ⋯ w_{n}) + 1. The map

w ↦ \begin{cases}w_{1} ⋯ w_{i−1}w_{n+1}w_{i+1} ⋯ w_{n} & if w_{n+1} ≠ p_{i}, \\ w_{1} ⋯ w_{i−1}w_{i+1} ⋯ w_{n} & if w_{n+1} = p_{i}, \end{cases}

is a (n_{m} + 1)-to-one correspondence between 𝒟(n + e_{m}) and 𝒟(n) ∪ 𝒟(n − e_{p_{i}}). Identifying now the indices i_{1}, …, i_{n_{m}+1}, there are e(w_{1} ⋯ w_{i−1}w_{n+1}w_{i+1} ⋯ w_{n}) − n_{m} “distinct” excedances and n−n_{m} −e(w_{1} ⋯ w_{i−1}w_{n+1}w_{i+1} ⋯ w_{n}) “distinct” non-excedances in [n − n_{m}]. Consequently, we have

(n_{m} + 1)d_{n+e_{m}}(x) = ∑_{i=1}^{n−n_{m}}( ∑_{w∈𝒟(n)} x^{e(w)+χ(i∉exc(w))} + ∑_{w∈𝒟(n−e_{p_{i}})} x^{e(w)+1})

= ∑_{w∈𝒟(n)}[(e(w) − n_{m})x^{e(w)} + (n − n_{m} − e(w))x^{e(w)+1}] + x ∑_{i=1}^{n−n_{m}} d_{n−e_{p_{i}}}(x)

= xd′_{n}(x) − n_{m}d_{n}(x) + (n − n_{m})xd_{n}(x) − x^{2}d′_{n}(x) + x ∑_{i=1}^{n−n_{m}} d_{n−e_{p_{i}}}(x)

= x[n_{1}d_{n−e_{1}}(x) + ⋯ + n_{m−1}d_{n−e_{m−1}}(x)] + [(n − n_{m})x − n_{m}]d_{n}(x)

+ x(1 − x)d′_{n}(x).

Case 3: Let ω be the cyclic permutation of (1, 2, …, m), i.e., ω(i) = i + 1 for i = 1, 2, …, m − 1 and ω(m) = 1. For j = 1, 2, …, m − 1, denote by

ω^{m−j}n = {ω^{m−j}(1)^{n_{1}}, ω^{m−j}(2)^{n_{2}}, …, ω^{m−j}(m)^{n_{m}}}
= {1^{n_{j+1}}, 2^{n_{j+2}}, …, (m − j)^{n_{m}}, (m − j + 1)^{n_{1}}, …, (m − 1)^{n_{j−1}}, m^{n_{j}}}

the multiset obtained by applying ω^{m−j} to the elements of n. It is clear that n + e_{j} = ω^{−(m−j)}(ω^{m−j}n + e_{m}). By Property 2.1(iii) and Case 2, we have

(n_{j} + 1)d_{n+e_{j}}(x) = (n_{j} + 1)d_{ω^{−(m−j)}(ω^{m−j}n+e_{m})}(x)
= (n_{j} + 1)d_{ω^{m−j}n+e_{m}}(x)
= x[n_{j+1}d_{ω^{m−j}n−e_{1}}(x) + ⋯ + n_{j−1}d_{ω^{m−j}n−e_{m−1}}(x)]
+ [(n − n_{j})x − n_{j}]d_{ω^{m−j}n}(x) + x(1 − x)d′_{ω^{m−j}n}(x)

= x[n_{j+1}d_{ω^{−(m−j)}(ω^{m−j}n−e_{1})}(x) + ⋯ + n_{j−1}d_{ω^{−(m−j)}(ω^{m−j}n−e_{m−1})}(x)]

+ [(n − n_{j})x − n_{j}]d_{n}(x) + x(1 − x)d′_{n}(x)
= x[n_{1}d_{n−e_{1}}(x) + ⋯ + n_{j−1}d_{n−e_{j−1}}(x) + n_{j+1}d_{n−e_{j+1}}(x)

+ ⋯ + n_{m}d_{n−e_{m}}(x)] + [(n − n_{j})x − n_{j}]d_{n}(x) + x(1 − x)d′_{n}(x),

as desired. □

In case n_{1} = n_{2} = ⋯ = n_{m} = 1, (5) reduces to (1) with n = n_{1} + ⋯ + n_{m} = m. Note that if we regard n = {1^{n_{1}}, …, m^{n_{m}}} as the multiset {1^{n_{1}}, …, m^{n_{m}}, (m + 1)^{n_{m+1}}}, where n_{m+1} := 0, then (6) with m + 1 in place of m and j = m + 1 becomes (5).

By exploiting (2), an alternative proof of the recurrence relation (6) can be given. Towards this end, we first note the following properties of the elementary symmetric

functions e_{k} = e_{k}(x_{1}, …, x_{m}):

(i) e_{k} = ê_{j,k} + x_{j}ê_{j,k−1}, (ii) \frac{∂}{∂x_{j}} e_{k} = ê_{j,k−1}, (iii) ∑_{j=1}^{m} ê_{j,k} = (m − k)e_{k}, (iv) ∑_{j=1}^{m} x_{j}ê_{j,k} = (k + 1)e_{k+1},

where ê_{j,k} = e_{k}(x_{1}, …, x̂_{j}, …, x_{m}) denotes the kth elementary symmetric function in the alphabet {x_{1}, …, x_{m}} \ {x_{j}}, and j, k = 1, 2, …, m. We have

I = ∑_{n_{1},...,n_{m}⩾0}(n_{j} + 1)d_{n+e_{j}}(x)x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}

= \frac{∂}{∂x_{j}} ∑_{n_{1},...,n_{m}⩾0}d_{n+e_{j}}(x)x_{1}^{n_{1}} ⋯ x_{j}^{n_{j}+1} ⋯ x_{m}^{n_{m}}

= \frac{∂}{∂x_{j}} ( ∑_{n_{1},...,n_{j},...,n_{m}⩾0}d_{n}(x)x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}

− ∑_{n_{1},...,n_{j−1},n_{j+1},...,n_{m}⩾0}dn̂(x)x_{1}^{n_{1}} ⋯ x_{j−1}^{n_{j−1}}x_{j+1}^{n_{j+1}} ⋯ x_{m}^{n_{m}})

= \frac{∂}{∂x_{j}} (\frac{1}{1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k}} )

= \frac{∑_{k=2}^{m}(x + ⋯ + x^{k−1})ê_{j,k−1}}{(1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k})^{2}} ,

II = ∑_{n_{1},...,n_{m}⩾0} ∑_{i≠j} xn_{i}d_{n−e_{i}}(x)x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}

= ∑_{i≠j}[xx_{i}^{2} ∑_{\begin{matrix}n_{1},...,n_{i−1},n_{i+1},...,n_{m}⩾0 \\ n_{i}⩾1 \end{matrix}}(n_{i} − 1)d_{n−e_{i}}(x)x_{1}^{n_{1}} ⋯ x_{i}^{n_{i}−2} ⋯ x_{m}^{n_{m}}

+ xx_{i} ∑_{\begin{matrix}n_{1},...,n_{i−1},n_{i+1},...,n_{m}⩾0 \\ n_{i}⩾1 \end{matrix}}d_{n−e_{i}}(x)x_{1}^{n_{1}} ⋯ x_{i}^{n_{i}−1} ⋯ x_{m}^{n_{m}}]

= ∑_{i≠j}[xx_{i}^{2} \frac{∂}{∂x_{i}} (\frac{1}{1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k}} ) + \frac{xx_{i}}{1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k}} ]

= ∑_{i≠j} \frac{xx_{i}^{2} ∑_{k=2}^{m}(x + ⋯ + x^{k−1})ê_{i,k−1}}{(1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k})^{2}} + \frac{xê_{j,1}}{1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k}}

= \frac{∑_{i≠j} x_{i} ∑_{k=2}^{m}(x^{2} + ⋯ + x^{k})(e_{k} − ê_{i,k}) + xê_{j,1}(1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k})}{(1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k})^{2}}

= \frac{xê_{j,1} − ∑_{k=2}^{m}(x^{2} + ⋯ + x^{k}) ∑_{i≠j} x_{i}ê_{i,k}}{(1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k})^{2}}

= \frac{xê_{j,1} − ∑_{k=2}^{m}(x^{2} + ⋯ + x^{k})(ke_{k+1} + ê_{j,k+1})}{(1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k})^{2}},

III = ∑_{n_{1},...,n_{m}⩾0}[(n − n_{j})x − n_{j}]d_{n}(x)x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}

= ∑_{i≠j} x ∑_{n_{1},...,n_{m}⩾0}n_{i}d_{n}(x)x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}} − ∑_{n_{1},...,n_{m}⩾0}n_{j}d_{n}(x)x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}

= ∑_{i≠j} xx_{i} \frac{∂}{∂x_{i}} (\frac{1}{1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k}} )

− x_{j} \frac{∂}{∂x_{j}} (\frac{1}{1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k}} )

= \frac{∑_{i≠j} xx_{i} ∑_{k=2}^{m}(x + ⋯ + x^{k−1})ê_{i,k−1} − x_{j} ∑_{k=2}^{m}(x + ⋯ + x^{k−1})ê_{j,k−1}}{(1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k})^{2}}

= \frac{∑_{k=2}^{m}(x^{2} + ⋯ + x^{k}) ∑_{i≠j} x_{i}ê_{i,k−1} − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})x_{j}ê_{j,k−1}}{(1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k})^{2}}

= \frac{∑_{k=2}^{m}(x^{2} + ⋯ + x^{k})ke_{k} − ∑_{k=2}^{m}(x + 2x^{2} + ⋯ + 2x^{k−1} + x^{k})x_{j}ê_{j,k−1}}{(1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k})^{2}}

= \frac{∑_{k=2}^{m}(x^{2} + ⋯ + x^{k})ke_{k} − ∑_{k=2}^{m}(x + 2x^{2} + ⋯ + 2x^{k−1} + x^{k})(e_{k} − ê_{j,k})}{(1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k})^{2}}

= \frac{∑_{k=2}^{m}(−x + (k − 2)x^{2} + ⋯ + (k − 2)x^{k−1} + (k − 1)x^{k})e_{k}}{(1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k})^{2}}

+ \frac{∑_{k=2}^{m}(x + 2x^{2} + ⋯ + 2x^{k−1} + x^{k})ê_{j,k}}{(1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k})^{2}} ,

IV = ∑_{n_{1},...,n_{m}⩾0}x(1 − x)d′_{n}(x)x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}

= x(1 − x)\frac{∂}{∂x}(\frac{1}{1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k}} )

= \frac{x(1 − x) ∑_{k=2}^{m}(1 + 2x + 3x^{2} + ⋯ + (k − 1)x^{k−2})e_{k}}{(1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k})^{2}}

= \frac{∑_{k=2}^{m}(x + ⋯ + x^{k−1} − (k − 1)x^{k})e_{k}}{(1 − ∑_{k=2}^{m}(x + ⋯ + x^{k−1})e_{k})^{2}} .

It is not hard to see that

I = II + III + IV,

so that

∑_{n_{1},...,n_{m}⩾0}d_{n+e_{j}}(x)x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}} = ∑_{n_{1},...,n_{m}⩾0}{x[n_{1}d_{n+e_{1}}(x) + ⋯ + n_{j−1}d_{n+e_{j−1}}(x)
+ n_{j+1}d_{n+e_{j+1}}(x) + ⋯ + n_{m}d_{n+e_{m}}(x)]
+ [(n − n_{j})x − n_{j}]d_{n}(x) + x(1 − x)d′_{n}(x)}x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}.

Equating the coefficients of x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}}, (6) follows.

4. Real-rootedness

A real polynomial f(x) is standard if its leading coefficient is positive; it is simply real-rooted if all its zeros are real and simple. Let f(x) and g(x) be simply real-rooted standard polynomials of degrees n and n−1, respectively. Then g(x) is said to interlace f(x) if

(7)  θ_{1} ⩽ ξ_{1} ⩽ θ_{2} ⩽ ξ_{2} ⩽ ⋯ ⩽ θ_{n−1} ⩽ ξ_{n−1} ⩽ θ_{n},

where θ_{1}, …, θ_{n} and ξ_{1}, …, ξ_{n−1} are the zeros of f(x) and g(x), respectively. If all the inequalities in (7) are strict, then g(x) is said to strictly interlace f(x).

We shall need the following easily established fact about interlacing polynomials:

(*) If f(x) and g(x) are two simply real-rooted standard polynomials of degrees n and n − 1, respectively, and g(x) strictly interlaces f(x), then sgn g(θ_{i}) = (−1)^{n−i} for i = 1, 2, …, n, and sgn f(ξ_{j}) = (−1)^{n−j} for j = 1, 2, …, n−1, where θ_{1} < θ_{2} < ⋯ < θ_{n} and ξ_{1} < ξ_{2} < ⋯ < ξ_{n−1} are the simple real zeros of f(x) and g(x), respectively.

Theorem 4.1. For each multiset n = {1^{n_{1}}, 2^{n_{2}}, …, m^{n_{m}}}, the polynomial d_{n}(x) is realrooted. The multiplicity of 0 as a zero of d_{n}(x) is equal to max_{1⩽i⩽m} n_{i} if d_{n}(x) is not

identically zero.

Proof. For the sake of simplicity, we let N(n) := max_{1⩽i⩽m} n_{i}. By virtue of Proposition 2.3, d_{n}(x) is a polynomial in x of degree n − N(n) and with center of symmetry at n/2. The symmetry of d_{n}(x) then implies that the lowest order term of d_{n}(x) has degree N(n). Thus, d_{n}(x) = x^{N(n)}d̃_{n}(x) for some symmetric polynomial d̃_{n}(x) of degree n − 2N(n) and with positive constant term. The multiplicity of 0 as a zero of d_{n}(x) being equal to N(n) follows.

To prove the real-rootedness of d_{n}(x), we proceed by proving that d̃_{n}(x) (respectively, d̃_{n+e_{j}}(x)) strictly interlaces d̃_{n+e_{j}}(x) (respectively, d̃_{n}(x)) if deg d̃_{n+e_{j}}(x) = deg d̃_{n}(x)+1 (respectively, deg d̃_{n}(x) = deg d̃_{n+e_{j}}(x)+1) by induction on n = n_{1} +⋯+n_{m}, the cases n = 2, 3, 4 being clear from the first eight entries of Table 1. Assume now that the result holds for any multiset n′ such that n′ ⩽ n, where n ⩾ 4. Let n′′ be a multiset such that n′′ = n + 1, which can be obtained from a multiset n = {1^{n_{1}}, 2^{n_{2}}, …, m^{n_{m}}} with n_{1} + ⋯ + n_{m} = n by adjoining an additional copy of the jth type element for some j ∈ [m + 1] (see the paragraph following the proof of Proposition 3.1). If N(n + e_{j}) > (n+1)/2, then Property 2.1(i) implies that d_{n+e_{j}}(x) ≡ 0. If N(n+e_{j}) = (n+1)/2, then Property 2.1(i) implies that d_{n+e_{j}}(x) is a monomial having only the trivial zero x = 0 of multiplicity N(n + e_{j}). If N(n + e_{j}) < (n + 1)/2, there are two cases to consider, namely

(a) N(n + e_{j}) = N(n) + 1,

(b) N(n + e_{j}) = N(n). Note that in Case (a),

deg d̃_{n+e_{j}}(x) = n + 1 − 2N(n + e_{j}) = n − 2N(n) − 1 = deg d̃_{n}(x) − 1,

and in Case (b)

deg d̃_{n+e_{j}}(x) = n + 1 − 2N(n + e_{j}) = n − 2N(n) + 1 = deg d̃_{n}(x) + 1.

Let x_{1} < x_{2} < ⋯ < x_{n−2N(n)} < 0 be the real zeros of d̃_{n}(x). Let also x_{0} := −∞ and x_{n−2N(n)+1} := 0.

Since d_{n}(x) = x^{N(n)}d̃_{n}(x), differentiation with respect to x gives that

d′_{n}(x) = N(n)x^{N(n)−1}d̃_{n}(x) + x^{N(n)}d̃′_{n}(x).

Since d̃′_{n}(x) strictly interlaces d̃_{n}(x), (*) above implies that

(8)  sgn d′_{n}(x_{i}) = (−1)^{N(n)}(−1)^{n−2N(n)−i} = (−1)^{n−N(n)−i}

for i = 1, 2, …, n − 2N(n).

Let k ∈ [m + 1] \ {j}. If N(n − e_{k}) = N(n), then

deg d̃_{n−e_{k}}(x) = n − 1 − 2N(n) = deg d̃_{n}(x) − 1

so that by the induction hypothesis, d̃_{n−e_{k}}(x) strictly interlaces d̃_{n}(x). Fact (*) above then yields that sgn d̃_{n−e_{k}}(x_{i}) = (−1)^{n−2N(n)−i} for i = 1, 2, …, n − 2N(n). Since d_{n−e_{k}}(x) = x^{N(n)}d̃_{n−e_{k}}(x), we have

(9)  sgn d_{n−e_{k}}(x_{i}) = (−1)^{N(n)}(−1)^{n−2N(n)−i} = (−1)^{n−N(n)−i}

for i = 1, 2, …, n − 2N(n).

If N(n − e_{k}) = N(n) − 1, then

deg d̃_{n−e_{k}}(x) = n − 1 − 2(N(n) − 1) = deg d̃_{n}(x) + 1

so that the induction hypothesis then implies that d̃_{n}(x) strictly interlaces d̃_{n−e_{k}}(x). Fact (*) then yields that sgn d̃_{n−e_{k}}(x_{i}) = (−1)^{n+1−2N(n)−i} for i = 1, 2, …, n − 2N(n). Since d_{n−e_{k}}(x) = x^{N(n)−1}d̃_{n−e_{k}}(x), we have

(10)  sgn d_{n−e_{k}}(x_{i}) = (−1)^{N(n)−1}(−1)^{n+1−2N(n)−i} = (−1)^{n−N(n)−i}

for i = 1, 2, …, n − 2N(n).

Setting now x = x_{i} in (6), we have

(n_{j} + 1)d_{n+e_{j}}(x_{i}) = x_{i}[n_{1}d_{n−e_{1}}(x_{i}) + ⋯ + n_{j−1}d_{n−e_{j−1}}(x_{i})

+ n_{j+1}d_{n−e_{j+1}}(x_{i}) + ⋯ + n_{m}d_{n−e_{m}}(x_{i})] + x_{i}(1 − x_{i})d′_{n}(x_{i}).

Since x_{i} < 0 and x_{i}(1 − x_{i}) < 0, by (8), (9) and (10), all terms on the right side have the same sign so that

sgn d_{n+e_{j}}(x_{i}) = (−1)^{n−N(n)+1−i}

for i = 1, 2, …, n − 2N(n).

In Case (a), d_{n+e_{j}}(x) = x^{N(n)+1}d̃_{n+e_{j}}(x) so that

sgn d̃_{n+e_{j}}(x_{i}) = (−1)^{n−2N(n)−i}

for i = 1, 2, …, n − 2N(n). Thus, there exist x_{i}^{∗} ∈ (x_{i}, x_{i+1}) for which d̃_{n+e_{j}}(x_{i}^{∗}) = 0 for i = 1, 2, …, n − 2N(n) − 1. These n − 2N(n) − 1 simple real zeros of d̃_{n+e_{j}}(x), together with the trivial zero x = 0 of multiplicity N(n)+1, account for the n+1−N(n+e_{j}) = n − N(n) real zeros of d_{n+e_{j}}(x).

In Case (b), d_{n+e_{j}}(x) = x^{N(n)}d̃_{n+e_{j}}(x) so that

sgn d̃_{n+e_{j}}(x_{i}) = (−1)^{n+1−2N(n)−i}

for i = 1, 2, …, n − 2N(n). Also,

sgn d̃_{n+e_{j}}(x_{0}) = (−1)^{n+1−2N(n)} and sgn d̃_{n+e_{j}}(x_{n−2N(n)+1}) = +1

(since the constant term of d̃_{n+e_{j}}(x) is positive). Thus, there exist x_{i}^{∗} ∈ (x_{i−1}, x_{i}) for which d̃_{n+e_{j}}(x_{i}^{∗}) = 0 for i = 1, 2, …, n − 2N(n) + 1. These n − 2N(n) + 1 simple real zeros of d̃_{n+e_{j}}(x), together with the trivial zero x = 0 of multiplicity N(n), account for the n + 1 − N(n + e_{j}) = n − N(n) + 1 real zeros of d_{n+e_{j}}(x).

Note finally that in Case (a), deg d̃_{n+e_{j}}(x) = deg d̃_{n}(x) − 1 and d̃_{n+e_{j}}(x) strictly interlaces d̃_{n}(x), and that in Case (b), deg d̃_{n+e_{j}}(x) = deg d̃_{n}(x) + 1 and d̃_{n}(x) strictly interlaces d̃_{n+e_{j}}(x). This completes the induction and the proof of the theorem. □

Theorem 4.1 establishes that {d_{n}(x)} is a multi-indexed Sturm sequence. Similar Sturm sequences had been studied previously by Simion [11], who proved that f_{n}(x) has all its zeros in the interval [−1, 0] and that f_{n}(x) and f_{n+e_{j}}(x) have interlaced zeros, where f_{n}(x) := ∑_{k⩾0} 𝒪(n, k)x^{k} is the generating function of the number of compositions 𝒪(n, k) of the multiset n into exactly k parts.

A sequence {a_{0}, a_{1}, …, a_{d}} of real numbers is called log-concave if a_{i−1}a_{i+1} ⩽ a_{i}^{2} for i = 1, 2, …, d − 1. It is unimodal if there exists an index 0 ⩽ j ⩽ d such that a_{i} ⩽ a_{i+1} for i = 0, 1, …, j − 1 and a_{i} ⩾ a_{i+1} for i = j, j + 1, …, d − 1. It has no internal zeros if there are not three indices 0 ⩽ i < j < k ⩽ d such that a_{i}, a_{k} ≠ 0 but a_{j} = 0. It is symmetric if a_{i} = a_{d−i} for i = 0, …, ⌊d/2⌋. It is a Pólya frequency sequence of order r (or a PF_{r} sequence) if any minor of order r of the matrix M = (M_{ij})_{i,j∈ℕ} defined by M_{ij} = a_{j−i} for all i, j ∈ ℕ (where a_{k} = 0 if k < 0 or k > d) is non-negative. It is a Pólya frequency sequence of infinite order (or a PF sequence) if it is a PF_{r} sequence for all r ⩾ 1.

It is clear that a positive sequence is PF_{1}, and a log-concave (which is also unimodal and internal-zero free) sequence is PF_{2}.

A polynomial ∑_{i=0}^{d} a_{i}x^{i} is symmetric (respectively, unimodal, log-concave, with no internal zeros) if the sequence {a_{0}, a_{1}, …, a_{d}} has the corresponding property. If p(x) is a symmetric unimodal polynomial, then its center of symmetry C(p) = (deg(p) + mult(0, p))/2, where mult(0, p) is the multiplicity of 0 as a zero of p. If we write p(x) = x^{n}p(x^{−1}), then C(p) = n/2. An elementary property of symmetric unimodal polynomials is the following. See, e.g., [4, Proposition 2.1] and [12, Proposition 1].

Proposition 4.2. Let p(x) and q(x) be two symmetric unimodal polynomials. Then p(x)q(x) is a symmetric unimodal polynomial and C(pq) = C(p) + C(q).

An important classical result concerning PF sequences and polynomials having only real zeros is the following [2, Theorem 2.2.4].

Theorem 4.3 (Aissen–Schoenberg–Whitney). Let p(x) = ∑_{i=0}^{d} a_{i}x^{i} ∈ ℝ[x] have non-negative coefficients. Then p(x) has only real zeros if and only if {a_{0}, a_{1}, …, a_{d}} is a PF sequence.

Corollary 4.4. For each multiset n = {1^{n_{1}}, 2^{n_{2}}, …, m^{n_{m}}}, the sequence

{Θ(n, k)}_{k=N(n),...,n−N(n)}

is a PF sequence, where N(n) := max_{1⩽i⩽m} n_{i}. In particular, it is unimodal and log-concave.

Proof. Combine Theorem 4.1 and Theorem 4.3 to conclude. □

5. A combinatorial expansion

We give in this section an expansion formula of d_{n}(x). See Proposition 5.1 below.

By virtue of Property 2.1(iii), we may write

(11)  ∑_{n_{1},...,n_{m}⩾0}d_{n}(x)x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}} = 1 + ∑_{1⩽l(n)⩽m} d_{n}(x)m_{μ(n)},

where the sum on the right ranges over all multisets n = {1^{n_{1}}, 2^{n_{2}}, …, m^{n_{m}}} such that n_{1} ⩾ n_{2} ⩾ ⋯ ⩾ n_{m} ⩾ 0, μ(n) = (n_{1}, n_{2}, …, n_{m}), l(n) = #{i ∈ [m]: n_{i} > 0} (which is the number of positive parts of μ(n)) and m_{μ} = m_{μ}(x_{1}, x_{2}, …, x_{m}) is the monomial symmetric function in x_{1}, x_{2}, …, x_{m} indexed by μ.

Combining (2) and (11), we have the following symmetric function identity

1 + ∑_{1⩽l(n)⩽m} d_{n}(x)m_{μ(n)} = \frac{1}{1 − xe_{2} − (x + x^{2})e_{3} − ⋯ − (x + x^{2} + ⋯ + x^{m−1})e_{m}}

in Λ_{ℤ[x]}(x_{1}, …, x_{m}), the ring of symmetric functions in x_{1}, …, x_{m} over ℤ[x].

Proposition 5.1. We have

(12)  d_{n}(x) = ∑_{\begin{matrix}k_{1}+···+k_{l}=n \\ 2⩽k_{1},...,k_{l}⩽m \end{matrix}} M_{(k_{1},...,k_{l}),μ(n)} ∏_{j=1}^{l}(x + x^{2} + ⋯ + x^{k_{j}−1}),

where the sum ranges over all compositions (k_{1}, …, k_{l}) of n such that 2 ⩽ k_{1}, …, k_{l} ⩽ m.

Proof. Comparing (11) and (4), and invoking the linear independence of m_{μ}. □

The identity (12) is a combinatorial expansion of d_{n}(x) in terms of the polynomials ∏_{j=1}^{l}(x + x^{2} + ⋯ + x^{k_{j}−1}) each of which is symmetric unimodal and has center of symmetry at ∑_{j=1}^{l} k_{j}/2 = n/2 by Proposition 4.2, thus refining Proposition 2.3 and Corollary 4.4.

On the other hand, (12) is a multi-analogue of the one [3, Proposition 6] for d_{n}(x), namely,

(13)  d_{n}(x) = ∑_{λ⊢n} f^{λ}R_{λ}(x),

where

(14)  R_{λ}(x) = ∑_{\begin{matrix}k_{1}+···+k_{l}=n \\ 2⩽k_{1},...,k_{l}⩽n \end{matrix}} K_{λ,(k_{1},...,k_{l})} ∏_{j=1}^{l}(x + x^{2} + ⋯ + x^{k_{j}−1}),

f^{λ} is the number of standard Young tableaux of shape λ and K_{λ,μ} is a Kostka number. The identity (14) is obtained by expanding [3, eqn (6)], that is,

∑_{λ} R_{λ}(x)s_{λ} = \frac{1}{1 − ∑_{k⩾2}(x + x^{2} + ⋯ + x^{k−1})s_{k}} ,

where s_{k} and s_{λ} are Schur functions indexed, respectively, by the partitions (k) and λ. A combinatorial proof of (13) and (14) had been given by Stembridge in [14, p. 319].

Similar expansions of the generating function for multiderangements by the numbers of cycles and excedances has already been given by Zeng [15, Eq. (2.14)].

6. Extension to multipermutations

Let n = {1^{n_{1}}, 2^{n_{2}}, …, m^{n_{m}}} be a multiset, where n := n_{1} + ⋯ + n_{m}. Denote by ℛ(n) the set of all multipermutations of n. Let w = w_{1}w_{2} ⋯ w_{n} ∈ ℛ(n) and δ(w) = p_{1}p_{2} ⋯ p_{n} be its non-decreasing rearrangement. Denote by f(w) := #{i ∈ [n]: w_{i} = p_{i}} the number of fixed points of w, and define

r_{n}(x, Y) = ∑_{w∈ℛ(n)} x^{e(w)}Y^{f(w)}.

The identity (2) can be extended to count multipermutations by the numbers of excedances and fixed points by using the classical MacMahon Master Theorem [9, pp. 97– 98], which states that the coefficient of x_{1}^{k_{1}}x_{2}^{k_{2}} ⋯ x_{n}^{k_{n}} in the expansion of 1/V_{n} is the same as the coefficient of the same term in (a(1, 1)x_{1} + ⋯ + a(1, n)x_{n})^{k_{1}} ⋯ (a(n, 1)x_{1} + ⋯ + a(n, n)x_{n})^{k_{n}}, where V_{n} = det(δ_{i,j} − a(i, j)x_{j}).

Theorem 6.1. We have (15)

∑_{n_{1},...,n_{m}⩾0}r_{n}(x, Y)x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}} = {[1 − ∑_{k=2}^{m}(x + x^{2} + ⋯ + x^{k−1})e′_{k}] ∑_{0⩽k⩽m}(−1)^{k}e_{k}Y^{k}}^{−1},

where x, Y, x_{1}, …, x_{m} are commuting indeterminates and e_{k} and e′_{k} (1 ⩽ k ⩽ m) are the kth elementary symmetric function in x_{1}, …, x_{m} and in \frac{x_{1}}{1−Y x_{1}} , …, \frac{x_{m}}{1−Y x_{m}} , respectively.

Proof. For i, j = 1, 2, …, m, let

a(i, j) = \begin{cases}x & if i < j, \\ Y & if i = j, \\ 1 & if i > j. \end{cases}

Each w = w_{1} ⋯ w_{n} ∈ ℛ(n) is assigned the weight

x^{e(w)}Y^{f(w)} = ∏_{i=1}^{n} a(p_{i}, w_{i}),

where δ(w) = p_{1} ⋯ p_{n}. The MacMahon Master Theorem then yields that

∑_{n_{1},...,n_{m}⩾0}r_{n}(x, Y)x_{1}^{n_{1}} ⋯ x_{m}^{n_{m}} = V_{m}^{−1},

where the determinant of MacMahon V_{m} is given by

V_{m} = det(δ_{i,j} − a(i, j)x_{j})

= |\begin{matrix}1 − Y x_{1} & −xx_{2} & ⋯ & −xx_{m} \\ −x_{1} & 1 − Y x_{2} & ⋯ & −xx_{m} \\ ⋮ & ⋮ & ... & ⋮ \\ −x_{1} & −x_{2} & ⋯ & 1 − Y x_{m} \end{matrix}|

= (−1)^{m}x_{1} ⋯ x_{m} |\begin{matrix}−(\frac{x_{1}}{1−Y x_{1}} )^{−1} & x & ⋯ & x \\ 1 & −(\frac{x_{2}}{1−Y x_{2}} )^{−1} & ⋯ & x \\ ⋮ & ⋮ & ... & ⋮ \\ 1 & 1 & ⋯ & −(\frac{x_{m}}{1−Y x_{m}})^{−1} \end{matrix}|

= (−1)^{m} ∏_{i=1}^{m}(\frac{x_{i}}{1 − Y x_{i}}) |\begin{matrix}−(\frac{x_{1}}{1−Y x_{1}} )^{−1} & x & ⋯ & x \\ 1 & −(\frac{x_{2}}{1−Y x_{2}} )^{−1} & ⋯ & x \\ ⋮ & ⋮ & ... & ⋮ \\ 1 & 1 & ⋯ & −(\frac{x_{m}}{1−Y x_{m}})^{−1} \end{matrix}|

× ∏_{i=1}^{m}(1 − Y x_{i})

= [1 − ∑_{k=2}^{m}(x + x^{2} + ⋯ + x^{k−1})e′_{k}] ∑_{k=0}^{m}(−1)^{k}e_{k}Y^{k},

where the last equality follows from [10, p. 441]. □

7. Concluding remarks

We have considered in this work certain important properties, namely, the invariance under permutations of {n_{1}, …, n_{m}}, symmetry, recurrence relations and real-rootedness of the generating function d_{n}(x) of multiderangements by the number of excedances. Extension to multipermutations by the numbers of excedances and fixed points is also given. Those properties presented help make the theory of multiderangements more parallel to its classical counterparts.

8. Acknowledgements

The author thanks the anonymous referee for helpful suggestions.

References

[1] R. Askey and M. Ismail, Permutation problems and special functions, Canad. J. Math. 28 (1976) 853–874.

[2] F. Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc. 81 (1989), no. 413.

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

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

[5] C.-O. Chow, On derangement polynomials of type B. II, submitted, 2007.

[6] P. Cartier and D. Foata, Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Mathematics, vol. 85, Springer-Verlag, Berlin, 1969.

[7] D. Foata, Rearrangements of words, in: Combinatorics on Words, M. Lothaire, ed., 184–212, Addison-Wesley, Reading, Massachusetts, 1983.

[8] D.S. Kim and J. Zeng, A new decomposition of derangements, J. Combin. Theory Ser. A 96 (2001) 192–198.

[9] P.A. MacMahon, Combinatory Analysis, vol. 1, Chelsea, 1960.

[10] T. Muir, A Treatise on the Theory of Determinants, Longmans, London, 1933; reprinted: Dover, New York, 1960.

[11] R. Simion, A multi-indexed Sturm sequence of polynomials and unimodality of certain combinatorial sequences, J. Combin. Theory Ser. A 36 (1984) 15–22.

[12] R.P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Ann. New York Acad. Sci. 576 (1989) 500–535.

[13] R.P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.

[14] J.R. Stembridge, Eulerian numbers, tableaux, and the Betti numbers of a toric variety, Discrete Math. 99 (1992) 307–320.

[15] J. Zeng, Linéarisation de produits de polynômes de Meixner, Krawtchouk et Charlier, SIAM J. Math. Anal. 21 (1990) 1349–1368.

[16] X. Zhang, On q-derangement polynomials, in: Combinatorics and Graph Theory ’95, vol. 1 (Hefei), 462–465, World Sci. Publishing, River Edge, NJ, 1995.

[17] X. Zhang, On a kind of sequence of polynomials, in: Computing and Combinatorics (Xi’an, 1995), 379–383, Lecture Notes in Computer Science, vol. 959, Springer, Berlin, 1995.

P.O. Box 91100, Tsimshatsui Post Office, Hong Kong

E-mail address: cchow@alum.mit.edu