#OK to post homework
#Tianyi Liu, Oct 11, Assignment 10
1. 
(i)
p1:[2, 1, 3, 4, 7, 6, 5, 9, 8]
p2:[8, 3, 1, 7, 6, 4, 9, 2, 5]
 1, 2, 3, 4, 5, 6, 7, 8, 9   1, 2, 3, 4, 5, 6, 7, 8, 9   1, 2, 3, 4, 5, 6, 7, 8, 9
[                         ]*[                         ]=[                         ]
 2, 1, 3, 4, 7, 6, 5, 9, 8   8, 3, 1, 7, 6, 4, 9, 2, 5   3, 8, 1, 7, 9, 4, 6, 5, 2

MulPers(p1,p2)
[3, 8, 1, 7, 9, 4, 6, 5, 2]

 1, 2, 3, 4, 5, 6, 7, 8, 9   1, 2, 3, 4, 5, 6, 7, 8, 9   1, 2, 3, 4, 5, 6, 7, 8, 9
[                         ]*[                         ]=[                         ]
 8, 3, 1, 7, 6, 4, 9, 2, 5   2, 1, 3, 4, 7, 6, 5, 9, 8   9, 3, 2, 5, 6, 4, 8, 1, 7

MulPers(p2,p1)
[9, 3, 2, 5, 6, 4, 8, 1, 7]

(ii)
p:[2, 1, 3, 4, 7, 6, 5, 9, 8]
inv p:2, 1, 3, 4, 7, 6, 5, 9, 8
InvPer(p)
[2, 1, 3, 4, 7, 6, 5, 9, 8]

(iii)
p:[2, 1, 3, 4, 7, 6, 5, 9, 8]
[2, 1], [3], [4], [6], [7, 5], [9, 8]
PtoC(p)
[[2, 1], [3], [4], [6], [7, 5], [9, 8]]

(iv)
p:[2, 1, 3, 4, 7, 6, 5, 9, 8]
#inversions:5 (21,76,65,75,98)
major index:20
inv(p)
5
maj(p)
20


2.
InvGF:=proc(n,q) local L,l,f,i:

L:=permute(n):
l:=nops(L):
f:=0:

for i from 1 to l do
  f:=f+q^(inv(L[i])):
od:

f:
end:

MajGF:=proc(n,q) local L,l,f,i:

L:=permute(n):
l:=nops(L):
f:=0:

for i from 1 to l do
  f:=f+q^(maj(L[i])):
od:

f:
end:

They are the same for n=1..7

3.
seq(factor(InvGF(n,q)/InvGF((n-1),q)),n=2..7)
1+q, q^2+q+1, (1+q)*(q^2+1), q^4+q^3+q^2+q+1, (1+q)*(q^2+q+1)*(q^2-q+1), q^6+q^5+q^4+q^3+q^2+q+1


4.
IsBad:=proc(pi) local i,j,k,x,n:
x:=0:
n:=nops(pi):
 for i from 1 to n do
  for j from i+1 to n do
   for k from i+2 to n do
     if pi[i]<pi[j] then
       if pi[j]<pi[k] then
        x:=1:
       fi:
     fi:
   od:
  od:
 od:
x:
end:

abca:=proc(n) local L,l,i,co:

L:=permute(n):
l:=nops(L):
co:=0:
for i from 1 to l do
 if IsBad(L[i])=1 then 
  co:=co+1;
 fi:
od:

n!-co:
end:

1, 2, 5, 12, 29, 70, 169, 408
It is in the oeis.