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

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

## Problem 2
# Conjecture an expression for the following quantity, once you have read C5.txt:
# factor(WtE(powerset(n),S->nops(S),x)); 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-> xNumberOfElementsOfS

# seq(factor(WtE(powerset(n),S->nops(S),x)), n=1..6);
#                  2         3         4         5         6
#    1 + x, (1 + x) , (1 + x) , (1 + x) , (1 + x) , (1 + x) 

# conjecture: (1+x)^n 

# proof:
# expanding with the binomial theorem: (1+x)^n = sum_{k=0}^n binomial(n,k) x^k
# the powerset of [n] consists of all subsets of [n] of all sizes. the number of subsets of size k <= n is 
# n choose k, i.e., binomial(n,k). in the weight enumerator, we therefore expect the coefficient of x^k to be 
# the number of subsets of size k, which is binomial(n,k). this matches our sum from the 
# binomial theorem by allowing the subset size to range from 0 to n, so we have proven our conjecture!



## Problem 3 
# NumPat3(pi,sig): 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.
# e.g. 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 n,i,j,k,co:
if not nops(sig) = 3 then 
    RETURN(FAIL):
fi:

n := nops(pi):
co := 0:

for i from 1 to n-2 do 
    for j from i+1 to n-1 do 
        for k from j+1 to n do 
            if redu([pi[i],pi[j],pi[k]])=sig then 
                co++:
            fi:
        od:
    od:
od:

co:
end:


## Problem 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)];) 

# L := [1, 2, 5 + x, x^4 + 3*x^2 + 6*x + 14, x^10 + 4*x^7 + 6*x^5 + 9*x^4 + 7*x^3 + 24*x^2 + 27*x + 42, 
# x^20 + 5*x^16 + 8*x^13 + 6*x^12 + 6*x^11 + 16*x^10 + 12*x^9 + 24*x^8 + 32*x^7 + 37*x^6 + 54*x^5 + 74*x^4 + 70*x^3 + 133*x^2 + 110*x + 132, 
# x^35 + 6*x^30 + 10*x^26 + 10*x^25 + 8*x^23 + 13*x^22 + 30*x^21 + 10*x^20 + 32*x^19 + 18*x^18 + 62*x^17 + 74*x^16 + 24*x^15 + 100*x^14 + 130*x^13 + 104*x^12 + 162*x^11 + 191*x^10 + 232*x^9 + 260*x^8 + 320*x^7 + 387*x^6 + 395*x^5 + 507*x^4 + 461*x^3 + 635*x^2 + 429*x + 429, 
# x^56 + 7*x^50 + 12*x^45 + 15*x^44 + 10*x^41 + 16*x^40 + 40*x^39 + 18*x^38 + 47*x^36 + 38*x^35 + 68*x^34 + 60*x^33 + 58*x^32 + 66*x^31 + 154*x^30 + 138*x^29 + 115*x^28 + 156*x^27 + 252*x^26 + 324*x^25 + 228*x^24 + 288*x^23 + 537*x^22 + 466*x^21 + 546*x^20 + 656*x^19 + 682*x^18 + 1004*x^17 + 1047*x^16 + 886*x^15 + 1494*x^14 + 1456*x^13 + 1580*x^12 + 1818*x^11 + 2077*x^10 + 2182*x^9 + 2389*x^8 + 2544*x^7 + 2864*x^6 + 2570*x^5 + 3008*x^4 + 2528*x^3 + 2807*x^2 + 1638*x + 1430]


# 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))];

# j=0: [1, 2, 5, 14, 42, 132, 429, 1430] --> A000108

# j=1: [0, 0, 1, 6, 27, 110, 429, 1638] --> A003517

# j=2: [0, 0, 0, 3, 24, 133, 635, 2807] --> A001089

# j=3: [0, 0, 0, 0, 7, 70, 461, 2528] --> not in OEIS

# j=4: [0, 0, 0, 1, 9, 74, 507, 3008] --> not in OEIS

# j=5: [0, 0, 0, 0, 6, 54, 395, 2570] --> not in OEIS

# j=6: [0, 0, 0, 0, 0, 37, 387, 2864] --> not in OEIS

