Motzkin numbers


Write a function that accepts a whole number n and returns the nth Motzkin number.

Oh, oops. The timing numbers are almost meaningless because the testing code has filled in the motzkin-numbers data structure, and the timing code is doing nothing more than reporting the speed of vector references in motzkin-lin. Nevertheless, it does illustrate the exponential vs linear behavior for values of linear that are mostly constant.

 $ cat mkn.rkt  
 #lang racket 
  
 (define (motzkin-exp n) 
  
   ; Return the nth Motzkin number. 
    
   (cond 
  
     ((< n 0) 
        (error "the motzkin of a negative number is undefined")) 
      
     ((< n 2) 
        1) 
  
     (#t 
       (/ (+ (* (+ (* n 2) 1) 
                (motzkin-exp (- n 1))) 
             (* 3 (- n 1) 
                (motzkin-exp (- n 2)))) 
          (+ n 2))))) 
  
  
 (require "evc.rkt") 
  
 (define motzkin-lin 
  
   ; Return the nth Motzkin number. 
    
   (let ((motzkin-numbers (extendible-vector 1 1))) 
  
     (lambda (n) 
  
       (if (< n 0) 
  
         (error "the motzkin of a negative number is undefined") 
  
         (do ((i (motzkin-numbers 'size) (+ i 1))) 
             ((> i n) (motzkin-numbers 'get n)) 
           (motzkin-numbers 'append! 
             (/ (+ (* (+ (* i 2) 1) 
                      (motzkin-numbers 'get (- i 1))) 
                   (* 3 (- i 1) 
                      (motzkin-numbers 'get (- i 2)))) 
                (+ i 2)))))))) 
  
  
 (module+ test 
  
   (require rackunit "utl.rkt") 
  
   (define motzkins '( 1 1 2 4 9 21 51 127 323 835 2188 5798 
     15511 41835 113634 310572 853467 2356779 6536382 
     18199284 50852019 142547559 400763223 1129760415 
     3192727797 9043402501 25669818476 73007772802 
     208023278209 593742784829)) 
  
  
   (define (test f) 
     (let loop ((m motzkins) (i 0)) 
       (unless (null? m) 
         (check-equal? (f i) (car m)) 
         (loop (cdr m) (+ i 1))))) 
  
   (test motzkin-exp) 
   (test motzkin-lin) 
  
  
   (define (time f f-str n) 
     (printf "(~a ~a): ~a\n" 
         f-str n  
         (time-it  
          (lambda () 
                 (do ((i 0 (+ i 1))) ((> i n) #t) 
                   (f i))) 
              (lambda () '()) 3))) 
  
   (do ((i 5 (+ i 10))) ((> i 40) (void)) 
     (time motzkin-exp "motzkin-exp" i) 
     (time motzkin-lin "motzkin-lin" i))) 
  
  
 $ raco test mkn.rkt  
 raco test: (submod "mkn.rkt" test) 
 (motzkin-exp 5): (0 . 0) 
 (motzkin-lin 5): (1/3 . 0.4714045207910317) 
 (motzkin-exp 15): (1 . 0) 
 (motzkin-lin 15): (0 . 0) 
 (motzkin-exp 25): (391/3 . 2.6246692913372702) 
 (motzkin-lin 25): (1/3 . 0.4714045207910317) 
 (motzkin-exp 35): (47473/3 . 80.4169689113491) 
 (motzkin-lin 35): (1/3 . 0.4714045207910317) 
 60 tests passed 
  
 $