Identities for Permutations with Fixed Points

Jean-Christophe Pain CEA, DAM, DIF F-91297 Arpajon France and Université Paris-Saclay CEA, Laboratoire Matière en Conditions Extrêmes F-91680 Bruyères-le-Châtel France

                  jean-christophe.pain@cea.fr

Abstract We present identities for permutations with fixed points. The formulas are based

on successive derivations or integrations of the determinant of a particular matrix.

1 Introduction

The number of permutations with fixed points can be obtained by induction [1]. It is of interest for combinatorial interpretations of relations for the number of derangements [3]. For instance, the number of derangements can be interpreted as the sum of the values of the largest fixed points of all non-derangements of length n − 1 [2]. In the same paper, Deutsch and Elizalde [2] showed that the analogous sum for the smallest fixed points equals the number of permutations of length n with at least two fixed points. In this short article, we derive identities for the fixed-point statistics over the symmetric group.

Definition 1. Let us consider, for x ∈ ℝ and a natural number n ≥ 2, the n × n matrix

M_{x} = [\begin{matrix}x & 1 & ⋯ & 1 & 1 \\ 1 & x & ⋯ & 1 & 1 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 1 & 1 & ⋯ & x & 1 \\ 1 & 1 & ⋯ & 1 & x \end{matrix}] .

The characteristic polynomial of the matrix −M_{0} is

χ_{−M_{0}}(X) = det(XI_{n} + M_{0}).

Hence, since χ_{−M_{0}}(1) = 0, it follows that 1 is an eigenvalue, the corresponding eigenspace being

E_{1} = ker(−M_{0} − I_{n}) = ker(M_{0} + I_{n}).

We have

x = (x_{1}, ⋯, x_{n}) ∈ E_{1} ⟺ x_{1} + x_{2} + ⋯ + x_{n} = 0,

which is a hyperplane of dimension n − 1. This implies that the multiplicity of 1 is n − 1. In addition, the sum of all eigenvalues is equal to the trace of the matrix −M_{0}, i.e., 0, and therefore 1 − n is also an eigenvalue. We have

x = (x_{1}, ⋯, x_{n}) ∈ E_{1−n} ⟺ ∀i ∈ [1, n], (n − 1)x_{i} = ∑_{k=1,k≠i}^{n} x_{k}
⟺ x_{1} = x_{2} = ⋯ = x_{n}
⟺ x = span{(1, 1, ⋯, 1)},

and the multiplicity of 1 − n is 1. Thus

det M_{x} = det(xI_{n} + M_{0})
= (x − 1 + n)(x − 1)^{n−1}.  (1)

By the Leibniz formula [4], the determinant of the matrix M_{x} gives

det M_{x} = ∑_{σ∈𝔖_{n}} ϵ(σ) ∏_{i=1}^{n}(m(x))_{σ(i),i},

where ϵ(σ) is the signature of the permutation σ ∈ 𝔖_{n} and

(m(x))_{σ(i),i} = \begin{cases}1, & if σ(i) ≠ i; \\ x, & if σ(i) = i, \end{cases}

yielding

det M_{x} = ∑_{σ∈𝔖_{n}} ϵ(σ) ∏_{i∈fix(σ)} x
= ∑_{σ∈𝔖_{n}} ϵ(σ)x^{fix(σ)},  (2)

where fix(σ) is the number of fixed points of σ.

2 First relation by successive derivatives of the deter-

minant

Theorem 2. Let x ∈ ℝ and n be a natural number. We have

∑_{σ∈𝔖_{n}} ϵ(σ)fix(σ) (fix(σ) − 1) ⋯ (fix(σ) − k + 1) x^{fix(σ)−k} = (x − 1)^{n−k−1} \frac{n!(x + n − k − 1)}{(n − k)!}.

(3)

Proof. By differentiating Eq. (2) k times, for k ≥ 1, one gets

