Let n be a positive integer, let Sn be the set of all permutations of the set {1,2,…,n}, and, for each σ in Sn, let I(σ)={i:σ(i)≤i}. Evaluate the sum σ∈Sn∑∣I(σ)∣1i∈I(σ)∑(i+σ(i)).
Solution
Consider the involution of Sn which sends a permutation σ to the permutation σ∗ defined by σ∗(i)=j if and only if σ(n−j+1)=n−i+1. Notice that, for each σ in Sn, the assignment i↦n−σ(i)+1 defines a bijection from I(σ) to I(σ∗) whose inverse sends j to n−σ∗(j)+1. Consequently, σ∈Sn∑∣I(σ)∣1i∈I(σ)∑(i+σ(i))==21σ∈Sn∑∣I(σ)∣1i∈I(σ)∑(i+σ(i))+∣I(σ∗)∣1i∈I(σ∗)∑(i+σ∗(i))=21σ∈Sn∑∣I(σ)∣1i∈I(σ)∑(i+σ(i)+(n−σ(i)+1)+(n−i+1))=(n+1)!.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.