On Permutation Weights and q-Eulerian Polynomials

c 2020 Springer Nature Switzerland AG Published online June 6, 2020

https://doi.org/10.1007/s00026-020-00493-5 Annals of Combinatorics

On Permutation Weights and q -Eulerian Polynomials

Aman Agrawal, Caroline Choi and Nathan Sun

Abstract.Weights of permutations were originally introduced by Dugan et al. (Journal of Combinatorial Theory, Series A164:24–49, 2019) in their study of the combinatorics of tiered trees. Given a permutationσviewed as a sequence of integers, computing the weight ofσinvolves recursively counting descents of certain subpermutations ofσ. Using this weight func- tion, one can define aq-analogEn(x, q) of the Eulerian polynomials. We prove two main results regarding weights of permutations and the poly- nomialsEn(x, q). First, we show that the coefficients ofEn(x, q) stabilize asngoes to infinity, which was conjectured by Dugan et al. (Journal of Combinatorial Theory, Series A164:24–49, 2019), and enables the defini- tion of the formal power seriesWd(t), which has interesting combinatorial properties. Second, we derive a recurrence relation forEn(x, q), similar to the known recurrence for the classical Eulerian polynomials An(x).

Finally, we give a recursive formula for the numbers of certain integer partitions and, from this, conjecture a recursive formula for the stabilized coefficients mentioned above.

Mathematics Subject Classification.Primary: 05A05; Secondary: 05A30.

Keywords.q-Eulerian polynomials, Eulerian polynomials, permutations.

1. Introduction

Dugan et al. defined certain weights of permutations in their work on the combinatorics of tiered trees [2]. Tiered trees are a generalization of maxmin trees, which were originally introduced by Postnikov [8] and appear in the study of local binary search trees [4], hypergeometric functions [5], and hyper- plane arrangements [9,13]. In [2], Dugan et al. defined weight for tiered trees, motivated by their role in the enumerations of absolutely irreducible represen- tations of certain quivers and torus orbits on certain homogeneous varieties [6]. They showed that weight 0 maxmin trees are in natural bijection with per- mutations. They defined the weight of a permutationσ as the largest weight

of a maxmin tree that can be constructed fromσ. Computing the weight ofσ involves recursively counting descents of certain subpermutations ofσ.

Using the weight of a permutation, a newq-analog of the Eulerian poly- nomialsEn(x, q) was defined in [2]. Theq-Eulerian polynomialEn(x, q) differs from other q-Eulerian polynomials by Carlitz [1], Foata-Sch¨utzenberger [3], Stanley [12], and Shareshian-Wachs [10], and presents interesting combinato- rial properties. It was observed in [2] that the coefficients ofEn(x, q) seemed to exhibit a certain stabilization phenomenon. From this conjecture, the formal power series Wd(t) was extracted fromEn(x, q) and observed to have a con- nection with enumerations of a certain type of partitionT(n, k),see sequence A256193 in [11].

We present two main results regarding permutation weights and theq- Eulerian polynomialsEn(x, q). We prove the stabilization phenomenon conjec- tured in [2], which gives an explicit formula for the formal power series Wd(t) defined in [2]. We derive a recurrence relation for theq-Eulerian polynomials En(x, q), similar to the known recurrence for the classical Eulerian polynomials An(x).

This paper is organized as follows. In Sect. 2, we introduce preliminary definitions and notation. In Sect. 3, we define the weight disparity of a per- mutation and find a lower bound for weight disparity. We then use this result to show that the coefficients ofx^d in the formal power seriesWd(t) do indeed stabilize. In Sect. 4, we derive a recurrence relation for En(x, q). In Sect. 5, we determine the conditions for which coefficients of En(x, q) are stabilized and give a second proof of the stabilization phenomenon. We conclude with a conjecture regarding the coefficients ofWd(t) in Sect.6.

2. Preliminaries

LetSn denote the set of permutations of [n] ={1,2, . . . , n}. We consider the permutation σ ∈ Sn as an ordered sequence of integers a1a2. . . an. We say thatσ∈Sn is a permutation of lengthn. We say thati∈[n−1] is a descent ofσifai> ai+1, and we write des(σ) to denote the number of descents inσ. The definitions in this section follow from [2].

Definition 2.1. Given a permutation σ=a1a2· · ·an, we define a method for splittingσinto certain subpermutationsσ1, σ2, . . . , σj.