(det M_{x})^{(k)} = ∑_{σ∈𝔖_{n}} ϵ(σ)fix(σ) (fix(σ) − 1) ⋯ (fix(σ) − k + 1) x^{fix(σ)−k}.  (4)

The Leibniz formula for the multiple derivative of a product gives, using Eq. (1):

(det M_{x})^{(k)} = ∑_{p=0}^{k} \binom{k}{p}(x − 1 + n)^{(p)} ((x − 1)^{n−1})^{(k−p)}

and

(x + 1 − n)^{(p)} = \begin{cases}x − 1 + n, & if p = 0; \\ 1, & if p = 1; \\ 0, & otherwise, \end{cases}

and thus

(det M_{x})^{(k)} = (x − 1 + n) ((x − 1)^{n−1})^{(k)} + k ((x − 1)^{n−1})^{(k−1)}

= (x − 1)^{n−k−1} \frac{(n − 1)!}{(n − k − 1)!} (x − 1 + n + \frac{k(x − 1)}{n − k})

= (x − 1)^{n−k−1} \frac{n!(x + n − k − 1)}{(n − k)!},  (5)

which, combined with Eq. (4), completes the proof.

For x = 1, according to Eq. (5), one has

(det M_{1})^{(k)} = n! δ_{k,n−1},

where δ_{i,j} is the usual Kronecker delta symbol. Setting k = n − 1 in Eq. (4) yields

∑_{σ∈𝔖_{n}} ϵ(σ)fix(σ) (fix(σ) − 1) (fix(σ) − 2) ⋯ (fix(σ) − n + 2) = n!.

As another example, setting x = 2 in Eq. (3) gives

∑_{σ∈𝔖_{n}} ϵ(σ)fix(σ) (fix(σ) − 1) (fix(σ) − 2) ⋯ (fix(σ) − k + 1) 2^{fix(σ)−k} = \frac{n!(n − k + 1)}{(n − k)!}.

3 Second identity by successive integrations of the de-

terminant

Theorem 3. For k ∈ ℕ^{∗} we have

∑_{σ∈𝔖_{n}} ϵ(σ)\frac{(fix(σ))!}{(fix(σ) + k)!} = (−1)^{n+1} \frac{(n^{2} + (k − 1)n − (k − 1))}{(k − 1)!(n + k − 1)(n + k)}.  (6)

Proof. The left-hand side of Eq. (6) is obtained by successive integrations of

∑_{σ∈𝔖_{n}} ϵ(σ)x^{fix(σ)}.

According to Eq. (2), it is therefore equal to P_{n,k}(1) with, for k ≥ 2:

P_{n,k}(x) = ∫_{0}^{x} (∫_{0}^{x_{k−1}} (∫_{0}^{x_{k−2}} ⋯ (∫_{0}^{x_{2}} (∫_{0}^{x_{1}} det(M_{u})du) dx_{1}) ⋯) dx_{k−2}) dx_{k−1}, (7)

or also

P_{n,k}(x) = ∫_{0}^{x} P_{n,k−1}(u)du.

Since det(M_{x}) = (x − 1)^{n} + n(x − 1)^{n−1}, one has in particular

P_{n,1}(x) = ∫_{0}^{x} det(M_{u})du = (−1)^{n+1} \frac{n}{n + 1} + \frac{(x − 1)^{n+1}}{n + 1} + (x − 1)^{n},  (8)

as well as

P_{n,2}(x) = ∫_{0}^{x} (∫_{0}^{x_{1}} det(M_{u})du) dx_{1} = ∫_{0}^{x} P_{n,1}(u)du

yielding

P_{n,2}(x) = (−1)^{n+1} \frac{nx}{(n + 1)} + \frac{(−1)^{n+1}}{(n + 1)(n + 2)} + \frac{(−1)^{n}}{(n + 1)} + \frac{(x − 1)^{n+2}}{(n + 1)(n + 2)} + \frac{(x − 1)^{n+1}}{(n + 1)} . (9)

