# OK to post homework
# Hari Amoor, 10/14/20, HW #10

with(combinat):

# Problem 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

# 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

# (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]
# P^(-1) = [5 8 6 7 4 2 3 9 1]

# (iii)

# P = [2, 7, 8, 5, 1, 6, 9, 3, 4]
# 2 => 7 => 9 => 4 => 5 => 1 => 2, 6 => 6, 3 => 8 => 3
# The following are cyclic substructures of P: [[6], [8,3], [9,4,5,1,2,7]]

# (iv)

# P = [8, 9, 4, 1, 2, 6, 5, 3, 7] 
# There are 20 inversions, with major j m = 18

# Problem 2

InvGF:=proc(n,q) local i,f,S,m:

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

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

RETURN(f):

end:

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:

# The values are the same for n=1..7

# Problem 3

# We observe that, for a particular n, we have InvGF(n,q) = (1 + q + q^2 + ... + q^(n-1)) * InvGF(n-1,q), InvGF(0,q) = 1.
# Thus, we can hypothesize the following:

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

# Problem 4

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:=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:


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

# Problem 5

InvFunT:=proc(P) local i,j,L:

L:=[]:

j:=1:

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

L:=[op(L),[op(j..i-1,P)]]:

RETURN(CtoP(L)):

end:

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