# Compute the Eulerian number

The Eulerian number A(n, m) is the number of permutations of [1, 2, ..., n] in which exactly m elements are greater than the previous element. These are also called rises. For example, if n = 3, there are 3! = 6 permutations of [1, 2, 3]

1 2 3
< <  2 elements are greater than the previous

1 3 2
< >  1 ...

2 1 3
> <  1 ...

2 3 1
< >  1 ...

3 1 2
> <  1 ...

3 2 1
> >  0 ...


So the outputs for A(3, m) for m in [0, 1, 2, 3] will be

A(3, 0) = 1
A(3, 1) = 4
A(3, 2) = 1
A(3, 3) = 0


Also, this is the OEIS sequence A173018.

## Rules

• This is so the shortest code wins.
• The input n will be a nonnegative integer and m will be a integer in the range [0, 1, ..., n].

## Test Cases

n   m   A(n, m)
0   0   1
1   0   1
1   1   0
2   0   1
2   1   1
2   2   0
3   0   1
3   1   4
3   2   1
3   3   0
4   0   1
4   1   11
4   2   11
4   3   1
4   4   0
5   1   26
7   4   1191
9   5   88234
10  5   1310354
10  7   47840
10  10  0
12  2   478271
15  6   311387598411
17  1   131054
20  16  1026509354985
42  42  0

• Any limits on n, m? – Loovjo Oct 19 '16 at 15:45
• There is no limit, but it's not required that your submission be able to completely execute a test case in a certain amount of time, only have the correct logic. Preferably, I'd like submissions to handle values up to 20, but I left it without a performance requirement to allow brute-force solutions that may only work up to n = 10. – miles Oct 19 '16 at 15:48
• Can the input have m >= n, n > 0? – feersum Oct 19 '16 at 15:50
• Shouldn't, "m will be a integer in the range [0, 1, ..., n]" be "...[0, 1, ..., n-1]"? – Jonathan Allan Oct 19 '16 at 15:53
• @feersum Your solution can support any m if desired, but I only require that it be valid for 0 <= m <= n with 0 <= n. – miles Oct 19 '16 at 15:54

# Jelly, 8 bytes

Œ!Z>2\Sċ


Try it online! (takes a while) or verify the smaller test cases.

### How it works

Œ!Z>2\Sċ  Main link. Arguments: n, m

Œ!        Generate the matrix of all permutations of [1, ..., n].
Z       Zip/transpose, placing the permutations in the columns.
>2\    Compare columns pairwise with vectorizing greater-than.
This generates a 1 in the column for each rise in that permutation.
S   Compute the vectorizing sum of the columns, counting the number of rises.
ċ  Count how many times m appears in the computed counts.


## JavaScript (ES6), 5046 45 bytes

f=(n,m,d=n-m)=>m?d&&f(--n,m)*++m+f(n,m-2)*d:1


Based on the recursive formula:

A(n, m) = (n - m)A(n - 1, m - 1) + (m + 1)A(n - 1, m)


### Test cases

f=(n,m,d=n-m)=>m?d&&f(--n,m)*++m+f(n,m-2)*d:1

console.log(f( 0,  0));  // 1
console.log(f( 1,  0));  // 1
console.log(f( 1,  1));  // 0
console.log(f( 2,  0));  // 1
console.log(f( 2,  1));  // 1
console.log(f( 2,  2));  // 0
console.log(f( 3,  0));  // 1
console.log(f( 3,  1));  // 4
console.log(f( 3,  2));  // 1
console.log(f( 3,  3));  // 0
console.log(f( 4,  0));  // 1
console.log(f( 4,  1));  // 11
console.log(f( 4,  2));  // 11
console.log(f( 4,  3));  // 1
console.log(f( 4,  4));  // 0
console.log(f( 5,  1));  // 26
console.log(f( 7,  4));  // 1191
console.log(f( 9,  5));  // 88234
console.log(f(10,  5));  // 1310354
console.log(f(10,  7));  // 47840
console.log(f(10, 10));  // 0
console.log(f(12,  2));  // 478271
console.log(f(15,  6));  // 311387598411
console.log(f(17,  1));  // 131054
console.log(f(20, 16));  // 1026509354985
console.log(f(42, 42));  // 0

# MATL, 10 bytes

:Y@!d0>s=s


Try it online!

### Explanation

Consider as an example inputs n=3, m=1. You can place a % symbol to comment out the code from that point onwards and thus see the intermediate results. For example, the link shows the stack after the first step.

:      % Input n implicitly. Push [1 2 ... n]
% STACK: [1 2 ... n]
Y@     % Matrix of all permutations, one on each row
% STACK: [1 2 3; 1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1]
!      % Transpose
% STACK: [1 1 2 2 3 3; 2 3 1 3 1 2; 3 2 3 1 2 1]
d      % Consecutive differences along each column
% STACK: [1 2 -1 1 -2 -1; 1 -1 2 -2 1 -1]
0>     % True for positive entries
% STACK: [1 1 0 1 0 0; 1 0 1 0 1 0]
s      % Sum of each column
% STACK: [2 1 1 1 1 0]
=      % Input m implicitly. Test each entry for equality with m
% STACK: [0 1 1 1 1 0]
s      % Sum. Implicitly display
% STACK: 4


