17
\$\begingroup\$

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
\$\endgroup\$
8
  • \$\begingroup\$ Any limits on n, m? \$\endgroup\$
    – xenia
    Oct 19, 2016 at 15:45
  • \$\begingroup\$ 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. \$\endgroup\$
    – miles
    Oct 19, 2016 at 15:48
  • \$\begingroup\$ Can the input have m >= n, n > 0? \$\endgroup\$
    – feersum
    Oct 19, 2016 at 15:50
  • \$\begingroup\$ Shouldn't, "m will be a integer in the range [0, 1, ..., n]" be "...[0, 1, ..., n-1]"? \$\endgroup\$ Oct 19, 2016 at 15:53
  • \$\begingroup\$ @feersum Your solution can support any m if desired, but I only require that it be valid for 0 <= m <= n with 0 <= n. \$\endgroup\$
    – miles
    Oct 19, 2016 at 15:54

15 Answers 15

9
\$\begingroup\$

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.
\$\endgroup\$
6
\$\begingroup\$

JavaScript (ES6), 50 46 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

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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%.+}*=}

Online test suite.

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#     Pointwise addition
  }*
  =        e#   Extract the element at index j
}
\$\endgroup\$
3
  • \$\begingroup\$ It's shorter to avoid the variable by using a map: {e!f{2ew::>1b=}1e=}. Or just for fun: {e!f{2ew::>+:-}0e=} \$\endgroup\$ Oct 19, 2016 at 17:26
  • \$\begingroup\$ That was stupid, of course. The 1e= in the first solution can be 1b. \$\endgroup\$ Oct 19, 2016 at 17:28
  • \$\begingroup\$ You are allowed to use your own argument order \$\endgroup\$
    – miles
    Oct 23, 2016 at 7:59
3
\$\begingroup\$

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.)

\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$ Oct 19, 2016 at 16:34
  • \$\begingroup\$ I got it, just updating thanks \$\endgroup\$ Oct 19, 2016 at 16:34
  • \$\begingroup\$ Since our answers are very similar, and yours was posted first (and is shorter), I'll go ahead and delete mine. \$\endgroup\$
    – xenia
    Oct 19, 2016 at 16:40
  • \$\begingroup\$ @Loovjo A little bit of frantic tweaking though :( You got an ^vote from me anyway! \$\endgroup\$ Oct 19, 2016 at 16:42
3
\$\begingroup\$

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]&
\$\endgroup\$
4
  • \$\begingroup\$ Why not just f[n_,m_]:=... for 49? \$\endgroup\$ Oct 19, 2016 at 19:59
  • \$\begingroup\$ @JonathanAllan I'm not sure I understand. How does that handle the base case? \$\endgroup\$ Oct 19, 2016 at 20:01
  • \$\begingroup\$ OK, something was cached - just did it in a new worksheet and it failed with recursion limit. :) \$\endgroup\$ Oct 19, 2016 at 20:14
  • \$\begingroup\$ 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 \$\endgroup\$
    – miles
    Oct 22, 2016 at 17:55
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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).

Try it at Ideone.

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
1
  • \$\begingroup\$ Haven't seen THAT in a while! \$\endgroup\$
    – tomsmeding
    Oct 20, 2016 at 11:36
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)}
\$\endgroup\$
1
\$\begingroup\$

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 (add1 i))
                       (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
\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

J, 28 bytes

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

Uses the formula

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.