#OK to post
#Michael Yen, 10/11/20, Assignment 10

#1) Carefully read and understand the Maple code for Lecture 10, that contain procedures
#MulPers(P1,P2) , InvPer(P) , GrabCycle(P,i), PtoC(P), CtoP(C), FunT(pi), GG(S) , inv(pi), 
#maj(pi) , FunT(pi)

#By doing the following computations, both by hand and by computer as follows

#(i) Generate two random permuations of length 9 (use combinat[randperm](9)) , call them P1, P2, 
#and BY HAND, find both P1*P2 and P2*P1 (* in the sense of permutation multiplication) check your 
#answers by performing MulPerms(P1,P2) , and MulPerms(P2,P1). Are they the same

#P1 = 3 8 4 9 1 5 6 7 2
#P2 = 8 5 6 4 3 9 7 2 1

#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
#3 8 4 9 1 5 6 7 2     8 5 6 4 3 9 7 2 1       6 2 4 1 8 3 9 7 5

#Yes, they are the same.

#(ii) Generate a random permuations of length 9 (use combinat[randperm](9)) , call it P, and BY 
#HAND, find the inverse permutation P^(-1). Then check it with InvPer(P)

#P=2, 4, 1, 5, 8, 9, 7, 3, 6

#1 2 3 4 5 6 7 8 9      2 4 1 5 8 9 7 3 6     1 2 3 4 5 6 7 8 9
#2 4 1 5 8 9 7 3 6      1 2 3 4 5 6 7 8 9     3 1 8 2 4 9 6 5 6

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

#Yes, they are the same.

#(iii) Generate a random permuations of length 9 (use combinat[randperm](9)) , call it P, and BY 
#HAND, find its cycle structure using the convention of PtoC(P) (each cycle must start with the 
#largest element, and the cycles are arranged in increasing order of their first (i.e. largest) 
#element. Then test your calclulation by applying PtoC(P)

#P=4,6,9,1,3,7,5,8,2


#1 2 3 4 5 6 7 8 9
#4 6 9 1 3 7 5 8 2

#1->4->1
#(4,1)

#2->6->7->5->3->9->2
#(9,2,6,7,5,3)

#8->8
#(8)

#Yes, they are the same.

#(iv) Generate a random permuations of length 9 (use combinat[randperm](9)) , call it P, and BY 
#HAND, find its number of inversions and its major index (the sum of the places i such that 
#pi[i]>pi[i+1]). Check that it agrees with inv(P) and maj(pi)

#P= 5,7,1,4,9,8,3,6,2

#num of inversions
#11111111111111111111 (tally) = 20
#inv(P)=20

#major index
#2+5+6+8=21
#maj(P)=21

#Agrees

#2) Write procedures InvGF(n,q) and MajGF(n,q) that inputs a positive integer n, and a variable 
#q, and outputs the weight-enumerator of the set of permutations of length n according to the 
#number of inversion and major-index. In other words the sum of qinv(pi) and qmaj(pi) 
#respectively over all n! permutations. Is it true that InvGF(n,q)=MajGF(n,q) for n=1,...,7?

InvGF:=proc(n,q) local i,l:
l:=permute(n):
q*add(inv(l[i]),i=1..nops(l)):
end:

MajGF:=proc(n,q) local i,l:
l:=permute(n):
q*add(maj(l[i]),i=1..nops(l)):
end:

#Yes, true

#3) Try to conjecture a formula for InvGF(n,q), by looking at the ratios InvGF(n,q)/InvGF(n-1,q) 
#for n=2....,7.

#Cannot use 2 because of division by 0, so I used n=3...8 instead.
#These are the ratios [9, 8, 25/3, 9, 49/5, 32/3].
#It doesn't show much so I tried getting them separately.

#InvGF(n,q)
#9*q, 72*q, 600*q, 5400*q, 52920*q, 564480*q

#InvGF(n-1,q)
#q, 9*q, 72*q, 600*q, 5400*q, 52920*q

#InvGF(n,q)=?
#InvGF(1,q)=0
#InvGF(2,q)=q

#I don't think I can I see any relationship here.

#4) A permutation P is abc-avoiding if you can't find triples 1 ≤ a < b < c ≤ n such that pi[a] < 
#pi[b] < < pi[c]. For example 43215 is abc-avoiding but 31425 is not. Find the first 8 members of 
#the sequence
#"Number of abc-avoiding permutations of length n"

#and check whether it is in the OEIS.

#Hint: First write a procedure IsBad(P) that returns true as soon as you found an abc-pattern by 
#doing a triple do-loop similar to the double do-loop in inv(P). Then write another procedure 
#that goes over all the n! permutations and counts the ones that are not bad.

isBad:=proc(P) local i,j,k,n:
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]<P[k] then
	return true:
     fi:
   od:
 od:
od:

return false:

end:

abcAvoidCount:=proc(n) local l,co,i:

l:=permute(n):
co:=0:

for i from 1 to nops(l) do
  if not isBad(l[i]) then
    co:=co+1:
  fi:
od:

co:

end:

#[seq(abcAvoidCount(m), m = 1 .. 8)];
#              [1, 2, 5, 14, 42, 132, 429, 1430]
# Yes, this is in the OEIS as A000108 or Catalan Numbers

#5) [A little challenging, but do your best] Write a procedure InvFunT(P) that inputs a 
#permutation P and outputs a permutation Q such that P=FunT(Q). Check it by running
#S:=permute(7): {seq(evalb(InvFunT(FunT(pi))=pi), pi in S)};{evalb(FunT(InvFunT(pi))=pi), pi in 
#S)};

#getting {true} and {true}

#[Hint: Look at the structure of the output of FunT(P) and try "undo" it (or "parse" it), getting 
#a list of cycles, and then use procedure CtoP]