These identities may be derived by enumerating permutations directly. For example, a permutation of n elements with n − 3 cycles must have one of the following forms: * n − 6 fixed points and three two-cycles * n − 5 fixed points, a three-cycle and a two-cycle, or * n − 4 fixed points and a four-cycle. The three types may be enumerated as follows: * choose the six elements that go into the two-cycles, decompose them into two-cycles and take into account that the order of the cycles is not important: :: * choose the five elements that go into the three-cycle and the two-cycle, choose the elements of the three-cycle and take into account that three elements generate two three-cycles: :: * choose the four elements of the four-cycle and take into account that four elements generate six four-cycles: :: Sum the three contributions to obtain : (en)
We prove the recurrence relation using the definition of Stirling numbers in terms of permutations with a given number of cycles . Consider forming a permutation of objects from a permutation of objects by adding a distinguished object. There are exactly two ways in which this can be accomplished. We could do this by forming a singleton cycle, i.e., leaving the extra object alone. This increases the number of cycles by 1 and so accounts for the term in the recurrence formula. We could also insert the new object into one of the existing cycles. Consider an arbitrary permutation of objects with cycles, and label the objects , so that the permutation is represented by : To form a new permutation of objects and cycles one must insert the new object into this array. There are ways to perform this insertion, inserting the new object immediately following any of the already present. This explains the term of the recurrence relation. These two cases include all possibilities, so the recurrence relation follows. (en)
We prove the recurrence relation using the definition of Stirling numbers in terms of rising factorials. Distributing the last term of the product, we have : The coefficient of on the left-hand side of this equation is . The coefficient of in is , while the coefficient of in is . Since the two sides are equal as polynomials, the coefficients of on both sides must be equal, and the result follows. (en)