Applying the same procedure, the polynomial for k = 3 gives

P_{n,3}(x) = ∫_{0}^{x} (∫_{0}^{x_{1}} (∫_{0}^{x_{2}} det(M_{u})du) dx_{1}) dx_{2} = ∫_{0}^{x} P_{n,2}(u)du

leading to

P_{n,3}(x) = (−1)^{n+1} \frac{nx^{2}}{2(n + 1)}

+ (−1)^{n+1} \frac{x}{(n + 1)(n + 2)} + (−1)^{n} \frac{x}{(n + 1)}

+ \frac{(−1)^{n}}{(n + 1)(n + 2)(n + 3)} + \frac{(−1)^{n+1}}{(n + 1)(n + 2)}

+ \frac{(x − 1)^{n+3}}{(n + 1)(n + 2)(n + 3)} + \frac{(x − 1)^{n+2}}{(n + 1)(n + 3)}.  (10)

Setting k = 1, 2 and 3 in Eqs. (8), (9) and (10) gives (all the terms proportional to powers of x − 1 vanish):

P_{n,1}(1) = (−1)^{n+1} \frac{n}{(n + 1)},

P_{n,2}(1) = (−1)^{n+1} \frac{n}{(n + 1)} + \frac{(−1)^{n+1}}{(n + 1)(n + 2)} + \frac{(−1)^{n}}{(n + 1)},

and

P_{n,3}(1) = (−1)^{n+1} \frac{n}{2(n + 1)}

+ \frac{(−1)^{n+1}}{(n + 1)(n + 2)} + \frac{(−1)^{n}}{(n + 1)}

+ \frac{(−1)^{n}}{(n + 1)(n + 2)(n + 3)} + \frac{(−1)^{n+1}}{(n + 1)(n + 2)}.

Thus, for any value of k ≥ 2, we have

P_{n,k}(1) = \frac{(−1)^{n+1}n}{(n + 1)(k − 1)!} − ∑_{j=2}^{k} \frac{(−1)^{n+j}}{(k − j)!} (\frac{1}{∏_{l=n+1}^{n+j} l} − \frac{1}{∏_{l=n+1}^{n+j−1} l}) ,

with

∑_{j=2}^{k} \frac{1}{(k − j)!} \frac{(−1)^{n+j}}{∏_{l=n+1}^{n+j} l} = ∑_{j=2}^{k} \frac{(−1)^{n+j}}{(k − j)!} \frac{n!}{(n + j)!}.

Let us set

S_{n}(k) = ∑_{j=2}^{k} \frac{(−1)^{n+j}}{(k − j)!(n + j)!},

so that we can write

P_{n,k}(1) = \frac{(−1)^{n+1}n}{(n + 1)(k − 1)!} − n! S_{n}(k) − n! S_{n−1}(k).  (11)

Let us now assume that k ≥ 2. We have

S_{n}(k) = ∑_{j=2}^{k} \frac{(−1)^{n+j}}{(k − j)!(n + j)!}

= \frac{1}{(n + k)!} ∑_{j=2}^{k} \frac{(−1)^{n+j}(n + k)!}{(k − j)!(n + j)!}.

The latter quantity is equal to

S_{n}(k) = \frac{1}{(n + k)!} ∑_{j=2}^{k} \binom{n + k}{n + j}(−1)^{n+j}

= \frac{1}{(n + k)!} ∑_{m=n+2}^{n+k} \binom{n + k}{m}(−1)^{m}

= \frac{1}{(n + k)!} (∑_{m=0}^{n+k}(−1)^{m}\binom{n + k}{m} − ∑_{m=0}^{n+1}(−1)^{m}\binom{n + k}{m})

= −\frac{1}{(n + k)!} ∑_{m=0}^{n+1}(−1)^{m}\binom{n + k}{m}

= −\frac{T_{n}(k)}{(n + k)!},

with

T_{n}(k) = ∑_{m=0}^{n+1} \binom{n + k}{m}(−1)^{m}.

