An Eulerian number, denoted gives the number of permutations of nelement sets with k increasing runs of elements. For example, for n = 3 the permutations of {1, 2, 3} contain four increasing runs of length one, namely {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, and {3, 1, 2}. Hence

This can be programmed using the following recursive definition, where n and k are assumed to be integers:

Create a function EulerianNumber[n, k]. You can check your work against Table 5.2 which displays the first few Eulerian numbers.

Because of the triple recursion, you will find it necessary to use a dynamic programming implementation to compute any Eulerian numbers of even modest size.

Hint: Although the above formulas will compute it, you can add the following rule to simplify some of the computation:

See Graham, Knuth, and Patashnik (1994) for a discussion of Eulerian numbers.

Transcribed Image Text:

m = 4. m = 4.