# On Permutation Weights and q-Eulerian Polynomials

## Full text

(1)

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 andq-EulerianPolynomials

### 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 deﬁne 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 coeﬃcients ofEn(x, q) stabilize asngoes to inﬁnity, which was conjectured by Dugan et al. (Journal of Combinatorial Theory, Series A164:24–49, 2019), and enables the deﬁni- 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 coeﬃcients mentioned above.

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

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

### 1. Introduction

Dugan et al. deﬁned certain weights of permutations in their work on the combinatorics of tiered trees . Tiered trees are a generalization of maxmin trees, which were originally introduced by Postnikov  and appear in the study of local binary search trees , hypergeometric functions , and hyper- plane arrangements [9,13]. In , Dugan et al. deﬁned 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 . They showed that weight 0 maxmin trees are in natural bijection with per- mutations. They deﬁned the weight of a permutationσ as the largest weight

(2)

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 deﬁned in . Theq-Eulerian polynomialEn(x, q) diﬀers from other q-Eulerian polynomials by Carlitz , Foata-Sch¨utzenberger , Stanley , and Shareshian-Wachs , and presents interesting combinato- rial properties. It was observed in  that the coeﬃcients 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 .

We present two main results regarding permutation weights and theq- Eulerian polynomialsEn(x, q). We prove the stabilization phenomenon conjec- tured in , which gives an explicit formula for the formal power series Wd(t) deﬁned in . 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 deﬁnitions and notation. In Sect. 3, we deﬁne the weight disparity of a per- mutation and ﬁnd a lower bound for weight disparity. We then use this result to show that the coeﬃcients ofxd 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 coeﬃcients of En(x, q) are stabilized and give a second proof of the stabilization phenomenon. We conclude with a conjecture regarding the coeﬃcients 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 deﬁnitions in this section follow from .

Definition 2.1. Given a permutation σ=a1a2· · ·an, we deﬁne 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.

(3)

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 Z0 deﬁned 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 Deﬁnition2.1. Then the weight ofσis deﬁned 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 659243Aﬂattens 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 deﬁned as An(x) =

σ∈Sn

xdes(σ).

The coeﬃcient ofxmin 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 deﬁned in .

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

σ∈Sn

xdes(σ)qw(σ).

(4)

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) +x2

E4(x, q) = 1 +x(q2+ 3q+ 7) +x2(q2+ 4q+ 6) +x3

E5(x, q) = 1 +x(q3+ 3q2+ 7q+ 15) +x2(q4+ 4q3+ 11q2+ 25q+ 25) +x3(q3+ 5q2+ 10q+ 10) +x4

E6(x, q) = 1 +x(q4+ 3q3+ 7q2+ 15q+ 31)

+x2(q6+ 4q5+ 11q4+ 31q3+ 58q2+ 107q+ 90) +x3(q6+ 5q5+ 16q4+ 34q3+ 76q2+ 105q+ 65) +x4(q4+ 6q3+ 15q2+ 20q+ 15) +x5

E7(x, q) = 1 +x(q5+ 3q4+ 7q3+ 15q2+ 31q+ 63) +x2(q8+ 4q7+ 11q6+ 31q5+ 65q4 + 149q3+ 237q2+ 392q+ 301) +x3(q9 + 5q8+ 16q7+ 41q6+ 104q5+ 203q4+ 380q3 + 609q2+ 707q+ 350)

+x4(q8+ 6q7+ 22q6+ 55q5+ 106q4+ 210q3+ 336q2+ 315q+ 140) +x5(q5+ 7q4+ 21q3+ 35q2+ 35q+ 21) +x6

### 3. Proof of Stabilization Phenomenon

Let us ﬁxkand consider the coeﬃcients ofxk inEn(x, q). It was conjectured in  that asngoes to inﬁnity, these coeﬃcients converge to a ﬁxed sequence and thus display a stabilization phenomenon. Observe that fork = 2 in Ex- ample2.3, the coeﬃcients ofx2 seem to stabilize to

qN + 4qN1+ 11qN2+ 31qN3+ 65qN4+· · ·

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  and observed to have interesting combinatorial properties.

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

