An equivalence relation on a set determines a partition of that set, and vice versa; this is intuitively easy to understand. However, if I were to ask: for a finite set with n elements, how many different partitions are there in total? I used to think this was a very simple problem and didn’t give it much thought. But the day before yesterday, my Abstract Algebra teacher mentioned that this is a quite challenging problem. Upon investigating, I found that there is much more to it than meets the eye. Here, I will briefly share my research process, and readers can see the process of building understanding "from scratch."
In the following, we assume a finite set with n elements is \{1, 2, \dots, n\}, and we denote its number of partitions as B(n).
Early Stage: Brute Force Calculation
The case for n=3 is not difficult to list: \begin{aligned} &\{\{1,2,3\}\}, \{\{1,2\},\{3\}\}, \{\{1,3\},\{2\}\}, \\ &\{\{2,3\},\{1\}\}, \{\{1\},\{2\},\{3\}\} \end{aligned} Therefore, B(3)=5. B(4) is relatively large and not as easy to list. Based on integer partitions, I derived a complex formula for calculating the number of set partitions. Taking B(4) as an example, it has the following partition types: \begin{aligned} &4=1+1+1+1\\ &4=1+1+2\\ &4=1+3\\ &4=4\\ &4=2+2 \end{aligned} Each partition type represents a way to partition \{1, 2, 3, 4\}: it tells us how many blocks there are and how many elements are in each block. For example, 4=1+1+1+1 means partitioning \{1, 2, 3, 4\} into 4 blocks with one element each. The number of possible partitions for this type is: \frac{1}{4!}\binom{4}{1}\binom{3}{1}\binom{2}{1}\binom{1}{1}=1 We divide by 4! because the status of each "1" is equivalent; different orderings count as the same partition. Similarly, we have: \begin{aligned} &4=1+1+2: \quad \frac{1}{2!}\binom{4}{1}\binom{3}{1}=6\\ &4=1+3: \quad \binom{4}{1}=4\\ &4=4: \quad \binom{4}{4}=1\\ &4=2+2: \quad \frac{1}{2!}\binom{4}{2}=3 \end{aligned} Thus, B(4)=1+6+4+1+3=15. Using similar methods, I calculated by hand that B(5)=52 and B(6)=203. Listing all partitions for 5 and 6 is still acceptable for manual calculation.
Middle Stage: Casting a Wide Net
Now we have obtained part of the sequence: 5, 15, 52, 203. It doesn’t seem to have an obvious pattern, and intuition suggests this sequence grows faster than exponential. Inputting this sequence into OEIS, I found the sequence (number of ways to partition a set of n labeled elements):
1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, ...
Many unique formulas were listed in the FORMULA section. However, since there were only formulas without derivations, I couldn’t understand them. So, I had to look for another way. Searching for keywords like "number of set partitions" on Google yielded many similar results. These contents were helpful. For instance, by introducing S(n,k) to calculate B(n), where S(n,k) represents the number of ways to partition a set of n elements into k blocks. According to this definition, it is obvious that: B(n)=\sum_{k=1}^n S(n,k) S(n,k) is calculated via recursion. Consider adding one element to a set of n-1 elements; there are two possibilities:
1. The new element forms its own block, and the remaining n-1 elements are partitioned into k-1 blocks. The number of such cases is S(n-1, k-1).
2. The n-1 elements are already partitioned into k blocks, and the new element is placed into any one of these k blocks. The number of such cases is k S(n-1, k).
Thus, we have the recurrence relation: S(n,k)=S(n-1,k-1)+k S(n-1,k) This is probably the most convenient formula for programming. Written in Python:
def sp(n,m):
if m>n:
return 0
elif m==1 or m==n:
return 1
else:
return sp(n-1,m-1)+m*sp(n-1,m)
def setpart(n):
return sum([sp(n,m) for m in range(1,n+1)])
print(setpart(7))However, this code is actually quite slow. Calculating B(30) on PyPy is already a struggle. Yesterday, I spent a long time trying to calculate the generating function of B(n) from the recurrence formula, but the conditions were insufficient to obtain a complete result.
Mid-Late Stage: Analytical Calculation
During the search in the middle stage, most articles were similar, only introducing concepts and recursions without detailed descriptions. However, one website mentioned at the end that these numbers are called "Bell Numbers." Following this lead, I found the Wikipedia page: https://en.wikipedia.org/wiki/Bell_number
Wikipedia provided many valuable materials and informed me that the standard notation is B_n, and the S(n,k) introduced above is called "Stirling numbers of the second kind." Wikipedia gave the recurrence formula: B_{n+1}=\sum_{k=0}^{n}{{n \choose k}B_k} The combinatorial explanation for this formula can be found on Wikipedia and will not be repeated here. Last night, I calculated for a long time but couldn’t derive further information from this formula (I misread the formula, oops), such as calculating the generating function. So, I searched the English Wikipedia for "Bell Number," which provided more detailed results, though still without the derivation process. Today, following the hints on the English Wikipedia, I performed another calculation and derived the generating function. Let: f(x)=\sum_{n=0}^{\infty}\frac{B_n}{n!}x^n Differentiating it, substituting the recurrence formula, and swapping the summation signs: \begin{aligned} f'(x)&=\sum_{n=1}^{\infty}\frac{B_n}{(n-1)!}x^{n-1}=\sum_{n=0}^{\infty}\frac{B_{n+1}}{n!}x^n\\ &=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\frac{1}{n!}{n \choose k}B_k x^n\\ &=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\frac{1}{(n-k)!k!}B_k x^k x^{n-k}\\ &=\sum_{k=0}^{\infty}\sum_{n=k}^{\infty}\frac{1}{(n-k)!k!}B_k x^k x^{n-k}\\ &=\sum_{k=0}^{\infty}\frac{B_k x^k }{k!}\sum_{n=k}^{\infty}\frac{1}{(n-k)!}x^{n-k}\\ &=\sum_{k=0}^{\infty}\frac{B_k x^k }{k!}e^x\\ &=f(x)e^x \end{aligned} In this way, we find f(x)=e^{e^x-c}. From f(0)=1, we find c=1, so: \sum_{n=0}^{\infty}\frac{B_n}{n!}x^n=f(x)=e^{e^x-1} This is a concise and beautiful generating function, an "exponential of an exponential" function, which shows how rapidly B_n increases. Based on the generating function, we can derive an infinite series formula for B_n, because: \begin{aligned} e^{e^x}&=\sum_{m=0}^{\infty}\frac{1}{m!}e^{mx}\\ &=\sum_{m=0}^{\infty}\frac{1}{m!}\sum_{n=0}^{\infty}\frac{1}{n!}m^n x^n\\ &=\sum_{n=0}^{\infty}\frac{1}{n!}\sum_{m=0}^{\infty}\frac{1}{m!}m^n x^n \end{aligned} By comparing both sides of f(x), we can conclude: B_n=\frac{1}{e}\sum_{m=0}^{\infty}\frac{m^n}{m!} This is Dobinski’s formula.
Late Stage?
Learning is endless; there is no "late stage." Let’s encourage each other!
When reposting, please include the original address: https://kexue.fm/archives/2985
For more detailed reposting matters, please refer to: Scientific Space FAQ