2
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Please check whether your code is indented correctly. \$\endgroup\$ Nov 17, 2016 at 22:31

2 Answers 2

6
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$ May 28, 2012 at 14:54
  • \$\begingroup\$ 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 \$\endgroup\$
    – bpgergo
    May 28, 2012 at 15:26
  • \$\begingroup\$ 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. \$\endgroup\$ May 28, 2012 at 15:36
  • \$\begingroup\$ mpmath is a Python module (library). You'll need to install that before you can use it. mpmath install instructions \$\endgroup\$
    – bpgergo
    May 28, 2012 at 15:40
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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