(i) Find the minimum element ofσ, call itam. Divideσinto subpermutations σ,am, andσr, whereσ=a1a2· · ·am−1andσr=am+1am+2· · ·an. We haveσ=σ· am ·σr.

(ii) Find the largest element of σ, call it ak. Letσ1 =a1a2· · ·ak and let σ2 =ak+1ak+2· · ·am−1. We haveσ=σ1 ·σ2 · am ·σr.

(iii) Repeat step (ii) for σ2 until σ cannot be divided further. This process results in a collection of subpermutationsσ1, σ2, . . . , σs, σr.

Example 2.1. We split the permutation σ= 839562147.

By step (i), we have 839562·1·47.

By step (ii), we have 839·562·1·47.

By step (iii), we have 839·56·2·1·47.

Sinceσcannot be split further, we are done.

Definition 2.2. Letσ∈Sn. Then theweightofσis the functionw:Sn →Z^≥0 defined recursively as follows:

(i) If σis the identity permutation orn= 1, thenw(σ) = 0.

(ii) Otherwise, consider σ as a permutation of Sn+1 by appending n+ 1 to the right ofσ. Letσ1, σ2, . . . , σj be the subpermutations of this new permutation as in Definition2.1. Then the weight ofσis defined as

w(σ) = j

i=1

(des(σi) +w(σi)).

Example 2.2. Consider the permutationσ= 781659243∈S9. We complete σ to 781659243Aby adding a maximal element A to the end. After splitting, we have 78·1·659243A. The weight ofσis given by

w(σ) = (w(78) + des(78)) + (w(1) + des(1)) + (w(659243A) + des(659243A)). We computew(σ) as follows:

• Since the permutation 1 is of length 1, we havew(1) = 0 and des(1) = 0.

• It is clear that thatw(78) = 0 and des(78) = 0.

• If we consider the numbers in the permutation 659243Arelative to each other, we can see that 659243Aflattens to the permutation 5461327. We complete the permutation to 54613278 and split to get 546·1·3278. So the weight of 659243A is given byw(659243A) = (w(546) + des(546)) + (w(1) + des(1)) + (w(3278) + des(3278)). A quick computation shows that w(546) = 0 andw(3278) = 0, so we havew(65392) = (0 + 1) + (0 + 0) + (0 + 1) = 2.

Thusw(σ) = (0 + 0) + (0 + 0) + (2 + 3) = 5.

Definition 2.3. TheEulerian polynomialAn(x) is defined as An(x) =

σ∈Sn

x^des(σ).

The coefficient ofx^min An(x) count the permutations inSn withmdescents and are theEulerian numbers, denotedA(n, m).

Using the permutation statistic of weight, a new generalization of the Eulerian polynomialsEn(x, q) was defined in [2].

Definition 2.4. Theq-Eulerian polynomialEn(x, q) is defined as En(x, q) =

σ∈Sn

x^des(σ)q^w(σ).

Example 2.3. We list the q-Eulerian polynomialsEn(x, q) up ton= 7:

E0(x, q) = 1 E1(x, q) = 1 E2(x, q) = 1 +x

E3(x, q) = 1 +x(q+ 3) +x²

E4(x, q) = 1 +x(q²+ 3q+ 7) +x²(q²+ 4q+ 6) +x³

E5(x, q) = 1 +x(q³+ 3q²+ 7q+ 15) +x²(q⁴+ 4q³+ 11q²+ 25q+ 25) +x³(q³+ 5q²+ 10q+ 10) +x⁴

E6(x, q) = 1 +x(q⁴+ 3q³+ 7q²+ 15q+ 31)

+x²(q⁶+ 4q⁵+ 11q⁴+ 31q³+ 58q²+ 107q+ 90) +x³(q⁶+ 5q⁵+ 16q⁴+ 34q³+ 76q²+ 105q+ 65) +x⁴(q⁴+ 6q³+ 15q²+ 20q+ 15) +x⁵

E7(x, q) = 1 +x(q⁵+ 3q⁴+ 7q³+ 15q²+ 31q+ 63) +x²(q⁸+ 4q⁷+ 11q⁶+ 31q⁵+ 65q⁴ + 149q³+ 237q²+ 392q+ 301) +x³(q⁹ + 5q⁸+ 16q⁷+ 41q⁶+ 104q⁵+ 203q⁴+ 380q³ + 609q²+ 707q+ 350)

