# OK to post homework
# Lucy Martinez, 02-08-2026, Assignment 5

with(combinat):


# Question 2:
# Conjecture an expression for the following quantity, once you have read C5.txt:
#  factor(WtE(powerset(n),S->nops(S),x));
#  by doing it for n=1,n=2,n=3,n=4, .... 
#  Note that this is the weight-enumerator of the set of subsets of {1, ...,n}
#  according to the weight S-> x^NumberOfElementsOfS
#  Can you prove it? 

# Answer: The weight-enumerator is (1+x)^n for any n>=0
# Proof: Let W(n,x)=(1+x)^n denote the weight enumerator for according to 
# the weight S->x^NumberOfElementsOfS where S is a subset of the set {1,2,...,n}.
# Notice that a subset of {1,2,...,n} is constructed by repeatedly making choices of
# whether one wants to include an element from {1,2,...,n} or not. Let 1 represent the weight 
# that we do NOT choose an element from the set {1,2,...,n},
# and x^1 represent the weight that we DO choose an element from the set {1,2,...,n}.
# Hence, (1+x) represents the weight-enumerator for a single element that
# can be chosen or not.
# Thus, since there are n elements and we want to find the number of ways to form a subset,
# we multiply the weight-enumerator for each single element. Hence, (1+x)*...(1+x), n times which
# results in (1+x)^n=W(x,n).






# Question 3:
# Write a procedure NumPat3(pi,sig)
#  that inputs a permutation pi of any length and a permutation sig of length 3
#  (if it is not the procedure should return FAIL)
#  and by using redu (of C4.txt), a variable co that starts as 0,
#  and a triple do-loop that adds 1 to co each time it finds a triple that reduces to sig,
#  and outputs the number of occurrences of the pattern sig in pi. For example
#  NumPat3([2,1,3,4],[1,2,3]); should output 2,
#  since [pi[1],pi[3],pi[4]]=[2,3,4] and [pi[2],pi[3],pi[4]]=[1,3,4] reduce to 123, and none of the other triplets do. 
NumPat3:=proc(pi,sig) local m,n,co,i,j,k:
m:=nops(sig):
n:=nops(pi):
if m<>3 then
 print(`the second input should be a list of length 3`):
 return(FAIL):
fi:
co:=0:
for i from 1 to n do
 for j from i+1 to n do
  for k from j+1 to n do
   if redu([pi[i],pi[j],pi[k]])=sig then
    co:=co+1:
   fi:
  od:
 od:
od:
co:
end:





# Question 4:
# Define L:=[seq(WtE(permute(n),pi->NumPat3(pi,[1,2,3]),x),n=1..7)];
#  (if you have patience, try to do instead L:=[seq(WtE(permute(n),pi->NumPat3(pi,[1,2,3]),x),n=1..8)];)
#  For which j=0,1,2,3,... are the following sequences are in the OEIS? What are they A numbers? (if they exist)
#  [seq(coeff(L[i],x,j),i=1..nops(L))]; 
# Answer:
# For j=0: A000108 Catalan numbers: 1, 2, 5, 14, 42, 132, 429, 1430
# For j=1: A003517 Number of permutations of [n+1] with exactly 1 increasing subsequence of length 3: 1, 6, 27, 110, 429, 1638
# For j=2: A001089 Number of permutations of [n] containing exactly 2 increasing subsequences of length 3: 3, 24, 133, 635, 2807
# For j=3: It is not in the OEIS: 7, 70, 461, 2528
# For j=4: It is not in the OEIS: 1, 9, 74, 507, 3008



# Question 5:
# Repeat the above problem with the other five patterns of length 3,
#  i.e. by replacing [1,2,3] by each of the following {[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]} 

# For L:=[seq(WtE(permute(n),pi->NumPat3(pi,[1,3,2]),x),n=1..8)];
#
# For j=0: A000108 Catalan numbers: 1, 2, 5, 14, 42, 132, 429, 1430
# For j=1: A002054 Binomial coefficient C(2n+1, n-1): 1, 5, 21, 84, 330, 1287
# For j=2: A082970 Number of permutations of length n containing 2 occurrences of 132: 4, 23, 107, 464, 1950
# For j=3: A082971 Number of permutations of {1,2,...,n} containing exactly 3 occurrences of the 132 pattern: 1, 14, 82, 410, 1918
# For j=4: A138162 Number of permutations of {1,2,...,n} containing exactly 4 occurrences of the 132 pattern: 12, 96, 526, 2593
# For j=5: A138163 Number of permutations of {1,2,...,n} containing exactly 5 occurrences of the pattern 132: 5, 55, 394, 2225
# For j=6: It is not in the OEIS: 3, 64, 475, 2858


# For L:=[seq(WtE(permute(n),pi->NumPat3(pi,[2,1,3]),x),n=1..8)];
#
# For j=0: A000108 Catalan numbers: 1, 2, 5, 14, 42, 132, 429, 1430
# For j=1: A002054 Binomial coefficient C(2n+1, n-1): 1, 5, 21, 84, 330, 1287
# For j=2: A082970 Number of permutations of length n containing 2 occurrences of 132: 4, 23, 107, 464, 1950
# For j=3: A082971 Number of permutations of {1,2,...,n} containing exactly 3 occurrences of the 132 pattern: 1, 14, 82, 410, 1918
# For j=4: A138162 Number of permutations of {1,2,...,n} containing exactly 4 occurrences of the 132 pattern: 12, 96, 526, 2593
# For j=5: A138163 Number of permutations of {1,2,...,n} containing exactly 5 occurrences of the pattern 132: 5, 55, 394, 2225
# For j=6: It is not in the OEIS: 3, 64, 475, 2858


# For L:=[seq(WtE(permute(n),pi->NumPat3(pi,[2,3,1]),x),n=1..8)];
#
# For j=0: A000108 Catalan numbers: 1, 2, 5, 14, 42, 132, 429, 1430
# For j=1: A002054 Binomial coefficient C(2n+1, n-1): 1, 5, 21, 84, 330, 1287
# For j=2: A082970 Number of permutations of length n containing 2 occurrences of 132: 4, 23, 107, 464, 1950
# For j=3: A082971 Number of permutations of {1,2,...,n} containing exactly 3 occurrences of the 132 pattern: 1, 14, 82, 410, 1918
# For j=4: A138162 Number of permutations of {1,2,...,n} containing exactly 4 occurrences of the 132 pattern: 12, 96, 526, 2593
# For j=5: A138163 Number of permutations of {1,2,...,n} containing exactly 5 occurrences of the pattern 132: 5, 55, 394, 2225
# For j=6: It is not in the OEIS: 3, 64, 475, 2858


# For L:=[seq(WtE(permute(n),pi->NumPat3(pi,[3,1,2]),x),n=1..8)];
#
# For j=0: A000108 Catalan numbers: 1, 2, 5, 14, 42, 132, 429, 1430
# For j=1: A002054 Binomial coefficient C(2n+1, n-1): 1, 5, 21, 84, 330, 1287
# For j=2: A082970 Number of permutations of length n containing 2 occurrences of 132: 4, 23, 107, 464, 1950
# For j=3: A082971 Number of permutations of {1,2,...,n} containing exactly 3 occurrences of the 132 pattern: 1, 14, 82, 410, 1918
# For j=4: A138162 Number of permutations of {1,2,...,n} containing exactly 4 occurrences of the 132 pattern: 12, 96, 526, 2593
# For j=5: A138163 Number of permutations of {1,2,...,n} containing exactly 5 occurrences of the pattern 132: 5, 55, 394, 2225
# For j=6: It is not in the OEIS: 3, 64, 475, 2858


# For L:=[seq(WtE(permute(n),pi->NumPat3(pi,[3,2,1]),x),n=1..8)];
#
# For j=0: A000108 Catalan numbers: 1, 2, 5, 14, 42, 132, 429, 1430
# For j=1: A003517 Number of permutations of [n+1] with exactly 1 increasing subsequence of length 3: 1, 6, 27, 110, 429, 1638
# For j=2: A001089 Number of permutations of [n] containing exactly 2 increasing subsequences of length 3: 3, 24, 133, 635, 2807
# For j=3: It is not in the OEIS: 7, 70, 461, 2528
# For j=4: It is not in the OEIS: 1, 9, 74, 507, 3008
# For j=5: It is not in the OEIS: 6, 54, 395, 2570


