Combinatorics question See attached image Let dn k be the nu

Combinatorics question. See attached image

Let d(n, k) be the number of derangements of length n that consist of k cycles. Find a formula for d(n, k) in terms of signless Stirling numbers of the first kind.

Solution

Let c(n, k) denote the number of permutations of length n with k cycles. The numbers c(n, k) are then called the signless Stirling numbers of the first kind. It is well-known [3] that Cn(x) = Xn k=1 c(n, k)x k = x(x + 1)· · ·(x + n 1). (1) Setting x = 1, this shows that there are as many permutations of length n with an odd number of cycles as there are with an even number of cycles. If, instead of considering the sum of all Stirling numbers c(n, k) so that n is fixed and k belongs to a certain residue class modulo 2, we consider the sum of the Stirling numbers c(n, k) so that n is fixed and k belongs to a certain residue class modulo q, the result is a little bit less compact. These sums will no longer be equal to n!/q, but it will be true that as n goes to infinity, the limit of any of these q sums divided by n! will converge to 1/q. We will prove this fact in this paper, as a way to illustrate our techniques. A derangement is a permutation with no fixed points (cycles of length 1). It is well-known [2] that number of derangements of length n is D(n) = n! Pn i=0 (1)i i! , which is the integer closest to n!/e. Let d(n, k) be the number of derangements of length n with k cycles. The numbers d(n, k) are not nearly as well-studied as the numbers c(n, k), but the following important fact is known about them.