Return to Answer

You can use inclusion-exclusion to show that the number of permutations in $S_m$ having at least $n$ fixed points is $$\sum_{k=n}^m (-1)^{k-n}{k-1\choose n-1}{m\choose k}(m-k)! = m! \sum_{k=n}^m (-1)^{k-n}\frac{k-1}{k!}$$

We describe now how to obtain the lefthand expression, since the righthand expression is obtained from the lefthand one by straightforward manipulation.

The ${m\choose k}$ comes from choosing $k$ fixed points, the $(m-k)!$ counts permutations in $S_m$ having these $k$ fixed points, and then $(-1)^{k-n}{k-1\choose n-1}$ is an inclusion-exclusion counting coefficient, namely the Möbius function $\mu (\hat{0},\hat{1})$ on the subposet of the Boolean algebra of subsets of $\{ 1,\dots ,k \} $ where we exclude the subsets having size $1\le i \le n-1$.

One way to calculate this Möbius function is to use that each rank-selection of the Boolean algebra is lexicographically shellable. The desired Möbius function will be $(-1)^{k-n}$ multiplied by the number of so-called ``descending chains'' in the lexicographic shelling, which in this case is the number of permutations in $S_k$ that are ascending in the first $n$ letters and then descending after that, which in particular forces the letter $k$ to be the $n$-th letter in the permutation (in one-line notation).

This includes the well-known special case (usually phrased in terms of derangements) that the number of permutations in $S_m$ with at least one fixed point is $\sum_{k = 1}^m (-1)^{k-1} {m\choose k}(m-k)! $ which equals $ - (-m! + \sum_{k= 0}^m(-1)^k {m\choose k}(m-k)!) $. As $m$ goes to infinity, this approaches $ -m!(-1 + 1/e) = m!(1-1/e)$. A good reference for the $n=1$ case is chapter 2 of Enumerative Combinatorics, Volume 1, by Richard Stanley. The original source for lexicographic shellability is Anders Björner's paper ``Shellable and Cohen-Macaulay partially ordered sets''.

Added later: the comments above mention the recontres numbers. These give an approach for obtaining the $n>1$ case as a consequence of the $n=1$ case -- by choosing your fixed point set and then counting derangements on the remaining letters, summing over the possible fixed point sets. This results in a double sum, with an alternating sum as the inner sum.

You can use inclusion-exclusion to show that the number of permutations in $S_m$ having at least $n$ fixed points is $$\sum_{k=n}^m (-1)^{k-n}{k-1\choose n-1}{m\choose k}(m-k)! = m! \sum_{k=n}^m (-1)^{k-n}\frac{1}{k!}{k-1\choose n-1}$$

We describe now how to obtain the lefthand expression. The ${m\choose k}$ comes from choosing $k$ fixed points, the $(m-k)!$ counts permutations in $S_m$ having these $k$ fixed points, and then $(-1)^{k-n}{k-1\choose n-1}$ is an inclusion-exclusion counting coefficient, namely the Möbius function $\mu (\hat{0},\hat{1})$ on the subposet of the Boolean algebra of subsets of $\{ 1,\dots ,k \} $ where we exclude the subsets having size $1\le i \le n-1$.

One way to calculate this Möbius function is to use that each rank-selection of the Boolean algebra is lexicographically shellable. The desired Möbius function will be $(-1)^{k-n}$ multiplied by the number of so-called ``descending chains'' in the lexicographic shelling, which in this case is the number of permutations in $S_k$ that are ascending in the first $n$ letters and then descending after that, which in particular forces the letter $k$ to be the $n$-th letter in the permutation (in one-line notation).

This includes the well-known special case (usually phrased in terms of derangements) that the number of permutations in $S_m$ with at least one fixed point is $\sum_{k = 1}^m (-1)^{k-1} {m\choose k}(m-k)! $ which equals $ - (-m! + \sum_{k= 0}^m(-1)^k {m\choose k}(m-k)!) $. As $m$ goes to infinity, this approaches $ -m!(-1 + 1/e) = m!(1-1/e)$. A good reference for the $n=1$ case is chapter 2 of Enumerative Combinatorics, Volume 1, by Richard Stanley. The original source for lexicographic shellability is Anders Björner's paper ``Shellable and Cohen-Macaulay partially ordered sets''.

