Bell or exponential numbers are enumerations of the number of different ways to partition a set that has exactly n elements. Each element of the sequence Bn is the number of partitions of a set of size n where order of the elements and order of the partitions are non-significant. E.G.: {a b} is the same as {b a} and {a} {b} is the same as {b} {a}.



So

B0 = 1 trivially. There is only one way to partition a set with zero elements. { }
B1 = 1 There is only one way to partition a set with one element. {a}
B2 = 2 Two elements may be partitioned in two ways. {a} {b}, {a b}
B3 = 5 Three elements may be partitioned in five ways {a} {b} {c}, {a b} {c}, {a} {b c}, {a c} {b}, {a b c}
 and so on.


A simple way to find the Bell numbers is construct a Bell triangle, also known as an Aitken's array or Peirce triangle, and read off the numbers in the first column of each row. There are other generating algorithms though, and you are free to choose the best / most appropriate for your case.



Task

Write a routine (function, generator, whatever) to generate the Bell number sequence and call the routine to show here, on this page at least the first 15 and (if your language supports big Integers) 50th elements of the sequence.

If you do use the Bell triangle method to generate the numbers, also show the first ten rows of the Bell triangle.



See also

 OEIS:A000110 Bell or exponential numbers
 OEIS:A011971 Aitken's array
; Given the remainder of the previous row and the final cons of the current row,
; extend (in situ) the current row to be a complete row of the Bell triangle.
; Return the final value in the extended row (for use in computing the following row).
 
(define bell-triangle-row-extend
  (lambda (prevrest thisend)
    (cond
      ((null? prevrest)
        (car thisend))
      (else
        (set-cdr! thisend (list (+ (car prevrest) (car thisend))))
        (bell-triangle-row-extend (cdr prevrest) (cdr thisend))))))
 
; Return the Bell triangle of rows 0 through N (as a list of lists).
 
(define bell-triangle
  (lambda (n)
    (let* ((tri (list (list 1)))
           (triend tri)
           (rowendval (caar tri)))
      (do ((index 0 (1+ index)))
          ((>= index n) tri)
        (let ((nextrow (list rowendval)))
          (set! rowendval (bell-triangle-row-extend (car triend) nextrow))
          (set-cdr! triend (list nextrow))
          (set! triend (cdr triend)))))))
 
; Print out the Bell numbers 0 through 19 and 49 thgough 51.
; (The Bell numbers are the first number on each row of the Bell triangle.)
 
(printf "~%The Bell numbers:~%")
(let loop ((triangle (bell-triangle 51)) (count 0))
  (when (pair? triangle)
    (when (or (<= count 19) (>= count 49))
      (printf "  ~2d: ~:d~%" count (caar triangle)))
    (loop (cdr triangle) (1+ count))))
 
; Print out the Bell triangle of 10 rows.
 
(printf "~%First 10 rows of the Bell triangle:~%")
(let rowloop ((triangle (bell-triangle 9)))
  (when (pair? triangle)
    (let eleloop ((rowlist (car triangle)))
      (when (pair? rowlist)
        (printf " ~7:d" (car rowlist))
        (eleloop (cdr rowlist))))
    (newline)
    (rowloop (cdr triangle))))