Question

S(n,k) is the Stirling numbers of the second kind, and c(n,k) is the unsigned Stirling numbers of the first kind. For all positive integers 1≤k≤n, show that S(n,k)≤c(n,k). When does equality hold?

Answer 1

The comparison between Stirling numbers of the second and first kind involves understanding their combinatorial interpretations: partitions and cycles in permutations. It is typically fewer to partition than to order, implying S(n,k)≤c(n,k), with equality when k equals n or 1.

Step-by-step explanation:

The student's question involves the comparison between Stirling numbers of the second kind, S(n,k), and the unsigned Stirling numbers of the first kind, c(n,k). For all positive integers where 1≤k≤n, the task is to show that S(n,k)≤c(n,k) and to determine when equality holds. The Stirling numbers of the second kind count the number of ways to partition a set of n objects into k non-empty subsets, while the Stirling numbers of the first kind count the number of permutations of n objects with exactly k cycles.

One basic approach to show S(n,k)≤c(n,k) is to consider the representational meaning of both sets of numbers and their combinatorial interpretations. It is generally known that the number of ways to partition objects is fewer than the number of ways to order them, thus implying the stated inequality. The equality holds when k = n or k = 1, where both the Stirling numbers of the second and first kind count only one way to arrange the objects: as a single cycle or a set of singletons respectively.