# Combinatorial Interpretation of General Eulerian Numbers

Authors: Tingyao Xiong; Jonathan I. Hall; Hung-Ping Tsao
Journal: Journal of Discrete Mathematics
 (2014)

---

## Abstract

Since the 1950s, mathematicians have successfully interpreted the traditional Eulerian numbers andq-Eulerian numbers combinatorially. In this paper, the authors give a combinatorial interpretation to the general Eulerian numbers defined on general arithmetic progressions a,a+d,a+2d,….


---

## Body

## 1. Introduction

Definition 1.
Given a positive integern, define Ωn as the set of all permutations of [n]={1,2,3,…,n}. For a permutation π=p1p2p3…pn∈Ωn, i is called an ascent of π if pi<pi+1; i is called a weak exceedance of π if pi≥i.It is well known that a traditional Eulerian numberAn,k is the number of permutations π∈Ωn that have k weak exceedances [1, page 215]. And An,k satisfies the recurrence: An,1=1, (n≥1), An,k=0(k>n),
(1)An,k=kAn-1,k+(n+1-k)An-1,k-1(1≤k≤n).Besides the recursive formula (1), An,k can be calculated directly by the following analytic formula [2, page 8]:
(2)An,k=∑i=0k-1‍(-1)i(k-i)n(n+1i)(1≤k≤n).Definition 2.
Given a permutationπ=p1p2p3…pn∈Ωn, define functions
(3)majπ=∑pj>pj+1‍j,a(n,k,i)=#{π∣majπ=i&πhaskascents}.Since the 1950s, Carlitz [3, 4] and his successors have generalized Euler’s results to q-sequences {1,q,q2,q3,…}. Under Carlitz’s definition, the q-Eulerian numbers An,k(q) are given by
(4)An,k(q)=q(m-k+1)(m-k)/2∑i=0k(n-k-1)‍a(n,n-k,i)qi,
where functions a(n,k,i) are as defined in Definition 2.In [5], instead of studying q-sequences, the authors have generalized Eulerian numbers to any general arithmetic progression
(5){a,a+d,a+2d,a+3d,…}.Under the new definition, and given an arithmetic progression as defined in (5), the general Eulerian numbers An,k(a,d) can be calculated directly by the following equation [5, Lemma 2.6]:
(6)An,k(a,d)=∑i=0k‍(-1)i[(k+1-i)d-a]n(n+1i).
Interested readers can find more results about the general Eulerian numbers and even general Eulerian polynomials in [5].


## 2. Combinatorial Interpretation of General Eulerian Numbers

