Permutations by total distance

[Max A.]

On 12/7/06, franktaw at netscape.net <franktaw at netscape.net> wrote:
> A072949 also contains a conjecture (in question form).  Looking at> A062869, I see a more general conjecture: T(n,k) is even whenever k >=> n.  I don't see any start at a proof of this; but maybe somebody else> can.  (Or compute some more values and show it's wrong.)
For a permutation p, let f(p) = Sum |p(i)-i|.Let T(n,k) be the number of permutations on {1,2,...,n} with f(p)=2k.
Theorem. T(n,k) is even for all n and k>=n.Proof is done by induction on n.
For n=1, we have T(1,k)=0 for all k>=1.
Now let n>=2 be a fixed integer. Assume that T(n-1,k) is even for all k>=n-1.We will show that T(n,k) is even for all k>=n.
Consider the following three classes of permutations p on {1,2,...,n}with f(p)=2k and k>=n.
Class 1: permutations with p(n)=n.Removing element n from the permutation p transforms it into apermutation p' on {1,2,...,n-1} still with f(p')=2k.The mapping p -> p' is a bijection between Class 1 and permutations on{1,2,...,n-1} with f(p')=2k. Hence, the number of permutations inClass 1 is T(n-1,k) with k>=n>n-1, which is even by induction.
Class 2: permutations with p(n)=n-1.Let j be an index such that p(j)=n. Let p' be a permutation on{1,2,...,n-1} such that p'(i)=p(i) for i≠j and p'(j)=n-1. Thenf(p')=f(p)-2=2(k-1).The mapping p -> p' is a bijection between Class 2 and permutations p'on {1,2,...,n-1} with f(p')=2(k-1). Hence, the number of suchpermutations is T(n-1,k-1) with k-1>=n-1, which is even by induction.
Class 3: permutations with p(n) different from n and n-1.Let j1 and j2 be indices such that p(j1)=n-1 and p(j2)=n. Let p' be apermutation on {1,2,...,n} such that p'(i)=p(i) for i different fromj1 and j2, and p'(j1)=n, p'(j2)=n-1. Then p'≠p and f(p')=f(p)=2k,implying that p' belongs to the same Class 3.It is clear that the mapping p -> p' is an involution on Class 3,implying that all permutations in Class 3 can be partitioned intopairs {p,p'}. Hence, the total number of elements in Class  3 is even.
Therefore, T(n,k) as the total number of permutations in Classes 1,2,3 is even.QED.
Max