#OK to post
# Soham Palande, Assignment 10, 10/11/2020


#PART 1

#(i) 


p1:=randperm(9)
	p1 := [3, 8, 4, 9, 1, 5, 6, 7, 2]

p2:=randperm(9)
	p2 := [8, 5, 6, 4, 3, 9, 7, 2, 1]

#By hand: p1*p2= [6, 2, 4, 1, 8, 3, 9, 7, 5]
#         p2*p1= [7, 1, 5, 9, 4, 2, 6, 8, 3]

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

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


#(ii)

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

#By hand: [4, 9, 5, 1, 7, 2, 6, 8, 3]

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


#(iii)

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

#By hand: 1->5->9->2->7->3->1 : (159273)
#.                       4->4 : (4)
#                     8->6->8 : (86)
#. [[4], [8, 6], [9, 2, 7, 3, 1, 5]]


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


#(iv)

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

# 7+9+4+8 =28
# for number of inversions for each number in p count how many smaller numbers are to the right and add 
# those up  : 14

maj(p)
	20

inv(p)
	14






# PART 2

InvGF:=proc(n,q) local x,sum,P,pi:
P:=permute(n):
sum:=0:
for pi in P do
    x:=inv(pi):
    sum:=sum+q^x:
od:
sum:
end proc:
    


MajGF:=proc(n,q) local x,sum,P,pi:
P:=permute(n):
sum:=0:
for pi in P do
    x:=maj(pi):
    sum:=sum+q^x:
od:
sum:
end proc:

seq(InvGF(n,4), n=1..7)
	1, 5, 105, 8925, 3043425, 4154275125, 22686496457625

seq(MajGF(n,4), n=1..7)
	1, 5, 105, 8925, 3043425, 4154275125, 22686496457625

#Yes MajGF=InvGF for n=1..7


#PART 3

#Observing:

seq(InvGF(n,4)/InvGF(n-1,4), n=2..7)
	5, 21, 85, 341, 1365, 5461

seq(InvGF(n,5)/InvGF(n-1,5), n=2..7)
	6, 31, 156, 781, 3906, 19531

#We hypothesize the following recursive formula

# InvGF(n,q) =  [[[InvGF(n-1,q)/InvGF(n-2,q)]* q ] + 1] * InvGF(n-1,q)







# PART 4

#Checks whether a given permutation is abc-avoiding: returns true if it is
IsBad:=proc(p) local i,j,k,p1,p2,p3:
for i from 1 to nops(p)-2 do
  p1:=p[i]:
   for j from 2 to nops(p)-1 do
     p2:=p[j]:
       for k from 3 to nops(p) do
          p3:=p[k]:
          if p1<p2 and p2<p3 and p1<p3 then
                 RETURN(true):
          fi:
       od:
   od:
od:
RETURN(false)
end:


#counts number of permutations of length n that are abc-avoiding
Notabc:=proc(n) local p,count,P:
P:=permute(n):
count:=0:
for p in P do
   if not IsBad(p) then
      count:=count+1:
   fi:
od:
count:
end:

Notabc(5)
24
seq(Notabc(i),i=1..8)
1, 2, 5, 14, 24, 20, 0, 0


seq(Notabc(i),i=0..8)
	1, 1, 2, 5, 14, 24, 20, 0, 0


#No, it is not in the OEIS.


# PART 5

InvFunt:=proc(p) local max,list,cycleslist,cycle,i:
max:=p[1]:
list:=[1]:
cycleslist:=[]:
for i from 1 to nops(p) do
   if p[i]>max then
      list:=[op(list),i]:
      max:=p[i]:
   fi:
od:
for i from 1 to nops(list)-1 do:
   cycle:=p[i..(list[i+1]-1)]:
   cycleslist:=[op(cycleslist),cycle]:
od:
cycle:=p[list[nops(list)]..nops(p)]:
cycleslist:=[op(cycleslist),cycle]:
CtoP(cycleslist):
end:


#works when I tested it manually but for some reason the test command in the hw question gives false, 
# true instead of true, true