Anonymous user
Bell numbers: Difference between revisions
→With Bell triangle
Line 305:
=={{header|Common Lisp}}==
===With Bell triangle===
<lang lisp>;; The triangle is a list of arrays; each array is a
;; triangle's row; the last row is at the head of the list.
(defun grow-triangle (triangle)
(if (null triangle)
'(#(1))
(let* ((last-array (car triangle))
(last-length (length last-array))
(new-array (make-array (1+ last-length)
:element-type 'integer)))
;; copy over the last element of the last array
(setf (aref new-array 0) (aref last-array (1- last-length)))
;; fill in the rest of the array
(loop for i from 0
;; the last index of the new array is the length
;; of the last array, which is 1 unit shorter
for j from 1 upto last-length
for sum = (+ (aref last-array i) (aref new-array i))
do (setf (aref new-array j) sum))
;; return the grown list
(cons new-array triangle))))
(defun make-triangle (num)
(if (<= num 1)
(grow-triangle nil)
(grow-triangle (make-triangle (1- num)))))
(defun bell (num)
(cond ((< num 0) nil)
((= num 0) 1)
(t (aref (first (make-triangle num)) (1- num)))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Printing section
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defparameter *numbers-to-print*
(append
(loop for i upto 19 collect i)
'(49 50)))
(defun array->list (array)
(loop for i upto (1- (length array))
collect (aref array i)))
(defun print-bell-number (index bell-number)
(format t "B_~d (~:r Bell number) = ~:d~%"
index (1+ index) bell-number))
(defun print-bell-triangle (triangle)
(loop for row in (reverse triangle)
do (format t "~{~d~^, ~}~%" (array->list row))))
;; Final invocation
(loop for n in *numbers-to-print* do
(print-bell-number n (bell n)))
(princ #\newline)
(format t "The first 10 rows of Bell triangle:~%")
(print-bell-triangle (make-triangle 10))</lang>
{{out}}
<pre>B_0 (first Bell number) = 1
B_1 (second Bell number) = 1
B_2 (third Bell number) = 2
B_3 (fourth Bell number) = 5
B_4 (fifth Bell number) = 15
B_5 (sixth Bell number) = 52
B_6 (seventh Bell number) = 203
B_7 (eighth Bell number) = 877
B_8 (ninth Bell number) = 4,140
B_9 (tenth Bell number) = 21,147
B_10 (eleventh Bell number) = 115,975
B_11 (twelfth Bell number) = 678,570
B_12 (thirteenth Bell number) = 4,213,597
B_13 (fourteenth Bell number) = 27,644,437
B_14 (fifteenth Bell number) = 190,899,322
B_15 (sixteenth Bell number) = 1,382,958,545
B_16 (seventeenth Bell number) = 10,480,142,147
B_17 (eighteenth Bell number) = 82,864,869,804
B_18 (nineteenth Bell number) = 682,076,806,159
B_19 (twentieth Bell number) = 5,832,742,205,057
B_49 (fiftieth Bell number) = 10,726,137,154,573,358,400,342,215,518,590,002,633,917,247,281
B_50 (fifty-first Bell number) = 185,724,268,771,078,270,438,257,767,181,908,917,499,221,852,770
The first 10 rows of Bell triangle:
1
1, 2
2, 3, 5
5, 7, 10, 15
15, 20, 27, 37, 52
52, 67, 87, 114, 151, 203
203, 255, 322, 409, 523, 674, 877
877, 1080, 1335, 1657, 2066, 2589, 3263, 4140
4140, 5017, 6097, 7432, 9089, 11155, 13744, 17007, 21147
21147, 25287, 30304, 36401, 43833, 52922, 64077, 77821, 94828, 115975</pre>
===With Stirling numbers of the second kind===
| |||