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


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

  • $\begingroup$ Thanks. Am I - as an MO user - supposed to know how to get the closed form for F(k,n) from this "semi-exponential" generating function? $\endgroup$ – Hans-Peter Stricker Dec 21 '09 at 16:35
  • $\begingroup$ Not necessarily. It's not hard, though; I'll edit the solution to explain that. $\endgroup$ – Michael Lugo Dec 21 '09 at 16:57
  • $\begingroup$ The name "recontres numbers" is standard in the following ways: (1) EIS, (2) canonical name in Wikipedia, (3) 10 hits in Google Scholar. Although that last one is not a huge number, if you take all three together, it's plenty standard enough for a relatively obscure concept. $\endgroup$ – Greg Kuperberg Dec 21 '09 at 17:38
  • 1
    $\begingroup$ My claim that the name was nonstandard was entirely subjective; basically, this is something that I felt I should have known a name for, and the name was new to me. $\endgroup$ – Michael Lugo Dec 21 '09 at 17:50

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.


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:


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.