# j=7: [0, 0, 0, 0, 4, 32, 320, 2544] --> not in OEIS

# j=8: [0, 0, 0, 0, 0, 24, 260, 2389] --> not in OEIS



## Problem 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]}

# sig = [3,2,1] is the same L as when sig = [1,2,3] (mirror image, so this makes sense)
# sig = [1,3,2], [2,1,3], [2,3,1], and [3,1,2]: 

# L1 := [1, 2, 5 + x, x^3 + 4*x^2 + 5*x + 14, 3*x^6 + 5*x^5 + 12*x^4 + 14*x^3 + 23*x^2 + 21*x + 42, 
# 2*x^12 + 10*x^10 + 22*x^9 + 29*x^8 + 37*x^7 + 64*x^6 + 55*x^5 + 96*x^4 + 82*x^3 + 107*x^2 + 84*x + 132, 
# 2*x^20 + x^19 + 13*x^18 + 14*x^17 + 23*x^16 + 55*x^15 + 93*x^14 + 126*x^13 + 206*x^12 + 175*x^11 + 281*x^10 + 298*x^9 + 360*x^8 + 365*x^7 + 475*x^6 + 394*x^5 + 526*x^4 + 410*x^3 + 464*x^2 + 330*x + 429, 
# x^31 + 7*x^30 + 20*x^28 + 37*x^27 + 41*x^26 + 109*x^25 + 162*x^24 + 169*x^23 + 322*x^22 + 397*x^21 + 647*x^20 + 730*x^19 + 1048*x^18 + 1152*x^17 + 1417*x^16 + 1576*x^15 + 1770*x^14 + 1853*x^13 + 2321*x^12 + 2088*x^11 + 2620*x^10 + 2401*x^9 + 2682*x^8 + 2489*x^7 + 2858*x^6 + 2225*x^5 + 2593*x^4 + 1918*x^3 + 1950*x^2 + 1287*x + 1430]

# j=0: [1, 2, 5, 14, 42, 132, 429, 1430] --> A000108

# j=1: [0, 0, 1, 5, 21, 84, 330, 1287] --> not in OEIS

# j=2: [0, 0, 0, 4, 23, 107, 464, 1950] --> not in OEIS

# j=3: [0, 0, 0, 1, 14, 82, 410, 1918] --> not in OEIS

# j=4: [0, 0, 0, 0, 12, 96, 526, 2593] --> not in OEIS



## Problem 7
# Optional Challenge (5 dollars, no peeking). Prove that for every positive inteter
# factor(WtE(permute(n),pi->nops(CycDec(pi)),x))=x(x+1)(x+2)...(x+n-1)
# [Hint: Construct the permutations of length n from those of length n-1, given in cycle structure. 
# Where can you stick the n w/o creating a new cycle?, adding the singleton cycle (n) increases the number by 1]

# proof: by induction 
#   for permutations of length 1, there is one permutation with one cycle, so the weight enumerator is simply x 
# assume that the weight enumerator for a permutation of length n is x(x+1)(x+2)...(x+n-1)
# then consider a permutation of length n+1. to build a permutation of length n+1 (pi') from a permutation of length n (pi), 
# we must insert the element n+1 into the cyclic decomposition of pi. let pi consist of k cycles.
#   say that the element n+1 is inserted as its own singleton in the cycle decomposition of pi'. then there are now 
# k+1 cycles in pi'. there are x*(weight enumerator for length n) many cycles created in this way since each permutation has 
# one extra cycle now. by induction, there are x*[x(x+1)(x+2)...(x+n-1)] permutations in this case.
#   if n+1 is inserted into an existing cycle, there are n possible insertion points between any of the existing n elements. 
# then the number of permutations created this way is n*x*(weight enumerator for length n), or n*[x(x+1)(x+2)...(x+n-1)], by induction.
#   adding these two cases together, the weight enumerator for length n+1 permutations is:
# x*[x(x+1)(x+2)...(x+n-1)] + n*[x(x+1)(x+2)...(x+n-1)] = x(x+1)(x+2)...(x+n-1)*(x+n), proving the claim by induction!


