## Number of permutations with a specified number of fixed points

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

## 3 Answers

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

-
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 2009 at 16:35
Not necessarily. It's not hard, though; I'll edit the solution to explain that. – Michael Lugo Dec 21 2009 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 2009 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 2009 at 17:50

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-
-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 19, "mathjax_display_tex": 6, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9262185096740723, "perplexity_flag": "middle"}