Let $d(n,k)$ be the number of derangement of $[n]$ with $k$ cycles. Derive a recurrence for $d(n,k)$.
I know the formula for $d(n,k)$(which involves unsigned Stirling number of the first kid) but I am not sure how to derive a recurrence combinatorially for $d(n,k)$
Update: I have tried to derive a recurrence for $d(n,k)$ but not sure if it is right or not. Any help/ advice/ correction would be appreciated.
Here is my attempt: We count the ways to partition $[n]$ into $k$ cycles of length at least $2$. There are two cases:
1st Case: If the cycle containing the element $n$ has length $2$, then there are $n-1$ ways to pick its other element, and there are $d(n-2,k-1)$ ways to derange the remaining $n-2$ elements into $k-1$ cycles.
2nd Case: If the cycle containing the element $n$ has length $\geq$3, then skipping element $n$ in its cycle still leaves cycle of length at least $2$, and we can produce a derangement of $[n-1]$ into $k$ cycles, which gives us $d(n-1, k)$ ways. On the other hand, every derangement of $[n]$ with $n$ into $k$ cycles arises from a derangement of $[n-1]$ of $k$ cycle by inserting $n$ immediately following some $x\in[n-1]$ on the cycle containing $x$. So, there are $(n-1)d(n-1,k)$ of this type.
So, the derived recurrence is $d(n,k)= (n-1)(d(n-2,k-1)+ d(n-1,k))$
Any help/ advice/ correction would be appreciated.