Since

\binom{n + k}{m} = \binom{n + k − 1}{m} + \binom{n + k − 1}{m − 1},

we get

T_{n}(k) = ∑_{m=1}^{n+1}(−1)^{m}\binom{n + k − 1}{m} + ∑_{m=1}^{n+1}(−1)^{m}\binom{n + k − 1}{m − 1} + 1

= ∑_{m=1}^{n+1}(−1)^{m}\binom{n + k − 1}{m} + ∑_{m=0}^{n}(−1)^{m+1}\binom{n + k − 1}{m} + 1

= (−1)^{n+1}\binom{n + k − 1}{n + 1} − 1 + 1

= (−1)^{n−1}\binom{n + k − 1}{n + 1}.

We therefore obtain

S_{n}(k) = \frac{(−1)^{n}(n + k − 1)!}{(n + 1)!(k − 2)!(n + k)!}

= \frac{(−1)^{n}}{(n + 1)!(k − 2)!(n + k)},

which, combined with Eq. (11), yields

P_{n,k}(1) = \frac{(−1)^{n+1}n}{(n + 1)(k − 1)!} − n!\frac{(−1)^{n}}{(n + 1)!(k − 2)!(n + k)} − n!\frac{(−1)^{n+1}}{n!(k − 2)!(n − 1 + k)}

= (−1)^{n+1} \frac{(n^{2} + (k − 1)n − (k − 1))}{(k − 1)!(n + k − 1)(n + k)},

which completes the proof.

For k = 1, Eq. (6) becomes

∑_{σ∈𝔖_{n}} \frac{ϵ(σ)}{(fix(σ) + 1)} = (−1)^{n+1} \frac{n}{(n + 1)},

while for k = 2 one has

∑_{σ∈𝔖_{n}} \frac{ϵ(σ)}{(fix(σ) + 1)(fix(σ) + 2)} = (−1)^{n+1} \frac{(n + ϕ)(n + 1 − ϕ)}{(n + 1)(n + 2)}

= (−1)^{n+1} \frac{(n + ϕ)(n − 1/ϕ)}{(n + 1)(n + 2)},

where ϕ is the golden ratio, and in the k = 3 case:

∑_{σ∈𝔖_{n}} \frac{ϵ(σ)}{(fix(σ) + 1)(fix(σ) + 2)(fix(σ) + 3)} = (−1)^{n+1} \frac{((n + 1)^{2} − 3)}{2(n + 2)(n + 3)}.

Here also, as in the first section, we have set x = 1, but of course, further sum rules can be obtained by taking different values of x in Eq. (7) and using

P_{n,k}(x) = ∑_{σ∈𝔖_{n}} ϵ(σ)\frac{(fix(σ))!}{(fix(σ) + k)!}x^{fix(σ)+k}.

4 Conclusion

We introduced two families of identities concerning permutations with fixed points, obtained respectively through successive differentiation and repeated integration of the determinant of a specific matrix. Beyond these results, the methods presented here may lead to the derivation of further sum rules.

References

[1] M. Tian and E. Trevino, An unusual recursive formula to answer a question regarding fixed points in permutations, College Math. J. 52 (2021), 219–220.

[2] E. Deutsch and S. Elizalde, The largest and the smallest fixed points of permutations, European J. Combin. 5 (2010), 1404–1409.

[3] F. Rakotondrajao, k-fixed-points-permutations, INTEGERS 7 (2007), Paper A36.

[4] G. Strang, Introduction to Linear Algebra, Cambridge University Press, 2016.

2020 Mathematics Subject Classification: 05A05 ; 05A15. Keywords: permutation, fixed point, sum rule, linear algebra, determinant.

(Concerned with sequences \underline{A000166} and \underline{A008290}.)

Received September 5 2025; revised versions received September 6 2025; October 24 2025; October 27 2025. Published in Journal of Integer Sequences, October 28 2025.

Return to Journal of Integer Sequences home page.