## Problem 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: by induction 
#   for permutations of length 1, there is one permutation with one left-to-right maximum (1), so the weight enumerator is x.
# assume that the weight enumerator for a permutation of length n is x(x+1)(x+2)...(x+n-1)
# consider a permutation of length n+1. to build a permutation of length n+1, we will increment all elements of the length n permutation (pi)
# and insert a 1 somewhere into pi to form pi'. 
#   if 1 is inserted in front of the permutation pi, then every left-to-right maxima in pi is preserved in pi', and the element 1 
# forms a (trivial) maxima at the front of the permutation. then we add one additional left-ro-right maxima to each permutation, so the weight 
# enumerator becomes x*(weight enumerator for length n) = x*[x(x+1)(x+2)...(x+n-1)], by induction. 
#   if 1 is inserted anywhere else in the permutation, the number of left-ro-right maxima is preserved since no new entries become maxima, 
# and no entries are "demoted" since every remaining entry is larger than 1. there are n possible insertion points (after any of the n entries 
# of pi -- NOT before the first entry as that was the previous case) so the weight enumerator for this case becomes n*(weight enumerator for length n)
# or n*[x(x+1)(x+2)...(x+n-1)] by induction.
#   summing these two cases, we obtain:
# x*[x(x+1)(x+2)...(x+n-1)] + n*[x(x+1)(x+2)...(x+n-1)] = x(x+1)(x+2)...(x+n-1)(x+n), which proves the claim by induction




### copied from C5.txt 

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

with(combinat):

#maj(pi): The major index : The sum of the places where
#pi[i]>pi[i+1]
maj:=proc(pi) local n,i,co:
co:=0:
n:=nops(pi):
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
#For example inv([1,2,3])=0, inv([3,2,1])=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[i]>pi[j] then 
      co:=co+1:
    fi:
od:
od:
co:
end:
	



#LtoR(pi): The list places that are larger than anything
#to the left pi=[2,1,4,3]
LtoR:=proc(pi) local n,L,i,ma:
n:=nops(pi):
L:=[1]:
#ma is the current world record
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:

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



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

##start old stuff from C3.txt
#C3.txt, Jan. 29, 2026
Help3:=proc(): print(`FP(pi), Der(n), d(n) , ExtractCycle(pi,i) , CycDec(pi) `): end:

#FP(pi): The number of fixed points of per. pi
FP:=proc(pi) local n, i,co:
n:=nops(pi):

co:=0:
for i from 1 to n do
 if pi[i]=i then
   co:=co+1:
 fi:
od:
co:
end:

FP([2,1,4,3,5,6]);
 

# Der(n): The set of derangements (i.e. permutations w/o fixed points) of {1, ..., n}
Der := proc(n) local S,pi,DE:
S:=permute(n):
DE:={}:
for pi in S do
 if FP(pi)=0 then 
   DE:=DE union {pi}:
 fi:
od: 
DE:
end:

#a(n):=nops(permute(n))
#
#Solutions SOl. 
#a(n)-n*a(n-1)=0, a(0)=1 HOMOG. linear (first-order) recurrence
#
#d(n):=|Der(n)|
#

d:=proc(n) option remember: if n=1 then 0 else n*d(n-1)+(-1)^n fi:end:

#ExtractCycle(pi,i): The cycle corresponding to the member i of the permutation pi
#For example ExtractCycle([2,1,4,3],1)=[1,2]
ExtractCycle:=proc(pi,i) local C,ng:
C:=[i]:
ng:=pi[i]:
while ng<>i do
C:=[op(C),ng]:
ng:=pi[ng]:
od:
C:
end:

#CycDec(pi): The full cyclic decomposition of pi
CycDec:=proc(pi) local n,i,StillToDo,S,C,ng:
n:=nops(pi):
StillToDo:={seq(i,i=1..n)}:
S:={}:
while StillToDo<>{} do
 ng:=StillToDo[1];
 C:=ExtractCycle(pi,ng):
 S:=S union {C}:
#S\T : S minus T 
StillToDo:=StillToDo minus {op(C)}:
od:
S:
end:



### copied from C4.txt 

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