#OK to post homework
#Sam Minkin, 10/11, Assignment 10

Problem 1:

(i). 

P1: 
[1, 2, 3, 4, 5, 6, 7, 8, 9] 
[3, 8, 4, 9, 1, 5, 6, 7, 2]

P2:
[1, 2, 3, 4, 5, 6, 7, 8, 9] 
[8, 5, 6, 4, 3, 9, 7, 2, 1]

P1*P2:

1 2 3 4 5 6 7 8 9
8 5 6 4 3 9 7 2 1
7 1 5 9 4 2 6 8 3 <= P1*P2

P2*P1:

1 2 3 4 5 6 7 8 9
3 8 4 9 1 5 6 7 2
6 2 4 1 8 3 9 7 5 <= P2*P1

MulPers(P1, P2): [6, 2, 4, 1, 8, 3, 9, 7, 5] -> The same as P2*P1
MulPers(P2, P1): [7, 1, 5, 9, 4, 2, 6, 8, 3] -> The same as P1*P2


(ii). 

P:=[2, 4, 1, 5, 8, 9, 7, 3, 6]

The inverse is the permutation which composed with P results in the identity:

P^{-1}:
1 2 3 4 5 6 7 8 9
3 1 8 2 4 9 7 5 6

Check:
InvPer(P):
[3, 1, 8, 2, 4, 9, 7, 5, 6]. The same.


(iii). 

P := [5, 7, 1, 4, 9, 8, 3, 6, 2]

Equivalent Bijective Map:
1 2 3 4 5 6 7 8 9
5 7 1 4 9 8 3 6 2

Cycle Structure: (4)(86)(927315)

PtoC(P): [[4], [8, 6], [9, 2, 7, 3, 1, 5]] <- The same.


(iv). 

P := [7, 1, 3, 5, 2, 8, 9, 6, 4]
Inversions: (7,1),(7,2),(7,3),(7,5),(7,6),(7,4); (3,2); (5,2),(5,4); (8,6),(8,4); (9,6),(9,4); (6,4)

The total number of inversions is 14.
Check: inv(P) = 14.

Major indices: (1,2),(4,5),(7,8),(8,9).

Sum of indices: 1 + 4 + 7 + 8 = 20.
Check: maj(P) = 20.


Problem 2:

InvGF:=proc(n,q) local s,S:
S:=permute(n):
factor(add(q^(inv(s)), s in S)):
end:

MajGF:=proc(n,q) local s,S:
S:=permute(n):
factor(add(q^(maj(s)), s in S)):
end:

They are equal for n=2..7:
seq(evalb(InvGF(n, q) = MajGF(n, q)), n = 1 .. 7);
Output: true, true, true, true, true, true, true


Problem 3:

seq(InvGF(n, q)/InvGF(n - 1, q), n = 2 .. 7):

1 + q, q^2 + q + 1, (q^2 + 1)*(1 + q), q^4 + q^3 + q^2 + q + 1, (q^2 - q + 1)*(q^2 + q + 1)*(1 + q), q^6 + q^5 + q^4 + q^3 + q^2 + q + 1

Conjecture:

So far we have the pattern: 1 + q, 1 + q + q^2, 1 + q + q^2 + q^3, and so on.
It is evident that for each next n, we add q^n to the ratio between InvGF(n,q) and InvGF(n-1). 

So, InvGF(n,q) = sum(q^s, s in {0,1,..,n}) * InvGF(n-1,q) ->
InvGF(n,q) = sum(q^s, s in {0,1,..,n}) * sum(q^s, s in {0,1,..,n-1}) * InvGF(n-2,q) ->
And in general, we have:

InvGF(n,q) = sum(q^s, s in {0,1,..,n})*sum(q^s, s in {0,1,..,n-1})*...*(1+q)


Problem 4:

isBad Procedure:

isBad:=proc(P) local n,i,j,k:

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:

Find the first 8 abc-avoiding sequences procedure:

findBadPerms:=proc() local S,c,n,s:

n:=3:
c:=0:
S:={}:

while c <> 8 do
	for s in permute(n) do
		if isBad(s) and c <> 8 then
			S:=S union {s}:
			c:=c+1:
		fi:
		if c = 8 then
			RETURN(S):
		fi:
	od:
	n:=n+1:
od:
	
RETURN({}):

end:


The output is:
findBadPerms();
   {[1, 2, 3], [1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 3, 4], [2, 3, 1, 4]}


The first 8 members that are abc-avoiding:

123, 1234, 1243, 1324, 1342, 1423, 2134, 2314

This sequence is not in the OEIS.