> #Weiji Zheng, 10/11/2020, Assignment10
;
> #OK TO POST HOMEWORK
;
> 
;
> #Q1
;
> #Code
;
> MulPers:=proc(P1,P2) local n,i:
> #The first few lines checks that the input is correct
>  if not (type(P1,list) and type(P2,list)) then
>   print(`Bad input`):
>   RETURN(FAIL):
>  fi:
> n:=nops(P1):
> 
> if  not (convert(P1,set)={seq(i,i=1..n)} and convert(P2,set)={seq(i,i=1..n)} ) then
>   print(`Bad input`):
>   RETURN(FAIL):
>  fi:
> 
> [seq(P2[P1[i]],i=1..n)]:
> 
> 
> end:
> InvPer:=proc(P) local i,n,T:
>  if not type(P,list) then
>   print(`Bad input`):
>   RETURN(FAIL):
>  fi:
> 
> n:=nops(P):
> if  not convert(P,set)={seq(i,i=1..n)}  then
>   print(`Bad input`):
>   RETURN(FAIL):
>  fi:
> 
> #Recalling the list P is the function that maps i to P[i], we define a TABLE (a Maple Data structure) that
> #maps P[i] to i
> 
> for i from 1 to n do
>  T[P[i]]:=i:
> od:
> 
> #We convert it back into a list
> [seq(T[i],i=1..n)]:
> end:
> GrabCycle:=proc(P,i) local C,j:
> 
> #We view the cycle belnging to i as a list, starting at i
> C:=[i]:
> 
> #We find where i points to, call it j
> j:=P[i]:
> 
> while j<>i do
> #sooner or later we will wind back at i (since the permutation is finite) so we append the new
> #arrivals to the list C and rename j
> C:=[op(C),j]:
> j:=P[j]:
> od:
> 
> #We look at the place where it it is max
> j:=max[index](C):
> 
> #we rewrite the cycle with the largest entry first
> 
> [op(j..nops(C),C),op(1..j-1,C)]:
> 
> end:
> PtoC:=proc(P) local n,StillToDo,L,i,C,L1,T:
> 
> n:=nops(P):
> 
> StillToDo:={seq(i,i=1..n)}:
> 
> #L is a dynamically construcete list of cycles in the permutatib P, we start with the empty list
> #until no one is left
> L:=[]:
> 
> while StillToDo<>{} do
> #we pick the smallest survivor
>  i:=min(op(StillToDo)):
>  #we grab its cycle
>  C:=GrabCycle(P,i):
> 
> # We append C to L
>  L:=[op(L),C]:
> 
> #We update StillToDo by kicking out the members of C
> 
> StillToDo:= StillToDo minus convert(C,set):
> od:
> 
> #So far L is a list of cycles but arranged in a random order
> #Now we arrange them according to the convention that the first (largest) entries are increasing
> #L1 is the list of first (largest) entries of each cycle:
> L1:=[seq(L[i][1],i=1..nops(L))]:
> 
> #We now make a table where T[a] is the cycle that starts with  a
> for i from 1 to nops(L) do
>  T[L[i][1]]:=L[i]:
> od:
> 
> #Now we sort L1
> L1:=sort(L1):
> 
> #Now we rewrite L with the above convention
> [seq(T[L1[i]],i=1..nops(L1))]:
> 
> end:

> FunT:=proc(P) local P1,i:
> P1:=PtoC(P):
> [seq(op(P1[i]),i=1..nops(P1))]:
> end:
> 
> #GG(S): inputs a pos.  integer n and a set of permutations in {1,..n} outputs the subgroup generated by them
> GG:=proc(S) local Gr,s,g,Gr1,Gr2:
> Gr:=S:
> Gr1:=Gr union {seq(seq(MulPers(s,g), s in S), g in Gr)}:
> 
> while Gr<>Gr1 do
> Gr2:=Gr1 union {seq(seq(MulPers(s,g), s in S), g in Gr1)}:
> Gr:=Gr1:
> Gr1:=Gr2:
> od:
> Gr1:
> 
> end:
> inv:=proc(pi) local n,i,j,co:
> n:=nops(pi):
> co:=0:
> 
> for i from 1 to n do
>  for j from i+1 to n do
>    if pi[i]>pi[j] then
>     co:=co+1:
>    fi:
>  od:
> od:
> 
> co:
> 
> end:

> maj:=proc(pi) local n,i,co:
> n:=nops(pi):
> co:=0:
> 
> for i from 1 to n-1 do
>    if pi[i]>pi[i+1] then
>     co:=co+i:
>    fi:
>  od:
> 
> 
> co:
> 
> end:
> CtoP:=proc(C) local i,L,n,T,C1,j:
> L:=[seq(op(C[i]),i=1..nops(C))]:
> n:=nops(L):
> 
> if convert(L,set)<>{seq(i,i=1..n)} then
>   RETURN(FAIL):
> fi:
> 
> for i from 1 to nops(C) do
>  C1:=C[i]:
>  for j from 1 to nops(C1)-1 do
>    T[C1[j]]:=C1[j+1]:
>  od:
>  T[C1[nops(C1)]]:=C1[1]:
> od:
> 
> [seq(T[i],i=1..n)]:
> end:
> #(i)
;
> P1 := combinat[randperm](9)
P1 := [3, 8, 4, 9, 1, 5, 6, 7, 2]
;
> P2 := combinat[randperm](9)
P2 := [8, 5, 6, 4, 3, 9, 7, 2, 1]
;
> #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]
;
> [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]
;
> MulPers(P1,P2)
[6, 2, 4, 1, 8, 3, 9, 7, 5]
;
> #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]
;
> [8, 5, 6, 4, 3, 9, 7, 2, 1] [3, 8, 4, 9, 1, 5, 6, 7, 2]   [7, 1, 5, 9, 4, 2, 6, 8, 3]
;
> MulPers(P2,P1)
[7, 1, 5, 9, 4, 2, 6, 8, 3]
;
> #(ii)
;
> P := combinat[randperm](9)
P := [2, 4, 1, 5, 8, 9, 7, 3, 6]
;
> #Inverse := [3, 1, 8, 2, 4, 9, 7, 5, 6]
;
> InvPer(P)
[3, 1, 8, 2, 4, 9, 7, 5, 6]
;
> #(iii)
;
> P := combinat[randperm](9)
P := [4, 6, 9, 1, 3, 7, 5, 8, 2]
;
> #P:=
;
> #[1, 2, 3, 4, 5, 6, 7, 8, 9]
;
> #[4, 6, 9, 1, 3, 7, 5, 8, 2]
;
> #1->4, 2->6->7->5->3->9, 8
;
> #[[4, 1], [8], [9, 2, 6, 7, 5, 3]]
;
> PtoC(P)
[[4, 1], [8], [9, 2, 6, 7, 5, 3]]
;
> #Same
;
> #(iv)
;
> P := combinat[randperm](9)
P := [5, 7, 1, 4, 9, 8, 3, 6, 2]
;
> inv(P)
20
;
> maj(P)
21
;
> 
;
> #Q2
;
> 
;
> #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?

;
> #Q3
;
> 
;
> #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.
;
> 
;
> #Q4
;
> #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.
;
> #Q5
;
> #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}
;