# OK to post homework
# Lucy Martinez, 01-31-2026, Assignment 2

with(combinat):


# Question 3: 
# Part I: Write a procedure Bij(pi)
#  that inputs a permutation pi of {1,...n}, where n:=nops(pi),
#  and outputs the pair [i,pi'], where i is the location of n,
#  and pi' is the permutation of {1, ..., n-1} obtained from deleting n. 
#  For example Bij([3,1,4,6,2,5])=[4,[3,1,4,2,5]]
# Part II: Write a procedure InvBij(Pair)
#  that inputs a pair Pair of the form [i,pi'], such that pi' is a permutation of {1,...,n-1}
#  where n:=nops(pi')+1, and i is an integer between 1 and n inclusive,
#  and outputs the permutation pi of {1, ...,n} obtained from pi'
#  by inserting n right before the i-th place (and if i=n, at the end).
#  For example InvBij([4,[3,1,4,2,5]])=[3,1,4,6,2,5] 
Bij:=proc(pi) local n,i,j:
n:=nops(pi):
i:=0:
for j from 1 to n do
 if pi[j]=n then
  i:=j:
 fi:
od:
[i,[op(1..i-1,pi),op(i+1..n,pi)]]:
end:


InvBij:=proc(Pair) local n,perm,i:
perm:=Pair[2]:
n:=nops(Pair[2])+1:
i:=Pair[1]:
[op(1..i-1,perm),n,op(i..n-1, perm)]:
end:


# Question 5:
# Part I: Using procedure, Contain3(pi,sig), write a procedure Contain3S(pi,S)
#  that inputs a set of patterns, all of length 3 and
#  outputs true if and only of pi contains at least one of the patterns in S.
#  Note that for any pattern sig of length 3, Contain3S(pi,{sig}) is NOT the same as Contain3(pi,sig)
#  For example Contain3([1,2,4,3],{[1,2,3],[3,2,1]}) is true but Contain3S([4,3,2,1],{[1,2,3],[2,3,1]}) is false. 
# Part II: Using Contain3S(pi,S) write a procedure AvoidPer(n,S)
#  that inputs a pos. integer n and a set of patterns of length 3, S,
#  outputs the subset of permute(n) that avoids all the patterns in S. 
# Part III: Conjecture an explicit formula for the number of permutations of {1, ...,n}
#  avoding both the patterns 123 and 132, in other words, nops(AvoidPer(n,{[1,2,3],[1,3,2]})),
#  by entering seq(AvoidPer(n,{[1,2,3],[1,3,2]}),n=1..8)
# ANSWER: The sequence is [1, 2, 4, 7, 11, 16, 22, 29] for 1<=n<=8.
Contain3S:=proc(pi,S) local n,s,S1:
n:=nops(pi):
for s in S do
 if nops(s)<>3 then
  RETURN(FAIL):
 fi:
od:

for s in S do
  if Contain3(pi,s) then
     RETURN(true):
  fi:
od:
false:
end:

AvoidPer:=proc(n,S) local s,A,pi,G:
A:=permute(n):
G:={}:
for pi in A do
 if not Contain3S(pi,S) then
  G:=G union {pi}:
 fi:
od:
G:
end: