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.

2-2018 Teaching by misleading

2 months ago

## No comments:

## Post a Comment