#Please do not post homework
#Tifany Tong, October 11th, 2020, HW #10

# Question 1

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

# p1 * p2 = 
# [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]
# [                 ] * [		  ] = [                 ]
# [9 2 4 1 6 8 3 7 5]   [4 5 3 2 7 8 1 9 6] = [6 5 2 4 8 9 3 1 7]

# p2 * p1 = 
# [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]
# [                 ] * [		  ]   [                 ]
# [4,5,3,2,7,8,1,9,6]   [9,2,4,1,6,8,3,7,5] = [1 6 4 2 3 7 9 5 8] 

# p1*p2 and p2*p1 are not the same, and I confirmed this with MulPers(p1,p2) and MulPers(p2,p1). 

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

#1->9, 2->1, 3->2, 4->3, 5->7, 6->5, 7->8, 8->6, 9->4

#This gives you 912375864, and I confirm this with InvPer([2,3,4,9,6,8,5,7,1])

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

# 1-->7-->9-->4-->6-->2-->5 (9462517) 
# 3-->8 (83) 

# Now, from this, we get: [[8,3],[9,4,6,2,5,1,7]], which I confirm with PtoC([7,5,8,6,1,2,9,3,4])

# (iv): 
# [6,9,8,2,4,3,1,5,7] 
# Number of Inversion: |{(8,2), (6,1), (6,2), (6,3), (6,5), (6,4), (9,8), (9,2), (9,1), (9,3), (9,4), (9,5),
# (9,6), (9,7), (8,4), (8,3), (8,1), (8,5), (8,7), (4,3), (4,1), (3,1)}| = 22
# Major Index: 2+3+5+6 = 16
# inv([6,9,8,2,4,3,1,5,7] ) = 22 and maj([6,9,8,2,4,3,1,5,7]) = 16

# Question 2:

with(combinat);
InvGF := proc(n, q) local i, ans, sum, perms:
perms := permute(n):
ans := 0:
sum := 0:
for i to nops(perms) do 
  ans := inv(perms[i]):
  sum := sum + q^ans:
od:
sum:
end:

MajGF := proc(n, q) local i, ans, sum, perms:
perms := permute(n):
ans := 0:
sum := 0:
for i to nops(perms) do 
  sum := maj(perms[i]):
  ans := ans + q^sum:
od:
ans:
end:

# It is true that InvGF(n,q)=MajGF(n,q) for n=1,...,7.

# Question 3:

# I conjecture that we would get for (InvGF(n,q)/InvGF(n-1,q)) = q^(n-1) + q^(n-2) + ... q + 1

# Question 4: 

with(combinat):
IsBadP := proc(p) local i, j, k, ans, perms:
for i to nops(p) do 
  for j from i + 1 to nops(p) do 
    for k from j + 1 to nops(p) do 
         if p[j] < p[k] and p[i] < p[j] then return true: fi:
    od:
   od:
od: 
return false:
end:

check := proc(n) local perms, i, ans:
perms := permute(n):
ans := 0:
for i to nops(perms) do 
   if IsBadP(perms[i]) = false then ans := ans + 1: fi:
od:
ans:
end:

# I get the sequence: 1,2,5,14,42,132,429,1430 which corresponds to A108 in the OEIS. 


# Question 5

# My attempt: 

InvFunT := proc(P) local i, curr, help:
curr := []:
for i from 1 to nops(P) do 
   help := GrabCycle(P, i):
   if not member(help, curr) then curr := [op(curr), help]: fi: 
od:
return CtoP(curr):
end: