# OK to post homework
# Aurora Hiveley, 2/4/26, Assignment 4

Help:=proc(): print(``):   end:


### Problem 3

## execute the following 10 times:
# S:={seq(randperm(3),i=1..3)}; [seq(nops(AvoidPer(n,S)),n=1..8)];

# S := {[3, 1, 2], [3, 2, 1]}
# [1, 2, 4, 8, 16, 32, 64, 128]

# S := {[1, 2, 3], [1, 3, 2], [2, 3, 1]}
# [1, 2, 3, 4, 5, 6, 7, 8]

# S := {[1, 2, 3], [2, 1, 3], [2, 3, 1]}
# [1, 2, 3, 4, 5, 6, 7, 8]

# S := {[1, 2, 3], [1, 3, 2], [3, 2, 1]}
# [1, 2, 3, 1, 0, 0, 0, 0]

# S := {[1, 2, 3], [2, 3, 1], [3, 2, 1]}
# [1, 2, 3, 1, 0, 0, 0, 0]

# S := {[1, 3, 2], [2, 1, 3], [3, 2, 1]}
# [1, 2, 3, 4, 5, 6, 7, 8]

# S := {[1, 2, 3], [2, 3, 1], [3, 2, 1]}
# [1, 2, 3, 1, 0, 0, 0, 0]

# S := {[1, 3, 2], [2, 1, 3]}
# [1, 2, 4, 8, 16, 32, 64, 128]

# S := {[1, 3, 2], [2, 1, 3], [3, 1, 2]}
# [1, 2, 3, 4, 5, 6, 7, 8]

# S := {[1, 3, 2], [3, 1, 2], [3, 2, 1]}
# [1, 2, 3, 4, 5, 6, 7, 8]


## which are in the OEIS?
# [1, 2, 3, 4, 5, 6, 7, 8] --> A000027 
# [1, 2, 4, 8, 16, 32, 64, 128] --> A000079 
# [1, 2, 3, 1, 0, 0, 0, 0] --> not in OEIS, conjecture zero for n >=5



### Problem 4

## execute the following 10 times:
# S:={seq(randperm(3),i=1..2), seq(randperm(4),i=1..4)}; [seq(nops(AvoidPer(n,S)),n=1..7)];

# S := {[1, 3, 2], [3, 2, 1], [2, 3, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2]}
# [1, 2, 4, 5, 6, 7, 8]

# S := {[1, 2, 3], [3, 2, 1], [2, 1, 4, 3], [2, 4, 3, 1], [3, 2, 1, 4], [4, 2, 3, 1]}
# [1, 2, 4, 3, 0, 0, 0]

# S := {[2, 3, 1], [3, 2, 1], [2, 1, 3, 4], [2, 1, 4, 3], [3, 4, 1, 2], [4, 2, 1, 3]}
# [1, 2, 4, 6, 8, 10, 12]

# S := {[3, 1, 2], [1, 4, 2, 3], [2, 4, 3, 1], [4, 1, 2, 3], [4, 1, 3, 2]}
# [1, 2, 5, 13, 34, 89, 233]

# S := {[2, 1, 3], [2, 3, 1], [1, 3, 2, 4], [2, 3, 1, 4], [2, 3, 4, 1], [3, 4, 2, 1]}
# [1, 2, 4, 8, 16, 32, 64]

# S := {[1, 2, 3], [1, 3, 2], [1, 2, 3, 4], [1, 3, 2, 4], [2, 3, 4, 1], [4, 1, 2, 3]}
# [1, 2, 4, 8, 16, 32, 64]

# S := {[1, 3, 2], [2, 1, 3], [1, 4, 3, 2], [2, 4, 3, 1], [3, 1, 4, 2], [4, 3, 2, 1]}
# [1, 2, 4, 7, 11, 16, 22]

# S := {[1, 2, 3], [2, 1, 3], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [4, 3, 1, 2]}
# [1, 2, 4, 6, 7, 7, 7]

# S := {[2, 3, 1], [3, 1, 2], [1, 2, 4, 3], [1, 3, 2, 4], [4, 2, 1, 3], [4, 3, 1, 2]}
# [1, 2, 4, 6, 8, 10, 12]

# S := {[1, 3, 2], [3, 2, 1], [1, 4, 2, 3], [2, 4, 3, 1], [4, 1, 2, 3], [4, 3, 1, 2]}
# [1, 2, 4, 6, 8, 10, 12]


## which are in the OEIS?
# [1, 2, 4, 5, 6, 7, 8] --> several possible sequences, need additional terms 
# [1, 2, 4, 3, 0, 0, 0] --> not in OEIS, conjecture 0 for n >= 5
# [1, 2, 4, 6, 8, 10, 12] --> A002202
# [1, 2, 5, 13, 34, 89, 233] --> A001519 
# [1, 2, 4, 8, 16, 32, 64] --> A000079 
# [1, 2, 4, 7, 11, 16, 22] --> A000124
# [1, 2, 4, 6, 7, 7, 7] --> A331379






### copied from C4.txt 

# C4.txt, Feb. 02, 2026

Help4:=proc():
 print(`a(n), b(n), IncSeqs1(n,k,a), IncSeqs(n,k)`):
 print(`Contain1(pi,sig), Contain(pi,S), AvoidPer(n,S)`):
