Eulerian Numbers versus Stirling Numbers of the First Kind

n

1

2

3

4

5

6

7

8

1	1
1	1

In a permutation

(

a

1,

,

a

2

,…,

a

n

)

, an ascent is a pair

(

a

m

,

a

m+1

)

with

a

m

<

a

m+1

. The Eulerian number



n

k



counts the number of permutations of

{1,2,3,…,n}

with exactly

k

ascents,

0≤k≤n-1

. Alternatively,



n

k'-1



counts the number of permutations of

{1,2,3,…,n}

with exactly

k

' permutation runs,

1≤k'≤n

. For example, the permutation

(1,2,3,5,4)

has the three ascents

(1,2)

,

(2,3)

, and

(3,5)

and the two runs

(1,2,3,5)

and

(4)

.

The unsigned Stirling number of the first kind



n

k



counts the number of permutations of

{1,2,3,…,n}

whose cycle decomposition has

k

cycles. For example, the permutation

(1,2,3,5,4)

is the mapping

11

,

22

,

33

,

45

,

54

, so its cycle decomposition is

(1)(2)(3)(45)

with four cycles.

Both types of numbers count the

n!

permutations of

{1,2,3,…,n}

in different ways. Define the number



n

i,j



to count the number of permutations that have

i

cycles and

j

runs. This Demonstration lays out these numbers in a square; the row sums are



n

i



and the column sums are



n

j



; the sums of either of those is

n!

.