Added later: the comments above mention the recontres numbers. These give an approach for obtaining the $n>1$ case as a consequence of the $n=1$ case -- by choosing your fixed point set and then counting derangements on the remaining letters, summing over the possible fixed point sets. This results in a double sum, with an alternating sum as the inner sum.

You can use inclusion-exclusion to show that the number of permutations in $S_m$ having at least $n$ fixed points is $$\sum_{k=n}^m (-1)^{k-n}{k-1\choose n-1}{m\choose k}(m-k)! $$

The ${m\choose k}$ comes from choosing $k$ fixed points, the $(m-k)!$ counts permutations in $S_m$ having these $k$ fixed points, and then $(-1)^{k-n}{k-1\choose n-1}$ is an inclusion-exclusion counting coefficient, namely the Möbius function $\mu (\hat{0},\hat{1})$ on the subposet of the Boolean algebra of subsets of $\{ 1,\dots ,k \} $ where we exclude the subsets having size $1\le i \le n-1$.

One way to calculate this Möbius function is to use that each rank-selection of the Boolean algebra is lexicographically shellable. The desired Möbius function will be $(-1)^{k-n}$ multiplied by the number of so-called ``descending chains'' in the lexicographic shelling, which in this case is the number of permutations in $S_k$ that are ascending in the first $n$ letters and then descending after that, which in particular forces the letter $k$ to be the $n$-th letter in the permutation (in one-line notation).

This includes the well-known special case (usually phrased in terms of derangements) that the number of permutations in $S_m$ with at least one fixed point is $\sum_{k = 1}^m (-1)^{k-1} {m\choose k}(m-k)! $ which equals $ - (-m! + \sum_{k= 0}^m(-1)^k {m\choose k}(m-k)!) $. As $m$ goes to infinity, this approaches $ -m!(-1 + 1/e) = m!(1-1/e)$. A good reference for the $n=1$ case is chapter 2 of Enumerative Combinatorics, Volume 1, by Richard Stanley. The original source for lexicographic shellability is Anders Björner's paper ``Shellable and Cohen-Macaulay partially ordered sets''.

Added later: the comments above mention the recontres numbers. These give a faster approach for obtaining the $n>1$ case quickly as a consequence of the $n=1$ case -- by choosing your fixed point set and then counting derangements on the remaining letters, summing over the possible fixed point sets.

You can use inclusion-exclusion to show that the number of permutations in $S_m$ having at least $n$ fixed points is $$\sum_{k=n}^m (-1)^{k-n}{k-1\choose n-1}{m\choose k}(m-k)! = m! \sum_{k=n}^m (-1)^{k-n}\frac{k-1}{k!}$$

We describe now how to obtain the lefthand expression, since the righthand expression is obtained from the lefthand one by straightforward manipulation.

The ${m\choose k}$ comes from choosing $k$ fixed points, the $(m-k)!$ counts permutations in $S_m$ having these $k$ fixed points, and then $(-1)^{k-n}{k-1\choose n-1}$ is an inclusion-exclusion counting coefficient, namely the Möbius function $\mu (\hat{0},\hat{1})$ on the subposet of the Boolean algebra of subsets of $\{ 1,\dots ,k \} $ where we exclude the subsets having size $1\le i \le n-1$.

One way to calculate this Möbius function is to use that each rank-selection of the Boolean algebra is lexicographically shellable. The desired Möbius function will be $(-1)^{k-n}$ multiplied by the number of so-called ``descending chains'' in the lexicographic shelling, which in this case is the number of permutations in $S_k$ that are ascending in the first $n$ letters and then descending after that, which in particular forces the letter $k$ to be the $n$-th letter in the permutation (in one-line notation).

This includes the well-known special case (usually phrased in terms of derangements) that the number of permutations in $S_m$ with at least one fixed point is $\sum_{k = 1}^m (-1)^{k-1} {m\choose k}(m-k)! $ which equals $ - (-m! + \sum_{k= 0}^m(-1)^k {m\choose k}(m-k)!) $. As $m$ goes to infinity, this approaches $ -m!(-1 + 1/e) = m!(1-1/e)$. A good reference for the $n=1$ case is chapter 2 of Enumerative Combinatorics, Volume 1, by Richard Stanley. The original source for lexicographic shellability is Anders Björner's paper ``Shellable and Cohen-Macaulay partially ordered sets''.

