Permutations by total distance

[franktaw at netscape.net]

This is in the OEIS, without the final 0's, as A007623.  The 
representation without the final 0 is more common; I have usually seen 
it referred to as "base factorial", not "factoradic".

I don't know why you'd have trouble emailing me; when you send email 
with me and the mailing list both on the address lines, I always get 
two copies.

As for my question, Max answered it, with a very nice proof.

Franklin T. Adams-Watters


-----Original Message-----
From: jvospost3 at gmail.com

   Permutations can be lexicographically ordered according to the 
"factoradic"

 http://en.wikipedia.org/wiki/Factoradic

  I don't see in OEIS, but it might be relevant to your inquiry, the 
digits (not subscripts) of factoradic of n read as if a decimal 
representation:

  10, 100, 110, 200, 210, 1000, 1010, 1100, 1110, 1200, 1210, 2000, 
2010, 2100, 2110, 2200, 2210, 3000, 3010, 3100, ...

  I apologize for too many seqfan emails, but this seemed on-topic to 
your question, and giving an easy sequence not already in OEIS. I'd 
email Frank directly, but my emails to him seem not to go through.

 Best,

 Jonathan Vos Post


On 12/7/06, Max A. <maxale at gmail.com> wrote: 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




________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and 
industry-leading spam and email virus protection.