+x⁴(q⁸+ 6q⁷+ 22q⁶+ 55q⁵+ 106q⁴+ 210q³+ 336q²+ 315q+ 140) +x⁵(q⁵+ 7q⁴+ 21q³+ 35q²+ 35q+ 21) +x⁶

3. Proof of Stabilization Phenomenon

Let us fixkand consider the coefficients ofx^k inEn(x, q). It was conjectured in [2] that asngoes to infinity, these coefficients converge to a fixed sequence and thus display a stabilization phenomenon. Observe that fork = 2 in Ex- ample2.3, the coefficients ofx² seem to stabilize to

q^N + 4q^N−1+ 11q^N−2+ 31q^N−3+ 65q^N−4+· · ·

whereN is the maximum weight of a permutation of lengthnwith 2 descents.

Using this conjectural observation, the formal power seriesWd(t)∈Z[[t]] was extracted in [2] and observed to have interesting combinatorial properties.

In this section, we prove the stabilization phenomenon conjectured in [2].

We first define the weight disparity of a permutation and find a lower bound for weight disparity in Theorem3.4. We then use this bound to prove Theorem3.6.

We thus give an explicit formula for the formal power seriesWd(t), enabling the study of certain combinatorial properties in the coefficients ofWd(t).

Definition 3.1. We denote the maximum weight of a permutation of lengthn withddescents by maxwt(n, d).

It was shown in [2] that the maximum weight of such a permutation is d(n−d−1).

The following lemma follows directly from the proof of Theorem 6.10 in [2]. A permutation that ends in 1 is of maximum weight when its subpermu- tation πL is a single component, in which case w(σ) = des(πL) +w(πL) ≤ (d−1)(n−d−1).

Lemma 3.2. Let σ ∈ Sn be a permutation with d descents. If we fix the last number inσ to be1, then maxwt(σ) = (d−1)(n−d−1).

Definition 3.3. Let σ ∈Sn be a permutation with d descents. We define the weight disparityΔ(σ) ofσas Δ(σ) = maxwt(n, d)−w(σ).

We now prove a lower bound for weight disparity, Δ(σ).

Theorem 3.4. Let σ∈Sn be a permutation withddescents. Ifσdoes not start with1, thenΔ(σ)≥n−d−1.

Letσ∈Sn be a permutation withddescents such thatσ=πL·1·πR, where the subpermutationπL is nonempty. We have two cases:

(i) The subpermutationπR is empty. Thenσ=πL·1, and by Lemma 3.1, we havew(σ)≤(d−1)(n−d−1) so Δ(σ)≥n−d−1.

(ii) The subpermutation πR is nonempty. Then σ=πL·1·πR. LetπL be a permutation onnumbers with des(πL) =q. We haveπR∈Sn−−1 and des(πR) =d−q−1. We proceed to boundw(σ). Computing the weight ofσ, we have

w(σ) =w(πL·1) +w(πR) + des(πR), which implies

w(σ)≤q(−q−1) + (d−q−1)(n−−d+q).

Since des(πR) = d−q−1 ≥ 0 and des(πL) =q < , we have (q−d+ 1)(−q−1)≤0. Similarly, we havedes(πR) =d−q−1< n−−1 and soq(−n++d−q)≤0. Combining these two inequalities, we get

(q−d+ 1)(−q−1) +q(−n++d−q)≤0. (3.1) Adding (d−1)(n−d−1) to (3.1) and substituting forw(σ), we obtain

w(σ)≤(d−1)(n−d−1), or equivalently,

Δ(σ)≥n−d−1.

Definition 3.5. We denote the coefficient of x^d inEn(x, q) byEn[x^d] and the coefficient ofx^dq^min En(x, q) byEn[x^dq^m].

We now show that the coefficients ofEn[x^d] display a stabilization phe- nomenon.

Theorem 3.6. For all k, d, m ∈ N such that m =d+k+ 1 and n ≥m, the value ofEn[x^dqmaxwt(n,d)−k] is independent ofn.

Proof. We show that for sufficiently large n, the number of permutations of lengthnwith a given weight disparity is constant. Letσ∈Sm+1 be such that m=d+k+ 1 fork, m, d∈N. We determine the form of the permutationsσ counted byEm+1[x^dqmaxwt(m+1,d)−k]. We have the following cases:

