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



So

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


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



Task

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

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



See also

 OEIS:A000110 Bell or exponential numbers
 OEIS:A011971 Aitken's array
 
// 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
 