The following concepts and properties will be heavily used in this section.Definition 3.
LetWn,k be the set of n-permutations with k weak exceedances. Then |Wn,k|=An,k. Furthermore, given a permutation π=p1p2p3…pn, let Qn(π)=i, where pi=n.Given a permutationπ∈Ωn, it is known that π can be written as a one-line form like π=p1p2p3…pn, or π can be written in a disjoint union of distinct cycles. For π written in a cycle form, we can use a standard representation by writing (a) each cycle starting with its largest element and (b) the cycles in increasing order of their largest element. Moreover, given a permutation π written in a standard representation cycle form, define a function f as f(π) to be the permutation obtained from π by erasing the parentheses. Then f is known as the fundamental bijection from Ωn to itself [6, page 30]. Indeed, the inverse map f-1 of the fundamental bijection function f is also famous in illustrating the relation between the ascents and weak exceedances as follows [2, page 98].Proposition 4.
The functionf-1 gives a bijection between the set of permutations on [n] with k ascents and the set Wn,k+1.Example 5.
The standard representation of permutationπ=5243716 is (2)(43)(7615)∈Ω7, and f(π)=2437615; Q7(π)=5; π=5243716 has 3 ascents, while f-1(π)=(5243)(716)=6453271∈W7,4 has 3+1=4 weak excedances because p1=6>1, p2=4>2, p3=5>3, and p6=7>6.Now suppose we want to construct a sequence consisting ofk vertical bars and the first n positive integers. Then the k vertical bars divide these n numbers into k+1 compartments. In each compartment, there is either no number or all the numbers are listed in a decreasing order. The following definition is analogous to the definition of [2, page 8].Definition 6.
A bar in the above construction is called extraneous if either(a)
it is immediately followed by another bar; or(b)
each of the rest compartment is either empty or consists of integers in a decreasing order if this bar is removed.Example 7.
Supposen=7, k=4; then in the following arrangement
(7)32|1||7654|
the 1st, 2nd, and 4th bars are extraneous.Now we are ready to give combinatorial interpretations to the general Eulerian numbersAn,k(a,d). First note that (6) implies that An,k(a,d) is a homogeneous polynomial of degree n with respect to a and d. Indeed,
(8)An,k(a,d)=∑i=0k‍(-1)i[(k+1-i)d-a]n(n+1i)=∑i=0k‍(-1)i[(k+1-i)(d-a)+(k-i)a]n(n+1i)=∑j=0n‍[∑i=0k‍(-1)i(k+1-i)n-j(k-i)j(n+1i)]×(nj)(d-a)n-jaj=∑j=0n‍cn,k(j)(nj)(d-a)n-jaj,
where
(9)cn,k(j)=∑i=0k‍(-1)i(k+1-i)n-j(k-i)j(n+1i),0≤j≤n.The following theorem gives combinatorial interpretations to the coefficientscn,k(j), 0≤j≤n.Theorem 8.
Let the general Eulerian numbersAn,k(a,d) be written as in (8). Then
(10)cn,k(j)=#{π∈Wn,k+1,j<Qn(π)≤n}+#{π∈Wn,k,1≤Qn(π)≤j}.Proof.
We can check the result in (10) for two special values j=0 and j=n quickly. By (2),whenj=0, cn,k(0)=∑i=0k‍(-1)i(k+1-i)n(n+1i)=An,k+1;whenj=n, cn,k(n)=∑i=0k‍(-1)i(k-i)n(n+1i)=An,k. Therefore, (10) is true for j=0 and j=n.
Generally, for1≤j≤n-1, we write down k bars with k+1 compartments in between. Place each element of [n] in a compartment. If none of the k bars is extraneous, then the arrangement corresponds to a permutation with k ascents. Let B be the set of arrangements with at most one extraneous bar at the end and none of integers {1,2,…,j} locating in the last compartment. We will show that cn,k(j)=|B|.
To achieve that goal, we use the Principle of Inclusion and Exclusion. There are(k+1)n-jkj ways to put n numbers into k+1 compartments with elements {1,2,…,j} avoiding the last compartments.
LetBi be the number of arrangements with the following features:(1) none of {1,2,…,j} sits in the last compartment;(2) each arrangement in Bi has at least i extraneous bars.(3) in each arrangement in Bi, any two extraneous bars are not located right next to each other.
Then the Principle of Inclusion and Exclusion shows that(11)|B|=(k+1)n-jkj-B1+B2+⋯+(-1)kBk.
Now we consider the value ofBi, where 1≤i≤k. Suppose that we have k+1-i compartments with k-i bars in between. There are (k+1-i)n-j(k-i)j ways to insert n numbers into these k+1-i compartments with first j integers avoiding the last compartment and list integers in each component in a decreasing order. Then insert i separating extraneous bars into n+1 positions. So we get
(12)Bi=(k+1-i)n-j(k-i)j(n+1i).
Plug formula (12) into (11); we have cn,k(j)=|B|.
Given an arrangementπ∈B, if we remove the bars, then we obtain a permutation π∈Ωn. So without confusion, we just use the same notation π to represent both an arrangement in set B and a permutation on [n]. Now for each π∈B, π either (case 1) has no extraneous bar and none of{1,2,…,j} locates in the last compartment or(case 2) has only one extraneous bar at the end.
Ifπ is in case 1, then π has k ascents since each bar is non-extraneous. And the last compartment of π is nonempty. Therefore the last cycle of f-1(π) has to be (n…pg). In other words, Qn(f-1(π))=pg>j since none of {1,2,…,j} locates in the last compartment. And by Proposition 4, f-1(π)∈Wn,k+1.
Ifπ is in case 2, then π has k-1 ascents since only the last bar is extraneous. Note that in this case, the arrangement with no elements of {1,2,…,j} in the compartment second to the last or the last nonempty compartment has been removed by the Principle of Inclusion and Exclusion. Equivalently, at least one number of {1,2,…,j} has to be in the compartment second to the last. So the last cycle of f-1(π) has to be (n…pl), and Qn(f-1(π))=pl≤j. Also by Proposition 4, f-1(π)∈Wn,k.
Combing all the results above, statement (10) is correct.The next Theorem describes some interesting properties of the coefficientscn,k.Theorem 9.
Let the coefficientscn,k be as described in Theorem 8. Then, (1)
∑k=0n‍cn,k(j)=n!, for any 0≤j≤n;(2)
cn,k(j)=cn,n-k(n-j), for all 0≤j,k≤n.Before we can prove Theorem9, we need the following lemma which is also interesting by itself.Lemma 10.
Given a positive integern, then
(13)#{π∈Wn,k&Qn(π)=j}=#{π∈Wn,n+1-k&Qn(π)=n+1-j}
for any 1≤k,j≤n.Proof.
First of all, given a positive integern, we define a function g:Ωn→Ωn as follows:
(14)forπ=p1p2…pn∈Ωn,g(π)=(n+1-p1)(n+1-p2)…(n+1-pn).
For instance, for π=53214∈Ω5, g(π)=13452. g is obviously a bijection of Ωn to itself.
Now for some fixed1≤k,j≤n, suppose Sk,j={π∈Wn,k&Qn(π)=j}, and Tk,j={π∈Wn,n+1-k&Qn(π)=n+1-j}. For any π∈Sk,j, we write π in the standard representation cycle form. So π=(pu…)…(n…j) and f(π)=pu…n…j has k-1 ascents by Proposition 4. Now we compose f(π) with the bijection function g as just defined. Then g(f(π))=n+1-pu…1…n+1-j has n-k ascents, which implies that f-1(g(f(π))) has n+1-k weak excedances. So f-1(g(f(π)))∈Wn,n+1-k. Note that the last cycle of f-1(g(f(π))) has to be (n…n+1-j). Therefore, f-1(g(f(π)))∈Tk,j. Since both f and g are bijection functions, f-1gf gives a bijection between Sk,j and Tk,j.Now we are ready to prove Theorem9.Proof of Theorem9.
For part1, by Theorem 8,
(15)∑k=0n‍cn,k(j)=∑k=0n‍#{π∈Wn,k+1,j<Qn(π)≤n}+∑k=0n‍#{π∈Wn,k,1≤Qn(π)≤j}=∑k=0n‍#{π∈Wn,k}=|Ωn|=n!.
For part 2, also by Theorem 8,
(16)cn,k(j)=∑i=j+1n‍#{π∈Wn,k+1,Qn(π)=i}+∑m=1j‍#{π∈Wn,k,Qn(π)=m}=∑i=j+1n‍#{π∈Wn,n-k,Qn(π)=n+1-i}+∑m=1j‍#{π∈Wn,n+1-k,Qn(π)=n+1-mWn,n+1-k}byLemma10=#{π∈Wn,k,1≤Qn(π)≤n-j}+#{π∈Wn,n+1-k,n-j<Qn(π)≤n}=cn,n-k(n-j).Remark 11.
Using the analytic formula ofcn,k(j) as in (9), part 2 of Theorem 9 implies the following identity:
(17)∑i=0k‍(-1)i(k+1-i)n-j(k-i)j(n+1i)=∑l=0n-k‍(-1)l(n+1-k-l)j(n-k-l)n-j(n+1l),
where n is a positive integer, and 0≤j,k≤n.


