1

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.

coffeemath
  • 7,403
  • 1
    How about simply subtracting the number of permutations which do fix even one of the first $k$ components from the total number of permutations $n!$ in $S_n$? You will need to use PIE (principle of inclusion-exclusion) while counting the number of permutations to subtract to ensure none of the first $k$ components are fixed and not over-subtract. – Prasun Biswas Jun 30 '21 at 04:33
  • I do not know what they are called, but I believe that the numbers satisfy $$\begin{align}a_{n, 0} &= n! &\ a_{n, n} &= {!n} &\ a_{n,k} &= (n - k) a_{n-1,k} + k a_{n-1,k-1}, & 0 < k < n\end{align}$$ – shoteyes Jun 30 '21 at 04:34

1 Answers1

3

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)$

Prasun Biswas
  • 6,334