As we can deduce from the recurrence
C(n,k) = C(n-1,k-1) + C(n-1,k) that
C(n,k) = \frac{1}{k!} \prod_{j=0}^{k-1}(n-j),
where C(n,k) is the number of k-subsets out of an n-set, we can similarly find a closed form for the recurrence S(n,k) = S(n-1,k-1) + k \cdot S(n-1,k) which is
S(n,k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} j^n C(k,j) , where S(n,k) is the number of k-partitions of an n-set, a Stirling number of the second kind.
The tech for doing discrete sums is really spectaculair imho and therefore want to know much more about it.
5-2024 Boxing day is not for boxers only !
3 months ago
No comments:
Post a Comment