end:


#IncSeqs1(n,k,a): The set of increasing sequences of length k of integers 
# that ends with a
IncSeqs1:=proc(n,k,a) local S,b,S1,s1:
option remember:
if not type(n,integer) and type(k,integer) and k<=n and k>=1 and a<=n and n>=1then
 return(FAIL):
fi:

if k=1 then
 return({[a]}):
fi:
S:={}:

#a-1-(k-1)+1=a-k
for b from k-1 to a-1 do
 S1:=IncSeqs1(n,k-1,b):
 #append a to the list s1: [op(s1),a]
 S:=S union {seq([op(s1),a],s1 in S1)}:
od:
S:
end:


#IncSeqs(n,k): The set of increasing sequences of length k from the integers 
# 1 to n
IncSeqs:=proc(n,k) local a:
{seq(op(IncSeqs1(n,k,a)),a=k..n)}:
end:

#Contain1(pi,sig): Does the permutation pi contain the pattern sig?
Contain1:=proc(pi,sig) local n,k,S,s,i1:
n:=nops(pi):
k:=nops(sig):
S:=IncSeqs(n,k):
for s in S do
 #here we are looking at all the places in pi from each s1
 # for example if s=[1,4,9] and n=10, k=3 then we look at 
 # pi[1]pi[4]pi[9] and see if it reduces to sig then return true
 if redu([seq(pi[s[i1]],i1=1..k)])=sig then
  return(true):
 fi:
od:
false:
end:

#Contain(pi,S): does pi contain at least one of the patterns in S?
Contain:=proc(pi,S) local sig:
for sig in S do
 if Contain1(pi,sig) then
  return true:
 fi:
od:
false:
end:


#AvoidPer(n,S): the permutations of length n that avoid the patterns in S1
AvoidPer:=proc(n,S) local G, G1,i,pi1,pi:
option remember:
if n=0 then
 return({[]}):
fi:
# G is the set with good permutations (avoiding the patterns in S)
G:={}:
G1:=AvoidPer(n-1,S):

#i is the location of n
for i from 1 to n do
 for pi1 in G1 do
  pi:=[op(1..i-1,pi1),n,op(i..n-1,pi1)]:
  if not Contain(pi,S) then
   G:=G union {pi}:
  fi:
 od:
od:
G:
end:



#This is still open: Why is it that it is all integers up to n=17
a:=proc(n) local i: option remember: 
 if  n=1 then
  2:
 else
  add(a(i)^2,i=1..n-1)/(n-1):
 fi:
end:

b:=proc(n) option remember:
if n>=1 and n<=4 then
 1:
else
 (b(n-1)*b(n-3)+b(n-2)^2)/b(n-4):
fi:
end:

##################################
##################################
##################################

##From C2.txt and Jike Liu's homework
with(combinat):
Help2:=proc():
 print(`redu(L), SubSeq3(L), Contain3(pi,sig)`):
end:

Help2New:=proc():
 print(`Contain3S(pi,S), AvoidPer(n,S)`):
end:

#redu(L): inputs a list of distinct numbers and outputs its reduction
# according to their order
# For example redu([5,9,1]): [2,3,1]
# redu([Pi,e])=[2,1]
# redu([phi,sqrt(2),10])= [2,1,3]
redu:=proc(L) local n,L1,T,i:
n:=nops(L):
L1:=sort(L):
for i from 1 to n do
 T[L1[i]]:=i:
od:
[seq(T[L[i]],i=1..n)]:
end:


#SubSeqs3(L): The set of subsequences of the list L of length 3. For example
#SubSeqs3([1,6,2,4])={[1,6,2],[1,6,4],[1,2,4],[6,2,4]}
SubSeqs3:=proc(L) local n,i1,i2,i3,S:
n:=nops(L):
S:={}:
for i1 from 1 to n do
 for i2 from i1+1 to n do
  for i3 from i2+1 to n do
   S:=S union {[L[i1],L[i2],L[i3]]}:
  od:
 od:
od:
S:
end:


#Contain3(pi,sig): does the permutation pi contain the pattern sig?
#Contain3([2,1,3,4],[1,2,3]) returns true Contain3([4,3,2,1],[1,2,3]) returns false
Contain3:=proc(pi,sig) local n,S,s:
n:=nops(pi):
if nops(sig)<>3 then
  RETURN(FAIL):
fi:

S:=SubSeqs3(pi):

for s in S do
 if redu(s)=sig then
  return(true):
 fi:
od:
false:
end:


#AvoidPer1(n,sig): inputs a pos. integer n and a pattern of length 3 outputs the subset of permute(n)
#that avoid the parttern sig
AvoidPer1:=proc(n,sig) local A,pi,G:
A:=permute(n):
G:={}:
for pi in A do
 if not Contain3(pi,sig) then
  G:=G union {pi}:
 fi:
od:
G:
end:


#added after class, thanks to Jike Liu
Contain3S := proc(pi,S)
local sig;
for sig in S do
 if Contain3(pi,sig) then
  return true:
 fi:
od:
false:
end:


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

#End added after class, thanks to Jike Liu