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\$
  • \$\begingroup\$ Any limits on n, m? \$\endgroup\$ – Loovjo Oct 19 '16 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 '16 at 15:48
  • \$\begingroup\$ Can the input have m >= n, n > 0? \$\endgroup\$ – feersum Oct 19 '16 at 15:50
  • \$\begingroup\$ Shouldn't, "m will be a integer in the range [0, 1, ..., n]" be "...[0, 1, ..., n-1]"? \$\endgroup\$ – Jonathan Allan Oct 19 '16 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 '16 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\$
  • \$\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\$ – Martin Ender Oct 19 '16 at 17:26
  • \$\begingroup\$ That was stupid, of course. The 1e= in the first solution can be 1b. \$\endgroup\$ – Martin Ender Oct 19 '16 at 17:28
  • \$\begingroup\$ You are allowed to use your own argument order \$\endgroup\$ – miles Oct 23 '16 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\$
  • \$\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\$ – Peter Taylor Oct 19 '16 at 16:34
  • \$\begingroup\$ I got it, just updating thanks \$\endgroup\$ – Jonathan Allan Oct 19 '16 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\$ – Loovjo Oct 19 '16 at 16:40
  • \$\begingroup\$ @Loovjo A little bit of frantic tweaking though :( You got an ^vote from me anyway! \$\endgroup\$ – Jonathan Allan Oct 19 '16 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\$
  • \$\begingroup\$ Why not just f[n_,m_]:=... for 49? \$\endgroup\$ – Jonathan Allan Oct 19 '16 at 19:59
  • \$\begingroup\$ @JonathanAllan I'm not sure I understand. How does that handle the base case? \$\endgroup\$ – Martin Ender Oct 19 '16 at 20:01
  • \$\begingroup\$ OK, something was cached - just did it in a new worksheet and it failed with recursion limit. :) \$\endgroup\$ – Jonathan Allan Oct 19 '16 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 '16 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\$
  • \$\begingroup\$ Haven't seen THAT in a while! \$\endgroup\$ – tomsmeding Oct 20 '16 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, privacy policy and cookie policy

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