Is there a formula, direct or recursive, for the number of permutations $\sigma$ of $\{1,2,\cdots,n\}$ for which $\sigma(j) \neq j$ for $1 \le j \le k$ ? [For $j>k$ the permutation may or may not fix $j.$] I would also be interested in any kind of inductive procedure which would compute these values.
Note this is not the same as the "recontres numbers" $D_{n,k}$ which are counts of the number of permutations of $S_n$ having exactly $k$ fixed points. The difference is that I want the first $k$ places not to be fixed, and the remaining $n-k$ can be fixed or not.
I'd also be interested if these counts had a name used to describe them, and any link to where they are discussed. Thank you.
Best Answer
We can simply count the number of permutations which fix even one of the first $k$ components and subtract them from the total number $n!$ of the permutations of $\{1,2,\ldots,n\}$
The number of permutations which fix all the first $j$ components is given by $m_j=(n-j)!$ for $0\le j\le k$
Now, we use PIE to compute the number of permutations which fix even one of the first $k$ components. The count is given by,
$$k(n-1)!-\binom k2(n-2)!+\binom k3(n-3)!-\ldots=\sum_{r=1}^k(-1)^{r+1}\binom kr(n-r)!$$
So, the number of permutations of $\{1,2,\ldots,n\}$ which fix not even one of the first $k$ components is given by subtracting this count from $n!$, ie, the desired count is,
$$\sum_{r=0}^k (-1)^r\binom kr(n-r)!\tag 1$$
which, according to W|A can be written as $n!_1F_1(-k;-n;-1)$ where $_1F_1(a;b;x)$ denotes the Kummer confluent hypergeometric function.
I doubt there's a simpler closed form than $(1)$