From: Max Alekseyev
Date: Thu, Dec 7, 2006 at 5:58 PM
Subject: Re: Permutations by total distance


On 12/7/06, Franklin T. Adams-Watters 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 a
permutation 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 in
Class 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. Then
f(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 such
permutations 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 a
permutation on {1,2,...,n} such that p'(i)=p(i) for i different from
j1 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 into
pairs {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