11
$\begingroup$

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

$\endgroup$

5 Answers 5

13
$\begingroup$

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

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

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.

$\endgroup$
0
$\begingroup$

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:

$\endgroup$
0
$\begingroup$

Let $S_n$ be the set of all permutations of $X$ \(i.e. $S_n = \{ f$ $|$ $f : X \rightarrow X\}$). Now consider the set of permutations, $A$, that have exactly k fixed points. More formally, $A$ is the union of all sets

$$A_i = \{f \in S_n : N' \in {\{1,...,n\} \choose k}, f(N') = N', \text{ and } \forall j \in \{1,...,n\} \setminus N', f(x_j) \neq x_j\}$$ where $i \in \{1,...,{n \choose k}\}$.

(Note that each $A_i$ must uniquely correspond to some $N' \in {\{1,...,n\} \choose k}$, which is why $i \in \{1,...,{n \choose k}\}$. In other words, the definition of $A_i$ implicitly defines a bijection between all $A_i$ and ${\{1,..., n\} \choose k}$).

Since there are $k$ fixed elements for all $f \in A$, we consider how to permute the remaining $n - k$ elements. These elements cannot be fixed. Thus, by letting arbitrary $N' \in {\{1,...,n\} \choose k}$, the number of permutations of $X$ where the $k$ points in $N'$ are fixed and the rest are not is equivalent to the number of derangements (see side note for further explanation) of the set $X \setminus N'$. Additionally, because there are ${n \choose k}$ ways to fix $k$ elements, we have

$${n \choose k} \cdot D(|X \setminus N'|) = {n \choose k} \cdot D(n - k) = {n \choose k} \cdot ((n - k)! - \displaystyle\sum_{i = 1}^{n - k} (-1)^{i - 1} {(n - k) \choose i} (n - k - i)!)$$

as the total number of permutations of $X$ with exactly $k$ fixed points. More concisely, we have $${n \choose k} \cdot D(|X \setminus N'|) = {n \choose k} ((n - k)! - \displaystyle\sum_{i = 1}^{n - k} (-1)^{i - 1} \dfrac{(n - k)!}{i!})$$

Side note: A derangement of a set is a permutation of the set such that no element is mapped to itself. The total number of derangements of an n-element set is $$D(n) = n! - \displaystyle\sum_{i = 1}^n (-1)^{i - 1} {n \choose i}(n - i)! = n! - \displaystyle\sum_{i = 1}^n (-1)^{i - 1} \dfrac{n!}{i!}$$ The proof for the total number of derangements of a set utilizes the principle of inclusion-exclusion, but I will not include it here as it does not directly answer your question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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