## CJam (21 19 bytes - or 18 if argument order is free)

{\e!f{2ew::>1b=}1b}


This is an anonymous block (function) which takes n m on the stack. (If it's permitted to take m n on the stack then the \ can be saved). It computes all permutations and filters, so the online test suite must be rather limited.

Thanks to Martin for pointing out an approximation to filter-with-parameter.

### Dissection

{        e# Define a block. Stack: n m
\      e#   Flip the stack to give m n
e!f{   e#   Generate permutations of [0 .. n-1] and map with parameter m
2ew  e#     Stack: m perm; generate the list of n-1 pairs of consecutive
e#     elements of perm
::>  e#     Map each pair to 1 if it's a rise and 0 if it's a fall
1b   e#     Count the falls
=    e#     Map to 1 if there are m falls and 0 otherwise
}
1b     e#   Count the permutations with m falls
}


Note that the Eulerian numbers are symmetric: E(n, m) = E(n, n-m), so it's irrelevant whether you count falls or rises.

### Efficiently: 32 bytes

{1a@{0\+_ee::*(;\W%ee::*W%.+}*=}


This implements the recurrence on whole rows.

{          e# Define a block. Stack: n m
1a@      e#   Push the row for n=0: [1]; and rotate n to top of stack
{        e#   Repeat n times:
e#     Stack: m previous-row
0\+_   e#     Prepend a 0 to the row and duplicate
ee::*  e#     Multiply each element by its index
e#     This gives A[j] = j * E(i-1, j-1)
(;     e#     Pop the first element, so that A[j] = (j+1) * E(i-1, j)
\W%    e#     Get the other copy of the previous row and reverse it
ee::*  e#     Multiply each element by its index
e#     This gives B[j] = j * E(i-1, i-1-j)
W%     e#     Reverse again, giving B[j] = (i-j) * E(i-1, j-1)
}*
=        e#   Extract the element at index j
}

• It's shorter to avoid the variable by using a map: {e!f{2ew::>1b=}1e=}. Or just for fun: {e!f{2ew::>+:-}0e=} – Martin Ender Oct 19 '16 at 17:26
• That was stupid, of course. The 1e= in the first solution can be 1b. – Martin Ender Oct 19 '16 at 17:28
• You are allowed to use your own argument order – miles Oct 23 '16 at 7:59

# Python, 55 56 bytes

a=lambda n,m:n>=m>0and(n-m)*a(n-1,m-1)-~m*a(n-1,m)or m<1


All tests at repl.it

Applies the recursive formula on OEIS.
Note that +(m+1)*a(n-1,m) is golfed to -~m*a(n-1,m).
(May return boolean values to represent 1 or 0. Returns True when n<0 and m<=0 or m<0.)

• There are various other ways to handle the edge cases. It suffices to handle m<1 ? 1 : m==n ? 0 : formula, equivalently m%n<1 ? (m<1) : formula; or alternatively m<1 ? (n>=0) : formula. – Peter Taylor Oct 19 '16 at 16:34
• I got it, just updating thanks – Jonathan Allan Oct 19 '16 at 16:34
• Since our answers are very similar, and yours was posted first (and is shorter), I'll go ahead and delete mine. – Loovjo Oct 19 '16 at 16:40
• @Loovjo A little bit of frantic tweaking though :( You got an ^vote from me anyway! – Jonathan Allan Oct 19 '16 at 16:42

## Mathematica, 59 56 bytes

_~f~0=1
n_~f~m_:=If[m>n,0,(n-m)f[n-1,m-1]+(m+1)f[n-1,m]]


And here is a 59 byte version implementing the definition more literally:

Count[Count@1/@Sign/@Differences/@Permutations@Range@#,#2]&

• Why not just f[n_,m_]:=... for 49? – Jonathan Allan Oct 19 '16 at 19:59
• @JonathanAllan I'm not sure I understand. How does that handle the base case? – Martin Ender Oct 19 '16 at 20:01
• OK, something was cached - just did it in a new worksheet and it failed with recursion limit. :) – Jonathan Allan Oct 19 '16 at 20:14
• There is also the formula which uses 46 bytes Sum[Binomial[#+1,k](#2+1-k)^#(-1)^k,{k,0,#2}]& which might be possible to golf more – miles Oct 22 '16 at 17:55

## Python, 53 bytes

t=lambda n,k:n and(n-k)*t(n-1,k-1)-~k*t(n-1,k)or k==0


Recursion from OEIS. Outputs Boolean True as 1 when n==k.

# MATLAB / Octave, 40 bytes

@(n,m)sum(sum(diff((perms(1:n))')>0)==m)


This is a port of my MATL answer, in the form of an anonymous function. Call it as ans(7,4).

# GameMaker Language, 62 bytes

This is a recursive script A based on @Arnauld's formula.

n=argument0;m=argument1;return (n-m)*A(n-1,m-1)+(m+1)*A(n-1,m)

• Haven't seen THAT in a while! – tomsmeding Oct 20 '16 at 11:36

# Perl, 98 bytes

sub a{my($b,$c)=@_;return$c?$c>$b?0:($b-$c)*a($b-1,$c-1)+($c+1)*a($b-1,$c):1;}print a(@ARGV[0,1]);


Based on the same property as Arnauld's answer.

# R, 72 bytes

Recursive function following the logic on OEIS.

A=function(n,m)if(!m)1 else if(m-n)0 else(n-m)*A(n-1,m-1)+(m+1)*A(n-1,m)


This challenge turned out to be quite close between the different approaches I tried. For instance, using the wikipedia formula and looping over the sum resulted in 92 bytes:

function(n,m){s=0;if(!n)1 else for(k in -1:m+1)s=c(s,(-1)^k*choose(n+1,k)*(m+1-k)^n);sum(s)}


or the vectorized version for 87 bytes:

function(n,m)if(!m)1 else sum(sapply(-1:m+1,function(k)(-1)^k*choose(n+1,k)*(m+1-k)^n))


and finally the brute force solution (103 bytes) that generates a matrix of all permutations by using the permute package and the function allPerms. This approach only works up to n<8 though.

function(n,m){if(!m)1 else sum(apply(rbind(1:n,permute:::allPerms(n)),1,function(x)sum(diff(x)>0))==m)}


## Racket 141 bytes

(count(λ(x)(= x m))(for/list((t(permutations(range 1(+ 1 n)))))(count
(λ(x)x)(for/list((i(sub1 n)))(>(list-ref t(+ 1 i))(list-ref t i))))))


Ungolfed:

(define (f n m)
(let* ((l (range 1 (add1 n)))                ; create a list till n
(pl (permutations l))                 ; get all permutations
(enl (for/list ((t pl))               ; check each permutation;
(define rl
(for/list ((i (sub1 n)))     ; check if an element is a 'rise'
(list-ref t i))))
(count (lambda(x)x) rl))))     ; how many numbers are 'rises'
(count (lambda(x) (= x m)) enl)))          ; how many permutations had m rises
; i.e. Eulerian number


Testing:

(f 3 0)
(f 3 1)
(f 3 2)
(f 3 3)
(f 4 2)
(f 5 1)
(f 7 4)


Output:

1
4
1
0
11
26
1191


# Actually, 21 19 bytes

This answer uses an algorithm similar to the one Dennis uses in his Jelly answer. The original definition counts < while I count >. This ends up being equivalent in the end. Golfing suggestions welcome. Try it online!

;R╨;\ZdX"i>"£MΣMc


Ungolfing

         Implicit input m, then n.
;        Duplicate n. Stack: n, n, m
R        Push range [1..n].
╨        Push all n-length permutations of the range.
...M   Map the following function over each permutation p.
;\       Duplicate and rotate p so that we have a list of the next elements of p.
Z        Zip rot_p and p.
(order of operands here means the next element is first,
so we need to use > later)
dX       Remove the last pair as we don't compare the last and first elements of the list.
"i>"£    Create a function that will flatten a list and check for a rise.
M        Map that function over all the pairs.
Σ        Count how many rises there are in each permutation.
c        Using the result of the map and the remaining m,
count how many permutations have m rises.
Implicit return.


# Swift 3, 82 88 Bytes

func A(_ n:Int,_ m:Int)->Int{return m<1 ?1:n>m ?(n-m)*A(n-1,m-1)+(m+1)*A(n-1,m):0}

Just the same recursive formula in a language that is definitely not for golf

# J, 28 bytes

+/@((!>:)~*(^~#\.)*_1^])i.,]


Uses the formula

## Usage

   f =: +/@((!>:)~*(^~#\.)*_1^])i.,]
0 f 0
1
1 f 0
1
1 f 1
0
(f"+i.,]) 6
1 57 302 302 57 1 0
20x f 16x
1026509354985


## Explanation

+/@((!>:)~*(^~#\.)*_1^])i.,]  Input: n (LHS), m (RHS)
i.    Range [0, 1, ..., m-1]
]  Get m
,   Join to get k = [0, 1, ..., m]
]       Get k
_1^        Raise -1 to each in k
#\.               Get the length of each suffix of k
Forms the range [m+1, m, ..., 2, 1]
^~                  Raise each value by n
*           Multiply elementwise with (-1)^k
(   )~                      Commute operators
>:                        Increment n
!                          Binomial coefficient, C(n+1, k)
*                   Multiply elementwise
+/@                           Reduce by addition to get the sum and return