Bell numbers
You are encouraged to solve this task according to the task description, using any language you may know.
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
11l
<lang 11l>F bellTriangle(n)
BigInt tri L(i) 0 .< n tri.append([BigInt(0)] * i) tri[1][0] = 1 L(i) 2 .< n tri[i][0] = tri[i - 1][i - 2] L(j) 1 .< i tri[i][j] = tri[i][j - 1] + tri[i - 1][j - 1] R tri
V bt = bellTriangle(51) print(‘First fifteen and fiftieth Bell numbers:’) L(i) 1..15
print(‘#2: #.’.format(i, bt[i][0]))
print(‘50: ’bt[50][0]) print() print(‘The first ten rows of Bell's triangle:’) L(i) 1..10
print(bt[i])</lang>
- Output:
First fifteen and fiftieth Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 50: 10726137154573358400342215518590002633917247281 The first ten rows of Bell's 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]
Ada
<lang Ada> with Ada.Text_IO; use Ada.Text_IO; procedure Main is type Bell_Triangle is array(Positive range <>, Positive range <>) of Natural;
procedure Print_Rows (Row : in Positive; Triangle : in Bell_Triangle) is
begin
if Row in Triangle'Range(1) then
for I in Triangle'First(1) .. Row loop
Put_Line (Triangle (I, 1)'Image);
end loop;
end if;
end Print_Rows;
procedure Print_Triangle (Num : in Positive; Triangle : in Bell_Triangle) is begin if Num in Triangle'Range then for I in Triangle'First(1) .. Num loop for J in Triangle'First(2) .. Num loop if Triangle (I, J) /= 0 then Put (Triangle (I, J)'Image); end if; end loop; New_Line; end loop; end if; end Print_Triangle;
procedure Bell_Numbers is Triangle : Bell_Triangle(1..15, 1..15) := (Others => (Others => 0)); Temp : Positive := 1; begin
Triangle (1, 1) := 1;
for I in Triangle'First(1) + 1 .. Triangle'Last(1) loop Triangle (I, 1) := Temp;
for J in Triangle'First(2) .. Triangle'Last(2) - 1 loop if Triangle (I - 1, J) /= 0 then Triangle (I, J + 1) := Triangle (I, J) + Triangle (I - 1, J); else Temp := Triangle (I, J); exit; end if; end loop; end loop;
Put_Line ("First 15 Bell numbers:"); Print_Rows (15, Triangle);
New_Line;
Put_Line ("First 10 rows of the Bell triangle:"); Print_Triangle (10, Triangle); end Bell_Numbers; begin Bell_Numbers; end Main; </lang>
- Output:
First 15 Bell numbers: 1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322 First 10 rows of the 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
ALGOL 68
Uses Algol 68G's LONG LONG INT to calculate the numbers up to 50. Calculates the numbers using the triangle algorithm but without storing the triangle as a whole - each line of the triangle replaces the previous one. <lang algol68>BEGIN # show some Bell numbers #
PROC show bell = ( INT n, LONG LONG INT bell number )VOID:
print( ( whole( n, -2 ), ": ", whole( bell number, 0 ), newline ) );
INT max bell = 50;
[ 0 : max bell - 2 ]LONG LONG INT a; FOR i TO UPB a DO a[ i ] := 0 OD;
a[ 0 ] := 1;
show bell( 1, a[ 0 ] );
FOR n FROM 0 TO UPB a DO
# replace a with the next line of the triangle #
a[ n ] := a[ 0 ];
FOR j FROM n BY -1 TO 1 DO
a[ j - 1 ] +:= a[ j ]
OD;
IF n < 14 THEN
show bell( n + 2, a[ 0 ] )
ELIF n = UPB a THEN
print( ( "...", newline ) );
show bell( n + 2, a[ 0 ] )
FI
OD
END</lang>
- Output:
1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 ... 50: 10726137154573358400342215518590002633917247281
ALGOL-M
<lang algolm>begin integer function index(row, col); integer row, col; index := row * (row-1)/ 2 + col;
integer ROWS; ROWS := 15; begin
decimal(11) array bell[0:ROWS*(ROWS+1)/2]; integer i, j;
bell[index(1, 0)] := 1.;
for i := 2 step 1 until ROWS do
begin
bell[index(i, 0)] := bell[index(i-1, i-2)];
for j := 1 step 1 until i-1 do
bell[index(i,j)] := bell[index(i,j-1)] + bell[index(i-1,j-1)];
end;
write("First fifteen Bell numbers:");
for i := 1 step 1 until ROWS do
begin
write(i);
writeon(": ");
writeon(bell[index(i,0)]);
end;
write("");
write("First ten rows of Bell's triangle:");
for i := 1 step 1 until 10 do
begin
write("");
for j := 0 step 1 until i-1 do
writeon(bell[index(i,j)]);
end;
end; end</lang>
- Output:
First fifteen Bell numbers:
1: 1.0
2: 1.0
3: 2.0
4: 5.0
5: 15.0
6: 52.0
7: 203.0
8: 877.0
9: 4140.0
10: 21147.0
11: 115975.0
12: 678570.0
13: 4213597.0
14: 27644437.0
15: 190899322.0
First ten rows of Bell's triangle:
1.0
1.0 2.0
2.0 3.0 5.0
5.0 7.0 10.0 15.0
15.0 20.0 27.0 37.0 52.0
52.0 67.0 87.0 114.0 151.0 203.0
203.0 255.0 322.0 409.0 523.0 674.0 877.0
877.0 1080.0 1335.0 1657.0 2066.0 2589.0 3263.0 4140.0
4140.0 5017.0 6097.0 7432.0 9089.0 11155.0 13744.0 17007.0 21147.0
21147.0 25287.0 30304.0 36401.0 43833.0 52922.0 64077.0 77821.0 94828.0 115975.0
APL
<lang apl>bell←{
tr←↑(⊢,(⊂⊃∘⌽+0,+\)∘⊃∘⌽)⍣14⊢,⊂,1 ⎕←'First 15 Bell numbers:' ⎕←tr[;1] ⎕←'First 10 rows of Bells triangle:' ⎕←tr[⍳10;⍳10]
}</lang>
- Output:
First 15 Bell numbers:
1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322
First 10 rows of Bell's triangle:
1 0 0 0 0 0 0 0 0 0
1 2 0 0 0 0 0 0 0 0
2 3 5 0 0 0 0 0 0 0
5 7 10 15 0 0 0 0 0 0
15 20 27 37 52 0 0 0 0 0
52 67 87 114 151 203 0 0 0 0
203 255 322 409 523 674 877 0 0 0
877 1080 1335 1657 2066 2589 3263 4140 0 0
4140 5017 6097 7432 9089 11155 13744 17007 21147 0
21147 25287 30304 36401 43833 52922 64077 77821 94828 115975
Arturo
<lang rebol>bellTriangle: function[n][
tri: map 0..n-1 'x [ map 0..n 'y -> 0 ]
set get tri 1 0 1
loop 2..n-1 'i [
set get tri i 0 get (get tri i-1) i-2
loop 1..i-1 'j [
set get tri i j (get (get tri i) j-1) + ( get (get tri i-1) j-1)
]
]
return tri
] bt: bellTriangle 51
loop 1..15 'x ->
print [x "=>" first bt\[x]]
print ["50 =>" first last bt] print "" print "The first ten rows of Bell's triangle:"
loop 1..10 'i ->
print filter bt\[i] => zero?</lang>
- Output:
1 => 1 2 => 1 3 => 2 4 => 5 5 => 15 6 => 52 7 => 203 8 => 877 9 => 4140 10 => 21147 11 => 115975 12 => 678570 13 => 4213597 14 => 27644437 15 => 190899322 50 => 10726137154573358400342215518590002633917247281 The first ten rows of Bell's 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
AutoHotkey
<lang AutoHotkey>;----------------------------------- Bell_triangle(maxRows){ row := 1, col := 1, Arr := [] Arr[row, col] := 1 while (Arr.Count() < maxRows){ row++ max := Arr[row-1].Count() Loop % max{ if (col := A_Index) =1 Arr[row, col] := Arr[row-1, max] Arr[row, col+1] := Arr[row, col] + Arr[row-1, col] } } return Arr }
- -----------------------------------
Show_Bell_Number(Arr){ for i, obj in Arr{ res .= obj.1 "`n" } return Trim(res, "`n") }
- -----------------------------------
Show_Bell_triangle(Arr){ for i, obj in Arr{ for j, v in obj res .= v ", " res := Trim(res, ", ") . "`n" } return Trim(res, "`n") }
- -----------------------------------</lang>
Examples:<lang AutoHotkey>MsgBox % Show_Bell_Number(Bell_triangle(15)) MsgBox % Show_Bell_triangle(Bell_triangle(10)) return</lang>
- Output:
1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322 --------------------------- 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
C
<lang c>#include <stdio.h>
- include <stdlib.h>
// row starts with 1; col < row size_t bellIndex(int row, int col) {
return row * (row - 1) / 2 + col;
}
int getBell(int *bellTri, int row, int col) {
size_t index = bellIndex(row, col); return bellTri[index];
}
void setBell(int *bellTri, int row, int col, int value) {
size_t index = bellIndex(row, col); bellTri[index] = value;
}
int *bellTriangle(int n) {
size_t length = n * (n + 1) / 2; int *tri = calloc(length, sizeof(int)); int i, j;
setBell(tri, 1, 0, 1);
for (i = 2; i <= n; ++i) {
setBell(tri, i, 0, getBell(tri, i - 1, i - 2));
for (j = 1; j < i; ++j) {
int value = getBell(tri, i, j - 1) + getBell(tri, i - 1, j - 1);
setBell(tri, i, j, value);
}
}
return tri;
}
int main() {
const int rows = 15; int *bt = bellTriangle(rows); int i, j;
printf("First fifteen Bell numbers:\n");
for (i = 1; i <= rows; ++i) {
printf("%2d: %d\n", i, getBell(bt, i, 0));
}
printf("\nThe first ten rows of Bell's triangle:\n");
for (i = 1; i <= 10; ++i) {
printf("%d", getBell(bt, i, 0));
for (j = 1; j < i; ++j) {
printf(", %d", getBell(bt, i, j));
}
printf("\n");
}
free(bt); return 0;
}</lang>
- Output:
First fifteen Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 The first ten rows of Bell's 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
C#
<lang csharp>using System; using System.Numerics;
namespace BellNumbers {
public static class Utility {
public static void Init<T>(this T[] array, T value) {
if (null == array) return;
for (int i = 0; i < array.Length; ++i) {
array[i] = value;
}
}
}
class Program {
static BigInteger[][] BellTriangle(int n) {
BigInteger[][] tri = new BigInteger[n][];
for (int i = 0; i < n; ++i) {
tri[i] = new BigInteger[i];
tri[i].Init(BigInteger.Zero);
}
tri[1][0] = 1;
for (int i = 2; i < n; ++i) {
tri[i][0] = tri[i - 1][i - 2];
for (int j = 1; j < i; ++j) {
tri[i][j] = tri[i][j - 1] + tri[i - 1][j - 1];
}
}
return tri;
}
static void Main(string[] args) {
var bt = BellTriangle(51);
Console.WriteLine("First fifteen and fiftieth Bell numbers:");
for (int i = 1; i < 16; ++i) {
Console.WriteLine("{0,2}: {1}", i, bt[i][0]);
}
Console.WriteLine("50: {0}", bt[50][0]);
Console.WriteLine();
Console.WriteLine("The first ten rows of Bell's triangle:");
for (int i = 1; i < 11; ++i) {
//Console.WriteLine(bt[i]);
var it = bt[i].GetEnumerator();
Console.Write("[");
if (it.MoveNext()) {
Console.Write(it.Current);
}
while (it.MoveNext()) {
Console.Write(", ");
Console.Write(it.Current);
}
Console.WriteLine("]");
}
}
}
}</lang>
- Output:
First fifteen and fiftieth Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 50: 10726137154573358400342215518590002633917247281 The first ten rows of Bell's 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]
C++
Requires C++14 or later. If HAVE_BOOST is defined, we use the cpp_int class from Boost so we can display the 50th Bell number, as shown in the output section below. <lang cpp>#include <iostream>
- include <vector>
- ifdef HAVE_BOOST
- include <boost/multiprecision/cpp_int.hpp>
typedef boost::multiprecision::cpp_int integer;
- else
typedef unsigned int integer;
- endif
auto make_bell_triangle(int n) {
std::vector<std::vector<integer>> bell(n);
for (int i = 0; i < n; ++i)
bell[i].assign(i + 1, 0);
bell[0][0] = 1;
for (int i = 1; i < n; ++i) {
std::vector<integer>& row = bell[i];
std::vector<integer>& prev_row = bell[i - 1];
row[0] = prev_row[i - 1];
for (int j = 1; j <= i; ++j)
row[j] = row[j - 1] + prev_row[j - 1];
}
return bell;
}
int main() {
- ifdef HAVE_BOOST
const int size = 50;
- else
const int size = 15;
- endif
auto bell(make_bell_triangle(size));
const int limit = 15;
std::cout << "First " << limit << " Bell numbers:\n";
for (int i = 0; i < limit; ++i)
std::cout << bell[i][0] << '\n';
- ifdef HAVE_BOOST
std::cout << "\n50th Bell number is " << bell[49][0] << "\n\n";
- endif
std::cout << "First 10 rows of the Bell triangle:\n";
for (int i = 0; i < 10; ++i) {
std::cout << bell[i][0];
for (int j = 1; j <= i; ++j)
std::cout << ' ' << bell[i][j];
std::cout << '\n';
}
return 0;
}</lang>
- Output:
First 15 Bell numbers: 1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322 50th Bell number is 10726137154573358400342215518590002633917247281 First 10 rows of the 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
CLU
<lang clu>bell = cluster is make, get
rep = array[int]
idx = proc (row, col: int) returns (int)
return (row * (row - 1) / 2 + col)
end idx
get = proc (tri: cvt, row, col: int) returns (int)
return (tri[idx(row, col)])
end get
make = proc (rows: int) returns (cvt)
length: int := rows * (rows+1) / 2
arr: rep := rep$fill(0, length, 0)
arr[idx(1,0)] := 1
for i: int in int$from_to(2, rows) do
arr[idx(i,0)] := arr[idx(i-1, i-2)]
for j: int in int$from_to(1, i-1) do
arr[idx(i,j)] := arr[idx(i,j-1)] + arr[idx(i-1,j-1)]
end
end
return(arr)
end make
end bell
start_up = proc ()
rows = 15
po: stream := stream$primary_output()
belltri: bell := bell$make(rows)
stream$putl(po, "The first 15 Bell numbers are:")
for i: int in int$from_to(1, rows) do
stream$putl(po, int$unparse(i)
|| ": " || int$unparse(bell$get(belltri, i, 0)))
end
stream$putl(po, "\nThe first 10 rows of the Bell triangle:")
for row: int in int$from_to(1, 10) do
for col: int in int$from_to(0, row-1) do
stream$putright(po, int$unparse(bell$get(belltri, row, col)), 7)
end
stream$putc(po, '\n')
end
end start_up</lang>
- Output:
The first 15 Bell numbers are:
1: 1
2: 1
3: 2
4: 5
5: 15
6: 52
7: 203
8: 877
9: 4140
10: 21147
11: 115975
12: 678570
13: 4213597
14: 27644437
15: 190899322
The first 10 rows of the 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
Common Lisp
via 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>
- Output:
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
via Stirling numbers of the second kind
This solution's algorithm is substantially slower than the algorithm based on the Bell triangle, because of the many nested loops. <lang lisp>;;; Compute bell numbers analytically
- Compute the factorial
(defun fact (n)
(cond ((< n 0) nil)
((< n 2) 1)
(t (* n (fact (1- n))))))
- Compute the binomial coefficient (n choose k)
(defun binomial (n k)
(loop for i from 1 upto k
collect (/ (- (1+ n) i) i) into lst
finally (return (reduce #'* lst))))
- Compute the Stirling number of the second kind
(defun stirling (n k)
(/
(loop for i upto k summing
(* (expt -1 i) (binomial k i) (expt (- k i) n)))
(fact k)))
- Compute the Bell number
(defun bell (n)
(loop for k upto n summing (stirling n k)))
- Printing section
(defparameter *numbers-to-print*
(append
(loop for i upto 19 collect i)
'(49 50)))
(defun print-bell-number (index bell-number)
(format t "B_~d (~:r Bell number) = ~:d~%"
index (1+ index) bell-number))
- Final invocation
(loop for n in *numbers-to-print* do
(print-bell-number n (bell n)))</lang>
- Output:
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
Cowgol
<lang cowgol>include "cowgol.coh";
typedef B is uint32; typedef I is intptr;
sub bellIndex(row: I, col: I): (addr: I) is
addr := (row * (row - 1) / 2 + col) * @bytesof B;
end sub;
sub getBell(row: I, col: I): (bell: B) is
bell := [LOMEM as [B] + bellIndex(row, col)];
end sub;
sub setBell(row: I, col: I, bell: B) is
[LOMEM as [B] + bellIndex(row, col)] := bell;
end sub;
sub bellTriangle(n: I) is
var length := n * (n + 1) / 2;
var bytes := length * @bytesof B;
if HIMEM - LOMEM < bytes then
print("not enough memory\n");
ExitWithError();
end if;
MemZero(LOMEM, bytes);
setBell(1, 0, 1);
var i: I := 2;
while i <= n loop
setBell(i, 0, getBell(i-1, i-2));
var j: I := 1;
while j < i loop
var value := getBell(i, j-1) + getBell(i-1, j-1);
setBell(i, j, value);
j := j + 1;
end loop;
i := i + 1;
end loop;
end sub;
const ROWS := 15; bellTriangle(ROWS); print("First fifteen Bell numbers:\n"); var i: I := 1; while i <= ROWS loop
print_i32(i as uint32);
print(": ");
print_i32(getBell(i, 0) as uint32);
print_nl();
i := i + 1;
end loop;
print("\nThe first ten rows of Bell's triangle:\n"); i := 1; while i <= 10 loop
var j: I := 0;
loop
print_i32(getBell(i, j) as uint32);
j := j + 1;
if j == i then break;
else print(", ");
end if;
end loop;
i := i + 1;
print_nl();
end loop;</lang>
- Output:
First fifteen Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 The first ten rows of Bell's 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
D
<lang d>import std.array : uninitializedArray; import std.bigint; import std.stdio : writeln, writefln;
auto bellTriangle(int n) {
auto tri = uninitializedArray!(BigInt[][])(n);
foreach (i; 0..n) {
tri[i] = uninitializedArray!(BigInt[])(i);
tri[i][] = BigInt(0);
}
tri[1][0] = 1;
foreach (i; 2..n) {
tri[i][0] = tri[i - 1][i - 2];
foreach (j; 1..i) {
tri[i][j] = tri[i][j - 1] + tri[i - 1][j - 1];
}
}
return tri;
}
void main() {
auto bt = bellTriangle(51);
writeln("First fifteen and fiftieth Bell numbers:");
foreach (i; 1..16) {
writefln("%2d: %d", i, bt[i][0]);
}
writeln("50: ", bt[50][0]);
writeln;
writeln("The first ten rows of Bell's triangle:");
foreach (i; 1..11) {
writeln(bt[i]);
}
}</lang>
- Output:
First fifteen and fiftieth Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 50: 10726137154573358400342215518590002633917247281 The first ten rows of Bell's 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]
Delphi
A console application written in Delphi 7. It shows a way of calculating Bell numbers without using a triangle. Output numbering is as in the statement of the task, namely B_0 = 1, B_1 = 1, B_2 = 2, .... <lang Delphi> program BellNumbers;
// For Rosetta Code. // Delphi console application to display the Bell numbers B_0, ..., B_25. // Uses signed 64-bit integers, the largest integer type available in Delphi.
{$APPTYPE CONSOLE}
uses SysUtils; // only for the display
const
MAX_INDEX = 25; // maximum index within the limits of int64
var
n : integer; // index of Bell number j : integer; // loop variable a : array [0..MAX_INDEX - 1] of int64; // working array to build up B_n
{ Subroutine to display that a[0] is the Bell number B_n }
procedure Display();
begin
WriteLn( SysUtils.Format( 'B_%-2d = %d', [n, a[0]]));
end;
(* Main program *) begin
n := 0; a[0] := 1; Display(); // some programmers would prefer Display; while (n < MAX_INDEX) do begin // and give begin a line to itself a[n] := a[0]; for j := n downto 1 do inc( a[j - 1], a[j]); inc(n); Display(); end;
end. </lang>
- Output:
B_0 = 1 B_1 = 1 B_2 = 2 B_3 = 5 B_4 = 15 B_5 = 52 B_6 = 203 B_7 = 877 B_8 = 4140 B_9 = 21147 B_10 = 115975 B_11 = 678570 B_12 = 4213597 B_13 = 27644437 B_14 = 190899322 B_15 = 1382958545 B_16 = 10480142147 B_17 = 82864869804 B_18 = 682076806159 B_19 = 5832742205057 B_20 = 51724158235372 B_21 = 474869816156751 B_22 = 4506715738447323 B_23 = 44152005855084346 B_24 = 445958869294805289 B_25 = 4638590332229999353
Elixir
<lang Elixir> defmodule Bell do
def triangle(), do: Stream.iterate([1], fn l -> bell_row l, [List.last l] end) def numbers(), do: triangle() |> Stream.map(&List.first/1)
defp bell_row([], r), do: Enum.reverse r defp bell_row([a|a_s], r = [r0|_]), do: bell_row(a_s, [a + r0|r])
end
- io.format "The first 15 bell numbers are ~p~n~n",
[Bell.numbers() |> Enum.take(15)]
IO.puts "The 50th Bell number is #{Bell.numbers() |> Enum.take(50) |> List.last}" IO.puts ""
IO.puts "THe first 10 rows of Bell's triangle:" IO.inspect(Bell.triangle() |> Enum.take(10)) </lang>
- Output:
The first 15 bell numbers are [1,1,2,5,15,52,203,877,4140,21147,115975,678570,
4213597,27644437,190899322]
The 50th Bell number is 10726137154573358400342215518590002633917247281
THe first 10 rows of Bell's 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]
]
F#
The function
<lang fsharp> // Generate bell triangle. Nigel Galloway: July 6th., 2019 let bell=Seq.unfold(fun g->Some(g,List.scan(+) (List.last g) g))[1I] </lang>
The Task
<lang fsharp> bell|>Seq.take 10|>Seq.iter(printfn "%A") </lang>
- Output:
[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]
<lang fsharp> bell|>Seq.take 15|>Seq.iter(fun n->printf "%A " (List.head n));printfn "" </lang>
- Output:
1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322
<lang fsharp> printfn "%A" (Seq.head (Seq.item 49 bell)) </lang>
- Output:
10726137154573358400342215518590002633917247281
Factor
via Aitken's array
<lang factor>USING: formatting io kernel math math.matrices sequences vectors ;
- next-row ( prev -- next )
[ 1 1vector ] [ dup last [ + ] accumulate swap suffix! ] if-empty ;
- aitken ( n -- seq )
V{ } clone swap [ next-row dup ] replicate nip ;
0 50 aitken col [ 15 head ] [ last ] bi "First 15 Bell numbers:\n%[%d, %]\n\n50th: %d\n\n" printf "First 10 rows of the Bell triangle:" print 10 aitken [ "%[%d, %]\n" printf ] each</lang>
- Output:
First 15 Bell numbers:
{ 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322 }
50th: 10726137154573358400342215518590002633917247281
First 10 rows of the 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 }
via recurrence relation
This solution makes use of a recurrence relation involving binomial coefficients.
<lang factor>USING: formatting kernel math math.combinatorics sequences ;
- next-bell ( seq -- n )
dup length 1 - [ swap nCk * ] curry map-index sum ;
- bells ( n -- seq )
V{ 1 } clone swap 1 - [ dup next-bell suffix! ] times ;
50 bells [ 15 head ] [ last ] bi "First 15 Bell numbers:\n%[%d, %]\n\n50th: %d\n" printf</lang>
- Output:
First 15 Bell numbers:
{ 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322 }
50th: 10726137154573358400342215518590002633917247281
via Stirling sums
This solution defines Bell numbers in terms of sums of Stirling numbers of the second kind.
<lang factor>USING: formatting kernel math math.extras math.ranges sequences ;
- bell ( m -- n )
[ 1 ] [ dup [1,b] [ stirling ] with map-sum ] if-zero ;
50 [ bell ] { } map-integers [ 15 head ] [ last ] bi "First 15 Bell numbers:\n%[%d, %]\n\n50th: %d\n" printf</lang>
- Output:
As above.
FreeBASIC
<lang freebasic>#define MAX 21
- macro ncp(n, p)
(fact(n)/(fact(p))/(fact(n-p)))
- endmacro
dim as ulongint fact(0 to MAX), bell(0 to MAX) dim as uinteger n=0, k
fact(0) = 1 for k=1 to MAX
fact(k) = k*fact(k-1)
next k
bell(n) = 1 print n, bell(n) for n=0 to MAX-1
for k=0 to n
bell(n+1) += ncp(n, k)*bell(k)
next k
print n+1, bell(n+1)
next n</lang>
Go
<lang go>package main
import (
"fmt" "math/big"
)
func bellTriangle(n int) [][]*big.Int {
tri := make([][]*big.Int, n)
for i := 0; i < n; i++ {
tri[i] = make([]*big.Int, i)
for j := 0; j < i; j++ {
tri[i][j] = new(big.Int)
}
}
tri[1][0].SetUint64(1)
for i := 2; i < n; i++ {
tri[i][0].Set(tri[i-1][i-2])
for j := 1; j < i; j++ {
tri[i][j].Add(tri[i][j-1], tri[i-1][j-1])
}
}
return tri
}
func main() {
bt := bellTriangle(51)
fmt.Println("First fifteen and fiftieth Bell numbers:")
for i := 1; i <= 15; i++ {
fmt.Printf("%2d: %d\n", i, bt[i][0])
}
fmt.Println("50:", bt[50][0])
fmt.Println("\nThe first ten rows of Bell's triangle:")
for i := 1; i <= 10; i++ {
fmt.Println(bt[i])
}
}</lang>
- Output:
First fifteen and fiftieth Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 50: 10726137154573358400342215518590002633917247281 First ten rows of Bell's 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]
Groovy
<lang groovy>class Bell {
private static class BellTriangle {
private List<Integer> arr
BellTriangle(int n) {
int length = (int) (n * (n + 1) / 2)
arr = new ArrayList<>(length)
for (int i = 0; i < length; ++i) {
arr.add(0)
}
set(1, 0, 1)
for (int i = 2; i <= n; ++i) {
set(i, 0, get(i - 1, i - 2))
for (int j = 1; j < i; ++j) {
int value = get(i, j - 1) + get(i - 1, j - 1)
set(i, j, value)
}
}
}
private static int index(int row, int col) {
if (row > 0 && col >= 0 && col < row) {
return row * (row - 1) / 2 + col
} else {
throw new IllegalArgumentException()
}
}
int get(int row, int col) {
int i = index(row, col)
return arr.get(i)
}
void set(int row, int col, int value) {
int i = index(row, col)
arr.set(i, value)
}
}
static void main(String[] args) {
final int rows = 15
BellTriangle bt = new BellTriangle(rows)
System.out.println("First fifteen Bell numbers:")
for (int i = 0; i < rows; ++i) {
System.out.printf("%2d: %d\n", i + 1, bt.get(i + 1, 0))
}
for (int i = 1; i <= 10; ++i) {
System.out.print(bt.get(i, 0))
for (int j = 1; j < i; ++j) {
System.out.printf(", %d", bt.get(i, j))
}
System.out.println()
}
}
}</lang>
- Output:
First fifteen Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 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
Haskell
<lang haskell>bellTri :: Integer bellTri =
let f xs = (last xs, xs) in map snd (iterate (f . uncurry (scanl (+))) (1, [1]))
bell :: [Integer] bell = map head bellTri
main :: IO () main = do
putStrLn "First 10 rows of Bell's Triangle:" mapM_ print (take 10 bellTri) putStrLn "\nFirst 15 Bell numbers:" mapM_ print (take 15 bell) putStrLn "\n50th Bell number:" print (bell !! 49)</lang>
- Output:
First 10 rows of Bell's 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] First 15 Bell numbers: 1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322 50th Bell number: 10726137154573358400342215518590002633917247281
And, of course, in terms of Control.Arrow or Control.Applicative, the triangle function could also be written as:
<lang haskell>import Control.Arrow
bellTri :: Integer bellTri = map snd (iterate ((last &&& id) . uncurry (scanl (+))) (1,[1]))</lang>
or:
<lang haskell>import Control.Applicative
bellTri :: Integer bellTri = map snd (iterate ((liftA2 (,) last id) . uncurry (scanl (+))) (1,[1]))</lang>
or, as an applicative without the need for an import: <lang haskell>bellTri :: Integer bellTri = map snd (iterate (((,) . last <*> id) . uncurry (scanl (+))) (1, [1]))</lang>
J
<lang>
bell=: ([: +/\ (,~ {:))&.>@:{:
,. bell^:(<5) <1
+--------------+ |1 | +--------------+ |1 2 | +--------------+ |2 3 5 | +--------------+ |5 7 10 15 | +--------------+ |15 20 27 37 52| +--------------+
{.&> bell^:(<15) <1
1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322
{:>bell^:49<1x
185724268771078270438257767181908917499221852770 </lang>
Java
<lang java>import java.util.ArrayList; import java.util.List;
public class Bell {
private static class BellTriangle {
private List<Integer> arr;
BellTriangle(int n) {
int length = n * (n + 1) / 2;
arr = new ArrayList<>(length);
for (int i = 0; i < length; ++i) {
arr.add(0);
}
set(1, 0, 1);
for (int i = 2; i <= n; ++i) {
set(i, 0, get(i - 1, i - 2));
for (int j = 1; j < i; ++j) {
int value = get(i, j - 1) + get(i - 1, j - 1);
set(i, j, value);
}
}
}
private int index(int row, int col) {
if (row > 0 && col >= 0 && col < row) {
return row * (row - 1) / 2 + col;
} else {
throw new IllegalArgumentException();
}
}
public int get(int row, int col) {
int i = index(row, col);
return arr.get(i);
}
public void set(int row, int col, int value) {
int i = index(row, col);
arr.set(i, value);
}
}
public static void main(String[] args) {
final int rows = 15;
BellTriangle bt = new BellTriangle(rows);
System.out.println("First fifteen Bell numbers:");
for (int i = 0; i < rows; ++i) {
System.out.printf("%2d: %d\n", i + 1, bt.get(i + 1, 0));
}
for (int i = 1; i <= 10; ++i) {
System.out.print(bt.get(i, 0));
for (int j = 1; j < i; ++j) {
System.out.printf(", %d", bt.get(i, j));
}
System.out.println();
}
}
}</lang>
- Output:
First fifteen Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 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
jq
<lang jq># nth Bell number def bell:
. as $n
| if $n < 0 then "non-negative integer expected"
elif $n < 2 then 1
else
reduce range(1; $n) as $i ([1];
reduce range(1; $i) as $j (.;
.[$i - $j] as $x
| .[$i - $j - 1] += $x )
| .[$i] = .[0] + .[$i - 1] )
| .[$n - 1]
end;
- The task
range(1;51) | bell</lang>
- Output:
For displaying the results, we will first use gojq, the Go implementation of jq, as it supports unbounded-precision integer arithmetic.
1 2 5 15 ... 37450059502461511196505342096431510120174682 628919796303118415420210454071849537746015761 10726137154573358400342215518590002633917247281 185724268771078270438257767181908917499221852770
Using the C-based implementation of jq, the results become inexact from bell(23) onwards:
[1,1] [2,2] ... [21,474869816156751] [22,4506715738447323] # inexact [23,44152005855084344] [24,445958869294805300] ... [49,1.0726137154573358e+46] [50,1.8572426877107823e+47]
Julia
Source: Combinatorics at https://github.com/JuliaMath/Combinatorics.jl/blob/master/src/numbers.jl <lang julia>"""
bellnum(n)
Compute the ``n``th Bell number. """ function bellnum(n::Integer)
if n < 0
throw(DomainError(n))
elseif n < 2
return 1
end
list = Vector{BigInt}(undef, n)
list[1] = 1
for i = 2:n
for j = 1:i - 2
list[i - j - 1] += list[i - j]
end
list[i] = list[1] + list[i - 1]
end
return list[n]
end
for i in 1:50
println(bellnum(i))
end</lang>
- Output:
1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322 1382958545 10480142147 82864869804 682076806159 5832742205057 51724158235372 474869816156751 4506715738447323 44152005855084346 445958869294805289 4638590332229999353 49631246523618756274 545717047936059989389 6160539404599934652455 71339801938860275191172 846749014511809332450147 10293358946226376485095653 128064670049908713818925644 1629595892846007606764728147 21195039388640360462388656799 281600203019560266563340426570 3819714729894818339975525681317 52868366208550447901945575624941 746289892095625330523099540639146 10738823330774692832768857986425209 157450588391204931289324344702531067 2351152507740617628200694077243788988 35742549198872617291353508656626642567 552950118797165484321714693280737767385 8701963427387055089023600531855797148876 139258505266263669602347053993654079693415 2265418219334494002928484444705392276158355 37450059502461511196505342096431510120174682 628919796303118415420210454071849537746015761 10726137154573358400342215518590002633917247281 185724268771078270438257767181908917499221852770
Kotlin
<lang scala>class BellTriangle(n: Int) {
private val arr: Array<Int>
init {
val length = n * (n + 1) / 2
arr = Array(length) { 0 }
set(1, 0, 1)
for (i in 2..n) {
set(i, 0, get(i - 1, i - 2))
for (j in 1 until i) {
val value = get(i, j - 1) + get(i - 1, j - 1)
set(i, j, value)
}
}
}
private fun index(row: Int, col: Int): Int {
require(row > 0)
require(col >= 0)
require(col < row)
return row * (row - 1) / 2 + col
}
operator fun get(row: Int, col: Int): Int {
val i = index(row, col)
return arr[i]
}
private operator fun set(row: Int, col: Int, value: Int) {
val i = index(row, col)
arr[i] = value
}
}
fun main() {
val rows = 15 val bt = BellTriangle(rows)
println("First fifteen Bell numbers:")
for (i in 1..rows) {
println("%2d: %d".format(i, bt[i, 0]))
}
for (i in 1..10) {
print("${bt[i, 0]}")
for (j in 1 until i) {
print(", ${bt[i, j]}")
}
println()
}
}</lang>
- Output:
First fifteen Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 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
Little Man Computer
Demonstrates an algorithm that uses a 1-dimensional array and addition. The maximum integer on the LMC is 999, so the maximum Bell number found is B_7 = 877.
In order to handle arrays, a program for the LMC has to modify its own code. This practice is usually frowned on nowadays, but was standard on very early real-life computers, such as EDSAC. <lang Little Man Computer> // Little Man Computer, for Rosetta Code. // Calculate Bell numbers, using a 1-dimensional array and addition. // // After the calculation of B_n (n > 0), the array contains n elements, // of which B_n is the first. Example to show calculation of B_(n+1): // After calc. of B_3 = 5, array holds: 5, 3, 2 // Extend array by copying B_3 to high end: 5, 3, 2, 5 // Replace 2 by 5 + 2 = 7: 5, 3, 7, 5 // Replace 3 by 7 + 3 = 10: 5, 10, 7, 5 // Replace first 5 by 10 + 5 = 15: 15, 10, 7, 5 // First element of array is now B_4 = 15.
// Initialize; B_0 := 1
LDA c1
STA Bell
LDA c0
STA index
BRA print // skip increment of index
// Increment index of Bell number inc_ix LDA index
ADD c1
STA index
// Here acc = index; print index and Bell number print OUT
LDA colon
OTC // non-standard instruction; cosmetic only
LDA Bell
OUT
LDA index
BRZ inc_ix // if index = 0, skip rest and loop back
SUB c7 // reached maximum index yet?
BRZ done // if so, jump to exit
// Manufacture some instructions
LDA lda_0
ADD index
STA lda_ix
SUB c200 // convert LDA to STA with same address
STA sta_ix
// Copy latest Bell number to end of array lda_0 LDA Bell // load Bell number sta_ix STA 0 // address was filled in above // Manufacture more instructions
LDA lda_ix // load LDA instruction
loop SUB c401 // convert to ADD with address 1 less
STA add_ix_1
ADD c200 // convert to STA
STA sta_ix_1
// Execute instructions; zero addresses were filled in above lda_ix LDA 0 // load element of array add_ix_1 ADD 0 // add to element below sta_ix_1 STA 0 // update element below
LDA sta_ix_1 // load previous STA instruction
SUB sta_Bell // does it refer to first element of array?
BRZ inc_ix // yes, loop to inc index and print
LDA lda_ix // no, repeat with addresses 1 less
SUB c1
STA lda_ix
BRA loop
// Here when done done HLT // Constants colon DAT 58 c0 DAT 0 c1 DAT 1 c7 DAT 7 // maximum index c200 DAT 200 c401 DAT 401 sta_Bell STA Bell // not executed; used for comparison // Variables index DAT Bell DAT // Rest of array goes here // end </lang>
- Output:
[formatted manually] 0:1 1:1 2:2 3:5 4:15 5:52 6:203 7:877
Lua
<lang lua>-- Bell numbers in Lua -- db 6/11/2020 (to replace missing original)
local function bellTriangle(n)
local tri = { {1} }
for i = 2, n do
tri[i] = { tri[i-1][i-1] }
for j = 2, i do
tri[i][j] = tri[i][j-1] + tri[i-1][j-1]
end
end
return tri
end
local N = 25 -- in lieu of 50, practical limit with double precision floats local tri = bellTriangle(N)
print("First 15 and "..N.."th Bell numbers:") for i = 1, 15 do
print(i, tri[i][1])
end print(N, tri[N][1])
print()
print("First 10 rows of Bell triangle:") for i = 1, 10 do
print("[ " .. table.concat(tri[i],", ") .. " ]")
end</lang>
- Output:
First 15 and 25th Bell numbers: 1 1 2 1 3 2 4 5 5 15 6 52 7 203 8 877 9 4140 10 21147 11 115975 12 678570 13 4213597 14 27644437 15 190899322 25 445958869294805289 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 ]
Maple
<lang maple>bell1:=proc(n)
option remember; add(binomial(n-1,k)*bell1(k),k=0..n-1)
end: bell1(0):=1:
bell1(50);
- 185724268771078270438257767181908917499221852770
combinat[bell](50);
- 185724268771078270438257767181908917499221852770
bell1~([$0..20]);
- [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570,
- 4213597, 27644437, 190899322, 1382958545, 10480142147,
- 82864869804, 682076806159, 5832742205057, 51724158235372]</lang>
Mathematica / Wolfram Language
Function definition: <lang Mathematica> BellTriangle[n_Integer?Positive] := NestList[Accumulate[# /. {a___, b_} :> {b, a, b}] &, {1}, n - 1]; BellNumber[n_Integer] := BellTriangle[n]n, 1; </lang>
Output: <lang Mathematica> In[51]:= Array[BellNumber, 25]
Out[51]= {1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, \ 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, \ 682076806159, 5832742205057, 51724158235372, 474869816156751, \ 4506715738447323, 44152005855084346, 445958869294805289}
In[52]:= BellTriangle[10]
Out[52]= {{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}}
</lang>
Nim
Using Recurrence relation
<lang Nim>import math
iterator b(): int =
## Iterator yielding the bell numbers.
var numbers = @[1]
yield 1
var n = 0
while true:
var next = 0
for k in 0..n:
next += binom(n, k) * numbers[k]
numbers.add(next)
yield next
inc n
when isMainModule:
import strformat
const Limit = 25 # Maximum index beyond which an overflow occurs.
echo "Bell numbers from B0 to B25:"
var i = 0
for n in b():
echo fmt"{i:2d}: {n:>20d}"
inc i
if i > Limit:
break</lang>
- Output:
Bell numbers from B0 to B25: 0: 1 1: 1 2: 2 3: 5 4: 15 5: 52 6: 203 7: 877 8: 4140 9: 21147 10: 115975 11: 678570 12: 4213597 13: 27644437 14: 190899322 15: 1382958545 16: 10480142147 17: 82864869804 18: 682076806159 19: 5832742205057 20: 51724158235372 21: 474869816156751 22: 4506715738447323 23: 44152005855084346 24: 445958869294805289 25: 4638590332229999353
Using Bell triangle
<lang Nim>iterator b(): int =
## Iterator yielding the bell numbers.
var row = @[1]
yield 1
yield 1
while true:
var newRow = newSeq[int](row.len + 1)
newRow[0] = row[^1]
for i in 1..newRow.high:
newRow[i] = newRow[i - 1] + row[i - 1]
row.shallowCopy(newRow)
yield row[^1] # The last value of the row is one step ahead of the first one.
iterator bellTriangle(): seq[int] =
## Iterator yielding the rows of the Bell triangle.
var row = @[1]
yield row
while true:
var newRow = newSeq[int](row.len + 1)
newRow[0] = row[^1]
for i in 1..newRow.high:
newRow[i] = newRow[i - 1] + row[i - 1]
row.shallowCopy(newRow)
yield row
when isMainModule:
import strformat import strutils
const Limit = 25 # Maximum index beyond which an overflow occurs.
echo "Bell numbers from B0 to B25:"
var i = 0
for n in b():
echo fmt"{i:2d}: {n:>20d}"
inc i
if i > Limit:
break
echo "\nFirst ten rows of Bell triangle:"
i = 0
for row in bellTriangle():
inc i
var line = ""
for val in row:
line.addSep(" ", 0)
line.add(fmt"{val:6d}")
echo line
if i == 10:
break</lang>
- Output:
Bell numbers from B0 to B25:
0: 1
1: 1
2: 2
3: 5
4: 15
5: 52
6: 203
7: 877
8: 4140
9: 21147
10: 115975
11: 678570
12: 4213597
13: 27644437
14: 190899322
15: 1382958545
16: 10480142147
17: 82864869804
18: 682076806159
19: 5832742205057
20: 51724158235372
21: 474869816156751
22: 4506715738447323
23: 44152005855084346
24: 445958869294805289
25: 4638590332229999353
First ten 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
PARIGP
From the code at OEIS A000110, <lang> genit(maxx=50)={bell=List(); for(n=0,maxx,q=sum(k=0,n,stirling(n,k,2)); listput(bell,q));bell} END</lang> Output: List([1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, 51724158235372, 474869816156751, 4506715738447323, 44152005855084346, 445958869294805289, 4638590332229999353, 49631246523618756274, 545717047936059989389, 6160539404599934652455, 71339801938860275191172, 846749014511809332450147, 10293358946226376485095653, 128064670049908713818925644, 1629595892846007606764728147, 21195039388640360462388656799, 281600203019560266563340426570, 3819714729894818339975525681317, 52868366208550447901945575624941, 746289892095625330523099540639146, 10738823330774692832768857986425209, 157450588391204931289324344702531067, 2351152507740617628200694077243788988, 35742549198872617291353508656626642567, 552950118797165484321714693280737767385, 8701963427387055089023600531855797148876, 139258505266263669602347053993654079693415, 2265418219334494002928484444705392276158355, 37450059502461511196505342096431510120174682, 628919796303118415420210454071849537746015761, 10726137154573358400342215518590002633917247281, 185724268771078270438257767181908917499221852770])
Pascal
Using bell's triangle. TIO.RUN up to 5000.See talk for more. <lang pascal>program BellNumbers; {$Ifdef FPC}
{$optimization on,all}
{$ElseIf}
{Apptype console}
{$EndIf} uses
sysutils,gmp;
var
T0 :TDateTime;
procedure BellNumbersUint64(OnlyBellNumbers:Boolean); var
BList : array[0..24] of Uint64; BellNum : Uint64; BListLenght,i :nativeUInt;
begin
IF OnlyBellNUmbers then
Begin
writeln('Bell triangles ');
writeln(' 1 = 1');
end
else
Begin
writeln('Bell numbers');
writeln(' 1 = 1');
writeln(' 2 = 1');
end;
BList[0]:= 1; BListLenght := 1; BellNum := 1; repeat
// For i := BListLenght downto 1 do BList[i] := BList[i-1]; or
move(Blist[0],Blist[1],BListLenght*SizeOf(Blist[0]));
BList[0] := BellNum;
For i := 1 to BListLenght do
Begin
BellNum += BList[i];
BList[i] := BellNum;
end;
// Output
IF OnlyBellNUmbers then
Begin
IF BListLenght<=9 then
Begin
write(BListLenght+1:3,' = ');
For i := 0 to BListLenght do
write(BList[i]:7);
writeln;
end
ELSE
BREAK;
end
else
writeln(BListLenght+2:3,' = ',BellNum);
inc(BListLenght); until BListLenght >= 25; writeln;
end;
procedure BellNumbersMPInteger; const
MaxIndex = 5000;//must be > 0
var //MPInteger as alternative to mpz_t -> selfcleaning
BList : array[0..MaxIndex] of MPInteger; BellNum : MPInteger; BListLenght,i :nativeUInt; BellNumStr : AnsiString;
Begin
BellNumStr := ;
z_init(BellNum);
z_ui_pow_ui(BellNum,10,32767);
BListLenght := z_size(BellNum);
writeln('init length ',BListLenght);
For i := 0 to MaxIndex do
Begin
// z_init2_set(BList[i],BListLenght);
z_add_ui( BList[i],i);
end;
writeln('init length ',z_size(BList[0]));
T0 := now;
BListLenght := 1;
z_set_ui(BList[0],1);
z_set_ui(BellNum,1);
repeat
//Move does not fit moving interfaces // call fpc_intf_assign
For i := BListLenght downto 1 do BList[i] := BList[i-1];
z_set(BList[0],BellNum);
For i := 1 to BListLenght do
Begin
BellNum := z_add(BellNum,BList[i]);
z_set(BList[i],BellNum);
end;
inc(BListLenght);
if (BListLenght+1) MOD 100 = 0 then
Begin
BellNumStr:= z_get_str(10,BellNum);
//z_sizeinbase (BellNum, 10) is not exact :-(
write('Bell(',(IntToStr(BListLenght)):6,') has ',
(IntToStr(Length(BellNumStr))):6,' decimal digits');
writeln(FormatDateTime(' NN:SS.ZZZ',now-T0),'s');
end;
until BListLenght>=MaxIndex;
BellNumStr:= z_get_str(10,BellNum);
writeln(BListLenght:6,'.th ',Length(BellNumStr):8);
//clean up ;-)
BellNumStr := ; z_clear(BellNum); For i := MaxIndex downto 0 do z_clear(BList[i]);
end;
BEGIN
BellNumbersUint64(True);BellNumbersUint64(False); BellNumbersMPInteger;
END.</lang>
- Output:
TIO.RUN Real time: 22.818 s User time: 22.283 s Sys. time: 0.109 s CPU share: 98.13 % Bell triangles 1 = 1 2 = 1 2 3 = 2 3 5 4 = 5 7 10 15 5 = 15 20 27 37 52 6 = 52 67 87 114 151 203 7 = 203 255 322 409 523 674 877 8 = 877 1080 1335 1657 2066 2589 3263 4140 9 = 4140 5017 6097 7432 9089 11155 13744 17007 21147 10 = 21147 25287 30304 36401 43833 52922 64077 77821 94828 115975 Bell numbers 1 = 1 2 = 1 3 = 2 4 = 5 5 = 15 6 = 52 7 = 203 8 = 877 9 = 4140 10 = 21147 11 = 115975 12 = 678570 13 = 4213597 14 = 27644437 15 = 190899322 16 = 1382958545 17 = 10480142147 18 = 82864869804 19 = 682076806159 20 = 5832742205057 21 = 51724158235372 22 = 474869816156751 23 = 4506715738447323 24 = 44152005855084346 25 = 445958869294805289 26 = 4638590332229999353 init length 1701 init length 0 Bell( 99) has 115 decimal digits 00:00.001s Bell( 199) has 275 decimal digits 00:00.005s Bell( 299) has 453 decimal digits 00:00.013s Bell( 399) has 643 decimal digits 00:00.022s Bell( 499) has 842 decimal digits 00:00.035s Bell( 599) has 1048 decimal digits 00:00.051s Bell( 699) has 1260 decimal digits 00:00.071s Bell( 799) has 1478 decimal digits 00:00.098s Bell( 899) has 1700 decimal digits 00:00.128s Bell( 999) has 1926 decimal digits 00:00.167s Bell( 1099) has 2155 decimal digits 00:00.208s Bell( 1199) has 2388 decimal digits 00:00.256s Bell( 1299) has 2625 decimal digits 00:00.310s Bell( 1399) has 2864 decimal digits 00:00.366s Bell( 1499) has 3105 decimal digits 00:00.440s Bell( 1599) has 3349 decimal digits 00:00.517s Bell( 1699) has 3595 decimal digits 00:00.608s Bell( 1799) has 3844 decimal digits 00:00.711s Bell( 1899) has 4095 decimal digits 00:00.808s Bell( 1999) has 4347 decimal digits 00:00.959s Bell( 2099) has 4601 decimal digits 00:01.189s Bell( 2199) has 4858 decimal digits 00:01.373s Bell( 2299) has 5115 decimal digits 00:01.560s Bell( 2399) has 5375 decimal digits 00:01.816s Bell( 2499) has 5636 decimal digits 00:02.065s Bell( 2599) has 5898 decimal digits 00:02.304s Bell( 2699) has 6162 decimal digits 00:02.669s Bell( 2799) has 6428 decimal digits 00:02.962s Bell( 2899) has 6694 decimal digits 00:03.366s Bell( 2999) has 6962 decimal digits 00:03.720s Bell( 3099) has 7231 decimal digits 00:04.145s Bell( 3199) has 7502 decimal digits 00:04.554s Bell( 3299) has 7773 decimal digits 00:05.198s Bell( 3399) has 8046 decimal digits 00:05.657s Bell( 3499) has 8320 decimal digits 00:06.270s Bell( 3599) has 8595 decimal digits 00:06.804s Bell( 3699) has 8871 decimal digits 00:07.475s Bell( 3799) has 9148 decimal digits 00:08.189s Bell( 3899) has 9426 decimal digits 00:08.773s Bell( 3999) has 9704 decimal digits 00:09.563s Bell( 4099) has 9984 decimal digits 00:10.411s Bell( 4199) has 10265 decimal digits 00:11.301s Bell( 4299) has 10547 decimal digits 00:12.230s Bell( 4399) has 10829 decimal digits 00:13.415s Bell( 4499) has 11112 decimal digits 00:14.830s Bell( 4599) has 11397 decimal digits 00:16.630s Bell( 4699) has 11682 decimal digits 00:18.210s Bell( 4799) has 11968 decimal digits 00:19.964s Bell( 4899) has 12254 decimal digits 00:21.332s Bell( 4999) has 12542 decimal digits 00:22.445s 5000.th 12544
Perl
<lang perl>use strict 'vars'; use warnings; use feature 'say'; use bigint;
my @b = 1; my @Aitkens = [1];
push @Aitkens, do {
my @c = $b[-1]; push @c, $b[$_] + $c[$_] for 0..$#b; @b = @c; [@c]
} until (@Aitkens == 50);
my @Bell_numbers = map { @$_[0] } @Aitkens;
say 'First fifteen and fiftieth Bell numbers:'; printf "%2d: %s\n", 1+$_, $Bell_numbers[$_] for 0..14, 49;
say "\nFirst ten rows of Aitken's array:"; printf '%-7d'x@{$Aitkens[$_]}."\n", @{$Aitkens[$_]} for 0..9;</lang>
- Output:
First fifteen and fiftieth Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 50: 10726137154573358400342215518590002633917247281 First ten rows of Aitken's array: 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
Phix
Started out as a translation of Go, but the main routine has now been completely replaced.
with javascript_semantics include mpfr.e function bellTriangle(integer n) -- nb: returns strings to simplify output mpz z = mpz_init(1) string sz = "1" sequence tri = {}, line = {} for i=1 to n do line = prepend(line,mpz_init_set(z)) tri = append(tri,{sz}) for j=2 to length(line) do mpz_add(z,z,line[j]) mpz_set(line[j],z) sz = mpz_get_str(z) tri[$] = append(tri[$],sz) end for end for line = mpz_free(line) z = mpz_free(z) return tri end function sequence bt = bellTriangle(50) printf(1,"First fifteen and fiftieth Bell numbers:\n%s\n50:%s\n\n", {join(vslice(bt[1..15],1)),bt[50][1]}) printf(1,"The first ten rows of Bell's triangle:\n") for i=1 to 10 do printf(1,"%s\n",{join(bt[i])}) end for
- Output:
First fifteen and fiftieth Bell numbers: 1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322 50:10726137154573358400342215518590002633917247281 The first ten rows of Bell's 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
PicoLisp
<lang PicoLisp>(de bell (N)
(make
(setq L (link (list 1)))
(do N
(setq L
(link
(make
(setq A (link (last L)))
(for B L
(setq A (link (+ A B))) ) ) ) ) ) ) )
(setq L (bell 51)) (for N 15
(tab (2 -2 -2) N ":" (get L N 1)) )
(prinl 50 ": " (get L 50 1)) (prinl) (prinl "First ten rows:") (for N 10
(println (get L N)) )</lang>
- Output:
1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 50: 10726137154573358400342215518590002633917247281 First ten rows: (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)
Prolog
<lang prolog>bell(N, Bell):-
bell(N, Bell, [], _).
bell(0, [[1]|T], T, [1]):-!. bell(N, Bell, B, Row):-
N1 is N - 1, bell(N1, Bell, [Row|B], Last), next_row(Row, Last).
next_row([Last|Bell], Bell1):-
last(Bell1, Last), next_row1(Last, Bell, Bell1).
next_row1(_, [], []):-!. next_row1(X, [Y|Rest], [B|Bell]):-
Y is X + B, next_row1(Y, Rest, Bell).
print_bell_numbers(_, 0):-!. print_bell_numbers([[Number|_]|Bell], N):-
writef('%w\n', [Number]),
N1 is N - 1,
print_bell_numbers(Bell, N1).
print_bell_rows(_, 0):-!. print_bell_rows([Row|Rows], N):-
print_bell_row(Row), N1 is N - 1, print_bell_rows(Rows, N1).
print_bell_row([Number]):-
!,
writef('%w\n', [Number]).
print_bell_row([Number|Numbers]):-
writef('%w ', [Number]),
print_bell_row(Numbers).
main:-
bell(49, Bell),
writef('First 15 Bell numbers:\n'),
print_bell_numbers(Bell, 15),
last(Bell, [Number|_]),
writef('\n50th Bell number: %w\n', [Number]),
writef('\nFirst 10 rows of Bell triangle:\n'),
print_bell_rows(Bell, 10).</lang>
- Output:
First 15 Bell numbers: 1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322 50th Bell number: 10726137154573358400342215518590002633917247281 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
Python
Procedural
<lang python>def bellTriangle(n):
tri = [None] * n
for i in xrange(n):
tri[i] = [0] * i
tri[1][0] = 1
for i in xrange(2, n):
tri[i][0] = tri[i - 1][i - 2]
for j in xrange(1, i):
tri[i][j] = tri[i][j - 1] + tri[i - 1][j - 1]
return tri
def main():
bt = bellTriangle(51)
print "First fifteen and fiftieth Bell numbers:"
for i in xrange(1, 16):
print "%2d: %d" % (i, bt[i][0])
print "50:", bt[50][0]
print
print "The first ten rows of Bell's triangle:"
for i in xrange(1, 11):
print bt[i]
main()</lang>
- Output:
First fifteen and fiftieth Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 50: 10726137154573358400342215518590002633917247281 The first ten rows of Bell's 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]
Functional
<lang python>Bell numbers
from itertools import accumulate, chain, islice from operator import add, itemgetter from functools import reduce
- bellNumbers :: [Int]
def bellNumbers():
Bell or exponential numbers.
A000110
return map(itemgetter(0), bellTriangle())
- bellTriangle :: Int
def bellTriangle():
Bell triangle.
return map(
itemgetter(1),
iterate(
compose(
bimap(last)(identity),
list, uncurry(scanl(add))
)
)((1, [1]))
)
- ------------------------- TEST --------------------------
- main :: IO ()
def main():
Tests
showIndex = compose(repr, succ, itemgetter(0))
showValue = compose(repr, itemgetter(1))
print(
fTable(
'First fifteen Bell numbers:'
)(showIndex)(showValue)(identity)(list(
enumerate(take(15)(bellNumbers()))
))
)
print('\nFiftieth Bell number:')
bells = bellNumbers()
drop(49)(bells)
print(
next(bells)
)
print(
fTable(
"\nFirst 10 rows of Bell's triangle:"
)(showIndex)(showValue)(identity)(list(
enumerate(take(10)(bellTriangle()))
))
)
- ------------------------ GENERIC ------------------------
- bimap :: (a -> b) -> (c -> d) -> (a, c) -> (b, d)
def bimap(f):
Tuple instance of bimap.
A tuple of the application of f and g to the
first and second values respectively.
def go(g):
def gox(x):
return (f(x), g(x))
return gox
return go
- compose :: ((a -> a), ...) -> (a -> a)
def compose(*fs):
Composition, from right to left,
of a series of functions.
def go(f, g):
def fg(x):
return f(g(x))
return fg
return reduce(go, fs, identity)
- drop :: Int -> [a] -> [a]
- drop :: Int -> String -> String
def drop(n):
The sublist of xs beginning at
(zero-based) index n.
def go(xs):
if isinstance(xs, (list, tuple, str)):
return xs[n:]
else:
take(n)(xs)
return xs
return go
- fTable :: String -> (a -> String) ->
- (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
Heading -> x display function -> fx display function ->
f -> xs -> tabular string.
def gox(xShow):
def gofx(fxShow):
def gof(f):
def goxs(xs):
ys = [xShow(x) for x in xs]
w = max(map(len, ys))
def arrowed(x, y):
return y.rjust(w, ' ') + ' -> ' + fxShow(f(x))
return s + '\n' + '\n'.join(
map(arrowed, xs, ys)
)
return goxs
return gof
return gofx
return gox
- identity :: a -> a
def identity(x):
The identity function. return x
- iterate :: (a -> a) -> a -> Gen [a]
def iterate(f):
An infinite list of repeated
applications of f to x.
def go(x):
v = x
while True:
yield v
v = f(v)
return go
- last :: [a] -> a
def last(xs):
The last element of a non-empty list. return xs[-1]
- scanl :: (b -> a -> b) -> b -> [a] -> [b]
def scanl(f):
scanl is like reduce, but returns a succession of
intermediate values, building from the left.
def go(a):
def g(xs):
return accumulate(chain([a], xs), f)
return g
return go
- succ :: Enum a => a -> a
def succ(x):
The successor of a value.
For numeric types, (1 +).
return 1 + x
- take :: Int -> [a] -> [a]
- take :: Int -> String -> String
def take(n):
The prefix of xs of length n,
or xs itself if n > length xs.
def go(xs):
return (
xs[0:n]
if isinstance(xs, (list, tuple))
else list(islice(xs, n))
)
return go
- uncurry :: (a -> b -> c) -> ((a, b) -> c)
def uncurry(f):
A function over a tuple,
derived from a curried function.
def go(tpl):
return f(tpl[0])(tpl[1])
return go
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
First fifteen Bell numbers: 1 -> 1 2 -> 1 3 -> 2 4 -> 5 5 -> 15 6 -> 52 7 -> 203 8 -> 877 9 -> 4140 10 -> 21147 11 -> 115975 12 -> 678570 13 -> 4213597 14 -> 27644437 15 -> 190899322 Fiftieth Bell number: 10726137154573358400342215518590002633917247281 First 10 rows of Bell's triangle: 1 -> [1] 2 -> [1, 2] 3 -> [2, 3, 5] 4 -> [5, 7, 10, 15] 5 -> [15, 20, 27, 37, 52] 6 -> [52, 67, 87, 114, 151, 203] 7 -> [203, 255, 322, 409, 523, 674, 877] 8 -> [877, 1080, 1335, 1657, 2066, 2589, 3263, 4140] 9 -> [4140, 5017, 6097, 7432, 9089, 11155, 13744, 17007, 21147] 10 -> [21147, 25287, 30304, 36401, 43833, 52922, 64077, 77821, 94828, 115975]
Quackery
<lang Quackery> [ ' [ [ 1 ] ] ' [ 1 ]
rot 1 - times
[ dup -1 peek nested
swap witheach
[ over -1 peek + join ]
tuck nested join swap ]
drop ] is bell's-triangle ( n --> [ )
[ bell's-triangle [] swap
witheach [ 0 peek join ] ] is bell-numbers ( n --> [ )
say "First fifteen Bell numbers:" cr
15 bell-numbers echo
cr cr
say "Fiftieth Bell number:" cr
50 bell-numbers -1 peek echo
cr cr
say "First ten rows of Bell's triangle:" cr
10 bell's-triangle witheach [ echo cr ]</lang>
- Output:
First fifteen Bell numbers: [ 1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322 ] Fiftieth Bell number: 10726137154573358400342215518590002633917247281 First ten rows of Bell's 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 ]
Racket
<lang racket>#lang racket
(define (build-bell-row previous-row)
(define seed (last previous-row))
(reverse
(let-values (((reversed _) (for/fold ((acc (list seed)) (prev seed))
((pprev previous-row))
(let ((n (+ prev pprev))) (values (cons n acc) n)))))
reversed)))
(define reverse-bell-triangle
(let ((memo (make-hash '((0 . ((1)))))))
(λ (rows) (hash-ref! memo
rows
(λ ()
(let ((prev (reverse-bell-triangle (sub1 rows))))
(cons (build-bell-row (car prev)) prev)))))))
(define bell-triangle (compose reverse reverse-bell-triangle))
(define bell-number (compose caar reverse-bell-triangle))
(module+ main
(map bell-number (range 15)) (bell-number 50) (bell-triangle 10))</lang>
- Output:
'(1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322) 185724268771078270438257767181908917499221852770 '((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) (115975 137122 162409 192713 229114 272947 325869 389946 467767 562595 678570))
Raku
(formerly Perl 6)
via Aitken's array
<lang perl6> my @Aitkens-array = lazy [1], -> @b {
my @c = @b.tail;
@c.push: @b[$_] + @c[$_] for ^@b;
@c
} ... *;
my @Bell-numbers = @Aitkens-array.map: { .head };
say "First fifteen and fiftieth Bell numbers:"; printf "%2d: %s\n", 1+$_, @Bell-numbers[$_] for flat ^15, 49;
say "\nFirst ten rows of Aitken's array:"; .say for @Aitkens-array[^10];</lang>
- Output:
First fifteen and fiftieth Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 50: 10726137154573358400342215518590002633917247281 First ten rows of Aitken's array: [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]
via Recurrence relation
<lang perl6>sub binomial { [*] ($^n … 0) Z/ 1 .. $^p }
my @bell = 1, -> *@s { [+] @s »*« @s.keys.map: { binomial(@s-1, $_) } } … *;
.say for @bell[^15], @bell[50 - 1];</lang>
- Output:
(1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322) 10726137154573358400342215518590002633917247281
via Stirling sums
<lang perl6>my @Stirling_numbers_of_the_second_kind =
(1,),
{ (0, |@^last) »+« (|(@^last »*« @^last.keys), 0) } … *
my @bell = @Stirling_numbers_of_the_second_kind.map: *.sum;
.say for @bell.head(15), @bell[50 - 1];</lang>
- Output:
(1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322) 10726137154573358400342215518590002633917247281
REXX
Bell numbers are the number of ways of placing n labeled balls into n indistinguishable boxes. Bell(0) is defined as 1.
This REXX version uses an index of the Bell number (which starts a zero).
A little optimization was added in calculating the factorial of a number by using memoization.
Also, see this task's discussion to view how the sizes of Bell numbers increase in relation to its index. <lang rexx>/*REXX program calculates and displays a range of Bell numbers (index starts at zero).*/ parse arg LO HI . /*obtain optional arguments from the CL*/ if LO== & HI=="" then do; LO=0; HI=14; end /*Not specified? Then use the default.*/ if LO== | LO=="," then LO= 0 /* " " " " " " */ if HI== | HI=="," then HI= 15 /* " " " " " " */ numeric digits max(9, HI*2) /*crudely calculate the # decimal digs.*/ !.=.; !.0= 1; !.1= 1; @.= 1 /*the FACT function uses memoization.*/
do j=0 for HI+1; $= j==0; jm= j-1 /*JM is used for a shortcut (below). */
do k=0 for j; _= jm - k /* [↓] calculate a Bell # the easy way*/
$= $ + comb(jm, k) * @._ /*COMB≡combination or binomial function*/
end /*k*/
@.j= $ /*assign the Jth Bell number to @ array*/
if j>=LO & j<=HI then say ' Bell('right(j, length(HI) )") = " commas($)
end /*j*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do c=length(_)-3 to 1 by -3; _=insert(',', _, c); end; return _ /*──────────────────────────────────────────────────────────────────────────────────────*/ comb: procedure expose !.; parse arg x,y; if x==y then return 1
if x-y<y then y= x - y; if !.x.y\==. then return !.x.y / fact(y)
_= 1; do j=x-y+1 to x; _= _*j; end; !.x.y= _; return _ / fact(y)
/*──────────────────────────────────────────────────────────────────────────────────────*/ fact: procedure expose !.; parse arg x; if !.x\==. then return !.x; != 1
do f=2 for x-1; != ! * f; end; !.x= !; return !</lang>
- output when using the internal default inputs of: 0 14
Bell( 0) = 1
Bell( 1) = 1
Bell( 2) = 2
Bell( 3) = 5
Bell( 4) = 15
Bell( 5) = 52
Bell( 6) = 203
Bell( 7) = 877
Bell( 8) = 4,140
Bell( 9) = 21,147
Bell(10) = 115,975
Bell(11) = 678,570
Bell(12) = 4,213,597
Bell(13) = 27,644,437
Bell(14) = 190,899,322
- output when using the inputs of: 49 49
Bell(49) = 10,726,137,154,573,358,400,342,215,518,590,002,633,917,247,281
Ruby
<lang ruby>def bellTriangle(n)
tri = Array.new(n)
for i in 0 .. n - 1 do
tri[i] = Array.new(i)
for j in 0 .. i - 1 do
tri[i][j] = 0
end
end
tri[1][0] = 1
for i in 2 .. n - 1 do
tri[i][0] = tri[i - 1][i - 2]
for j in 1 .. i - 1 do
tri[i][j] = tri[i][j - 1] + tri[i - 1][j - 1]
end
end
return tri
end
def main
bt = bellTriangle(51)
puts "First fifteen and fiftieth Bell numbers:"
for i in 1 .. 15 do
puts "%2d: %d" % [i, bt[i][0]]
end
puts "50: %d" % [bt[50][0]]
puts
puts "The first ten rows of Bell's triangle:"
for i in 1 .. 10 do
puts bt[i].inspect
end
end
main()</lang>
- Output:
First fifteen and fiftieth Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 50: 10726137154573358400342215518590002633917247281 The first ten rows of Bell's 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]
Rust
<lang rust>use num::BigUint;
fn main() {
let bt = bell_triangle(51);
// the fifteen first
for i in 1..=15 {
println!("{}: {}", i, bt[i][0]);
}
// the fiftieth
println!("50: {}", bt[50][0])
}
fn bell_triangle(n: usize) -> Vec<Vec<BigUint>> {
let mut tri: Vec<Vec<BigUint>> = Vec::with_capacity(n);
for i in 0..n {
let v = vec![BigUint::from(0u32); i];
tri.push(v);
}
tri[1][0] = BigUint::from(1u32);
for i in 2..n {
tri[i][0] = BigUint::from_bytes_be(&tri[i - 1][i - 2].to_bytes_be());
for j in 1..i {
let added_big_uint = &tri[i][j - 1] + &tri[i - 1][j - 1];
tri[i][j] = BigUint::from_bytes_be(&added_big_uint.to_bytes_be());
}
}
tri
} </lang>
- Output:
1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 50: 10726137154573358400342215518590002633917247281
Scala
<lang scala>import scala.collection.mutable.ListBuffer
object BellNumbers {
class BellTriangle {
val arr: ListBuffer[Int] = ListBuffer.empty[Int]
def this(n: Int) {
this()
val length = n * (n + 1) / 2
for (_ <- 0 until length) {
arr += 0
}
this (1, 0) = 1
for (i <- 2 to n) {
this (i, 0) = this (i - 1, i - 2)
for (j <- 1 until i) {
this (i, j) = this (i, j - 1) + this (i - 1, j - 1)
}
}
}
private def index(row: Int, col: Int): Int = {
require(row > 0, "row must be greater than zero")
require(col >= 0, "col must not be negative")
require(col < row, "col must be less than row")
row * (row - 1) / 2 + col }
def apply(row: Int, col: Int): Int = {
val i = index(row, col)
arr(i)
}
def update(row: Int, col: Int, value: Int): Unit = {
val i = index(row, col)
arr(i) = value
}
}
def main(args: Array[String]): Unit = {
val rows = 15
val bt = new BellTriangle(rows)
println("First fifteen Bell numbers:")
for (i <- 0 until rows) {
printf("%2d: %d\n", i + 1, bt(i + 1, 0))
}
for (i <- 1 to 10) {
print(bt(i, 0))
for (j <- 1 until i) {
print(s", ${bt(i, j)}")
}
println()
}
}
}</lang>
- Output:
First fifteen Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 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
Sidef
Built-in: <lang ruby>say 15.of { .bell }</lang>
Formula as a sum of Stirling numbers of the second kind: <lang ruby>func bell(n) { sum(0..n, {|k| stirling2(n, k) }) }</lang>
Via Aitken's array (optimized for space): <lang ruby>func bell_numbers (n) {
var acc = [] var bell = [1]
(n-1).times {
acc.unshift(bell[-1])
acc.accumulate!
bell.push(acc[-1])
}
bell
}
var B = bell_numbers(50) say "The first 15 Bell numbers: #{B.first(15).join(', ')}" say "The fiftieth Bell number : #{B[50-1]}"</lang>
- Output:
The first 15 Bell numbers: 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322 The fiftieth Bell number : 10726137154573358400342215518590002633917247281
Aitken's array: <lang ruby>func aitken_array (n) {
var A = [1]
1 + (n-1).of { A = [A[-1], A...].accumulate }
}
aitken_array(10).each { .say }</lang>
- Output:
[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]
Aitken's array (recursive definition): <lang ruby>func A((0), (0)) { 1 } func A(n, (0)) { A(n-1, n-1) } func A(n, k) is cached { A(n, k-1) + A(n-1, k-1) }
for n in (^10) {
say (0..n -> map{|k| A(n, k) })
}</lang>
(same output as above)
Swift
<lang swift>public struct BellTriangle<T: BinaryInteger> {
@usableFromInline var arr: [T]
@inlinable
public internal(set) subscript(row row: Int, col col: Int) -> T {
get { arr[row * (row - 1) / 2 + col] }
set { arr[row * (row - 1) / 2 + col] = newValue }
}
@inlinable
public init(n: Int) {
arr = Array(repeating: 0, count: n * (n + 1) / 2)
self[row: 1, col: 0] = 1
for i in 2...n {
self[row: i, col: 0] = self[row: i - 1, col: i - 2]
for j in 1..<i {
self[row: i, col: j] = self[row: i, col: j - 1] + self[row: i - 1, col: j - 1]
}
}
}
}
let tri = BellTriangle<Int>(n: 15)
print("First 15 Bell numbers:")
for i in 1...15 {
print("\(i): \(tri[row: i, col: 0])")
}
for i in 1...10 {
print(tri[row: i, col: 0], terminator: "")
for j in 1..<i {
print(", \(tri[row: i, col: j])", terminator: "")
}
print()
}</lang>
- Output:
First 15 Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 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
Visual Basic .NET
<lang vbnet>Imports System.Numerics Imports System.Runtime.CompilerServices
Module Module1
<Extension()>
Sub Init(Of T)(array As T(), value As T)
If IsNothing(array) Then Return
For i = 0 To array.Length - 1
array(i) = value
Next
End Sub
Function BellTriangle(n As Integer) As BigInteger()()
Dim tri(n - 1)() As BigInteger
For i = 0 To n - 1
Dim temp(i - 1) As BigInteger
tri(i) = temp
tri(i).Init(0)
Next
tri(1)(0) = 1
For i = 2 To n - 1
tri(i)(0) = tri(i - 1)(i - 2)
For j = 1 To i - 1
tri(i)(j) = tri(i)(j - 1) + tri(i - 1)(j - 1)
Next
Next
Return tri
End Function
Sub Main()
Dim bt = BellTriangle(51)
Console.WriteLine("First fifteen Bell numbers:")
For i = 1 To 15
Console.WriteLine("{0,2}: {1}", i, bt(i)(0))
Next
Console.WriteLine("50: {0}", bt(50)(0))
Console.WriteLine()
Console.WriteLine("The first ten rows of Bell's triangle:")
For i = 1 To 10
Dim it = bt(i).GetEnumerator()
Console.Write("[")
If it.MoveNext() Then
Console.Write(it.Current)
End If
While it.MoveNext()
Console.Write(", ")
Console.Write(it.Current)
End While
Console.WriteLine("]")
Next
End Sub
End Module</lang>
- Output:
First fifteen Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 50: 10726137154573358400342215518590002633917247281 The first ten rows of Bell's 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]
Wren
<lang ecmascript>import "/big" for BigInt import "/fmt" for Fmt
var bellTriangle = Fn.new { |n|
var tri = List.filled(n, null)
for (i in 0...n) {
tri[i] = List.filled(i, null)
for (j in 0...i) tri[i][j] = BigInt.zero
}
tri[1][0] = BigInt.one
for (i in 2...n) {
tri[i][0] = tri[i-1][i-2]
for (j in 1...i) {
tri[i][j] = tri[i][j-1] + tri[i-1][j-1]
}
}
return tri
}
var bt = bellTriangle.call(51) System.print("First fifteen and fifitieth Bell numbers:") for (i in 1..15) Fmt.print("$2d: $,i", i, bt[i][0]) Fmt.print("$2d: $,i", 50, bt[50][0]) System.print("\nThe first ten rows of Bell's triangle:") for (i in 1..10) Fmt.print("$,7i", bt[i])</lang>
- Output:
First fifteen and fifitieth Bell numbers:
1: 1
2: 1
3: 2
4: 5
5: 15
6: 52
7: 203
8: 877
9: 4,140
10: 21,147
11: 115,975
12: 678,570
13: 4,213,597
14: 27,644,437
15: 190,899,322
50: 10,726,137,154,573,358,400,342,215,518,590,002,633,917,247,281
The first ten rows of Bell's 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 1,080 1,335 1,657 2,066 2,589 3,263 4,140
4,140 5,017 6,097 7,432 9,089 11,155 13,744 17,007 21,147
21,147 25,287 30,304 36,401 43,833 52,922 64,077 77,821 94,828 115,975
zkl
<lang zkl>fcn bellTriangleW(start=1,wantRow=False){ // --> iterator
Walker.zero().tweak('wrap(row){
row.insert(0,row[-1]);
foreach i in ([1..row.len()-1]){ row[i]+=row[i-1] }
wantRow and row or row[-1]
}.fp(List(start))).push(start,start);
}</lang> <lang zkl>println("First fifteen Bell numbers:"); bellTriangleW().walk(15).println();</lang>
- Output:
First fifteen Bell numbers: L(1,1,2,5,15,52,203,877,4140,21147,115975,678570,4213597,27644437,190899322)
<lang zkl>println("Rows of the Bell Triangle:"); bt:=bellTriangleW(1,True); do(11){ println(bt.next()) }</lang>
- Output:
Rows of the Bell Triangle: 1 1 L(1,2) L(2,3,5) L(5,7,10,15) L(15,20,27,37,52) L(52,67,87,114,151,203) L(203,255,322,409,523,674,877) L(877,1080,1335,1657,2066,2589,3263,4140) L(4140,5017,6097,7432,9089,11155,13744,17007,21147) L(21147,25287,30304,36401,43833,52922,64077,77821,94828,115975)
GNU Multiple Precision Arithmetic Library
<lang zkl>print("The fiftieth Bell number: "); var [const] BI=Import("zklBigNum"); // libGMP bellTriangleW(BI(1)).drop(50).value.println();</lang>
- Output:
The fiftieth Bell number: 10726137154573358400342215518590002633917247281
- Programming Tasks
- Solutions by Programming Task
- 11l
- Ada
- ALGOL 68
- ALGOL-M
- APL
- Arturo
- AutoHotkey
- C
- C sharp
- C++
- Boost
- CLU
- Common Lisp
- Cowgol
- D
- Delphi
- Elixir
- F Sharp
- Factor
- FreeBASIC
- Go
- Groovy
- Haskell
- J
- Java
- Jq
- Julia
- Kotlin
- Little Man Computer
- Lua
- Maple
- Mathematica
- Wolfram Language
- Nim
- PARIGP
- Pascal
- Perl
- Phix
- Phix/mpfr
- PicoLisp
- Prolog
- Python
- Quackery
- Racket
- Raku
- REXX
- Ruby
- Rust
- Num
- Scala
- Sidef
- Swift
- Visual Basic .NET
- Wren
- Wren-fmt
- Zkl
- GMP