(i) Suppose σ is of the form 1 ·π, where π ∈ Sm and des(π) = d and w(π) = maxwt(m, d)−k= (d−1)(m−d−1). Then we have

w(σ) =w(π) +d= maxwt(m+ 1, d)−k.

Soσis counted byEm+1[x^dqmaxwt(m+1,d)−k]. Note that removing 1 from the beginning ofσand and subtracting 1 from every element is a bijection that gives us permutationsπ∈Smwithddescents and of weight equal to w(π) = maxwt(m, d)−k. Soσis also counted byEm[x^dq^{maxwt(m,d)−k}].

(ii) Supposeσis of the form 1·π, where des(π)=dorw(π)=d(m−d−1)−k. It is easy to see thatσis not counted byEm+1[x^dqmaxwt(m+1,d)−k].

(iii) Suppose σ does not start with 1. Let p = des(σ). By Theorem3.4, we have Δ(σ)≥m−des(σ), which implies the following:

maxwt(m+ 1, p)−w(σ) +p≥m⇒

maxwt(m+ 1, p)−w(σ) +p > m−1 =d+k⇒

p−w(σ)> d−(maxwt(m+ 1, p)−k).

So eitherp=dor w(σ)= maxwt(m+ 1, p)−k. Thusσ is not counted byEm+1[x^dqmaxwt(m+1,d)−k].

Since the number of permutations with weight disparitykandddescents inSm+1 is the same as those inSm, we have

Em[x^dq^{maxwt(m,d)−k}] =Em+1[x^dqmaxwt(m+1,d)−k]. It is easy to see that, by induction, the above argument shows that

Em+i[x^dqmaxwt(m+i,d)−k] =Em+i+1[x^dqmaxwt(m+i+1,d)−k]

for anyi≥0.

Theorem3.6shows that the formal power seriesWd(t) defined in [2] exists and is given byWd(t^k) =Ed+k+1[x^dq^(d−1)k]. We can now extractWd(t) from the stabilized coefficients ofEn(x, q).

Definition 3.7. IfEn[x^d] stabilizes toq^N+a1q^N−1+a2q^N−2+a3q^N−3+· · ·, whereN =d(n−d−1), then the formal power seriesWd(t) is defined in [2]

as

Wd(t) = 1 +a1t+a2t²+a3t³+· · ·

Example 3.1. By Theorem 3.6 and our data for the q-Eulerian polynomials, we have

W1(t) = 1 + 3t+ 7t²+ 15t³+ 31t⁴+ 63t⁵+· · · W2(t) = 1 + 4t+ 11t²+ 31t³+ 65t⁴+ 157t⁵+· · · W3(t) = 1 + 5t+ 16t²+ 41t³+ 112t⁴+ 244t⁵+· · · W4(t) = 1 + 6t+ 22t²+ 63t³+ 155t⁴+ 393t⁵+· · · W5(t) = 1 + 7t+ 29t²+ 92t³+ 247t⁴+ 590t⁵+· · ·

4. A Recurrence Relation for E

(x, q)

The classical Eulerian polynomialsAn(x) in Definition2.3enumerate permu- tations according to their number of descents. The Eulerian polynomialsAn(x) satisfy the following recurrence forn≥1:

A0(x) = 1, An(x) =

n−1 i=1

n−1 i

Ai(x)·An−i−1(x)·x.

We now derive a recurrence relation for theq-Eulerian polynomialsEn(x, q), similar to the recurrence forAn(x).

Theorem 4.1. The q-Eulerian polynomials En(x, q) satisfy the recurrence re- lation

E0(qx, q) = 1, En(x, q) =

n−1

i=1

n−1 i

Ei(x, q)·En−i−1(qx, q)·x+En−1(qx, q). We introduce the following definitions and lemmas used in the proof of Theorem4.1.

Definition 4.2. We defineS_n to be the set of all permutations inSn ending in 1. That is,S_n ={σ∈Sn|σ=π·1,whereπ∈Sn−1}.

Lemma 4.3. There exists a bijectionf :Sn↔S_n+1 such that, for all σ∈Sn, w(f(σ)) =w(σ)anddes(f(σ)) = des(σ) + 1.

Proof. We first show that there exists a functionf :Sn→S_n+1 that preserves weight and increases number of descents by 1. Let π∈Sn be such that π= πL·1·πR, where the subpermutationsπLandπRcan be empty. Consider the functionf :Sn→Sn+1 defined by

