(define (b n k) (define (helper x) (if (= x 1) 1 (* x (helper (- x 1))))) (cond ((= k 1) n) (else (/ (helper n) (* (helper (- n k)) (helper k)) ))))

1. This question asks you to define a SCHEME function that computes the Bell numbers. The nth Bell number is the number of partitions of n objects. To be precise, it is the number of ways to write the set {1,...,n} as a union of a family of disjoint subsets. Equivalently, it is the number of ways to take n items and arrange them into piles. For example, B3, the 3th Bell number, is equal to 5 because the set {1, 2, 3} has 5 different partitions: {1,2,3}, {1,2} U{3}, {1,3} U{2} {1} U {2,3}, and {1} U{2} U {3}. It might be worth defining the function b(n, k) equal to the number of ways that {1,...,n} can be expressed as a partition into exactly k sets; note then that Bn = b(n, 1) + ... + b(n, n). Note, also, that the b(n, k) satisfy a rather nice recursive relationship: b(n, k) = k b(n 1, k) + b(n 1, k 1). (To see this, notice that partitions of {1,...,n} can be divided into two different types: those where n is by itself (in a singleton set), and those where it appears with some other elements. If you remove the element n from the first type of partition, you obtain a partition of n - 1 objects into k 1 setsthere are b(n - 1, k 1) of these; if you remove n from the second type of partition, you obtain a partition of n-1 objects into k setsthere are b(n 1, k) of these.) Use this recursive rule to give a simple SCHEME definition for Bn. If you define a separate auxiliary function to compute b(n, k), make sure you keep it local to your function that computes the Bell number