Eulerian Number - Eulerian Numbers of The Second Kind

Eulerian Numbers of The Second Kind

The permutations of the multiset {1, 1, 2, 2, ···, n, n} which have the property that for each k, all the numbers appearing between the two occurrences of k in the permutation are greater than k are counted by the double factorial number (2n−1)!!. The Eulerian number of the second kind, denoted, counts the number of all such permutations that have exactly m ascents. For instance, for n = 3 there are 15 such permutations, 1 with no ascents, 8 with a single ascent, and 6 with two ascents:

The Eulerian numbers of the second kind satisfy the recurrence relation, that follows directly from the above definition:

with initial condition for n = 0, expressed in Iverson bracket notation:

Correspondingly, the Eulerian polynomial of second kind, here denoted P_n (no standard notation exists for them) are

and the above recurrence relations are translated into a recurrence relation for the sequence P_n(x):

with initial condition

The latter recurrence may be written in a somehow more compact form by means of an integrating factor:

so that the rational function

satisfies a simple autonomous recurrence:

whence one obtains the Eulerian polynomials as P_n(x) = (1−x)2n u_n(x), and the Eulerian numbers of the second kind as their coefficients.

Here are some values of the second order Eulerian numbers (sequence A008517 in OEIS):

n \ m	0	1	2	3	4	5	6	7	8
1	1
2	1	2
3	1	8	6
4	1	22	58	24
5	1	52	328	444	120
6	1	114	1452	4400	3708	720
7	1	240	5610	32120	58140	33984	5040
8	1	494	19950	195800	644020	785304	341136	40320
9	1	1004	67260	1062500	5765500	12440064	11026296	3733920	362880

The sum of the n-th row, which is also the value P_n(1), is then (2n−1)!!.