Bell number diagrams

_____________________________________
Back to Robert's Math Figures
_____________________________________
The Bell numbers (1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, ...) describe the number of ways a set with n elements can be partitioned into disjoint, non-empty subsets.

For example, the set {1, 2, 3} can be partitioned in the following ways:

The nth Bell number can be computed using the formula

 Sum[StirlingS2[n, k], {k, 0, n}] ,
where

 StirlingS2[n, k]

represents the Stirling numbers of the second kind.

Here are some diagrams representing the different ways the sets can be partitioned: a line connects elements in the same subset, and a point represents a singleton subset.

(See below for Mathematica code to generate the lists of partitions.)

{1, 2, 3}, 5 partitions:
Bell 3 (sorry -- doesn't make much sense without the graphics)

{1, 2, 3, 4}, 15 partitions:
Bell 4

{1, 2, 3, 4, 5}, 52 partitions:
Bell 5

{1, 2, 3, 4, 5, 6}, 203 partitions:
Bell 6

{1, 2, 3, 4, 5, 6, 7}, 877 partitions:
(The GIF image is about 125K, so let me know if you're dying to see it.)

__________

Here's some Mathematica 3.0 code to generate the lists of Bell partitions. In short, the program computes lists of partitions recursively, using two cases. We compute BellList[n] by appending the singleton {n} to each element of BellList[n-1], and by appending the number n to each subset of each element in BellList[n-1]; this technique corresponds to the summation of the recurrence for Stirling numbers of the second kind:

StirlingS2[n, k] = StirlingS2[n-1, k-1] + k StirlingS2[n-1, k].
BellList[1] = {{{1}}}; (* the basic case *)

BellList[n_Integer?Positive] := BellList[n] = (* do some caching *)

    Flatten[
      Join[
        Map[ReplaceList[#,{S__}->{S,{n}}]&, BellList[n-1]],

        Map[ReplaceList[#,{b___,{S__},a___}->{b,{S,n},a}]&, BellList[n-1]]],
      1]
Some samples:
BellList[2]//ColumnForm

{{1}, {2}}
{{1, 2}}


BellList[3]//ColumnForm

{{1}, {2}, {3}}
{{1, 2}, {3}}
{{1, 3}, {2}}
{{1}, {2, 3}}
{{1, 2, 3}}


BellList[4]//ColumnForm

{{1}, {2}, {3}, {4}}
{{1, 2}, {3}, {4}}
{{1, 3}, {2}, {4}}
{{1}, {2, 3}, {4}}
{{1, 2, 3}, {4}}
{{1, 4}, {2}, {3}}
{{1}, {2, 4}, {3}}
{{1}, {2}, {3, 4}}
{{1, 2, 4}, {3}}
{{1, 2}, {3, 4}}
{{1, 3, 4}, {2}}
{{1, 3}, {2, 4}}
{{1, 4}, {2, 3}}
{{1}, {2, 3, 4}}
{{1, 2, 3, 4}}
Designed and rendered using Mathematica 3.0 for the Apple Macintosh.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.

Copyright © 1996/7 Robert M. Dickau