13
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ If you use 0-indexing, an input of 3 should output 5 It would ouput 15, right? And with 1-indexing it would output 5 \$\endgroup\$ – Luis Mendo Jul 14 '17 at 8:34
  • \$\begingroup\$ The reasoning behind that was counting the 0th bell number as index 0 in 0-indexing and index 1 in 1-indexing. Your way might be more clear, but the existing answers work like that, so I can't change it now. I just joined this site a few hours ago \$\endgroup\$ – bushdid911 Jul 14 '17 at 8:37
  • \$\begingroup\$ But you say that with 1-indexing, input 3 should output 2. Then what would input 1 give with 1-indexing? \$\endgroup\$ – Luis Mendo Jul 14 '17 at 8:39
  • \$\begingroup\$ 1 -> 1, 2 - > 1, 3 -> 2 (corresponding to the 0th,1st, and 2nd Bell numbers) as opposed to 0 -> 1, 1 -> 1, 2 -> 2 Maybe i am using the wrong terminology \$\endgroup\$ – bushdid911 Jul 14 '17 at 8:42
  • \$\begingroup\$ I think I get it. The first 1 is missing in your example table and output, which confused me \$\endgroup\$ – Luis Mendo Jul 14 '17 at 8:44

22 Answers 22

2
\$\begingroup\$

Jelly, 9 bytes

ṖµṀcæ.߀‘

This uses the formula

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.
\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
8
\$\begingroup\$

Haskell, 36 bytes

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

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

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

Mathematica , 24 bytes

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

-13 bytes from @Kelly Lowder!

\$\endgroup\$
  • \$\begingroup\$ Sum[k^#/k!,{k,0,∞}]/E& is only 24 bytes \$\endgroup\$ – Kelly Lowder Jul 14 '17 at 13:40
3
\$\begingroup\$

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-).

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

MATL, 14 bytes

:dtEw1Zh1Ze/Yo

Input is 0-based. Try it online!

Explanation

This uses the formula

enter image description here

where p Fq (a1, ..., ap; b1, ..., bq; 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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ That's a nice solution. Note that using a built in for Stirling numbers of the second kind would be allowed to compute the Bell numbers (if using Mathematica or similar) \$\endgroup\$ – bushdid911 Jul 14 '17 at 8:40
  • \$\begingroup\$ You can save two bytes directly in the definition of s: since the recursive calls always reduce n and there's no division by k you can lose the *k in the first term. \$\endgroup\$ – Peter Taylor Jul 14 '17 at 11:31
  • \$\begingroup\$ Or you can save a bunch by flattening into one lambda, working on entire rows: B=lambda n,r=[1,0]:n and B(n-1,[k*r[k]+r[k-1]for k in range(len(r))]+[0])or sum(r) \$\endgroup\$ – Peter Taylor Jul 14 '17 at 11:49
  • \$\begingroup\$ as your function B is not recursive and it is your final answer, you can omit the B= to save 2 bytes \$\endgroup\$ – Felipe Nardi Batista Jul 14 '17 at 13:19
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

R, 46 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 42 bytes -- T defaults to TRUE (aka 1) unless it's been set somewhere else \$\endgroup\$ – Giuseppe Jul 14 '17 at 12:12
2
\$\begingroup\$

MATL, 19 18 bytes

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

Uses 0-based input. Based on the recurrence relation

enter image description here

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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???)
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 60 bytes. returning booleans instead of numbers (0,1) is acceptable in python \$\endgroup\$ – Felipe Nardi Batista Jul 14 '17 at 13:16
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 36 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.