sicp exercise 1.12

;    Exercise 1.12. The following pattern of numbers is called Pascal's triangle.
;                 1
;                1 1
;               1 2 1
;              1 3 3 1
;             1 4 6 4 1
;    The numbers at the edge of the triangle are all 1, and each number inside the
;    triangle is the sum of the two numbers above it. Write a procedure that computes
;    elements of Pascal's triangle by means of a recursive process.


;  Answer: use binomial coefficients
;
;           f(m,n-1)*(m-(n-1))
;  f(m,n) = ------------------
;                  n
;
;  f(m,0) = 1
;


(define f (lambda (m n)
  (if (= n 0) 1
      (/ (* (f m (- n 1)) (- m (- n 1))) n))))




(display (f 3 0))(display " ")
(display (f 3 1))(display " ")
(display (f 3 2))(display " ")
(display (f 3 3))(display " ")
(newline)
(display (f 4 0))(display " ")
(display (f 4 1))(display " ")
(display (f 4 2))(display " ")
(display (f 4 3))(display " ")
(display (f 4 4))(display " ")
(newline)
(display (f 5 5))(display " ")
(display (f 5 4))(display " ")
(display (f 5 3))(display " ")
(display (f 5 2))(display " ")
(display (f 5 1))(display " ")
(display (f 5 0))(display " ")
(newline)
(display (f 49 10))(display " ")