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



Number of permutations with a specified number of fixed points
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](https://oeis.org/A008290) 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)!} $$


