How many permutations with $k$ cycles and $j$ fixed points are there?

Question

Suppose I have the numbers $\{1,...,n\}$. I would like to know how many permutations have exactly $k$ cycles and $j$ fixed points.

Answer 1

Hint: Here the needed concept is $2-$associated Stirling numbers of the first kind. First choose your fix points and the remaining is that.

Answer 2

By way of enrichment here is an alternate formulation using combinatorial classes. What we present below has the advantage of permitting the computation of a wide variety of statistics. The class of permutations with cycles and fixed points marked is

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\mathcal{U}\times \mathcal{V} \times \textsc{CYC}_{=1}(\mathcal{Z}) + \mathcal{U}\times \textsc{CYC}_{=2}(\mathcal{Z}) \\ + \mathcal{U}\times \textsc{CYC}_{=3}(\mathcal{Z}) + \mathcal{U}\times \textsc{CYC}_{=4}(\mathcal{Z}) + \cdots).$$

This gives the generating function $$G(z, u, v) = \exp\left(uvz + u\frac{z^2}{2} + u\frac{z^3}{3} + u\frac{z^4}{4} + u\frac{z^5}{5} + \cdots\right)$$ which is $$G(z, u, v) = \exp\left(uvz-uz+u\log\frac{1}{1-z}\right).$$

Extracting first the coefficient on $[v^j]$ we obtain

$$\frac{u^j z^j}{j!} \exp\left(-uz+u\log\frac{1}{1-z}\right) = \frac{u^j z^j}{j!} \exp(-uz) \exp\left(u\log\frac{1}{1-z}\right).$$

We extract the coefficient on $[u^k]$ in the next step:

$$[u^k] \frac{u^j z^j}{j!} \exp(-uz) \exp\left(u\log\frac{1}{1-z}\right) \\ = \frac{z^j}{j!} [u^{k-j}] \exp(-uz) \exp\left(u\log\frac{1}{1-z}\right) \\ = \frac{z^j}{j!} \sum_{q=0}^{k-j} \frac{(-1)^q z^q}{q!} \frac{1}{(k-j-q)!} \left(\log\frac{1}{1-z}\right)^{k-j-q}.$$

To conclude we extract the coefficient on $[z^n]$ (EGF) which yields

$$n! [z^n] \frac{z^j}{j!} \sum_{q=0}^{k-j} \frac{(-1)^q z^q}{q!} \frac{1}{(k-j-q)!} \left(\log\frac{1}{1-z}\right)^{k-j-q} \\ = n! \frac{1}{j!} \sum_{q=0}^{k-j} \frac{(-1)^q}{q!} [z^{n-j-q}] \frac{1}{(k-j-q)!} \left(\log\frac{1}{1-z}\right)^{k-j-q} \\ = n! \frac{1}{j!} \sum_{q=0}^{k-j} \frac{(-1)^q}{q! \times (n-j-q)!} \\ \times (n-j-q)! [z^{n-j-q}] \frac{1}{(k-j-q)!} \left(\log\frac{1}{1-z}\right)^{k-j-q} \\ = n! \frac{1}{j!} \sum_{q=0}^{k-j} \frac{(-1)^q}{q! \times (n-j-q)!} \left[n-j-q\atop k-j-q\right].$$

This yields the closed form

$$\bbox[5px,border:2px solid #00A000]{ {n\choose j} \sum_{q=0}^{k-j} {n-j\choose q} (-1)^q \left[n-j-q\atop k-j-q\right].}$$

Note that we cannot simply use a Stirling number $\left[n-j\atop k-j\right]$ as the second factor because that would include potential additional fixed points. The formula accounts for this by inclusion-exclusion (PIE).

The following Maple program shows how to compute this statistic using the cycle index $Z(S_n)$ of the symmetric group.

with(combinat);

pet_cycleind_symm :=
proc(n)
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;


ENUM :=
proc(n, j, k)
    option remember;
    local part, idx, res;

    res := 0; 

    if n=1 then
        idx := [a[1]];
    else
        idx := pet_cycleind_symm(n);
    fi;

    for part in idx do
        if degree(part) = k and
        degree(part, a[1]) = j then
            res := res + lcoeff(part);
        fi;
    od;

    n!*res;
end;

X := (n, j, k) -> binomial(n,j)
* add(binomial(n-j,q)*(-1)^q
      * abs(stirling1(n-j-q, k-j-q)), q=0..k-j);