Permutations by total distance

[Jonathan Post]

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061209/132f414b/attachment-0002.htm>