3.17 Bell Number

Suppose we have \(n\) boxes, if we have

\(k\) numbered balls without restriction: \(n^k\)
Balls are not numbered and the number is not fixed and no more than \(1\) ball in every box: \(2^n\)
\(k\) numbered balls and no more than \(1\) ball to each box: \((n)_k\)
\(k\) unlabeled identical balls and no more than \(1\) ball per box: \(\binom{n}{k}=\frac{\left(n\right)_{k}}{k!}\)

Proposition

Suppose we have \(n\) boxes and \(n\) balls, if we have \(m\) different types of Balls and all the balls of the same type are identical, that is

\(k_1\) balls of the first type

\(k_{2}\) balls of the second type

......

\(k_{m}\) balls of the m-th type where \(k_1+...+k_m=n\)

In particular, when \(m=2\), the result is binomial coefficients

The number of ways to arrange balls into boxes equals \(\frac{n!}{k_{1}!k_{2}!...k_{m}!}=\binom{n}{k_1,\ldots,k_{m}}\) (means multinomial coefficients)

Proof

Suppose for the moment that the balls are all labeled: we assume \((a_1,b_1)\) and \(a_1\) refers type and \(b_1\) refers order

\((1,1),...,(1,k_1)\)

\((2,1),...,(2,k_{2})\)

....

\((m,1),...,(m,k_{m})\), we know the number of ways to arrange the labeled balls is \(n!\)

If we forget the labeling, we can use the division principle to count

So the number of arrangements of unlabeled balls is \(\frac{n!}{k_1!k_2!...k_m!}\)

Remark

Notice that \(\forall n\in \N\) for any \(k_{1},...,k_{m}\in\N\cup \{0\}\) such that: \(k_1+...+k_m=n\), the number is \(\frac{n!}{k_1!k_2!...k_m!}\)

Recursion for the multinomial coefficients

\(\forall n\in \N,\forall k_1,...,k_m\in \N\cup\{0\}\) such that \(\sum^{m}_{i=1}k_{i}=n\)

Then we have \(\begin{aligned} \binom{n}{k_1,\ldots,k_{m}}=\sum_{i=1}^{m}\binom{n-1}{k_1,\ldots,k_{i}-1,\ldots,k_{m}} \end{aligned}\)

This is because we know \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\). Then we imply \(\binom{n}{k,n-k}=\binom{n-1}{k-1,n-k}+\binom{n-1}{k,n-k-1}\), then recursively...

Proof

Consider the first box it can be either filled by a ball of type \(1:\binom{n-1}{k_1-1,k_2,\ldots,k_{m}}\), type \(2:\binom{n-1}{k_1,k_2-1,k_3\ldots,k_{m}}\) ....type \(m:\binom{n-1}{k_1,,\ldots,k_{m-1},k_{m}-1}\)

Then we use addition principle

For binomials we have \((x+y)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{k}y^{n-k}=\sum_{k=0}^{n}\binom{n}{k,n-k}x ^{k}y^{n-k}\) by definition

So, we claim that \((x_{1}+...+x_{m})^{n}=\sum_{k_1+\cdots+k_{m}=n}\binom{n}{k_1,\ldots,k_{m}}x_{1}^{k_1} \cdot\ldots\cdot x_{m}^{k_{m}}\)

Example

\(x_{i}=1,\forall i,(1+...+1)^{n}=\sum_{k_1+\cdots+k_{m}=n}\binom{n}{k_1,\ldots,k_{m}} =m^{n}\)

Imagine the boxes and balls, we assign one ball into boxes, that is we assign one type into boxes, then equal to \(m^n\)

Proposition(隔板法)

We have \(n\) boxes, \(k\) identical balls without restrictions, then the number of ways is \(\binom{n+k-1}{n-1}\)

set of \(n+k-1\) elements

Claim: There is a bijection between \(k\)-element subsets of and ways of distributing coins between the pirates

That is we have \(k\) coins and \(n-1\) delimiters

Another interpretation

The number on non-negative integer solutions for the equation \(x_1+...+x_n=k\) is \(\binom{n+k-1}{n-1}\)

Proposition

We have \(n\) identical boxes, \(k\) labelled balls. Every box should have at least \(1\) ball

Let \(S\) be a set, equivalence relation is a subset \(A\) of \(S\times S\) with the following properties:

\(\forall x\in S,(x,x)\in A\)
If \((x,y)\in A\Rightarrow(y,x)\in A\)
If \((x,y)\in A,(y,z)\in A\), then \((x,z)\in A\)

