MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let F(k,n) be the number of permutations of an n-element set that keep k elements fixed.

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 ( k! - \displaystyle\sum_{i=0}^{k-1} F(i,k) )$

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

share|cite|improve this question
up vote 9 down vote accepted

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

share|cite|improve this answer
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? – Hans Stricker Dec 21 '09 at 16:35
Not necessarily. It's not hard, though; I'll edit the solution to explain that. – Michael Lugo Dec 21 '09 at 16:57
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. – Greg Kuperberg Dec 21 '09 at 17:38
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. – 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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