Number of permutations of length $n$ such that all cycles have an element not greater than $k$

Question

I'm trying to solve a problem and I've transformed it into the above problem (suppose that $k\in[1,n]$) but I'm not sure how hard it is and I'm starting to lose motivation. I feel like this should be a well known problem, but I'm not able to find it anywhere at the moment.

I'll rephrase, in case I haven't made myself clear; I want to count the number of permutations $\pi\in\mathfrak{G}_n$ such that if I pick every number in positions from $1$ to $k$ ($\pi_j$, $j\in[k]$), then I will have covered every cycle in the permutation (i.e every sequence $k\to\pi_k\to\pi_{\pi_k}\to\dots$ will eventually have at least one element of $[1,k]$).

I've tried doing a bunch of stuff (for example playing around with Sieves) but they end up not getting me anywhere. I'm mainly looking for hints/guides but a solution will also do.

Answer 1

This can be computed recursively, for $n\le k$ the result is $n!$ by inspection. When $n\gt k$ we may insert the $n$ value in any admissible permutation from $[n-1]$ in $n-1$ possible slots on the factorization into disjoint cycles of the permutation. Unrolling the recursion we get $((n-1)!/(k-1)!)\times k! = k (n-1)!.$ This is

$$Q_{n,k} = \begin{cases} n! & \quad\text{if}\quad n\le k \\ k (n-1)! & \quad\text{if}\quad n\gt k. \end{cases}$$

We may verify this with the following Maple code (warning, iterates over all permutations, feasible for about $n\le 9$ on my machine).

with(combinat);


pet_disjcyc :=
proc(p)
local dc, pos;

    dc := convert(p, 'disjcyc');

    for pos to nops(p) do
        if p[pos] = pos then
            dc := [op(dc), [pos]];
        fi;
    od;

    dc;
end;

ENUM :=
proc(n, k)
option remember;
local perm, res, fact, mat;

    res := 0;
    perm := firstperm(n);

    while type(perm, `list`) do
        fact := map(min, pet_disjcyc(perm));
        mat := select(m -> m<=k, fact);
        if nops(mat) = nops(fact) then
            res := res+1;
        fi;

        perm := nextperm(perm);
    od;

    res;
end;

Q := (n,k) -> `if`(n <= k, n!, (n-1)!*k);

We get e.g. for $k=4$ the sequence

$$1, 2, 6, 24, 96, 480, 2880, 20160, 161280, \ldots$$