f(π) =f(πL·1·πR) =πR·(n+ 1)·πL·1.

That is, f replaces 1 with the maximum element (n+ 1), exchanges πL and πR, and appends a minimum element 1 at the end. Notice that for anyπ∈Sn,

we havef(π)∈S_n+1 and des(f(π)) = des(π) + 1. The weight off(π) is given by

w(f(π)) =w(πL·1) +w(πR) + des(πR),

sow(f(π)) =w(π). Sof preserves weight and increases the number of descents by 1.

Nowf is clearly invertible as (n+ 1) and 1 inf(π) uniquely determineπL

andπR. Moreover,f is a bijection as Sn andS_n+1 are equinumerous, where its inversef⁻¹ must preserve weight and reduce the number of descents by 1.

Definition 4.4. We writeE_n^∗(x, q) to denote theq-Eulerian polynomial

σ∈S_n

x^des(σ)q^w(σ).

The following corollary is a direct result of Lemma4.3.

Corollary 4.5. We have

xEn(x, q) =E_n+1^∗ (x, q). (4.1) Lemma 4.6. The q-Eulerian polynomials En(x, q) satisfy the recurrence rela- tion

En[x^d] =

n−1 i=1

n−1 i

ⁱ

k=1

En−i−1[x^d−k]·Ei[x^k−1]·q^d−k

+En−1[x^d]q^d. Letσ∈Sn be a permutation withddescents. We have two cases:

Case 1.Supposeσ= 1·π1for someπ1∈Sn−1. We havew(σ) =w(π1)+d. So the number of permutationsσ∈Sn with ddescents and of weight w(σ) is equal to the number of permutationsπ1∈Sn−1withddescents and of weight w(π1) +d. This is counted byEn−1[x^d]q^d.

Case 2. Supposeσ = πL·1·πR, where 1 is in position i+ 1 of σ and 1 ≤ i ≤ n−1. It is clear that πL ∈ Si and πR ∈ Sn−i−1. There are _n−1

i

ways to select the i elements in the subpermutation πL. Let k = des(πL · 1), where 1 ≤ k ≤ i. Then we have des(πR) = d−k and w(σ) = w(πL · 1) +w(πR) + des(πR). The permutations πL·1 are counted byE_i+1^∗ [x^k], and the permutationsπR are counted byEn−1−i[x^d−k]. We know thatEn[x^dq^w]· Em[x^eq^v] counts permutations of lengthn+mwithd+edescents and of weight w+v. Thus permutations of lengthnwithddescents and of weightw(πL·1) + w(πR) are counted byE_i+1^∗ [x^k]·En−1−i[x^d−k].We add des(πR) =d−kto the weight of these permutations to count permutations of weightw(σ), length n, andddescents. Multiplying by q^d−k, we have q^d−k·E_i+1^∗ [x^k]·En−1−i[x^d−k]. Thus the permutationsσare counted by

n−1

i=1

n−1 i

_i

k=1

E_i+1^∗ [x^k]·En−1−i[x^d−k]q^d−k,

which by Corollary4.5is equal to

n−1

i=1

n−1 i

i k=1

Ei[x^k−1]·En−1−i[x^d−k]q^d−k. Combining Case 1 and Case 2, we have

En[x^d] =

n−1

i=1

n−1 i

ⁱ

k=1

Ei[x^k−1]·En−1−i[x^d−k]q^d−k

+En−1[x^d]q^d.

Proof of Theorem4.1. From Lemma4.6, we have En(x, q) =

n−1

d=0

x^{d n−1}

i=1

n−1 i

ⁱ

k=1

En−i−1[x^d−k]·Ei[x^k−1]·q^d−k +En−1[x^d]q^d

.

If we distribute the first summation and let=d−k, we get En(x, q) =

n−1

i=1

n−1 i

ⁱ

k=1

ⁿ⁻¹⁻ⁱ

=0

En−i−1[x]·q·Ei[x^k−1]·x^+k

+

n−1 j=0

En−1[x^j]q^jx^j. We can rearrange terms to get

En(x, q) =

n−1 i=1

n−1 i

ⁱ

k=1

Ei[x^k−1]x^k−1

ⁿ⁻ⁱ⁻¹

=0

En−i−1[x]·qx ·x

+

n−1

j=0

En−1[x^j]q^jx^j.

