# OK to post homework
# Lucy Martinez, 02-05-2026, Assignment 4

with(combinat):


# Question 3:
# Type the following 10 times, after reading C4.txt,
#  S:={seq(randperm(3),i=1..3)}; [seq(nops(AvoidPer(n,S)),n=1..8)];
# How many of then are in the OEIS?
# For those that are not in the OEIS, can you conjecture a formula? 

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

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

# Third: S:={[1, 3, 2], [3, 2, 1]};
# Sequence A000124: 1, 2, 4, 7, 11, 16, 22, 29

# Fourth: S:={[2, 3, 1], [3, 1, 2], [3, 2, 1]};
# Sequence A000045: 1, 2, 3, 5, 8, 13, 21, 34

# Fifth: S:={[3, 2, 1]};
# Sequence A000108: 1, 2, 5, 14, 42, 132, 429, 1430

# There was a lot of repetition even though I ran S:={seq(randperm(3),i=1..3)}
#  more than 10 times



# Question 4:
# Type the following 10 times, after reading C4.txt ,
#  S:={seq(randperm(3),i=1..2), seq(randperm(4),i=1..4)}; 
#  [seq(nops(AvoidPer(n,S)),n=1..7)];
# How many of them are in the OEIS?
# For those that are not in the OEIS, can you conjecture a formula? 

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

# Second: S:= {[3, 1, 2], [3, 2, 1], [1, 2, 4, 3], [1, 4, 3, 2], [2, 4, 1, 3], [2, 4, 3, 1]};
# Sequence A033627: 1, 2, 4, 7, 10, 13, 16, 19, 22, 25

# Third: S:={[2, 3, 1], [3, 2, 1], [3, 1, 2, 4], [3, 2, 1, 4], [3, 4, 1, 2], [3, 4, 2, 1]};
# Sequence A000071: 1, 2, 4, 7, 12, 20, 33, 54, 88, 143

# Fourth: S:={[1, 3, 2], [3, 2, 1], [1, 2, 4, 3], [3, 2, 1, 4], [4, 2, 1, 3], [4, 3, 2, 1]};
# Sequence A000124: 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56

# Fifth: S:={[1, 2, 3], [2, 1, 3], [1, 4, 3, 2], [3, 1, 4, 2], [4, 2, 1, 3]};
# Sequence A000073 (Tribonacci): 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504

# Sixth: S:={[1, 3, 2], [1, 3, 2, 4], [2, 1, 4, 3], [3, 4, 2, 1], [4, 2, 1, 3]};
# Sequence A027927: 1, 2, 5, 12, 26, 51, 92, 155, 247, 376

# Seventh: S:={[1, 3, 2], [3, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2]};
# Sequence A004275: 1, 2, 4, 6, 8, 10, 12, 14, 16, 18

# Eighth: S:={[1, 2, 3], [1, 2, 4, 3], [1, 4, 3, 2], [3, 2, 4, 1]};
# Sequence A116714: 1, 2, 5, 12, 24, 46, 87, 162, 300, 554

# Ninth: S:={[2, 1, 3], [1, 2, 3, 4], [2, 1, 4, 3], [2, 4, 1, 3], [3, 2, 1, 4]};
# Sequence A001519: 1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181

# Tenth: S:={[3, 2, 1], [1, 2, 4, 3], [2, 4, 3, 1], [3, 1, 4, 2], [4, 2, 3, 1]};
# Sequence A116721: 1, 2, 5, 12, 24, 42, 67, 100, 142, 194

# Eleventh: S:={[2, 3, 1], [1, 2, 3, 4], [1, 3, 2, 4], [2, 3, 4, 1], [3, 2, 4, 1]};
# Sequence A116731: 1, 2, 5, 12, 25, 46, 77, 120, 177, 250





#######From before:
# 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

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