;; ! : natnum --> natnum
;; Return n!.
;;
(define (! n) 
  (if (zero? n)
      1
      (* n (! (sub1 n)))))

;; C: natnum, natnum --> natnum
;; Return n-choose-r (where r <= n).
;;
(define (C n r)
  (/ (! n) (! r) (! (- n r))))




;; If there is at least one bad edge, what is the 
;; probability it is found by random probing?


(define max-nodes 650)                 ; Bound on size of incoming class.
(define max-edges (C max-nodes 2))
; 
; Observation: For the 10-coloring example, we
; can improve max-edges down to floor(9*max-nodes/2).


; A minimum bound on the probability of detecting a bad 
; edge in one trial, if at least one exists.
; 
(define error1 (- 1 (/ 1 max-edges)))



; The probability of detecting a bad edge after many trials,
; if at least one exists:
; 
(expt error1 100)