Output the n-th Bell Number

Question

A Bell number (OEIS A000110) is the number of ways to partition a set of n labeled (distinct) elements. The 0th Bell number is defined as 1.

Let's look at some examples (I use brackets to denote the subsets and braces for the partitions):

1: {1}
2: {[1,2]}, {[1],[2]}
3: {[1,2,3]}, {[1,2],[3]}, {[1,3],[2]}, {[2,3],[1]}, {[1],[2],[3]}

There are many ways to compute Bell numbers, and you are free to use any of them. One way will be described here:

The easiest way to compute Bell numbers is to use a number triangle resembling Pascal's triangle for the binomial coefficients. The Bell numbers appear on the edges of the triangle. Starting with 1, each new row in the triangle is constructed by taking the last entry in the previous row as the first entry, and then setting each new entry to its left neighbor plus its upper left neighbor:

1
1    2
2    3    5
5    7   10   15
15  20   27   37   52

You may use 0-indexing or 1-indexing. If you use 0-indexing, an input of 3 should output 5, but should output 2 if you use 1-indexing.

Your program must work up to the 15th Bell number, outputting 1382958545. In theory, your program should be able to handle larger numbers (in other words, don't hardcode the solutions). EDIT: You are not required to handle an input of 0 (for 0-indexing) or 1(for 1-indexing) because it is not computed by the triangle method.

Test cases (assuming 0-indexing):

0 ->  1 (OPTIONAL)
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

Answers using a built-in method (such as BellB[n] in the Wolfram Language) that directly produces Bell numbers will be noncompetitive.

Shortest code (in bytes) wins.

Answer 1

JavaScript (ES6), 47 bytes

f=(n,a=[b=1])=>n--?f(n,[b,...a.map(e=>b+=e)]):b
f=(n,a=[b=1])=>--n?f(n,[b,...a.map(e=>b+=e)]):b

First one is 0-indexed, second is 1-indexed.

Answer 2

Haskell, 36 bytes

head.(iterate(last>>=scanl(+))[1]!!)

Uses the triangle method, correctly handles 0, 0-based.

Answer 3

R, 31 bytes

sum(gmp::Stirling2.all(scan()))

uses the Stirling Number of the Second Kind formula and calculates those numbers with the gmp package; reads from stdin and returns the value as a Big Integer; fails for 0; 1-indexed.

Answer 4

Mathematica , 24 bytes

Sum[k^#/k!,{k,0,∞}]/E&

-13 bytes from @Kelly Lowder!

Answer 5

Jelly, 14 12 11 bytes

ṫ0;⁸+\
1Ç¡Ḣ

Try it online!

Didn't exactly hit the strong points of Jelly with dynamic input to ¡, Ṫ always modifying the array and the lack of a prepending atom (one-byte ;@ or reverse-ṭ).

Answer 6

CJam (19 bytes)

Xa{X\{X+:X}%+}qi*0=

Online demo

Dissection

Xa         e# Start with an array [1]
{          e# Repeat...
  X\       e#   Put a copy of X under the current row
  {X+:X}%  e#   Map over x in row: push (X+=x)
  +        e#   Prepend that copy of last element of the previous row to get the next row
}
qi*        e# ... input() times
0=         e# Select the first element

Answer 7

MATL, 14 bytes

:dtEw1Zh1Ze/Yo

Input is 0-based. Try it online!

Explanation

This uses the formula

where _p F_q (a₁, ..., a_p; b₁, ..., b_q; x) is the generalized hypergeometric function.

:      % Implictly input n. Push array [1 2 ... n]
d      % Consecutive differences: array [1 ... 1] (n-1 entries)
tE     % Duplicate, multiply by 2: array [2 ... 2] (n-1 entries)
w      % Swap
1      % Push 1
Zh     % Hypergeometric function
1Ze    % Push number e
/      % Divide
Yo     % Round (to prevent numerical precision issues). Implicitly display

Answer 8

Python, 42 bytes

f=lambda n,k=0:n<1or k*f(n-1,k)+f(n-1,k+1)

Try it online!

The recursive formula comes from placing n elements into partitions. For each element in turn, we decide whether to place it:

• Into an existing partition, of which there are k choices
• To start a new partition, which increases the number of choices k for future elements

Either way decreases the remaining number n of elements to place. So, we have the recursive formula f(n,k)=k*f(n-1,k)+f(n-1,k+1) and f(0,k)=1, with f(n,0) the n-th Bell number.

Answer 9

Jelly, 9 bytes

ṖµṀcæ.߀‘

This uses the formula

which is closed whenever n < 2.

Try it online!

How it works

ṖµṀcæ.߀‘  Main link. Argument: n

Ṗ          Pop; yield A := [1, ..., n-1].
 µ         Begin a new, monadic chain with argument A.
  Ṁ        Maximum; yield n-1.
   c       Combinatons; compute (n-1)C(k) for each k in A.
      ߀   Recursively map the main link over A.
    æ.     Take the dot product of the results to both sides.
        ‘  Increment; add 1 to the result.

Answer 10

Python 2, 91 bytes

s=lambda n,k:n*k and k*s(n-1,k)+s(n-1,k-1)or n==k
B=lambda n:sum(s(n,k)for k in range(n+1))

Try it online!

B(n) calculated as a sum of Stirling numbers of the second kind.

Answer 11

MATLAB, 128 103 bytes

function q(z)
r(1,1)=1;for x=2:z
r(x,1)=r(x-1,x-1);for y=2:x
r(x,y)=r(x,y-1)+r(x-1,y-1);end
end
r(z,z)

Pretty self explanatory. Omitting a semicolon at the end of a line prints the result.

25 bytes saved thanks to Luis Mendo.

Answer 12

R, 46 bytes

r=1;for(i in 1:scan())r=cumsum(c(r[i],r));r[1]

Try it online!

Answer 13

MATL, 19 18 bytes

1i:"t@q@:qXn*sh]0)

Uses 0-based input. Based on the recurrence relation

Try it online!

Answer 14

Ohm, 15 bytes

2°M^┼ⁿ^!/Σ;αê/≈

Try it online!

Uses Dobinski's forumla (even works for B(0) yay).

Explanation

2°M^┼ⁿ^!/Σ;αê/≈
2°        ;     # Push 100
  M             # Do 100 times...
   ^             # Push index of current iteration
    ┼ⁿ           # Take that to the power of the user input
      ^!         # Push index factorial
        /        # Divide
         Σ       # Sum stack together
           αê   # Push e (2.718...)
             /  # Divide
              ≈ # Round to nearest integer (Srsly why doesn't 05AB1E have this???)

Answer 15

Python (79 bytes)

B=lambda n,r=[1]:n and B(n-1,[r[-1]+sum(r[:i])for i in range(len(r)+1)])or r[0]

Online demo in Python 2, but it also works in Python 3.

This builds Aitken's triangle using a recursive lambda for a golfy loop.

Answer 16

Haskell, 35 bytes

(%0)
n%k|n<1=1|m<-n-1=k*m%k+m%(k+1)

Try it online!

Formula explained in my Python answer.

Answer 17

J, 17 bytes

0{]_1&({+/\@,])1:

Uses the triangle calculation method.

Try it online!

Explanation

0{]_1&({+/\@,])1:  Input: integer n
               1:  The constant 1
  ]                Identity function, get n
   _1&(       )    Call this verb with a fixed left argument of -1 n times
                   on itself starting with a right argument [1]
             ]       Get right argument
       {             Select at index -1 (the last item)
            ,        Join
        +/\@         Find the cumulative sums
0{                 Select at index 0 (the first item)

Answer 18

Python 3, 78 bytes

from math import*
f=lambda n:ceil(sum(k**n/e/factorial(k)for k in range(2*n)))

I decided to try and go a different route for calculation. This uses Dobinski's formula, 0-indexed, doesn't work for 0.

Try it online!

Answer 19

Python 3, 68 60 bytes

Simple recursive construction of the triangle, but it's wildly inefficient for practical purposes. Calculating up to the 15th Bell number causes TIO to time out, but it works on my machine.

This uses 1-indexing, and returns True instead of 1.

f=lambda r,c=0:r<1or c<1and f(r-1,r-1)or f(r-1,c-1)+f(r,c-1)

Try it online!

---

Thanks to @FelipeNardiBatista for saving 8 bytes!

Answer 20

PHP, 72 bytes

recursive function 1-indexed

function f($r,$c=0){return$r?$c?f($r-1,$c-1)+f($r,$c-1):f($r-1,$r-2):1;}

Try it online!

PHP, 86 bytes

0-indexed

for(;$r++<$argn;)for($c=~0;++$c<$r;)$l=$t[$r][$c]=$c?$l+$t[$r-1][$c-1]:($l?:1);echo$l;

Try it online!

PHP, 89 bytes

recursive function 0-indexed

function f($r,$s=NULL){$c=$s??$r-1;return$r>1?$c?f($r-1,$c-1)+f($r,$c-1):f($r-1,$r-2):1;}

Try it online!

Answer 21

Alice, 22 bytes

/oi
\1@/t&wq]&w.q,+k2:

Try it online!

This uses the triangle method. For n=0, this calculates B(1) instead, which is conveniently equal to B(0).

Explanation

This is a standard template for programs that take input in ordinal mode, process it in cardinal mode, and output the result in ordinal mode. A 1 has been added to the template to put that value on the stack below the input.

The program uses the stack as an expanding circular queue to calculate each row of the triangle. During each iteration past the first, one implicit zero below the stack becomes an explicit zero.

1     Append 1 to the implicit empty string on top of the stack
i     Get input n
t&w   Repeat outer loop that many times (push return address n-1 times)
q     Get tape position (initially zero)
]     Move right on tape
&w    On iteration k, push this return address k-1 times
      The following inner loop is run once for each entry in the next row
.     Duplicate top of stack (the last number calculated so far)
q,    Move the entry k spaces down to the top of the stack: this is the appropriate entry
      in the previous row, or (usually) an implicit zero if we're in the first column
+     Add these two numbers
k     Return to pushed address: this statement serves as the end of two loops simultaneously
2:    Divide by two: see below
o     Output as string
@     Terminate

The first iteration effectively assumes an initial stack depth of zero, despite the required 1 at the top of the stack. As a result, the 1 ends up getting added to itself, and the entire triangle is multiplied by 2. Dividing the final result by 2 gives the correct answer.

Answer 22

Pari/GP, 36 bytes

n->n!*Vec(exp(exp(x+O(x^n++))-1))[n]

Try it online!

Answer 23

Mathematica, 5 bytes

Definitely, Mathematica has built-in.

Try it online!

BellB