Substituting the correspondingq-Eulerian polynomials, we have En(x, q) =

n−1

i=1

n−1 i

Ei(x, q)·En−i−1(qx, q)·x+En−1(qx, q). Remark 4.7. We compare our recurrence relation forEn(x, q) with other re- currences in the literature. Note that if we setq= 1, Theorem4.1becomes the recurrence for the classical Eulerian polynomialsAn(x). Since there are type B and D Eulerian polynomials that satisfy recurrence relations analogous to the recurrence for the polynomials An(x) [7], there may also be other q-analogs like the one we study.

Finally, we note that the recurrence relation in Theorem4.1 resembles the recurrence derived by Postnikov for the polynomialsfn(x), given by

fn(x) =x ⁿ⁻¹

=1

n−1

·f(x)fn−−1(x) +fn−1(x)

,

where fn(x) = _kfnkx^k and fnk denotes the number of all maxmin trees on the set [n+ 1] withkmaxima [8]. Given that weight 0 maxmin trees are in bijection with permutations [2], it would be interesting to explore this connection between all maxmin trees and permutations further.

Using Lemma4.6 and Theorem4.1, we give a recursive formula for the coefficients ofEn(x, q).

Corollary 4.8. The coefficients of the q-Eulerian polynomials En(x, q)satisfy the recurrence relation

En[x^dq^m] =

n−1

i=1

n−1 i

ⁱ

k=1

^m

j=0

En−i−1[x^d−kq^m−j]·Ei[x^k−1q^k+j−d]

+En−1[x^dq^m−d].

Proof. Since by Lemma4.6, we have En[x^d] =

n−1

i=1

n−1 i

i k=1

Ei[x^k−1]·En−1−i[x^d−k]q^d−k+En−1[x^d]q^d, we can piece together min En[x^dq^m] by introducing a third summation and

iterating through all possibilities.

5. Alternate Proof of the Stabilization Phenomenon

Using our recursive formula for the coefficients of En(x, q) in Corollary 4.8, we determine a lower bound for the exponent ofq such that the coefficients En[x^dq^w] are stabilized in Theorem5.1. We then use this result to give a second proof of Theorem3.6.

Theorem 5.1. If m >(d−1)(n−d−1) for0< d < n−1, then En[x^dq^m] =En−1[x^dq^m−d].

Proof. By Corollary4.8, we have En[x^dq^m] =En−1[x^dq^m−d]

+

n−1

i=1

n−1 i

ⁱ

k=1

^m

j=0

En−i−1[x^d−kq^m−j]·Ei[x^k−1q^k+j−d]

. (5.1) For fixed i and k, we show that for all j, we have En−i−1[x^d−kq^m−j] · Ei[x^k−1q^k+j−d] = 0. We consider the following two cases:

Case 1. Supposem= (d−1)(n−d−1) +ufor some u∈N. We show thatEn[x^dq^m] =En−1[x^dq^m−d]. Note thatm−d≥0 since 0< d < n−1. By Corollary4.8, we have

En[x^dq^{(d−1)(n−d−1)+u}] =En−1[x^dq^{(d−1)(n−d−1)+u−d}] +

n−1

i=1

n−1 i

ⁱ

k=1

(d−1)(n−d−1)+u

j=0

En−i−1[x^d−kq^{(d−1)(n−d−1)+u−j}]

·Ei[x^k−1q^k+j−d]

. (5.2)

The weight of a permutation of length n with d descents is bounded by maxwt(n, d) = d(n−d−1). So from the coefficients Ei[x^k−1q^k+j−d] and En−i−1[x^d−kq(d−1)(n−d−1)+u−j], we have the following inequalities:

(d−1)(n−d−1) + 1 +u−j ≤(d−k)(n−i−1−d+k−1) (5.3) k+j−d≤(k−1)(i−k). (5.4) Analyzing the terms and summation bounds in (5.2) gives 1 ≤k≤d, k ≤i and n−i−1 ≥d−k−1. A straightforward computation shows that these summation bounds and (5.3) and (5.4) contradict each other. Thus for all j, we haveEn−i−1[x^d−kq^m−j]·Ei[x^k−1q^k+j−d] = 0 and

n−1

i=1

n−1 i

ⁱ

k=1

(d−1)(n−d−1)+u

j=0

En−i−1[x^d−kq^{(d−1)(n−d−1)+u−j}]

·Ei[x^k−1q^k+j−d]