Added later: the comments above mention the recontres numbers. These give an approach for obtaining the $n>1$ case as a consequence of the $n=1$ case -- by choosing your fixed point set and then counting derangements on the remaining letters, summing over the possible fixed point sets. This results in a double sum, with an alternating sum as the inner sum.

You can use inclusion-exclusion to show that the number of permutations in $S_m$ having at least $n$ fixed points is $$\sum_{k=n}^m (-1)^{k-n}{k-1\choose n-1}{m\choose k}(m-k)! $$

The ${m\choose k}$ comes from choosing $k$ fixed points, the $(m-k)!$ counts permutations in $S_m$ having these $k$ fixed points, and then $(-1)^{k-n}{k-1\choose n-1}$ is an inclusion-exclusion counting coefficient, namely the Möbius function $\mu (\hat{0},\hat{1})$ on the subposet of the Boolean algebra of subsets of $\{ 1,\dots ,k \} $ where we exclude the subsets having size $1\le i \le n-1$.

One way to calculate this Möbius function is to use that each rank-selection of the Boolean algebra is lexicographically shellable. The desired Möbius function will be $(-1)^{k-n}$ multiplied by the number of so-called ``descending chains'' in the lexicographic shelling, which in this case is the number of permutations in $S_k$ that are ascending in the first $n$ letters and then descending after that, which in particular forces the letter $k$ to be the $n$-th letter in the permutation (in one-line notation).

This includes the well-known special case (usually phrased in terms of derangements) that the number of permutations in $S_m$ with at least one fixed point is $\sum_{k \ge 1} (-1)^{k-1} {m\choose k}(m-k)! $ which equals $ - (-m! + \sum_{k\ge 0}(-1)^k {m\choose k}(m-k)!) = -m!(-1 + 1/e) = m!(1-1/e)$. A good reference for the $n=1$ case is chapter 2 of Enumerative Combinatorics, Volume 1, by Richard Stanley. The original source for lexicographic shellability is Anders Björner's paper ``Shellable and Cohen-Macaulay partially ordered sets''.

Added later: the comments above mention the recontres numbers. These give a faster approach for obtaining the $n>1$ case quickly as a consequence of the $n=1$ case -- by choosing your fixed point set and then counting derangements on the remaining letters, summing over the possible fixed point sets.

You can use inclusion-exclusion to show that the number of permutations in $S_m$ having at least $n$ fixed points is $$\sum_{k=n}^m (-1)^{k-n}{k-1\choose n-1}{m\choose k}(m-k)! $$

The ${m\choose k}$ comes from choosing $k$ fixed points, the $(m-k)!$ counts permutations in $S_m$ having these $k$ fixed points, and then $(-1)^{k-n}{k-1\choose n-1}$ is an inclusion-exclusion counting coefficient, namely the Möbius function $\mu (\hat{0},\hat{1})$ on the subposet of the Boolean algebra of subsets of $\{ 1,\dots ,k \} $ where we exclude the subsets having size $1\le i \le n-1$.

One way to calculate this Möbius function is to use that each rank-selection of the Boolean algebra is lexicographically shellable. The desired Möbius function will be $(-1)^{k-n}$ multiplied by the number of so-called ``descending chains'' in the lexicographic shelling, which in this case is the number of permutations in $S_k$ that are ascending in the first $n$ letters and then descending after that, which in particular forces the letter $k$ to be the $n$-th letter in the permutation (in one-line notation).

This includes the well-known special case (usually phrased in terms of derangements) that the number of permutations in $S_m$ with at least one fixed point is $\sum_{k = 1}^m (-1)^{k-1} {m\choose k}(m-k)! $ which equals $ - (-m! + \sum_{k= 0}^m(-1)^k {m\choose k}(m-k)!) $. As $m$ goes to infinity, this approaches $ -m!(-1 + 1/e) = m!(1-1/e)$. A good reference for the $n=1$ case is chapter 2 of Enumerative Combinatorics, Volume 1, by Richard Stanley. The original source for lexicographic shellability is Anders Björner's paper ``Shellable and Cohen-Macaulay partially ordered sets''.

Added later: the comments above mention the recontres numbers. These give a faster approach for obtaining the $n>1$ case quickly as a consequence of the $n=1$ case -- by choosing your fixed point set and then counting derangements on the remaining letters, summing over the possible fixed point sets.