Then \(\forall x\in S,\{y\in S:(x,y)\in A\}=[x]_A\)

Every equivalence relation gives rise to a partition of the set \(S\) into equivalence classes

\(S=[x]_A\cup [y]_A\cup [z]_A\)

Explanation:

The balls are the elements of the set (e.g., balls labeled 1, 2, ..., \(k\)).
The boxes correspond to the equivalence classes.
Two balls are "equivalent" if they are placed in the same box.
Since the boxes are identical, we don’t care which box is which—only about how the balls are grouped into \(n\) non-empty subsets.

Thus, counting the number of ways to distribute the balls is the same as counting the number of ways to partition the set of \(k\) balls into \(n\) non-empty subsets. Each such partition corresponds to an equivalence relation with exactly \(n\) equivalence classes.

The number of equivalence relations with \(n\) equivalence class on the set of \(k\) elements is denoted \(S(k,n)\)

This number is given by the Stirling number of the second kind, denoted \(S(k, n)\),

Proof

Base cases: \(S(0,0)=1\)

For \(k\geq 1\): \(S(k,0)=0\), \(S(k,1)=1,S(k,k)=1\)

Proposition: \(\forall k\in \N,\forall n\in \N,n\leq k\), we have \(S(k,n)=S(k-1,n-1)+nS(k-1,n)\)

Proof

Consider the \(k\)-th ball. There are two possibilities:

It’s in its own box (singleton class) :
- Remaining \(k - 1\) balls go into \(n - 1\) boxes.
- Number of ways: \(S(k - 1, n - 1)\).
It joins an existing box:
- First, partition the \(k - 1\) balls into \(n\) boxes: \(S(k - 1, n)\) ways.
- Then, the \(k\)-th ball can join any of the \(n\) boxes: \(n\) choices.
- Total ways: \(n \cdot S(k - 1, n)\).

The total is the sum: \(S(k, n) = S(k - 1, n - 1) + n \cdot S(k - 1, n)\)

Bell numbers, \(B(k)\), which count the total number of ways to partition \(k\) elements into any number of non-empty subsets (not fixing \(n\)) and every box should have at least one ball

We define \(B(k) = \sum_{n=0}^{k} S(k, n)\)

Proposition

\(B(0)=1\), \(B(k+1)=\sum^k_{n=0}B(n)\binom{k}{n}\)

Proof

Base case: \(B(0)=1\)

Inductive step: Suppose it's true for \(k\), then for \(B(k+1)\), consider the element \(k+1\).

Focus on \(k+1\) : In any partition, the element \(k+1\) belongs to some group. This group can have 1 element (\(\{k+1\}\)), 2 elements (like \(\{k+1, 1\}\)), or more, up to all \(k+1\) elements. Let’s say this group has \(n+1\) elements total: \(k+1\) plus \(n\) others, where \(n\) ranges from 0 to \(k\).

Step 1: Choose the group for \(k+1\) :

We pick \(n\) elements from \(\{1, 2, \ldots, k\}\) to join \(k+1\) in its group.
Number of ways to choose \(n\) out of \(k\) elements = \(\binom{k}{n}\).

Step 2: Partition the rest:

After picking \(n\) elements, \(k - n\) elements remain.
These \(k - n\) elements can be partitioned in \(B(k - n)\) ways (by definition of Bell numbers).

Step 3: Add it all up:

For each \(n\) from 0 to \(k\), the number of partitions where \(k+1\)’s group has \(n+1\) elements is: \(\binom{k}{n} \cdot B(k - n)\)
So, the total number of partitions is: \(B(k+1) = \sum_{n=0}^{k} \binom{k}{n} B(k - n)\)

Step 4: Flip the sum:

The sum \(\sum_{n=0}^{k} \binom{k}{n} B(k - n)\) counts the same thing as \(\sum_{n=0}^{k} B(n) \binom{k}{n}\).
Why? Let \(m = k - n\). As \(n\) goes from 0 to \(k\), \(m\) goes from \(k\) to 0, and \(\binom{k}{n} = \binom{k}{k - n}\). This reverses the order, but the total is the same: \(\sum_{n=0}^{k} \binom{k}{n} B(k - n) = \sum_{n=0}^{k} B(n) \binom{k}{n}\)

Summary

\(S(k, n)\) Recursion: How to distribute \(k\) balls into \(n\) identical non-empty boxes and every box should have at least one ball.
\(B(k)\) Recursion: How to distribute \(k\) balls into into any number of non-empty subsets and every box should have at least one ball

‍