co.combinatorics - 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 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)!}$$

• Next pr.probability - distribution of degree of minimum polynomial for eigenvalues of random matrix with elements in finite field
• Previous Learning Class Field Theory: Local or Global First?