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