#k-comparable.maple
interface(quiet=true):
with(linalg):
##############################################################
#
#   This file computes the number of distinct pairs u<_kw
#   in S_n (for k=1,...,maxk), and records k and the length difference.
#   It is only necessary to do this for maxk at most n/2, which 
#   makes this a bit more efficient.
#
#	Frank Sottile
#	Toronto
#	19 September 1997
#
###############################################################

n:=8:
maxk:=4:

Sn:=[]:
pi:=[]:                            
for j from 1 to n do:       #  Initializes pi = identity
pi := [pi[],j]: od:         

asc := 1:                   #  The ASCents of pi
while (asc > 0) do:

w := eval(pi):              #   the value of pi
Sn:=[Sn[],w]:
asc := 0;
for j from 1 to n-1 do:                   #   Finds the last ascent of pi
if (pi[j]<pi[j+1]) then asc := j fi: od;   

if (asc >0) then                            # If pi has an ascent  at asc...
  dummy := eval(pi[asc]);
  for ii from asc+1 to n do:
  if (pi[ii]>dummy) then bigger:=ii fi: od:
  pi[asc]:= eval(w[bigger]):                # kills the ascent at asc
  w[bigger]:= dummy: 
  for jj from 1 to n-asc do;
  pi[asc+jj]:= eval(w[n+1-jj]); od;         # makes pi increasing afterwards
fi;
od:



STAT:=matrix(4,16,0):

for u in Sn do                            # Loops over all pairs

 for k from 1 to maxk do		  #  checks the k-B.O.
  size := k*(n-k):
  current:={u}:

#lprint(`size`,size,`u`,u);


  for j from 1 to size do
   Next:={}:
   if not(current={}) then
    for w in current do 
     for a from 1 to k do
      for b from k+1 to n do
       bigger:= evalb(w[a]<w[b]):
        for i from a+1 to b do
         bigger:= bigger and ((w[i]<w[a]) or (w[i]>=w[b]))
        od:
       if bigger  then 
         v := eval(w):
         v[a]:= eval(w[b]):
         v[b]:= eval(w[a]):
         Next:= Next union {v}:
       fi:
#lprint(j,`current`,current);
#lprint(Next);

    od:od:od:
   fi:

   STAT[k,j] := STAT[k,j]+ nops(Next):
   current:= eval(Next):

od:od:od:


print(STAT);

time();
quit

###################################