; challenge.scm  -- Jens Axel Søgaard -- 17th oct 2004

; This is a solution to the challenge set forth by Frank Buss
; at <http://www.frank-buss.de/challenge/index.html>

; We consider the triangle

;       C
;       ^
;      / \
;     /   \
;    /     \
;  A ------- B

; From A we drawn n lines and from B m lines.
; The goal is to count the number of triangles the lines form.

; Theorem
;   The number of triangles is given by the formula
;     B(n+1,2)(m+1) + B(m+1,2)*(n+1) + (n+1)(m+1)     ; n>0, m>0
;   where B denotes a binomial coeffecient.
; Proof
;   Call the line AB for bottom. We look at three cases.

;    i) Triangles where bottom is a side

;          The other sides are formed by one line emanating from A
;          and the other from B. This gives (n+1)(m+1) triangles.

;   ii) Triangles formed from two non-bottom lines from A and
;       one non-bottom line from B.

;          There is B(n+1,2) ways of choosing two non-bottom lines
;          from A. The number of non-bottom lines from B is m+1.
;          This gives B(n+1,2)*(m+1) triangles.

;  iii) Triangles formed from two non-bottom lines from B and
;       one non-bottom line from A.

;         By symmetry with ii) this gives B(m+1,2)*(n+1) triangles


;;; IMPLEMENTATION

(define (fact n)
  (if (= n 0) 1 (* n (fact (- n 1)))))

(define (binomial n m)
  (/ (fact n) (* (fact (- n m)) (fact m))))

(define (triangles n m)
  (cond
    [(= n 0) (+ m 1)]
    [(= m 0) (+ n 1)]
    [else    (+ (* (binomial (+ n 1) 2) (+ m 1))
                (* (binomial (+ m 1) 2) (+ n 1))
                (* (+ n 1) (+ m 1)))]))

;;; TEST

; (map (lambda (n) (triangles n n))
;      (list 0 1 2 3 4 5 6 7 8 9 10))

; => (1 8 27 64 125 216 343 512 729 1000 1331)

; (triangles 2 1) ; => 15