# Question 8: Optional CHALLENGE (5 dollars, no peeking).
#  Prove that for every positive inteter
#   factor(WtE(permute(n),pi->nops(LtoR(pi)),x))=x(x+1)(x+2)...(x+n-1)
# [Hint: Construct the permutations of length n from those of length n-1,
#   by adding 1 to all the entries, and sticking 1 in every-which place.
#   In most places it does not change the number of Left-To-Right maxima, but in one place it does. Which one?

# Proof: This is not a rigorous proof but here is the idea:
# We proceed by induction on n. For the base case: n=1
# Notice that the only permutation of length 1 is pi=1 and LtoR([1])=[1] since 1 is always in it.
# Hence, WtE(permute(1),pi->nops(LtoR(pi)),x)=x.
# Assume up to n-1: factor(WtE(permute(n-1),pi->nops(LtoR(pi)),x))=x(x+1)(x+2)...(x+n-2)
# Now, for each permutation of length n-1, increment each element by 1 and then we are going to insert the element 1
# into each permutation in all of the n places that we can insert it (at the beginning of the permutation, and then after each element,
# of which there are n-1 elements in the permutation. Notice that LtoR includes all the locations in which are larger than anything to the left.
# The only place that will incremement the number of locations will be when 1 is inserted at the beginning of the permutation of length n-1.
# This is because the first location is always included in LtoR. Now, for all the other places, it will not matter because 
# the element 1 is surely less than any of the other numbers and so nothing will be affected if the element 1 exists before the "current champion".
# The locations of the champions will change though.
# In all cases, inserting 1 at the beginning increases the LtoR statistic by one and therefore contributes a factor of 
# x, while inserting 1 in any of the remaining n−1 places/locations contributes a factor of 1.
# Thus, each permutation contributes (x+n-1) to the weight-enumerator and so we multiply
# x(x+1)(x+2)...(x+n-2) by (x+n-1).



#######From before:
# C5.txt, Feb. 05, 2026


Help5:=proc():
 print(`WtE(S,f,x), RF(x,n), LtoR(pi), inv(pi), maj(pi)`):
end:

#Notes:
# inv(pi): the number of pairs (i,j) for 1<=i<=j<=n such that pi[i]<pi[j]
# Sum(x[1,pi[1]]*x[2,pi[2]]*...*x[n,pi[n]]*(-1)^n) is the definition
#  of the determinant of a matrix

# Weighted counting
# numerical attribute
# Weight enumerator:
#  finite set S, and some weight f, Wt(S,f,a)=Sum(a^f(s),s in S)


#maj(pi): [the major index] the sum of the places/locations where
# pi[i]>pi[i+1]
# maj([4,5,3,2,1])=9 since
#  i=2,i=3,i=4 and 2+3+4=9
maj:=proc(pi) local n,i,co:
n:=nops(pi):
co:=0:
for i from 1 to n-1 do
 if pi[i]>pi[i+1] then
  co:=co+i:
 fi:
od:
co:
end:


#inv(pi): The number of inversions of the permutation pi
# i.e. the number of pairs (i,j) for 1<=i<=j<=n such that pi[i]<pi[j]
# For example: inv([1,2,3])=0, 
#  inv([3,2,1])=3 since the pairs are (1,2),(1,3),(2,3)
inv:=proc(pi) local n,i,j,co:
n:=nops(pi):
co:=0:
for i from 1 to n do
 for j from i+1 to n do
  if pi[j]<pi[i] then
   co:=co+1:
  fi:
 od:
od:
co:
end:


#WtE(S,f,x): Sum(x^f(s), s in S)
WtE:=proc(S,f,x) local s:
add(x^f(s), s in S):
end:


#RF(x,n): the rising factorial i.e. x*(x+1)*...*(x+n-1)
RF:=proc(x,n) local i:
mul(x+i,i=0..n-1):
end:


#LtoR(pi): The list of places that are larger than anything to the left
# For example: if pi=[2,1,4,3]
#  then LtoR(pi)={1,3}
LtoR:=proc(pi) local i,L,ma,n:
n:=nops(pi):
L:=[1]:
#ma is the current world record (the max)
ma:=pi[1]:
for i from 2 to n do
 if pi[i]>ma then
  L:=[op(L),i]:
  ma:=pi[i]:
 fi:
od:
L:
end:



# 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