<-- Back to the home page

Associated Bell Numbers

BnmB_{n\leq m} is the number of partitions of an nn element set such that every block in any partition contains at least mm elements.

They are the sum of the Associated Stirling Numbers for all values k{1...n}k \in \{1...n\}

Basic Recurrence

B0m=1B_{0 \geq m} = 1

Bnm=0 for m>n>0B_{n \geq m} = 0 \text{ for } m > n > 0

Bn,k=Bn,k1i=1nk1n!(k1)!i!(n(k1)i)!Bn(k1)i,k.B_{n, \geq k} = B_{n, \geq k-1} - \sum_{i=1}^{\left\lfloor \frac{n}{k-1} \right\rfloor} \frac{n!}{(k-1)!i!(n-(k-1)i)!} B_{n-(k-1)i, \geq k}.


There is no known formula for the general case.

Generating functions

Exponential generating function

n=0Bnmxnn!=exp(exp(x)i=0m1xii!)\sum_{n=0}^{\infty} \frac{B_{n \geq m} x^n}{n!} = \exp \left( \exp(x) - \sum_{i=0}^{m-1} \frac{x^i}{i!} \right)

Relation to Bell and Associated Bell numbers

Where BnB_n is a Bell number and BnmB_{n \leq m} is a Restricted Bell Number

Bn=i=0n(ni)BimBnim+1B_n = \sum_{i=0}^{n}\binom{n}{i} * B_{i\le m} * B_{n-i\ge m+1}

Bnk=Bni=1n(ni)Bik1Bnik.B_{n \geq k} = B_{n} - \sum_{i=1}^{n} \binom{n}{i} B_{i \leq k-1} B_{n-i \geq k}.

i=0n(ni)Bi2=Bn.\sum_{i=0}^{n} \binom{n}{i} B_{i \geq 2} = B_{n}.

Bn=Bn1B_n = B_{n \geq 1}


Combinatorial and Arithmetical Properties of the Restricted and Associated Bell and Factorial Numbers