#OK to post homework
#Karnaa Mistry, 10/11/20, Assignment HW #10

with(combinat):


# 1. 

# (i)

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

# 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]
# [1 8 9 2 3 6 7 4 5]   [4 8 5 2 6 1 9 7 3]   [4 7 3 8 5 1 9 2 6] = P1*P2 (same as MulPers)

# 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]
# [4 8 5 2 6 1 9 7 3]   [1 8 9 2 3 6 7 4 5]   [2 4 3 8 6 1 5 7 9] = P2*P1 (same as MulPers)

# (ii)

# [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]
# [9 6 7 5 1 3 4 2 8]   [? ? ? ? ? ? ? ? ?]   [1 2 3 4 5 6 7 8 9]
# Inverse of P = [5 8 6 7 4 2 3 9 1] (same as InvPer)

# (iii)

# P = [2, 7, 8, 5, 1, 6, 9, 3, 4]
# 2->7->9->4->5->1->2, 6->6, 3->8->3
# Cycle Structure of P = [[6], [8,3], [9,4,5,1,2,7]]

# (iv)

# P = [8, 9, 4, 1, 2, 6, 5, 3, 7] 
# Counted number of inversions = 20; major index = 18 (same as inv and maj)




# 2.

#InvGF(n,q): inputs a positive integer n and var q, outputs weight-enumerator of the set
#of permutations of length n according to the number of inversions
InvGF:=proc(n,q) local i,f,L,m:

m:=n!:
f:=0:
L:=permute(n):

for i from 1 to m do
   f := f+q^(inv(L[i])):
od:

RETURN(f):

end:


#MajGF(n,q): inputs a positive integer n and var q, outputs the weight-enumerator of the
#set of permutations of len n according to the major index
MajGF:=proc(n,q) local i,f,L,m:

m:=n!:
f:=0:
L:=permute(n):

for i from 1 to m do
   f := f+q^(maj(L[i])):
od:

RETURN(f):

end:


# Yes, they are the same for n=1..7




# 3.

# It appears that for a particular n, InvGF(n,q) = (1 + q + q^2 + ... + q^(n-1)) * InvGF(n-1,q), InvGF(0,q) = 1
# So, we may have some formula like:

#		InvGF(n,q) = product( sum(x^j, j=0..i-1), i=1..n-1)




# 4.

#IsBad(P): returns true as soon as an abc-pattern is found in P
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] and P[j]<P[k] then
        RETURN(true):
      fi:
    od:
  od:
od:

RETURN(false):

end:


#NumABCAvoids(n): finds number of abc-avoiding permutations of length n
NumABCAvoids:=proc(n) local i,L,m,c:

m:=n!:
L:=permute(n):
c:=0:

for i from 1 to m do
  if (IsBad(L[i])) then
    c:=c+1:
  fi:
od:

RETURN(c):

end:


# [seq(NumABCAvoids(n),n=1..8)] = [0, 0, 1, 10, 78, 588, 4611, 38890]
# This is in the OEIS: A056986

#COMMENT BY Dr. Z.: IN THIS OTHERWISE PERFECT ASSIGNMENT Karnaa computed the number of "bad guys" that do CONTAIN
#at least one occurrence of an abc-pattern,  Surprisngly this complementary sequence 
that Karnaa outputted , n!-C_n, (C_n being the Catalan numbers, A108) is ALSO in the OEIS



# 5. 

#InvFunT(P): inputs permutation P and outputs permutation Q s.t. P=FunT(Q)
InvFunT:=proc(P) local i,index,C:

C:=[]:

index:=1:

for i from 2 to nops(P) do:
  if (P[i]>P[index]) then
    C:=[op(C),[op(index..i-1,P)]]:
    index:=i:
  fi:
od:

C:=[op(C),[op(index..i-1,P)]]:

RETURN(CtoP(C)):

end:


# {seq(evalb(InvFunT(FunT(pi))=pi), pi in S)} = {true}
# {seq(evalb(FunT(InvFunT(pi))=pi), pi in S)} = {true}

# COMMENT BY Dr. Z.: GOOD JOB!