<-- Back to the home page

Restricted Bell Numbers

Bn≤mB_{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

B0≤m=1B_{0 \leq m} = 1

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

Bn+1≤m=∑k=0m−1(nk)Bn−k≤mB_{n+1 \leq m}=\sum_{k=0}^{m-1} \binom{n}{k} B_{n-k \leq m}

Formulas

There is no known formula for the general case.

Bn≤2=∑j=0⌊n2⌋(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!}

Bn≤3=∑i=0⌊n3⌋∑j=0⌊n2⌋(n3i)(3i)!6ii!(n−3i2j)(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=0∞Bn≤mn!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 Bn≥mB_{n \geq m} is an Associated Bell Number

Bn=∑i=0n(ni)∗Bi≤m∗Bn−i≥m+1B_n = \sum_{i=0}^{n}\binom{n}{i} * B_{i\le m} * B_{n-i\ge m+1}

Bn≥k=Bn−∑i=1n(ni)Bi≤k−1Bn−i≥k.B_{n \geq k} = B_{n} - \sum_{i=1}^{n} \binom{n}{i} B_{i \leq k-1} B_{n-i \geq k}.

Bn=Bn≤∞B_n = B_{n \leq \infty}

Articles

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