= 0. SoEn[x^dq^m] =En−1[x^dq^m−d].

Case 2.Supposem= (d−1)(n−d−1)−vfor some integerv≥0. Using the same reasoning as in Case 1, we have the following inequalities:

(d−1)(n−d−1)−j−v≤(d−k)(n−1−i−d+k−1) (5.5)

k+j−d≤(k−1)(i−k) (5.6)

A straightforward computation shows that there existjthat satisfy both (5.5) and (5.6). Thus we have

n−1

i=1

n−1 i

ⁱ

k=1

(d−1)(n−d−1)−v

j=0

En−i−1[x^d−kq^{(d−1)(n−d−1)−v−j}]

·Ei[x^k−1q^k+j−d] = 0.

SoEn[x^dq^m]=En−1[x^dq^m−d].

Using Theorem5.1, we give an alternate proof of Theorem3.6.

Proof of Theorem3.6. By Theorem5.1, we haveEn[x^dq^m] =En−1[x^dq^m−d] if m >(d−1)(n−d−1), where 0< d < n−1. Furthermore,En[x^dq^m] is stabilized whenm >(d−1)(n−d−1) and is not stabilized whenm≤(d−1)(n−d−1).

It is easy to show thatEn[x⁰q⁰] is stabilized andEn[xⁿ⁻¹q⁰] is not.

6. Connection Between W

(t) and Integer Partitions

Theorem4.1gives a recursive formula for theq-Eulerian polynomialsEn(x, q), and Theorem5.1states the condition for which the coefficientsEn[x^dq^w] are stabilized. We conclude with a conjecture regarding the coefficients ofWd(t), which are the stabilized coefficients ofEn(x, q).

It was observed in [2] that the coefficients ofWd(t) correspond to numbers in the sequenceA256193in the Online Encyclopedia of Integer Sequences [11].

The numbers T(n, k) count partitions of n with exactlyk parts of a second type, denoted by a prime. For example, we have

T(3,0) = 3, corresponding to 111, 21, 3,

T(3,1) = 6, corresponding to 111,111,111,21,21,3, T(3,2) = 4, corresponding to 111,111,111,21, T(3,3) = 1, corresponding to 111.

Table1is a short table ofT(n, k) withkconstant along the columns

We will give a recursive formula for T(d+k, d), but we first need the following lemma.

Lemma 6.1. Letn, k, b∈Nsuch that b≤2k−n. The numbers T(n, k)satisfy the relation

T(n, k) = b j=0

b j

·T(n−b, k−j).

Proof. Let n, k, b ∈ N such that b ≤ 2k−n. We first show that T(n, k) ≥

b j=0

_b

j

·T(n−b, k−j). We then show thatT(n, k)≤ ^b_j=0b

j

·T(n−b, k−j).

To each partition counted by T(n−b, k−j), we append all possible partitions consisting of b−j 1s and j 1s and obtain partitions of n with k parts of a second type. For fixedj, there are_b

j

·T(n−b, k−j) such partitions.

Summing over all possible values ofj, there are ^b_j=0b

j

·T(n−b, k−j) such partitions formed in this way. ThusT(n, k)≥ ^b_j=0b

j

·T(n−b, k−j).

We now show that this summation counts all partitions which are counted by T(n, k). Since n < 2k, each partition represented by T(n, k) contains at least one singleton part (1 or 1). In particular, the partition with the fewest singleton parts is the partition 2 2. . .2

n−k

11. . .1

2k−n

. So every partition counted byT(n, k) ends in at least 2k−nsingleton parts. This means that forb <2k−n, truncating the lastb elements from a partition which hasb−j 1s and j 1s results in a partition counted byT(n−b, k−j). As there can be at most_b

j

such partitions, we haveT(n, k) = ^b_j=0b

j

·T(n−b, k−j).

Theorem 6.2. For fixed k∈Nandd≥2k, we have T(d+k, d) =

k i=1

(−1)ⁱ⁺¹· k

i

·T(d+k−i, d−i)

+ 1 .

Letk∈Nbe fixed andd≥2k. By Lemma6.1, we get T(d+k, d) =

k j=1

k j

·T(d, d−j) + 1.

Table1.ThenumbersT(n,k) 1 11 231 3641 5121151 720241661 113549412271 15548991632981 2286158186155923791 3012826235134224712946101 NumbersinboldcorrespondtocoefficientsofthepowerseriesWd(t)

