<-- Back to the home page

Restricted 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 most mm elements.

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

Basic Recurrence

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

Bnm=Bn for m>=nB_{n \leq m} = B_n \text{ for } m >= n

Bn+1m=k=0m1(nk)BnkmB_{n+1 \leq m}=\sum_{k=0}^{m-1} \binom{n}{k} B_{n-k \leq m}


There is no known formula for the general case.

Bn2=j=0n2(n2j)(2j)!2jj!B_{n \leq 2} = \sum_{j=0}^{\left\lfloor \frac{n}{2} \right\rfloor} \binom{n}{2j} \frac{(2j)!}{2^j j!}

Bn3=i=0n3j=0n2(n3i)(3i)!6ii!(n3i2j)(2jj)j!2jB_{n \leq 3} = \sum_{i=0}^{\left\lfloor \frac{n}{3} \right\rfloor} \sum_{j=0}^{\left\lfloor \frac{n}{2} \right\rfloor} \binom{n}{3i} \frac{(3i)!}{6^i i!} \binom{n-3i}{2j} \binom{2j}{j} \frac{j!}{2^j}

Generating functions

Exponential generating function

n=0Bnmn!xn=exp(i=1mxii!)\sum_{n=0}^\infty \frac{B_{n \leq m}}{n!} x^n = exp(\sum_{i=1}^{m} \frac{x^i}{i!})

Relation to Bell and Associated Bell numbers

Where BnB_n is a Bell number and BnmB_{n \geq m} is an Associated 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}.

Bn=BnB_n = B_{n \leq \infty}


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