We study the difference between the numbers of even and odd permutations in \(\mathfrak{S}_n\) having exactly \(k\) fixed points. We derive a closed formula for this quantity using four complementary approaches: exponential generating functions, a determinant representation, a combinatorial derivation based on inclusion–exclusion on cycle structures, and a factorization via the stabilizer subgroup, through restriction to the complement of the fixed-point set. The resulting expression provides a signed refinement of the classical rencontres numbers and yields a simple polynomial form for the associated signed fixed-point distribution.
Let \(\mathfrak{S}_n\) be the symmetric group [20, 19, 21, 17, 2]. For \(0 \le k \le n\), we denote: \[E_{n,k} = \#\{\sigma \in \mathfrak{S}_n : \sigma \text{ even and has exactly $k$ fixed points}\},\] and \[O_{n,k} = \#\{\sigma \in \mathfrak{S}_n : \sigma \text{ odd and has exactly $k$ fixed points}\}.\]
Let \(D_m = {!m}\) be the number of derangements of size \(m\) (see for instance [7, 8, 13, 14]), which is equal to \[D_m = m! \sum_{j=0}^m \frac{(-1)^j}{j!}.\]
The number of permutations in \(\mathfrak{S}_n\) with exactly \(k\) fixed points has already been the subject of a number of investigations (see for instance Refs. [6, 9, 5, 18]). As an example, in 1975, Goldman published the following formula [11]: \[\frac{1}{n!}\sum_{\sigma\in\mathfrak{S}_n}f(\sigma)^k=\sum_{i=1}^{\min(k,n)}S(k,i),\] where \(f(\sigma)\) denotes the number of fixed points of \(\sigma\) and \(S(k,i)\) the Stirling number of the second kind. The number of permutations with \(k\) fixed points is given by the classical formula: \[T_{n,k} = \binom{n}{k} D_{n-k}.\]
Let us define the signed difference of even and odd permutations: \[\Delta_{n,k} = E_{n,k} – O_{n,k}.\]
We propose four different proofs of the following result:
Theorem 1.1.
The difference of even and odd permutations with \(k\) fixed points (denoted respectively \(E_{n,k}\) and \(O_{n,k}\)) is equal to \[\Delta_{n,k} = (-1)^{\,n-k}\binom{n}{k}(k – n + 1),\] and we have \[E_{n,k} = \frac{T_{n,k} + \Delta_{n,k}}{2} = \frac{\binom{n}{k}}{2} \left( D_{n-k} + (-1)^{n-k}(k-n+1) \right),\] as well as \[O_{n,k} = \frac{T_{n,k} – \Delta_{n,k}}{2} = \frac{\binom{n}{k}}{2} \left( D_{n-k} – (-1)^{n-k}(k-n+1) \right).\]
Although the enumeration of permutations with \(k\) fixed points (rencontres numbers) is classical, the signed refinement involving the alternating character is not usually stated in explicit polynomial form. While it can be derived from the cycle index of the symmetric group, the simplified closed form obtained here does not seem to appear explicitly in the literature.
The first proof is presented in Section 2. It takes advantage of the exponential generating function approach. The second proof, detailed in Section 3, is a self-contained matrix proof, relying on the determinant expansion over permutations. The third proof, given in Section 4, combines a sign-reversing cancellation idea with an exponential generating function evaluation of the remaining signed derangement sum. Finally, a representation-theoretic explanation of the formula is discussed in Section 5, consisting in interpreting \(\Delta_{n,k}\) as the evaluation of the sign character of \(\mathfrak{S}_n\) on permutations with exactly \(k\) fixed points.
The proof of Theorem 1.1 given in this section is based on the exponential generating function.
First proof of Theorem 1.1. The sign of a cycle of length \(m\) is \((-1)^{m-1}\). Thus, the sign of a permutation is the product of these weights over its cycles. To construct a signed exponential generating function, each fixed point (1-cycle) can be marked with an auxiliary variable \(u\) and each \(m\)-cycle for \(m \ge 2\) is weighted by \((-1)^{m-1}\). The exponential generating function of signed permutations with fixed-point marking is \[\mathscr{F}(z,u) = \exp\left( uz + \sum_{m\ge2} \frac{(-1)^{m-1}}{m} z^m \right),\] and satisfies \[n!\,[z^n]\,\mathscr{F}(z,u) = \sum_{k=0}^n \Delta_{n,k}\,u^k,\] because extracting \(u^k\) isolates the signed count of permutations with exactly \(k\) fixed points. Using the classical identity \[\sum_{m\ge1}\frac{(-1)^{m-1}}{m}z^m = \log(1+z),\] we get \[\sum_{m\ge2}\frac{(-1)^{m-1}}{m}z^m = \log(1+z) – z,\] and thus, \[\mathscr{F}(z,u) = \exp\!\left( uz + \log(1+z) – z \right) = (1+z)e^{(u-1)z}.\]
Therefore, we have \[n![z^n]\mathscr{F}(z,u) = (u-1)^n + n(u-1)^{n-1},\] yielding \[\sum_{k=0}^n \Delta_{n,k} u^k = (u-1)^n + n(u-1)^{n-1}.\]
Expanding \[(u-1)^n = \sum_{k=0}^n \binom{n}{k} u^k (-1)^{n-k},\] we get \[n(u-1)^{n-1} = n \sum_{k=0}^{n-1} \binom{n-1}{k} u^k (-1)^{n-1-k},\] and thus \[\Delta_{n,k} = \binom{n}{k}(-1)^{n-k} + n\binom{n-1}{k}(-1)^{n-1-k}.\]
Using the relation \[n\binom{n-1}{k} = (n-k)\binom{n}{k},\] we obtain \[\Delta_{n,k} = (-1)^{n-k}\binom{n}{k}(1-(n-k)) = (-1)^{n-k}\binom{n}{k}(k-n+1).\]
Since \[T_{n,k}=E_{n,k}+O_{n,k}, \qquad \Delta_{n,k}=E_{n,k}-O_{n,k},\] we find \[E_{n,k} = \frac{T_{n,k} + \Delta_{n,k}}{2} = \frac{\binom{n}{k}}{2} \left( D_{n-k} + (-1)^{n-k}(k-n+1) \right),\] \[O_{n,k} = \frac{T_{n,k} – \Delta_{n,k}}{2} = \frac{\binom{n}{k}}{2} \left( D_{n-k} – (-1)^{n-k}(k-n+1) \right),\] which completes the first proof of Theorem 1.1. ◻
As an example, in the \(k=n\) case, only the identity permutation is counted, which is even: \(\Delta_{n,n} = 1\). In the \(k=n-1\) case, we find \(\Delta_{n,n-1} = 0\). For \(n=3, k=1\), we get \[T_{3,1}=\binom{3}{1}D_2 = 3, \qquad \Delta_{3,1} = -3,\] and \[E_{3,1}=0, \qquad O_{3,1}=3.\]
The proof of Theorem 1.1 given in this section is based on matrix determinants.
Second proof of Theorem 1.1. For each permutation \(\sigma\in \mathfrak{S}_n\), denote by \(\operatorname{fix}(\sigma)\) the number of fixed points of \(\sigma\), and define the generating polynomial \[P_n(u)=\sum_{k=0}^n \Delta_{n,k}\,u^k =\sum_{\sigma\in \mathfrak{S}_n} \operatorname{sgn}(\sigma)\, u^{\operatorname{fix}(\sigma)} ,\] where \(\operatorname{sgn}(\sigma)\) denotes the signature of \(\sigma\), which is a morphism from \(\mathfrak{S}_n\) to \(\{-1,1\}\). In the following, \(P_n(u)\) will be called the signed enumeration polynomial.
A determinant whose expansion produces \(P_n(u)\). Consider the \(n\times n\) matrix \(A(u)=(a_{ij})\) defined by \[a_{ii}=u, \qquad a_{ij}=-1 \quad (i\neq j).\]
Equivalently, \[A(u)=(u+1)I-J,\] where \(I\) is the identity matrix and \(J\) is the all-ones matrix. By the Leibniz formula for the determinant, we have \[\det A(u) =\sum_{\sigma\in \mathfrak{S}_n}\operatorname{sgn}(\sigma) \prod_{i=1}^n a_{i,\sigma(i)} .\]
If \(\sigma\) has \(f=\operatorname{fix}(\sigma)\) fixed points, then \[\prod_{i=1}^n a_{i,\sigma(i)} = u^{f}(-1)^{n-f}.\]
Hence, \[\det A(u) = \sum_{\sigma\in \mathfrak{S}_n} \operatorname{sgn}(\sigma)\, u^{\operatorname{fix}(\sigma)} (-1)^{n-\operatorname{fix}(\sigma)} = (-1)^n \sum_{\sigma\in \mathfrak{S}_n} \operatorname{sgn}(\sigma) (-u)^{\operatorname{fix}(\sigma)} .\]
Therefore, \[\det A(u)=(-1)^n P_n(-u). \label{eq:relation} \tag{1}\]
Direct computation of the determinant. We use the following determinant identity. Let \(B\) be an invertible \(n\times n\) matrix and let \(x,y\in\mathbb{R}^n\). Then \[\det(B+xy^T)=\det(B)\bigl(1+y^TB^{-1}x\bigr).\]
Indeed, since \(B\) is invertible, we have \[\det(B+xy^T) = \det\bigl(B(I+B^{-1}xy^T)\bigr) = \det(B)\det(I+B^{-1}xy^T).\]
Now \(B^{-1}xy^T\) is a rank-one matrix. If \(M=uv^T\) is a rank-one matrix, then its only possible nonzero eigenvalue is \(v^Tu\). Thus, \[\det(I+uv^T)=1+v^Tu.\]
Applying this with \(u=B^{-1}x\) and \(v=y\), we obtain \[\det(I+B^{-1}xy^T)=1+y^TB^{-1}x.\]
Consequently, \[\det(B+xy^T)=\det(B)\bigl(1+y^TB^{-1}x\bigr).\]
The same identity can also be obtained by using the Schur complement. Consider the block matrix \[M= \begin{pmatrix} B & x\\ -y^T & 1 \end{pmatrix}.\]
Computing its determinant through the Schur complement of \(B\) gives \[\det(M)=\det(B)\bigl(1+y^TB^{-1}x\bigr),\] whereas computing it through the Schur complement of the scalar block \(1\) gives \[\det(M)=\det(B+xy^T).\]
Equating these two expressions yields \[\det(B+xy^T)=\det(B)\bigl(1+y^TB^{-1}x\bigr).\]
Since \(A(u)=(u+1)I-J\) and \(J=\mathbf{1}\mathbf{1}^T\) is of rank one, we apply the above identity with \[B=(u+1)I, \qquad xy^T=-J=-\mathbf{1}\mathbf{1}^T.\]
Then \(B^{-1}=(u+1)^{-1}I\), and therefore \[\mathbf{1}^TB^{-1}\mathbf{1} = \frac{n}{u+1}.\]
It follows that \[\begin{aligned} \det\bigl((u+1)I-J\bigr) &= \det((u+1)I) \left(1-\frac{n}{u+1}\right)\\ &= (u+1)^n\frac{u+1-n}{u+1}\\ &= (u+1)^{n-1}(u+1-n). \end{aligned}\]
Combining this with (1), we obtain \[P_n(u) = (-1)^n\det A(-u) = (-1)^n(1-u)^{n-1}(1-u-n).\]
Equivalently, \[\begin{aligned} P_n(u) &= (u-1)^{n-1}(u+n-1)\\ &= (u-1)^n+n(u-1)^{n-1}. \end{aligned}\]
Writing \[P_n(u)=\sum_{k=0}^n \Delta_{n,k}u^k\] and extracting the coefficient of \(u^k\) from \[(u-1)^n+n(u-1)^{n-1},\] we obtain \[\Delta_{n,k} = (-1)^{n-k}\binom{n}{k}(k-n+1).\]
This is the desired signed enumeration formula, and hence the second proof of Theorem 1.1 is complete. ◻
The determinant expansion provides a direct algebraic encoding of the signed enumeration, and the rank–one structure of \((u+1)I-J\) gives a closed form for the determinant, yielding immediately the polynomial identity for \(P_n(u)\) and the explicit signed counts.
We give a direct derivation of the signed sum over derangements using the inclusion–exclusion principle.
Third proof of Theorem 1.1. Let \[\Delta_{n,k} = \sum_{\substack{\sigma \in \mathfrak{S}_n\\ \operatorname{fix}(\sigma)=k}} \operatorname{sgn}(\sigma).\] Fix a subset \(F\subset [n]=\{1,\dots,n\}\) with \(|F|=k\), and let \(R=[n]\setminus F\). Let \[C_{n,k} = \{\sigma\in\mathfrak{S}_n:\operatorname{fix}(\sigma)=k\}\] denote the set of permutations with exactly \(k\) fixed points.
Any permutation \(\sigma\in\mathfrak{S}_n\) whose fixed-point set is \(F\) acts as the identity on \(F\) and induces a permutation \(\tau\) of \(R\) with no fixed points. Conversely, every derangement \(\tau\) of \(R\) extends uniquely to such a permutation \(\sigma\). Hence there is a bijection between permutations in \(C_{n,k}\) and pairs \((F,\tau)\), where \(|F|=k\) and \(\tau\in\mathcal{D}_{n-k}\), with \[\mathcal{D}_m := \{\sigma\in\mathfrak{S}_m:\operatorname{fix}(\sigma)=0\} = C_{m,0}.\] Thus, if \(D_m:=\#\mathcal{D}_m\), then \[\Delta_{n,k} = \binom{n}{k} \sum_{\tau\in\mathcal{D}_{n-k}}\operatorname{sgn}(\tau).\]
We now calculate \[S_m := \sum_{\tau\in\mathcal{D}_m}\operatorname{sgn}(\tau).\] We use the standard exponential formula for labelled combinatorial classes, where cycles of length \(r\) contribute the weight \((-1)^{r-1}/r\) in the exponential generating function. The exponential generating function of signed permutations is \[\exp\left(\sum_{r\ge1}\frac{(-1)^{r-1}}{r}z^r\right) = 1+z.\] This follows from the fact that the sign-weighted cycle index exponential simplifies because of cancellation of higher-order terms. To exclude fixed points, that is, cycles of length \(1\), we remove the term \(z\): \[\sum_{r\ge2}\frac{(-1)^{r-1}}{r}z^r = \log(1+z)-z.\] Hence the exponential generating function of signed derangements is \[F(z) = \exp(\log(1+z)-z) = (1+z)e^{-z}.\] Therefore, \[S_m = m!\,[z^m](1+z)e^{-z}.\] Expanding, \[(1+z)e^{-z} = \sum_{m\ge0}\frac{(-1)^m}{m!}z^m + \sum_{m\ge0}\frac{(-1)^m}{m!}z^{m+1},\] and extracting coefficients gives \[S_m = (-1)^m(1-m).\] Finally, we obtain \[\Delta_{n,k} = \binom{n}{k}(-1)^{n-k}(k-n+1),\] which completes the third proof of Theorem 1.1. ◻
The proof of Theorem 1.1 given in this section is based on a factorization via the stabilizer subgroup.
Fourth proof of Theorem 1.1. The formula obtained in Section 4 admits a natural representation-theoretic interpretation. Indeed, the sign function \[\chi^{\mathrm{sgn}}_{\mathfrak{S}_n}:\mathfrak{S}_n\to\{\pm1\},\] defined by \[\chi^{\mathrm{sgn}}_{\mathfrak{S}_n}(\sigma) = \operatorname{sgn}(\sigma) = \begin{cases} +1, & \text{if $\sigma$ is even,}\\ -1, & \text{if $\sigma$ is odd,} \end{cases}\] is the irreducible sign character of the symmetric group [10]. Therefore, \[\Delta_{n,k} = \sum_{\sigma\in C_{n,k}} \chi^{\mathrm{sgn}}_{\mathfrak{S}_n}(\sigma),\] is the evaluation of this character over the subset of permutations having exactly \(k\) fixed points.
Using the decomposition \[C_{n,k} \simeq \mathcal{P}_k([n])\times \mathcal{D}_{n-k},\] where \(\mathcal{P}_k([n])\) denotes the set of all subsets of \([n]\) having cardinality \(k\), one obtains \[\Delta_{n,k} = \binom{n}{k} \sum_{\tau\in\mathcal{D}_{n-k}} \chi^{\mathrm{sgn}}_{\mathfrak{S}_{n-k}}(\tau).\]
Applying the signed derangement identity established in Section 4, we have \[\sum_{\tau\in\mathcal{D}_m} \chi^{\mathrm{sgn}}_{\mathfrak{S}_m}(\tau) = (-1)^m(1-m),\] for \(m\ge0\). Taking \(m=n-k\) gives \[\sum_{\tau\in\mathcal{D}_{n-k}} \chi^{\mathrm{sgn}}_{\mathfrak{S}_{n-k}}(\tau) = (-1)^{n-k}(k-n+1).\]
Combining the two factors, we obtain the representation-theoretic formula \[\Delta_{n,k} = \binom{n}{k} \sum_{\tau\in\mathcal{D}_{n-k}} \chi^{\mathrm{sgn}}_{\mathfrak{S}_{n-k}}(\tau) = (-1)^{n-k}\binom{n}{k}(k-n+1),\] which completes the fourth proof of Theorem 1.1. ◻
This proof explicitly uses the sign character and can be interpreted in terms of the subgroup of \(\mathfrak{S}_n\) stabilizing a fixed subset \(F\), which is isomorphic to \(\mathfrak{S}_k \times \mathfrak{S}_{n-k}\). The factor \(\binom{n}{k}\) corresponds to the number of ways to choose the fixed points \(F\), while the sum of the character over derangements of \(R\) produces the factor \((-1)^{n-k}(k-n+1)\). This approach shows that combinatorial formulas for signed permutation counts can be interpreted naturally in the language of representations and characters of \(\mathfrak{S}_n\). The first values of \(\Delta_{n,k}\) for \(1\leq n\leq 10\) and \(1\leq k\leq n\) are displayed in Table 1.
| \(n \backslash k\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | |||||||||
| 2 | 0 | 1 | ||||||||
| 3 | -3 | 0 | 1 | |||||||
| 4 | -8 | -6 | 0 | 1 | ||||||
| 5 | -15 | 20 | -10 | 0 | 1 | |||||
| 6 | 24 | -45 | 40 | -15 | 0 | 1 | ||||
| 7 | -35 | 84 | -105 | 70 | -21 | 0 | 1 | |||
| 8 | 48 | -140 | 224 | -210 | 112 | -28 | 0 | 1 | ||
| 9 | -63 | 216 | -420 | 504 | -378 | 168 | -36 | 0 | 1 | |
| 10 | 80 | -315 | 720 | -1050 | 1008 | -630 | 240 | -45 | 0 | 1 |
We have obtained complete closed formulas for even and odd permutations of \(\mathfrak{S}_n\) with \(k\) fixed points, and in particular of the quantity \[\#\{\sigma \in \mathfrak{S}_n : \sigma \text{ even},\ \operatorname{fix}(\sigma)=k\} – \#\{\sigma \in \mathfrak{S}_n : \sigma \text{ odd},\ \operatorname{fix}(\sigma)=k\}.\]
The first proof relies on the generating function method, which provides a clean and efficient derivation of the signed difference formula, and the second proof is based on a determinant expansion over permutations. The third proof uses an inclusion–exclusion decomposition together with an exponential generating function evaluation of signed derangements. The fourth proof consists in a factorization via the stabilizer subgroup, and gives a complete representation-theoretic explanation of the formula by interpreting \(\Delta_{n,k}\) as the evaluation of the sign character of \(\mathfrak{S}_n\) on permutations with exactly \(k\) fixed points.
The methods presented here may find applications to the study of fixed points in other groups. For instance, let \(G\) be a Coxeter group, \(u\) an involution of \(G\), and \(G_u\) the centralizer of \(u\) in \(G\). In certain cases, for example when \(u\) is a reflection, the group \(G_u\) is generated by reflections of \(G\) and is itself a Coxeter group [3]. Coxeter groups are also connected with the theory of braid groups [4]. The group \(\mathfrak{S}_n\) admits a presentation whose generators are the reflections \(s_1,\ldots, s_{n-1}\), subject to the following families of relations \(s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}\), \(s_i s_j = s_j s_i\) if \(|i-j| \ge 2\) and \(s_i^2 = 1\). If we remove the third type of relations, we obtain a new group: this is the braid group on \(n\) strands, in which each element corresponds to a certain way of braiding \(n\) strands, up to deformation. These groups have been extensively studied, notably in Ref. [1]. Such a topic is strongly related to Schubert polynomials [16, 15]. Finally, the odd-even staggering in the permutations with extremal number of fixed points would also be worth investigating [12].