Note that_k

j

= ^j_i=1k

j

_j

i

(−1)ⁱ⁺¹. We have

T(d+k, d) = k

j=1

T(d, d−j) ^j

i=1

k j

j i

(−1)ⁱ⁺¹ + 1. By the identity_r

s

_s

t

=_r

t

_r−t

s−t

, we get

T(d+k, d) = k j=1

T(d, d−j) ^j

i=1

k i

k−i j−i

(−1)ⁱ⁺¹ + 1. If we change the order of summations and leta=j−i, we obtain

T(d+k, d) = k

i=1

k i

(−1)^i+1k−i

a=0

k−i a

·T(d, d−a−i)

+ 1. Sincek−i≤2(d−i)−(d+k−i), by Lemma6.1we have

T(d+k, d) = k i=1

(−1)ⁱ⁺¹ k

i

·T(d+k−i, d−i)

+ 1.

Conjecture 6.3. For fixedk∈N andd≥2k, we have Wd[t^k] =

k i=1

(−1)ⁱ⁺¹· k

i

·Wd−i[t^k]

+ 1.

Acknowledgements

We would like to thank Professor Einar Steingr´ımsson for his support and invaluable advice on this paper. We are grateful to Roger Van Peski for his dedicated mentoring and copious feedback. We thank Professor Paul E. Gun- nells for proposing this area of research and for his guidance. Finally, we thank the PROMYS program and the Clay Mathematics Institute, under which this research was made possible.

Publisher’s Note Springer Nature remains neutral with regard to jurisdic- tional claims in published maps and institutional affiliations.

References

[1] L. Carlitz. q-bernoulli and eulerian numbers. Transactions of the American Mathematical Society, 76(2):332–350, 1954.

[2] W. Dugan, S. Glennon, P. E. Gunnells, and E. Steingr´ımsson. Tiered trees, weights, and q-eulerian numbers. Journal of Combinatorial Theory, Series A, 164:24–49, 2019.

[3] D. Foata and M.-P. Sch¨utzenberger. Major index and inversion number of per- mutations. Mathematische Nachrichten, 83(1):143–159, 1978.

[4] D. Forge. Linial arrangements and local binary search trees. arXiv preprint arXiv:1411.7834, 2014.

[5] I. M. Gelfand, M. I. Graev, and A. Postnikov. Combinatorics of hypergeometric functions associated with positive roots. In The Arnold-Gelfand Mathematical Seminars, pages 205–221. Springer, 1997.

[6] P. E. Gunnells, E. Letellier, and F. R. Villegas. Torus orbits on homogeneous va- rieties and kac polynomials of quivers. Mathematische Zeitschrift, 290(1-2):445–

467, 2018.

[7] M. Hyatt. Recurrences for eulerian polynomials of type b and type d. Annals of Combinatorics, 20(4):869–881, 2016.

[8] A. Postnikov. Intransitive trees. Journal of Combinatorial Theory, Series A, 79(2):360–366, 1997.

[9] A. Postnikov and R. P. Stanley. Deformations of coxeter hyperplane arrange- ments. Journal of Combinatorial Theory, Series A, 91(1-2):544–597, 2000.

[10] J. Shareshian and M. Wachs.q-eulerian polynomials: excedance number and ma- jor index. Electronic Research Announcements of the American Mathematical Society, 13(4):33–45, 2007.

[11] N. J. Sloane et al. The on-line encyclopedia of integer sequences, 2003.

[12] R. P. Stanley. Binomial posets, m¨obius inversion, and permutation enumeration.

Journal of Combinatorial Theory, Series A, 20(3):336–356, 1976.

[13] R. P. Stanley. Hyperplane arrangements, interval orders, and trees. Proceedings of the National Academy of Sciences, 93(6):2620–2625, 1996.

Aman Agrawal Department of Physics Indian Institute of Science CV Raman Road

Bengaluru Karnataka 560012 India

e-mail: amanagrawal@iisc.ac.in Caroline Choi

Department of Mathematics Stanford University

450 Serra Mall Stanford CA 94305 USA

e-mail: cchoi1@stanford.edu

Nathan Sun

Department of Mathematics Harvard University

86 Brattle Street Cambridge MA 02138 USA

e-mail: nsun@college.harvard.edu Received: 4 May 2019.

Accepted: 8 January 2020.