Printing nth bell number

Question

Bell number \$B(n)\$ is defined as the number of ways of splitting \$n\$ into any number of parts, also defined as the sum of previous \$n\$ Stirling numbers of second kind.

Here is a snippet of Python code that Wikipedia provides (slightly modified) to print bell numbers:

def bell_numbers(start, stop):
 t = [[1]] ## Initialize the triangle as a two-dimensional array
 c = 1 ## Bell numbers count
 while c <= stop:
 if c >= start:
 yield t[-1][0] ## Yield the Bell number of the previous row
 row = [t[-1][-1]] ## Initialize a new row
 for b in t[-1]:
 row.append(row[-1] + b) ## Populate the new row
 c += 1 ## We have found another Bell number
 t.append(row) ## Append the row to the triangle
 for b in bell_numbers(1, 9):
 print b

But I have to print the \$n\$th bell number, so what I did was I changed the second last line of code as follows:

for b in bell_numbers(n,n)

This does the job, but I was wondering of an even better way to print the \$n\$th bell number.

• 200_success: Please check whether your code is indented correctly.

Answer 1

You can use the Dobinski formula for calculating Bell numbers more efficiently.

Dobinski's formula is basically something like this line, although the actual implementation is a bit more complicated (this function neither returns precise value nor is efficient, see this blogpost for more on this):

import math
ITERATIONS = 1000
def bell_number(N):
 return (1/math.e) * sum([(k**N)/(math.factorial(k)) for k in range(ITERATIONS)])

E.g. you can use the mpmath package to calculate the nth Bell number using this formula:

from mpmath import *
mp.dps = 30
print bell(100)

You can check the implementation here

• Tomarinator: The first method is returning error values as follows, the 5th bell number is actually 52 but this returns 50.767... and same is for other higher bell polynomials as well, I dont understand why this error is showing up.
• bpgergo: I know my bell_number function doesn't return precise value, it is just meant to display the general idea. The reason for the error is described in the referred blogpost, look for this part
• Tomarinator: I see, thanks for this awesome answer, but i cant fully understand what mpmaths is, is it a pyhton library? and how to write the code that uses mpmaths in calculating Bell number,that code returns an error.
• bpgergo: mpmath is a Python module (library). You'll need to install that before you can use it. mpmath install instructions

Answer 2

Change yield t[-1][0] to yield t[-1][-1] so the \$n\$th Bell number is on the \$n\$th line - that is, gives correct output, so the call:

for b in bell_numbers(1, 9):
 print b

prints the correct bell numbers 1 to 9.

So, if you just want the \$n\$th Bell number only:

for b in bell_numbers(n, n):
 print b

or change the code to take just one argument.