#OK to post homework
#Kent Mei, 10/11/20, Assignment 10

#---------------------------------
#Part 1

#Part i)
#P1 := [3, 8, 4, 9, 1, 5, 6, 7, 2]
#P2 := [8, 5, 6, 4, 3, 9, 7, 2, 1]

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

#MulPers(P1,P2) = [6, 2, 4, 1, 8, 3, 9, 7, 5]
#MulPers(P2,P1) = [7, 1, 5, 9, 4, 2, 6, 8, 3]
#They are the same.

#Part ii)
#P := [4, 6, 9, 1, 3, 7, 5, 8, 2]
#P^(-1) = [4, 9, 5, 1, 7, 2, 6, 8, 3]

#InvPer(P) = [4, 9, 5, 1, 7, 2, 6, 8, 3]
#They are the same.

#Part iii)
#P := [5, 7, 1, 4, 9, 8, 3, 6, 2]
#Cycle structure: (4)(86)(927315).

#PtoC(P) = [[4], [8, 6], [9, 2, 7, 3, 1, 5]]
#They are the same.

#Part iv)
#P := [7, 1, 3, 5, 2, 8, 9, 6, 4]
#Num of inversions = 6 + 0 + 1 + 2 + 0 + 2 + 2 + 1 + 0 = 14.
#Major index       = 1 + 0 + 0 + 4 + 0 + 0 + 7 + 8 + 0 = 20.

#inv(P) = 14
#maj(P) = 20
#They agree.


#---------------------------------
#Part 2

InvGF:=proc(n,q) local Ans, p:

Ans := 0:

for p in permute(n) do:
	Ans := Ans + q^inv(p)
od:

Ans:

end:


MajGF:=proc(n,q) local Ans, p:

Ans := 0:

for p in permute(n) do:
	Ans := Ans + q^maj(p)
od:

Ans:

end:


#{seq(InvGF(n,q) - MajGF(n,q),n = 1..7)} = {0}
#This means that InvGF(n,q) = MajGF(n,q) for n = 1..7.


#---------------------------------
#Part 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]

#It seems like InvGF(n,q) / InvGF(n-1,q) = 1 + q + q^2 + ... + q^(n-2) + q^(n-1).


#---------------------------------
#Part 4

IsBad:=proc(P) local n, i, j, k:

n := nops(P):

for i from 1 to n do
 for j from i+1 to n do
  for k from j+1 to n do
   if P[i] < P[j] and P[j] < P[k] then
    return true:
   fi:
  od:
 od:
od:

return false:

end:

NumABCAvoiding:=proc(n) local p, count:

count := 0:
for p in permute(n) do
 if not IsBad(p) then
  count := count + 1:
 fi:
od:

count:

end:

#Number of abc avoiding permutations of length n (from n = 0 .. 7):
#[1, 1, 2, 5, 14, 42, 132, 429]
#The sequence in the OEIS is A108, the sequence of Catalan numbers.

#---------------------------------
#Part 5

InvFunT:=proc(P) local i, n, max, cycle, cycles:

n := nops(P):
cycles := []:
cycle := []:

for i from 1 to n do
 if i = 1 then
   cycle := [P[1]]:
   max := P[1]:

 elif max < P[i] then
   cycles := [op(cycles),cycle]:
   cycle := [P[i]]:
   max := P[i]:
 else 
   cycle := [op(cycle), P[i]]:
 fi:

od:

if nops(cycle) > 0 then
  cycles := [op(cycles), cycle]:
fi:

CtoP(cycles):

end:

#S:=permute(7): {seq(evalb(InvFunT(FunT(pi))=pi), pi in S)};{seq(evalb(FunT(InvFunT(pi))=pi), pi in S)};
#{true} {true} is the output which verifies the procedure works.

#COMMENT BY Dr. Z.: GOOD JOB!