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
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(n, 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
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
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]
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.
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 = map snd (iterate (f . uncurry (scanl (+))) (1,[1]))
where f xs = (last xs, xs)
bell :: [Integer] bell = map head bellTri
main = do
putStrLn "First 10 rows of Bell's Triangle" mapM_ print (take 10 bellTri) putStrLn "First 15 Bell numbers" mapM_ print (take 15 bell) putStrLn "50th 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
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
Lua
The numbers in lua default to the system's double representation. A big number library is needed to get accurate results for the 50th row <lang lua></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: 10726137154573358000000000000000000000000000000 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]
Pascal
Calculating in one row <lang pascal>program BellNumbers; uses
gmp;
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 = 49;//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 := ; For i := 0 to MaxIndex do z_init(BList[i]);
BListLenght := 1; z_set_ui(BList[0],1); z_init_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); until BListLenght>=MaxIndex;
BellNumStr:= z_get_str(10,BellNum); writeln(' 50.th Bell number',#13#10,BellNumStr);
//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:
Bell triangles 1 = 1 3 = 1 2 4 = 2 3 5 5 = 5 7 10 15 6 = 15 20 27 37 52 7 = 52 67 87 114 151 203 8 = 203 255 322 409 523 674 877 9 = 877 1080 1335 1657 2066 2589 3263 4140 10 = 4140 5017 6097 7432 9089 11155 13744 17007 21147 11 = 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 .. 25 = 445958869294805289 26 = 4638590332229999353 50.th Bell number 10726137154573358400342215518590002633917247281
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. <lang Phix>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</lang>
- 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)
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( fanArrow(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-------------------------
- compose :: ((a -> a), ...) -> (a -> a)
def compose(*fs):
Composition, from right to left, of a series of functions. return lambda x: reduce( lambda a, f: f(a), fs[::-1], x )
- 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 lambda xs: go(xs)
- fanArrow (&&&) :: (a -> b) -> (a -> c) -> (a -> (b, c))
def fanArrow(f):
A tuple of the outputs of two separate functions applied to the same value. return lambda g: lambda x: (f(x), g(x))
- 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 go(xShow, fxShow, f, xs): ys = [xShow(x) for x in xs] w = max(map(len, ys)) return s + '\n' + '\n'.join(map( lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)), xs, ys )) return lambda xShow: lambda fxShow: lambda f: lambda xs: go( xShow, fxShow, f, xs )
- 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 lambda x: go(x)
- 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. return lambda a: lambda xs: ( accumulate(chain([a], xs), f) )
- 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. return lambda xs: ( xs[0:n] if isinstance(xs, (list, tuple)) else list(islice(xs, n)) )
- uncurry :: (a -> b -> c) -> ((a, b) -> c)
def uncurry(f):
A function over a tuple, derived from a curried function. return lambda tpl: f(tpl[0])(tpl[1])
- 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]
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.*/ !.=; @.= 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 y>x then return 0
if x-y<y then y= x - y _= 1; do j=x-y+1 to x; _= _ * j; end; return _ / fact(y)
/*──────────────────────────────────────────────────────────────────────────────────────*/ fact: procedure expose !.; parse arg x; if !.x\== then return !.x
!= 1; do f=2 to x; != ! * 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
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
Unable to calculate 50th Bell number accurately due to lack of 'big integer' support. <lang ecmascript>import "/fmt" for Fmt
var bellTriangle = Fn.new { |n|
var tri = List.filled(n, []) for (i in 0...n) tri[i] = List.filled(i, 0) tri[1][0] = 1 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(16) System.print("First fifteen Bell numbers:") for (i in 1..15) System.print("%(Fmt.d(2, i)): %(bt[i][0])") System.print("\nThe first ten rows of Bell's triangle:") for (i in 1..10) System.print(bt[i])</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]
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