Number of permutations with a specified number of fixed points Let $F(k,n)$ be the number of permutations of an n-element set that fix exactly $k$ elements.
We know:

*

*$F(n,n) = 1$


*$F(n-1,n) = 0$


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


*$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?)
 A: 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.
A: 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)!} $$
A: see Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points
A: 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
A: 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.
