Number of permutations with a specified number of fixed points

Question

Let $F(k,n)$ be the number of permutations of an n-element set that fix exactly $k$ elements.

We know:

1. $F(n,n) = 1$

2. $F(n-1,n) = 0$

3. $F(n-2,n) = \binom {n} {2}$

   ...

4. $F(0,n) = n! \cdot \sum_{k=0}^n \frac {(-1)^k}{k!}$ (the subfactorial)

The summation formula is obviously

$\displaystyle\sum_{k=0}^n F(k,n) = n!$

A recursive definition of $F(k,n)$ is (my claim):

$$F(k,n) = \binom {n} {k} \cdot \Big( k! - \displaystyle\sum_{i=0}^{k-1} F(i,k) \Big)$$

Question 1: Is there a common name for the "generalized factorial" $F(k,n)$?

Question 2: Does anyone know a closed form for $F(k,n)$ or have an idea how to get it from the recursive definition? (generating function?)

Answer 1

The "semi-exponential" generating function for these is

$\sum_{n=0}^\infty \sum_{k=0}^n {F(k,n) z^n u^k \over n!} = {\exp((u-1)z) \over 1-z}$

which follows from the exponential formula.

These numbers are apparently called the rencontres numbers although I'm not sure how standard that name is.

Now, how do we get a formula for these numbers out of this? First note that

$$exp((u-1)z) = 1 + (u-1)z + {(u-1)^2 \over 2!} z^2 + {(u-1)^3 \over 3!} z^3 + \cdots $$

and therefore the "coefficient" (actually a polynomial in $u$) of $z^n$ in $exp((u-1)z)/(1-z)$ is

$$ P_n(u) = 1 + (u-1) + {(u-1)^2 \over 2!} + \cdots + {(u-1)^n \over n!} = \sum_{j=0}^n {{(u-1)^j } \over j!} $$

since division of a generating function by $1-z$ has the effect of taking partial sums of the coefficients.

The coefficient of $u^k$ in $P_n(u)$ (which I'll denote $[u^k] P_n(u)$, where $[u^k]$ denotes taking the $u^k$-coefficient) is then

$$ [u^k] P_n(u) = \sum_{j=0}^n [u^k] {(u-1)^j \over j!} $$

But we only need to do the sum for $j = k, \ldots, n$; the lower terms are zero, since they are the $u^k$-coefficient of a polynomial of degree less than $k$. So

$$ [u^k] P_n(u) = \sum_{j=k}^n [u^k] {(u-1)^j \over j!} $$

and by the binomial theorem,

$$ [u^k] P_n(u) = \sum_{j=k}^n {(-1)^{j-k} \over k! (j-k)!} $$

Finally, $F(k,n) = n! [u^k] P_n(u)$, and so we have

$$ F(k,n) = n! \sum_{j=k}^n {(-1)^{j-k} \over k!(j-k)!} $$

Answer 2

A permutation of {1, ..., n} with k fixed points is determined by choosing which k elements of {1, ..., n} it fixes and choosing a derangement of the remaining n-k elements. So,

$F(k, n) = {n \choose k} F(0, n-k)$.

(This formula is also on the page Michael Lugo linked to.) You have already given one formula for the number of derangements on n letters. Another one is F(0, n) = the nearest integer to n!/e.

Answer 3

Various links on this answer have expired, so I thought I would add an answer.

One can use inclusion--exclusion. First, note (as in @ReidBarton's answer) that $$ F(k,n) = \binom kn F(0,n-k). $$ So it is sufficient to only study permutations with no fixed points. This is known as the number of derangements. Various proofs using inclusion--exclusion can be found on Wikipedia:

• https://en.wikipedia.org/wiki/Derangement#Counting_derangements
• https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle#Counting_derangements_2

Answer 4

Let $S_n$ be the set of all permutations of $X$ \(i.e. $S_n = \{ f$ $|$ $f : X \rightarrow X\}$). Now consider the set of permutations, $A$, that have exactly k fixed points. More formally, $A$ is the union of all sets

$$A_i = \{f \in S_n : N' \in {\{1,...,n\} \choose k}, f(N') = N', \text{ and } \forall j \in \{1,...,n\} \setminus N', f(x_j) \neq x_j\}$$ where $i \in \{1,...,{n \choose k}\}$.

(Note that each $A_i$ must uniquely correspond to some $N' \in {\{1,...,n\} \choose k}$, which is why $i \in \{1,...,{n \choose k}\}$. In other words, the definition of $A_i$ implicitly defines a bijection between all $A_i$ and ${\{1,..., n\} \choose k}$).

Since there are $k$ fixed elements for all $f \in A$, we consider how to permute the remaining $n - k$ elements. These elements cannot be fixed. Thus, by letting arbitrary $N' \in {\{1,...,n\} \choose k}$, the number of permutations of $X$ where the $k$ points in $N'$ are fixed and the rest are not is equivalent to the number of derangements (see side note for further explanation) of the set $X \setminus N'$. Additionally, because there are ${n \choose k}$ ways to fix $k$ elements, we have

$${n \choose k} \cdot D(|X \setminus N'|) = {n \choose k} \cdot D(n - k) = {n \choose k} \cdot ((n - k)! - \displaystyle\sum_{i = 1}^{n - k} (-1)^{i - 1} {(n - k) \choose i} (n - k - i)!)$$

as the total number of permutations of $X$ with exactly $k$ fixed points. More concisely, we have $${n \choose k} \cdot D(|X \setminus N'|) = {n \choose k} ((n - k)! - \displaystyle\sum_{i = 1}^{n - k} (-1)^{i - 1} \dfrac{(n - k)!}{i!})$$

Side note: A derangement of a set is a permutation of the set such that no element is mapped to itself. The total number of derangements of an n-element set is $$D(n) = n! - \displaystyle\sum_{i = 1}^n (-1)^{i - 1} {n \choose i}(n - i)! = n! - \displaystyle\sum_{i = 1}^n (-1)^{i - 1} \dfrac{n!}{i!}$$ The proof for the total number of derangements of a set utilizes the principle of inclusion-exclusion, but I will not include it here as it does not directly answer your question.

Answer 5

see Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points