Derangements of Permutations

Question

I am trying to review a problem I answered incorrectly on a test in my Combinatorics class. The problem reads:

Let $d(n,k)$ denote the number of derangements of length $n$ that have exactly $k$ cycles. Find a formula for $d(n,k)$. Your formula may contain one summation sign. It may also contain Stirling numbers.

Not sure how to approach this problem, as it has been a while since this exam.

Answer 1

Maybe I can help here even if my methodolgy probably shows up somewhat later in your course.

The combinatorial species $\mathcal{Q}$ of derangements with cycles marked is given by $$\mathcal{Q} = \mathfrak{P}( \mathcal{U}\mathfrak{C}_2(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_3(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_4(\mathcal{Z}) + \cdots).$$ This translates into generating functions like so: $$Q(z,u) = \exp\left(u\frac{z^2}{2}+u\frac{z^3}{3}+u\frac{z^4}{4}+\cdots\right) = \exp\left(-uz + u\log\frac{1}{1-z}\right).$$ This becomes $$Q(z, u) = \exp\left(-uz\right)\left(\frac{1}{1-z}\right)^u.$$ Switching to series this yields $$Q(z, u) = \left(\sum_{q=0}^\infty (-u)^q \frac{z^q}{q!}\right) \sum_{q=0}^\infty {q+u-1\choose q} z^q.$$ Extracting coefficients from this we get $$n! [z^n] Q(z, u) = n! \sum_{q=0}^n {q+u-1\choose q} \frac{(-u)^{n-q}}{(n-q)!}.$$ This is our first formula and it can be used to calculate $d_{n,k}$ quite effectively. The problem asks for Stirling numbers, however, so we provide a second formula. Recall that $$n! [z^n] [u^k] \left(\frac{1}{1-z}\right)^u = \left[n\atop k\right].$$ Taking into account the exponential term in $Q(z,u)$, we get $$n! [z^n] [u^k] Q(z, u) = n! \sum_{q=0}^k \frac{(-1)^q}{q!} [z^{n-q}] [u^{k-q}] \left(\frac{1}{1-z}\right)^u \\= \sum_{q=0}^k (-1)^q\frac{n!}{q!(n-q)!} (n-q)! [z^{n-q}] [u^{k-q}] \left(\frac{1}{1-z}\right)^u \\= \sum_{q=0}^k (-1)^q {n\choose q} \left[n-q\atop k-q\right].$$ Here is a Maple program that can be used to verify the above formulas. The second formula represents inclusion-exclusion, with the variable $q$ counting the number of fixed points.

with(combinat):

dnk :=
proc(n, k)
    option remember;
    local res, p, dc, nonfix, lens;

    res := 0;

    for p in permute(n) do
        dc := convert(p, 'disjcyc');
        lens := map(nops, dc);

        if add(lens[q], q=1..nops(lens)) = n then
            if nops(lens) = k then
                res := res+1;
            fi;
        fi;
    od;

    res;
end;

Answer 2

You can approach it as a straightforward inclusion-exclusion problem. There are ${n\brack k}$ permutations of $[n]$ with exactly $k$ cycles. For each $i\in[n]$ there are ${n-1}\brack{k-1}$ permutations of $[n]$ that fix $i$ and have $k-1$ other cycles. In general, if $0\le\ell\le k$, and $S$ is an $\ell$-element subset of $[n]$, there are ${n-\ell}\brack{k-\ell}$ permutations of $[n]$ that fix each element of $S$ and have a total of $k$ cycles. There are $\binom{n}\ell$ such subsets of $[n]$, so the usual inclusion-exclusion calculation tells you that

$$d(n,k)=\sum_{\ell=0}^k(-1)^\ell\binom{n}\ell{{n-\ell}\brack{k-\ell}}\;.$$