PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium Entry average rating: High
Bell number (Definition)

The Bell number, denoted $B(n)$ is the total number of partitions of a set with $n$ elements. For $n=0$ , we have $B(0)=1$ . For $n\ge 1$ , we have $$ B(n) = \sum_{k=0}^n S(n,k) \qquad \textrm{for } n \ge 1 $$ where $S(n,k)$ are the Stirling numbers of the second kind.

Proposition 1   $$ B(n+1) = \sum_{k=0}^n \binom{n}{k} B(k) $$
Proof. We count the number of partitions of a set of $n+1$ elements, depending on the size of the block containing the $n+1$ st element. If the block has size $j$ for $1 \le j \le n+1$ then we have $\binom{n}{j-1}$ choices for the $n$ other elements of the block. The remaining $n+1=j$ elements can be partitioned in $B(n+1-j)$ ways. We have therefore that: \begin{eqnarray*} B(n+1) & = & \sum_{j=1}^{n+1}\binom{n}{j-1} B(n+1-j) \\ & = & \sum_{j=1}^{n+1}\binom{n}{n+1-j} B(n+1-j) \\ & = & \sum_{k=0}^n \binom{n}{k} B(k) \end{eqnarray*} $ \qedsymbol$

Using the formula above, one can easily derive the first few Bell numbers. Starting with $n=0$ , the first ten Bell numbers are 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147.




"Bell number" is owned by aoh45. [ full author list (2) ]
(view preamble | get metadata)

View style:

See Also: Stirling numbers of the second kind


Attachments:
Bell's triangle (Data Structure) by PrimeFan
Log in to rate this entry.
(view current ratings)

Cross-references: formula, block, size, Stirling numbers of the second kind, partitions, number
There is 1 reference to this entry.

This is version 3 of Bell number, born on 2004-11-01, modified 2008-07-14.
Object id is 6436, canonical name is BellNumber.
Accessed 7254 times total.

Classification:
AMS MSC11B73 (Number theory :: Sequences and sets :: Bell and Stirling numbers)
 05A18 (Combinatorics :: Enumerative combinatorics :: Partitions of sets)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)