Bell numbers

Bell numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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 B_n 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

B₀ = 1 trivially. There is only one way to partition a set with zero elements. { }

B₁ = 1 There is only one way to partition a set with one element. {a}

B₂ = 2 Two elements may be partitioned in two ways. {a} {b}, {a b}

B₃ = 5 Three elements may be partitioned in five ways {a} {b} {c}, {a b} {c}, {a} {b c}, {a c} {b}, {a b c}

and so on.

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

Task

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

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

See also

• OEIS:A000110 Bell or exponential numbers
• OEIS:A011971 Aitken's array

F#

The function

<lang fsharp> // Generate bell triangle. Nigel Galloway: November 19July 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> printfn "%A" (Seq.head (Seq.item 49 bell)) </lang>

Output:

10726137154573358400342215518590002633917247281

Factor

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

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(50)
   fmt.Println("First fifteen and fiftieth Bell numbers:")
   fmt.Println(" 1: 1")
   for i := 1; i < 15; i++ {
       fmt.Printf("%2d: %d\n", i+1, bt[i][i-1])
   }
   fmt.Println("50:", bt[49][48])
   fmt.Println("\nFirst ten rows of Bell's triangle:")
   for i := 1; i < 11; 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]

Perl 6

via Aitken's array

Works with: Rakudo version 2019.03

<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

Works with: Rakudo version 2019.03

<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

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. <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) )") = "      $
    end   /*j*/

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ 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( 2) =  2
    Bell( 3) =  5
    Bell( 4) =  15
    Bell( 5) =  52
    Bell( 6) =  203
    Bell( 7) =  877
    Bell( 8) =  4140
    Bell( 9) =  21147
    Bell(10) =  115975
    Bell(11) =  678570
    Bell(12) =  4213597
    Bell(13) =  27644437
    Bell(14) =  190899322

output   when using the inputs of:     49   49

    Bell(49) =  10726137154573358400342215518590002633917247281

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)

Library: GMP

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