## 3. Another Combinatorial Interpretation ofcn,k(1) and cn,k(n-1)

In pursuing the combinatorial meanings of the coefficientscn,k, the authors have found some other interesting properties about permutations. The results in this section will reveal close connections between the traditional Eulerian numbers An,k and cn,k(j), where j=1 or j=n-1.One fundamental concept of permutation combinatorics isinversion. A pair (pi,pj) is called an inversion of the permutation π=p1p2…pn if i<j and pi>pj [6, page 36]. The following definition provides the main concepts of this section.Definition 12.
For a fixed positive integern, let AWn,k={π=p1p2p3…pn∣π∈Wn,k and p1<pn} (or (p1,pn) is not an inversion) and BWn,k=Wn,k∖AWn,k (or (p1,pn) is an inversion).
It is obvious that|AWn,k|+|BWn,k|=An,k. The following theorem interprets coefficients cn,k(1) and cn,k(n-1) in terms of AWn,k and BWn,k.Theorem 13.
Let the coefficientscn,k of the general Eulerian numbers be written as in (9). AWn,k and BWn,k are as defined in Definition 12. Then (1)
cn,k(1)=2|AWn,k+1|,(2)
cn,k(n-1)=2|BWn,k|.Proof.
For part(1), by Theorem 8, cn,k(1)=|S1|+|S2|, where S1={π=p1p2…pn∣π∈Wn,k+1&p1≠n}, S2={π=p1p2…pn∣π∈Wn,k&p1=n}. Given a permutation π=p1p2…pn∈S1 and pn≠n, then both p1p2…pn and pnp2…p1 belong to S1, so one of them has to be in AWn,k+1. If π=p1p2…pn∈S1 and pn=n, then π∈AWn,k+1, but pnp2…p1∈S2. Therefore, (1/2)cn,k(1)=|AWn,k+1|.
Part(2) can be proved using exactly the same method. So we leave it to the readers as an exercise.|
A
W
n
,
k
| and |BWn,k| are interesting combinatorial concepts by themselves. Note that generally speaking, |AWn,k|≠|BWn,k|. Indeed, |AWn,k|=|BWn,n+1-k|.Theorem 14.
For any positive integern≥2, the sets AWn,k and BWn,k are defined in Definition 12. Then |AWn,k|=|BWn,n+1-k| for 1≤k≤n.Proof.
It is an obvious result of part 2 of Theorems9 and 13.Our last result of this paper is the following theorem which reveals that both|AWn,k| and |BWn,k| take exactly the same recursive formula as the traditional Eulerian numbers An,k as shown in (1).Theorem 15.
For a fixed positive integern, let AWn,k and BWn,k be as defined in Definition 12; then
(18)k|AWn-1,k|+(n+1-k)|AWn-1,k-1|=|AWn,k|,(19)k|BWn-1,k|+(n+1-k)|BWn-1,k-1|=|BWn,k|.Proof.
A computational proof can be obtained straightforward by using (9) and Theorem 13. But here we provide a proof in a flavor of combinatorics.
Idea of the Proof. For (18), given a permutation A1=p1p2p3…pn-1∈AWn-1,k, for each position i with pi≥i, we insert n into a certain place of A1, such that the new permutation A1′ is in AWn,k. There are k such positions, so we can get k new permutations in AWn,k. Similarly, if A2=p1p2p3…pn-1∈AWn-1,k-1, for each position i with pi<i, and the position at the end of A2, we insert n into a specific position of A2 and the resulting new permutation A2′ is in AWn,k. There are n+1-k such positions, so we can get n+1-k new permutations in AWn,k. We will show that all the permutations obtained from the above constructions are distinct, and they have exhausted all the permutations in AWn,k
For any fixedA′=π1π2π3…πn∈AWn,k, then π1<πn. We classify A′ into the following disjoint cases:
Case a. Consider that πi=n with i<n. So A′=π1π2…πi-1nπi+1…πn-1πn. (a1)π1<πn-1, and πn≥i;(a2)π1<πn-1, and πn<i;(a3)π1>πn-1, πn<n-1, and πn≥i;(a4)π1>πn-1, πn<n-1, and πn<i;(a5)π1>πn-1, and πn=n-1.
Case b. Consider that πn=n. So πi=n-1 for some i<n and A′=π1π2…πi-1n-1…πn-1n: (b1)π1<πn-1;(b2)πn-1<π1<n-1, and πn-1≥i;(b3)πn-1<π1<n-1, and πn-1<i;(b4)π1=n-1.Based on the classifications listed above, we can construct a map f:{AWn-1,k,AWn-1,k-1}→AWn,k by applying the idea of the proof we have illustrated at the beginning of the proof. To save space, the map f is demonstrated in Table 1. From Table 1 we can see that in each case, the positions of inserting n are all different. So all the images obtained in a certain case are different. Since all the cases are disjoint, all the images A′∈AWn,k are distinct.
Similarly, for eachB′=π1π2π3…πn∈BWn,k, then π1>πn. We classify B′ into the following disjoint cases.
Case c. Consider that πi=n with 1<i≤n-1. So B′=π1π2…πi-1nπi+1…πn-1πn: (c1)π1>πn-1, and πn≥i;(c2)π1>πn-1, and πn<i;(c3)π1<πn-1<n-1, πn-1≥i;(c4)π1<πn-1<n-1, πn-1<i;(c5)πn-1=n-1;(c6)πn-1=n.
Case d. Consider that π1=n. So B′=nπ2…πn-2πn-1: (d1)πn-2<πn-1;(d2)πn-2>πn-1.To prove (19), we use a similar idea of proof as shown above. If B1=p1p2p3…pn-1∈BWn-1,k, for each position i with pi≥i, we insert n into a certain place of B1 to get B1′∈AWn,k. If B2=p1p2p3…pn-1∈BWn-1,k-1, for each position i with pi<i, and the position i where pi=n-1, we insert n into a specific position of B2 to obtain B2′∈AWn,k. Such a map g:{BWn-1,k,BWn-1,k-1}→BWn,k is illustrated in Table 2. And the distinct images under g exhaust all the permutations in BWn,k.Table 1
The mapf:{AWn-1,k,AWn-1,k-1}→AWn,k.
A
=
p
1
p
2
…
p
n
-
1
Positioni
Condition
A
′
∈
A
W
n
,
k
A∈AWn-1,k
1
<
i
≤
n
-
1  and  pi≥i
p
i
>
p
1
A
′
=
p
1
p
2
…
p
i
-
1
n
p
i
+
1
…
p
n
-
1
p
i  With  p1<pn-1,p1<pi  Case  (a1)
p
i
<
p
1  and  pn-1<n-1
A
′
=
p
1
p
2
…
p
i
-
1
n
p
i
+
1
…
p
n
-
2
p
i
p
n
-
1  With pi<p1<pn-1<n-1  Case  (a3)
p
i
<
p
1  and  pn-1=n-1
A
′
=
p
1
p
2
…
p
i
-
1
n
-
1
p
i
+
1
…
p
n
-
2
p
i
n  With pi<p1,pi≥i  Case  (b2)
i
=
1
p
j
=
n
-
1  and  j<n-1
A
′
=
p
n
-
1
p
2
…
p
j
-
1
n
p
j
+
1
…
p
n
-
2
p
1
n
-
1  With   p1<pn-1  Case  (a5)
p
n
-
1
=
n
-
1
A
′
=
n
-
1
p
2
…
p
n
-
2
p
1
n  Case  (b4)
A
∈
A
W
n
-
1
,
k
-
1
1
<
i
≤
n
-
1  and  pi<i
p
i
>
p
1
A
′
=
p
1
p
2
…
p
i
-
1
n
p
i
+
1
…
p
n
-
1
p
i  With  p1<pn-1,p1<pi  Case  (a2)
p
i
<
p
1  and  pn-1<n-1
A
′
=
p
1
p
2
…
p
i
-
1
n
p
i
+
1
…
p
n
-
2
p
i
p
n
-
1  With pi<p1<pn-1<n-1  Case  (a4)
p
i
<
p
1  and  pn-1=n-1
A
′
=
p
1
p
2
…
p
i
-
1
n
-
1
p
i
+
1
…
p
n
-
2
p
i
n  With pi<p1,pi<i  Case  (b3)
i
=
n
A
′
=
p
1
p
2
…
p
n
-
1
n  Case  (b1)Table 2
The mapg:{BWn-1,k,BWn-1,k-1}→BWn,k.
B
=
p
1
p
2
…
p
n
-
1
Positioni
Condition
B
′
∈
B
W
n
,
k
B∈WBn-1,k
1
<
i
<
n
-
1  and  pi≥i
p
1
>
p
i
B
′
=
p
1
…
p
i
-
1
n
p
i
+
1
…
p
n
-
1
p
i  With  p1>pn-1 and pi≥i  Case  (c1)
p
1
<
p
i
<
n
-
1
B
′
=
p
1
…
p
i
-
1
n
p
i
+
1
…
p
i
p
n
-
1  With  p1<pi<n-1, pi≥i  Case  (c3)
p
1
<
p
i
=
n
-
1
B
′
=
n
p
2
…
p
i
-
1
n
-
1
p
i
+
1
…
p
1
p
n
-
1  With   pi=n-1, p1>pn-1  Case  (d2)
i
=
1
p
1
≥
1
B
′
=
n
p
2
…
p
n
-
1
p
1  With pn-1<p1  Case  (d1)
B
∈
W
B
n
-
1
,
k
-
1
1
<
i
<
n
-
1  and  pi<i
p
1
>
p
i
B
′
=
p
1
…
p
i
-
1
n
p
i
+
1
…
p
n
-
1
p
i  With  p1>pn-1 and pi<i  Case  (c2)
p
1
<
p
i
B
′
=
p
1
…
p
i
-
1
n
p
i
+
1
…
p
i
p
n
-
1  With  p1<pi<n-1,  pi<i  Case  (c4)
i
=
n
-
1  pi<i
p
1
>
p
i
=
p
n
-
1
B
′
=
p
1
…
p
n
-
2
n
p
n
-
1  Case  (c6)
1
≤
i
<
n
-
1  and  pi=n-1
p
i
=
n
-
1
B
′
=
p
1
…
p
i
-
1
n
p
i
+
1
…
p
n
-
2
n
-
1
p
n
-
1  Case  (c5)Here is a concrete example for the constructions illustrated in Table2.Example 16.
Supposen=4, k=2. We want to obtain BW4,2={3142,3412,3421,4132,4213,4312,4321} from BW3,2={321,231} and BW3,1={312}. For 321∈BW3,2, p1=3≥1, then it corresponds to B′=4213 which is case (d1) in Table 2; p2=2≥2, then it corresponds to B′=3412 which is case (c1) in Table 2. Similarly, we can construct {4312,4321} from 231∈BW3,2 and {3421,3142,4132} from 312∈BW3,1 using Table 2.



---

*Source: 870596-2014-01-02.xml*