6
$\begingroup$

Proposition: The Stirling numbers, $s(n, k)$, satisfy the recurrence relation $$s(n,k) = s(n - 1, k - 1) + (n - 1)s(n - 1, k) \qquad (n \ge 1)$$ with initial conditions $s(0,0) = 1$ and $s(n,0) = s(0,n) = 0, n > 0$.

Proof: Consider forming a new permutation with $n$ objects from a permutation of $n - 1$ objects by adding a distinguished object. There are exactly two ways in which this can be accomplished.

First, we could form a singleton cycle, leaving the extra object fixed. This increases the number of cycles by $1$ and so accounts for the $s(n - 1, k - 1)$ term in the recurrence.

Second, we could insert the object into one of the existing cycles. Consider an arbitrary permutation of $n - 1$ objects with $k$ cycles. To form the new permutation, we insert the new object before any of the $n - 1$ objects already present. This explains the $(n - 1)s(n - 1, k)$ term of the recurrence.

These two cases include all of the possibilities, so the recurrence relation follows with the given initial conditions. QED

Here, I cannot understand the second part of the proof. How one arrives to this part: $$(n-1)s(n-1,k) $$

$\endgroup$
8
$\begingroup$

So, to count a class of combinatorial objects you may break it into cases and add the amounts so long as 1) there is no overlap between cases and 2) every object is counted in at least one of the cases. This is just like how if you wish to count the number of students in a classroom you may instead count all of the male students and add that to the number of female students or how if you want to count the number of four-digit numbers you may count the even four digit numbers and add that to the number of odd four digit numbers.

Stirling numbers and the objects they count are no exception. Remember that Stirling numbers of the first kind count the number of permutations of $n$ elements whose cyclic decomposition has precisely $k$ cycles. We choose to count $s(n,k)$ by breaking it up into cases as described in the previous paragraph. These cases are:

  • $1$ is in a cycle by itself.

  • $1$ is not in a cycle by itself, i.e. in a cycle with something else.

Case 1: In the case that $1$ is in a cycle by itself, we recognize that for there to be $k$ cycles in total, the remaining $n-1$ elements must be arranged into $k-1$ cycles. Stirling numbers of the first kind count exactly this scenario, giving us $s(n-1,k-1)$ such arrangements in this case.

Yes, I know we are using stirling numbers to count stirling numbers... it seems roundabout, but that is exactly the strength of recurrence relations. Given enough initial information and a recurrence relation, we have now enough information to calculate any specific outcome we wish, and in particular the value of $s(n,k)$ for any value of $n$ and $k$.

Case 2: (the case you are interested in) In the case that $1$ is not in a cycle by itself, that implies that it must be in a cycle with something else. Since it is in a cycle with something else if we were to remove $1$ from the picture entirely the resulting configuration would still have $k$ cycles though only $n-1$ elements since removing $1$ will not have removed a cycle, only shortened one.

We recognize now that we can work in reverse. First take an arrangement of the numbers $\{2,3,4,\dots,n\}$ into a permutation that has precisely $k$ cycles. Now... pick one of the numbers in the arrangement and we shall insert $1$ into the place just before that number but into the same cycle.

For example, if we have the permutation in cyclic form $(2~3~5)(4)(6~7)$ and we chose to insert the $1$ before the $3$, the new resulting permutation would be $(2~\color{red}{1~3}~5)(4)(6~7)$. Alternatively if we had chosen to insert the $1$ before the $4$ we would have $(2~3~5)(\color{red}{1~4})(6~7)$, etc...

We recognize now that there is an easy bijection between the number of permutations of $n$ elements which decompose into $k$ cycles where $1$ is not in a cycle by itself (is not a fixed point) and the cartesian product of the set of permutations of $n-1$ elements which decompose into $k$ cycles and the set of numbers $\{2,3,\dots,n\}$. The bijection in the reverse direction is the process we described in the previous two paragraphs, first taking a permutation of the type we are interested in without $1$ and then inserting $1$ into the position just before the specified number.

As the cardinality of the cartesian product of two sets is the product of the cardinalities of the two sets (i.e. the multiplication principle/rule of product) we have a count of $s(n-1,k)\cdot (n-1)$ (the term $s(n-1,k)$ comes from the number of permutations of $n-1$ elements into $k$ cycles and the factor of $(n-1)$ comes from picking which element our newly introduced $1$ is to be placed in front of).


As a final result, we have $s(n,k)=|\mathrm{Case1}|+|\mathrm{Case2}|$ implying

$$s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.