Eshaan Gandhi
Ok to post


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

Answer 1

l1 := randperm(9);
               l1 := [8, 5, 6, 4, 3, 9, 7, 2, 1]
l2 := randperm(9);
               l2 := [2, 4, 1, 5, 8, 9, 7, 3, 6]

By hand:
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

l1*l2 = 3 8 9 5 1 6 7 4 2
 
MulPers(l1, l2);
                  [3, 8, 9, 5, 1, 6, 7, 4, 2]

They are the same

(ii)
p := randperm(9);
                p := [4, 6, 9, 1, 3, 7, 5, 8, 2]
InvPer(p);
                  [4, 9, 5, 1, 7, 2, 6, 8, 3]
MulPers(%, `%%`);
                  [1, 2, 3, 4, 5, 6, 7, 8, 9]

This is also the same as we calulated by hand

(iii)
p1 := randperm(9);
               p1 := [5, 7, 1, 4, 9, 8, 3, 6, 2]

Let's find the cycles of this permuation

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

(4)(1, 5, 9, 2, 7, 3)(6, 8)
But according to convention they should be written as
(4)(9, 2, 7, 3, 1, 5)(8, 6)

PtoC(p1);
               [[4], [8, 6], [9, 2, 7, 3, 1, 5]]
And sure enough we get the same result when we use the maple code

(iv)
p1 := randperm(9);
               p1 := [5, 7, 1, 4, 9, 8, 3, 6, 2]
inv(p1);
                               20
maj(p1);
                               21

Question 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?

Question 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.

Question 4:
isBad := proc(p) local i, j, k; for i to nops(p) do for j from i to nops(p) do for k from j to nops(p) 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
This is the isBad function

count := proc(n) local ans, P, i; with(combinat); P := permute(n); ans := 0; for i in P do if isBad(i) then continue; else ans := ans + 1; end if; end do; end proc;

seq(count(i), i = 1 .. 8);
                1, 2, 5, 14, 42, 132, 429, 1430
They are called catalan numbers in OEIS
A108

Question 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

Answer 5:
How to identify where the next cycle starts?