#its ok to post #TaerimKim,10/11/2020,Assignment 10 #1. #(i). P1 := combinat[randperm](9); P1 := [8, 5, 6, 4, 3, 9, 7, 2, 1] P2 := combinat[randperm](9); P2 := [2, 4, 1, 5, 8, 9, 7, 3, 6] #by hand #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 #[ ] * [ ] = [ ] # 8 5 6 4 3 9 7 2 1 2 4 1 5 8 9 7 3 6 3 8 9 5 1 6 7 4 2 #85643972*241589736 = 389516742 #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 #[ ] * [ ] = [ ] # 2 4 1 5 8 9 7 3 6 8 5 6 4 3 9 7 2 1 5 4 8 3 2 1 7 6 9 #241589736*85643972 = 548321769 #by maple MulPers(P1, P2); [3, 8, 9, 5, 1, 6, 7, 4, 2] MulPers(P2, P1); [5, 4, 8, 3, 2, 1, 7, 6, 9] #CORRECT! ###################################################### #(ii). P:=combinat[randperm](9) P := [4, 6, 9, 1, 3, 7, 5, 8, 2] #Inverse of P # 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 6 9 1 3 7 5 8 2 4 9 5 1 7 2 6 8 3 1 2 3 4 5 6 7 8 9 # 469137582*495172683=123456789, So Inverse of P is 495172683 #Check with maple, P3 := InvPer(P); P3 := [4, 9, 5, 1, 7, 2, 6, 8, 3] MulPers(P, P3); [1, 2, 3, 4, 5, 6, 7, 8, 9] #GOOD ###################################################### #(iii) P := combinat[randperm](9); P := [5, 7, 1, 4, 9, 8, 3, 6, 2] #By hand, #We can see fixed point for 4 -> (4) # 1 2 3 4 5 6 7 8 9 # 5 7 1 4 9 8 3 6 2 # 1->5->9->2->7->3->1: (159273)->(927315) # 6->8->6; (86) #So, it should be ((4),(8,6),(9,2,7,3,1,5)) #Check it with maple. PtoC(P); [[4], [8, 6], [9, 2, 7, 3, 1, 5]] #Correct ######################################################## #(iv) P := combinat[randperm](9); P := [7, 1, 3, 5, 2, 8, 9, 6, 4] #Inversion of P #by hand # 1 2 3 4 5 6 7 8 9 # 7 1 3 5 2 8 9 6 4 #before 1, (7) -> 1 #before 3, (7) -> 1 #before 5, (7) -> 1 #before 2, (7,3,5) -> 3 #before 8, none #before 9, none #before 6, (7,8,9) -> 3 #before 4, (7,5,8,9,6) -> 5 #total=1+1+1+3+3+5 = 14 #By maple, inv(P); 14 #correct #Major index of P #by hand, # 1 2 3 4 5 6 7 8 9 # 7 1 3 5 2 8 9 6 4 #P[1]->(7>1) : 1 #P[4]->(5>2) : 4 #P[7]->(9>6) : 7 #P[8]->(6>4) : 8 #total=1+4+7+8=20 #Check with maple, maj(P); 20 #Coreect ################################################################################## #2. #By using the inv and maj statement, we can formulate polynomials inv := proc(pi) local n, i, j, co; n := nops(pi); co := 0; for i to n do for j from i + 1 to n do if pi[j] < pi[i] then co := co + 1; end if; end do; end do; co; end proc; maj := proc(pi) local n, i, co; n := nops(pi); co := 0; for i to n - 1 do if pi[i + 1] < pi[i] then co := i + co; end if; end do; co; end proc; InVGF:=proc(n,q) local A,B,a; A:=combinat[permute](n); B:=[seq(inv(a), a in A)]; b:= nops(B); add(q^B[i],i=0..b); end: #Same analogous algorithm as InVGF, but replaced inv as maj MajGF:=proc(n,q) local A,B,a; A:=combinat[permute](n); B:=[seq(maj(a), a in A)]; b:= nops(B); add(q^B[i],i=0..b); end: #examples, InVGF(4, q); q^6 + 3*q^5 + 5*q^4 + 6*q^3 + 5*q^2 + 3*q + 1 MajGF(4, q) q^6 + 3*q^5 + 5*q^4 + 6*q^3 + 5*q^2 + 3*q + 1 #Lets check if they are same for n=2..7 [seq(MajGF(i, q), i = 2 .. 7)]; [1 + q, q^3 + 2*q^2 + 2*q + 1, q^6 + 3*q^5 + 5*q^4 + 6*q^3 + 5*q^2 + 3*q + 1, q^10 + 4*q^9 + 9*q^8 + 15*q^7 + 20*q^6 + 22*q^5 + 20*q^4 + 15*q^3 + 9*q^2 + 4*q + 1, q^15 + 5*q^14 + 14*q^13 + 29*q^12 + 49*q^11 + 71*q^10 + 90*q^9 + 101*q^8 + 101*q^7 + 90*q^6 + 71*q^5 + 49*q^4 + 29*q^3 + 14*q^2 + 5*q + 1, q^21 + 6*q^20 + 20*q^19 + 49*q^18 + 98*q^17 + 169*q^16 + 259*q^15 + 359*q^14 + 455*q^13 + 531*q^12 + 573*q^11 + 573*q^10 + 531*q^9 + 455*q^8 + 359*q^7 + 259*q^6 + 169*q^5 + 98*q^4 + 49*q^3 + 20*q^2 + 6*q + 1] [seq(InVGF(i, q), i = 2 .. 7)]; [1 + q, q^3 + 2*q^2 + 2*q + 1, q^6 + 3*q^5 + 5*q^4 + 6*q^3 + 5*q^2 + 3*q + 1, q^10 + 4*q^9 + 9*q^8 + 15*q^7 + 20*q^6 + 22*q^5 + 20*q^4 + 15*q^3 + 9*q^2 + 4*q + 1, q^15 + 5*q^14 + 14*q^13 + 29*q^12 + 49*q^11 + 71*q^10 + 90*q^9 + 101*q^8 + 101*q^7 + 90*q^6 + 71*q^5 + 49*q^4 + 29*q^3 + 14*q^2 + 5*q + 1, q^21 + 6*q^20 + 20*q^19 + 49*q^18 + 98*q^17 + 169*q^16 + 259*q^15 + 359*q^14 + 455*q^13 + 531*q^12 + 573*q^11 + 573*q^10 + 531*q^9 + 455*q^8 + 359*q^7 + 259*q^6 + 169*q^5 + 98*q^4 + 49*q^3 + 20*q^2 + 6*q + 1] evalb(% = `%%`); true #its the same ######################################################################################## #3. newInVGF(4, q)/InVGF(3, q) (q^6 + 3*q^5 + 5*q^4 + 6*q^3 + 5*q^2 + 3*q + 1)/(q^3 + 2*q^2 + 2*q + 1) factor(%) (1 + q)*(q^2 + 1) = q^3+q^2+q+1 #maybe we can see a pattern by evaluating over some range of n seq(factor(InVGF(i, q)/InVGF(i - 1, q)), i = 3 .. 5) q^2 + q + 1, (1 + q)*(q^2 + 1), q^4 + q^3 + q^2 + q + 1 #when i=3, q^(3-1)+q^(3-2)+q^(3-3) #when i=4, q^(4-1)+q^(4-2)+q^(4-3)+q^(4-4) ##so we see a pattern now. then we can formulate incursion here #lets conjecture a formula, InvGF:=proc(n,q) local B; option remember if n = 1 then return 1 fi: B:=add(q^(n-i),i=1..n); expand(B*newInvGF(n-1,q)); end: #lets check newInvGF(4, q) q^6 + 3*q^5 + 5*q^4 + 6*q^3 + 5*q^2 + 3*q + 1 InvGF(4, q) q^6 + 3*q^5 + 5*q^4 + 6*q^3 + 5*q^2 + 3*q + 1 evalb(% = `%%`); true #GOOD JOB ######################################################################################### #4. 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 P; end if; end do; end do; end do; end proc #returning abc permutations for minus from the total permutation abcAvoid := proc(n) local P, A, B, C, i, j, P1; P := combinat[permute](n); A := nops(P); C := {seq(P[j], j = 1 .. A)}; #total permutation B := {seq(Isbad(P[i]), i = 1 .. A)}; #abc permutation nops(C minus B); #number of permutations that are not abc end proc #to get the Sequence seq(abcAvoid(i),i=1..8) 1, 2, 5, 14, 42, 132, 429, 1430 #IN Oeis,this is Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!), given as A000108. ####################################################################################### #5. # we can do this by sorting out the numbers in the permutation, by comparing their numbers, regrouping them, and execute CtoP. InvFunT:=proc(P)