Lecture 10: Due Oct. 11, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

hw10FirstLast.txt

OK to Post

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

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

(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)

	#A:p = [4, 6, 9, 1, 3, 7, 5, 8, 2]
	   p^1 = [4, 9, 5, 1, 7, 2, 6, 8, 3]

(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)

	#A:p = [5, 7, 1, 4, 9, 8, 3, 6, 2]
	   PtoC(p) = {[5, 9, 2, 7, 3, 1],[4],[6,8]}

(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)

	#A:p = [7, 1, 3, 5, 2, 8, 9, 6, 4]
	   inversions: 14
	   major index: 20

############################################################################################################################################################################
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 Sum, fact, i:

 Sum:=0:
 fact:= n!:
 for i from 1 to fact do:
  Sum:= Sum + q^inv(i):
 od:

 Sum:
 
 end:



MajGF:=proc(n,q) local Sum, fact, i;

 Sum:=0:
 fact:= n!:
 for i from 1 to fact do:
  Sum:= Sum + q^maj(i):
 od:

 Sum:
 
 end:

#The output of both these are the same: (where seq(InVGF(i,x), i=1..7) and seq(MajGF(i,x), i=1..7) outputs: 1, 1+x, x^3+2*x^2+2*x+1, x^6+3*x^5+5*x^4+6*x^3+5*x^2+3*x+1, x^10+4*x^9+9*x^8+15*x^7+20*x^6+22*x^5+20*x^4+15*x^3+9*x^2+4*x+1, x^15+5*x^14+14*x^13+29*x^12+49*x^11+71*x^10+90*x^9+101*x^8+101*x^7+90*x^6+71*x^5+49*x^4+29*x^3+14*x^2+5*x+1, x^21+6*x^20+20*x^19+49*x^18+98*x^17+169*x^16+259*x^15+359*x^14+455*x^13+531*x^12+573*x^11+573*x^10+531*x^9+455*x^8+359*x^7+259*x^6+169*x^5+98*x^4+49*x^3+20*x^2+6*x+1)
############################################################################################################################################################################
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.

[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]
n=1 := 1+q 
n=2 := q^2+q+1, 
n=3 := (1+q)*(q^2+1) = q^3+q^2+q+1
n=4 := q^4+q^3+q^2+q+1 = q^4+q^3+q^2+q+1
n=5 := (1+q)*(q^2+q+1)*(q^2-q+1) = q^5+q^4+q^3+q^2+q+1
n=6 := q^6+q^5+q^4+q^3+q^2+q+1 

Conjecture: for f where f is InvGF(n,q)/InvGF(n-1,q) f(n) = Sum(x^i, i=0..n)

###########################################################################################################################################################################
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 a, i, j, k, n, N, co; 
n := nops(P); 
 for i 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; 
    end if; 
   end do; 
  end do; 
 end do;
return false; 
end proc

AvoidABC := proc(n) local p, total:

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

count:

end:


############################################################################################################################################################################
5) 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] 


#A: need help with this.