We ﬁrst deﬁne the weight disparity of a permutation and ﬁnd 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 coeﬃcients ofWd(t).

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

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

(5)

The following lemma follows directly from the proof of Theorem 6.10 in . 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 ﬁx 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 deﬁne 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 coeﬃcient of xd inEn(x, q) byEn[xd] and the coeﬃcient ofxdqmin En(x, q) byEn[xdqm].

We now show that the coeﬃcients ofEn[xd] 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[xdqmaxwt(n,d)−k] is independent ofn.

(6)

Proof. We show that for suﬃciently 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[xdqmaxwt(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[xdqmaxwt(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[xdqmaxwt(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[xdqmaxwt(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[xdqmaxwt(m+1,d)−k].

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

Em[xdqmaxwt(m,d)−k] =Em+1[xdqmaxwt(m+1,d)−k]. It is easy to see that, by induction, the above argument shows that

Em+i[xdqmaxwt(m+i,d)−k] =Em+i+1[xdqmaxwt(m+i+1,d)−k]

for anyi≥0.

Theorem3.6shows that the formal power seriesWd(t) deﬁned in  exists and is given byWd(tk) =Ed+k+1[xdq(d−1)k]. We can now extractWd(t) from the stabilized coeﬃcients ofEn(x, q).

Definition 3.7. IfEn[xd] stabilizes toqN+a1qN−1+a2qN2+a3qN−3+· · ·, whereN =d(n−d−1), then the formal power seriesWd(t) is deﬁned in 

as

Wd(t) = 1 +a1t+a2t2+a3t3+· · ·

(7)

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

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

n

### (x, q)

The classical Eulerian polynomialsAn(x) in Deﬁnition2.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 deﬁnitions and lemmas used in the proof of Theorem4.1.

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

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

Proof. We ﬁrst show that there exists a functionf :Sn→Sn+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 deﬁned 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,

(8)

we havef(π)∈Sn+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 andSn+1 are equinumerous, where its inversef−1 must preserve weight and reduce the number of descents by 1.

Definition 4.4. We writeEn(x, q) to denote theq-Eulerian polynomial

σ∈Sn

xdes(σ)qw(σ).

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

Corollary 4.5. We have

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

En[xd] =

n−1 i=1

n−1 i

i

k=1

En−i−1[xd−k]·Ei[xk−1]·qd−k

+En−1[xd]qd. 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[xd]qd.

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 byEi+1 [xk], and the permutationsπR are counted byEn−1−i[xd−k]. We know thatEn[xdqw]· Em[xeqv] counts permutations of lengthn+mwithd+edescents and of weight w+v. Thus permutations of lengthnwithddescents and of weightw(πL·1) + w(πR) are counted byEi+1 [xk]·En−1−i[xd−k].We add des(πR) =d−kto the weight of these permutations to count permutations of weightw(σ), length n, andddescents. Multiplying by qd−k, we have qd−k·Ei+1 [xk]·En−1−i[xd−k]. Thus the permutationsσare counted by

n−1

i=1

n−1 i

i

k=1

Ei+1 [xk]·En−1−i[xd−k]qd−k,

(9)

which by Corollary4.5is equal to

n−1

i=1

n−1 i

i k=1

Ei[xk−1]·En−1−i[xd−k]qd−k. Combining Case 1 and Case 2, we have

En[xd] =

n−1

i=1

n−1 i

i

k=1

Ei[xk−1]·En−1−i[xd−k]qd−k

+En−1[xd]qd.

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

n−1

d=0

xd n−1

i=1

n−1 i

i

k=1

En−i−1[xd−k]·Ei[xk−1]·qd−k +En−1[xd]qd

.

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

n−1

i=1

n−1 i

i

k=1

n−1−i

=0

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

+

n−1 j=0

En−1[xj]qjxj. We can rearrange terms to get

En(x, q) =

n−1 i=1

n−1 i

i

k=1

Ei[xk−1]xk−1

n−i−1

=0

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

+

n−1

j=0

En−1[xj]qjxj.

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) , 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 n−1

=1

n−1

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

,

(10)

where fn(x) = kfnkxk and fnk denotes the number of all maxmin trees on the set [n+ 1] withkmaxima . Given that weight 0 maxmin trees are in bijection with permutations , 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 coeﬃcients ofEn(x, q).

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

En[xdqm] =

n−1

i=1

n−1 i

i

k=1

m

j=0

En−i−1[xd−kqm−j]·Ei[xk−1qk+j−d]

+En−1[xdqm−d].

Proof. Since by Lemma4.6, we have En[xd] =

n−1

i=1

n−1 i

i k=1

Ei[xk−1]·En−1−i[xd−k]qd−k+En−1[xd]qd, we can piece together min En[xdqm] by introducing a third summation and

iterating through all possibilities.

### 5. Alternate Proof of the Stabilization Phenomenon

Using our recursive formula for the coeﬃcients of En(x, q) in Corollary 4.8, we determine a lower bound for the exponent ofq such that the coeﬃcients En[xdqw] 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[xdqm] =En−1[xdqm−d].

Proof. By Corollary4.8, we have En[xdqm] =En−1[xdqm−d]

+

n−1

i=1

n−1 i

i

k=1

m

j=0

En−i−1[xd−kqm−j]·Ei[xk−1qk+j−d]

. (5.1) For ﬁxed i and k, we show that for all j, we have En−i−1[xd−kqm−j] · Ei[xk−1qk+j−d] = 0. We consider the following two cases:

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

En[xdq(d−1)(n−d−1)+u] =En−1[xdq(d−1)(n−d−1)+u−d] +

n−1

i=1

n−1 i

i

k=1

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

j=0

En−i−1[xd−kq(d−1)(n−d−1)+u−j]

·Ei[xk−1qk+j−d]

. (5.2)

(11)

The weight of a permutation of length n with d descents is bounded by maxwt(n, d) = d(n−d−1). So from the coeﬃcients Ei[xk−1qk+j−d] and En−i−1[xd−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[xd−kqm−j]·Ei[xk−1qk+j−d] = 0 and

n−1

i=1

n−1 i

i

k=1

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

j=0

En−i−1[xd−kq(d−1)(n−d−1)+u−j]

·Ei[xk−1qk+j−d]

= 0. SoEn[xdqm] =En−1[xdqm−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

i

k=1

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

j=0

En−i−1[xd−kq(d−1)(n−d−1)−v−j]

·Ei[xk−1qk+j−d] = 0.

SoEn[xdqm]=En−1[xdqm−d].

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

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

It is easy to show thatEn[x0q0] is stabilized andEn[xn−1q0] is not.

d

### (t)and Integer Partitions

Theorem4.1gives a recursive formula for theq-Eulerian polynomialsEn(x, q), and Theorem5.1states the condition for which the coeﬃcientsEn[xdqw] are stabilized. We conclude with a conjecture regarding the coeﬃcients ofWd(t), which are the stabilized coeﬃcients ofEn(x, q).

It was observed in  that the coeﬃcients ofWd(t) correspond to numbers in the sequenceA256193in the Online Encyclopedia of Integer Sequences .

(12)

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 ﬁrst 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 ﬁrst show that T(n, k)

b j=0

b

j

·T(n−b, k−j). We then show thatT(n, k) bj=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 ﬁxedj, there areb

j

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

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

j

·T(n−b, k−j) such partitions formed in this way. ThusT(n, k) bj=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 mostb

j

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

j

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

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

k i=1

(−1)i+1· k

i

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

+ 1 .

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

k j=1

k j

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

(13)

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

(14)

Note thatk

j

= ji=1k

j

j

i

(1)i+1. We have

T(d+k, d) = k

j=1

T(d, d−j) j

i=1

k j

j i

(−1)i+1 + 1. By the identityr

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)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)i+1 k

i

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

+ 1.

Conjecture 6.3. For ﬁxedk∈N andd≥2k, we have Wd[tk] =

k i=1

(−1)i+1· k

i

·Wd−i[tk]

+ 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 aﬃliations.

### References

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

 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.

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

(15)

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

 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.

 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.

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

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

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

 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.

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

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

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

 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

(16)

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.

Updating...

## References

Related subjects :