1#lang typed/racket/base
2
3(require "types.rkt")
4
5(provide eulerian-number)
6
7(: eulerian-number* : Natural Natural -> Natural)
8;   computes the Eulerian number <n,k>
9;   http://mathworld.wolfram.com/EulerianNumber.html
10(define (eulerian-number* n k)
11  ; Implementation note:
12  ;   Uses standard recurrence : <n,k> = (k+1) <n-1,k> + (n-k) <n-1,k-1>
13  ;   Time: O(n^2)
14  (cond
15    [(= k 0) 1]
16    [else
17     (define: E : (Vectorof Integer)
18       (make-vector (max (+ k 1) (+ n 1)) 0))
19     (vector-set! E 0 1) ; <0,0> = 1
20     (for: ([i : Positive-Integer (in-range 1 (+ n 1))])
21       (for: ([j : Integer (in-range (- i 1) 0 -1)])
22         (vector-set! E j (+ (* (+ j 1) (vector-ref E j))
23                             (* (- i j) (vector-ref E (- j 1)))))))
24     (assert (vector-ref E k) natural?)]))
25
26(: eulerian-number (Integer Integer -> Natural))
27(define (eulerian-number n k)
28  (cond [(n . < . 0)  (raise-argument-error 'eulerian-number "Natural" 0 n k)]
29        [(k . < . 0)  (raise-argument-error 'eulerian-number "Natural" 1 n k)]
30        [else  (eulerian-number* n k)]))
31