Binomial coefficients in Lisp


(defun binomial-coeff (n k)
  (when (<= 0 k n)
    (flet ((f (p q)   
             (do ((j p (- j 1))
                  (f 1 (* j f)))
                  ((= j q) f))))
      (/ (f n (- n k)) (f k 0)))))

Thanks to some of my wonderful students for hints and ideas.

A recursive version:


(defun binomial-coeff-r (n k)
  (cond
    ((or (and (= 0 k) (<= 0 n))
         (and (< 0 k) (= k n))) 1)
    ((< 0 k n) (+ (binomial-coeff-r (- n 1) (- k 1))
                  (binomial-coeff-r (- n 1) k)))
    (t nil)))
Advertisements
Published in: on 10/01/2013 at 18:34  Leave a Comment  

The URI to TrackBack this entry is: https://burubaxair.wordpress.com/2013/01/10/binomial-coefficients-in-lisp/trackback/

RSS feed for comments on this post.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: