Let n be a positive integer, and let Sn be the set of all permutations of 1,2,...,n. let k be a non-negative integer, let an,k be the number of even permutations σ in Sn such that ∑ni=1|σ(i)−i|=2k and bn,k be the number of odd permutations σ in Sn such that ∑ni=1|σ(i)−i|=2k. Evaluate an,k−bn,k. * * *
Problem
Source:
Tags: combinatorics, permutations, Romanian TST, 2017
30.01.2022 21:08
The answer is (-1)^k \binom{n-1}{k}. Let f(n,k)=a_{n,k}-b_{n,k}. The key idea is to pair most odd and even permutations and count number of unpaired ones by getting a recurrence relation. Suppose \sigma(1)=k and for some l, \sigma(l)\ge l and l\le k. This means swapping \sigma(l) and \sigma(1) creates another permutation with the opposite parity but same \sum\limits_{j=1}^n |\sigma(j)-j|. Let f(\sigma) be the smallest integer l>1 such that \sigma(l)\ge l and \sigma(1)\ge l (if it doesn't exist f(\sigma)=-1). If I swap \sigma(1), \sigma(l), we have \sigma(j)=j-1 for all 2\le j\le l-1, so swapping \sigma(1), \sigma(l) preserves f(\sigma). Furthermore, the operation is an involution, so it is a bijection. (Note swapping any two arbitrarily doesn't make it involution, but this is valid). Hence the number of even permutations with f(\sigma)=k is equal to the number of odd permutations with f(\sigma)=k. It follows that \sigma(j)=j-1 for all 2\le j\le \sigma(1). This means \sum\limits_{j=1}^{\sigma(1)} |\sigma(j)-j| = 2\sigma(1). The parity of the first \sigma(j) elements is (-1)^{\sigma(j)-1} since we have a cycle of length \sigma(j). Therefore, we have the recursion f(n,k)=\sum\limits_{j=0}^k (-1)^j f(n-1-j,k-j). We can check that f(n,k)=(-1)^k \binom{n-1}{k} for small n,k by hand. We can use strong induction: f(n-1-j,k-j) = (-1)^{k-j} \binom{n-2-j}{k-j} then it follows f(n,k)=\sum\limits_{j=0}^k (-1)^k \binom{n-2-j}{k-j} = (-1)^k \sum\limits_{j=0}^k \binom{n-2-j}{n-2-k} = (-1)^k\binom{n-1}{n-1-k}=(-1)^k\binom{n-1}{k}.