Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

3 Answers

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|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
1  
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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.