#Please do not post homework
#Caroline Cote, Feb. 8th, 2026, Assignment 5
Help := proc(): print(`NumPat3(pi,sig)`): end:

#problem 1
#done!

#problem 2
with(combinat):
read "C5.txt":

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

#I would conjecture the quantity for the following expression is (1+x)^n. 
#n =1: 
#powerset(1) is {1} so the function is just 1 + x^1.
#n=2:
#powerset(2) is {1} and {2}, {1,2} so we have (1 + x) + x + x^2 = (1+x)^2 
#                                                                      { n-1 } + {  new  }
#n=3:
#powerset(2) is {1}, {2}, {1,2} and {3}, {1,3}, {2,3}, {1,2,3} so we have 
#((1 + x) + x + x^2) + x + x^2 + x^2 + x^3 = (1+x)^3
# {        n-1            } + {           new          }
#so for each n the pattern continues adding to the previous so that we have (1+x)^n.

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

#NumPat3(pi,sig): inputs a permutation pi of any length and a permutation sig of length 3
#uses redu from C4.txt
#a variable co that starts as 0, triple do-loop adding 1 to co each time it finds a triple that reduces to sig
#outputs the number of occurrences of the pattern sig in pi.
read "C4.txt":
NumPat3:= proc(pi,sig) local co, n, i, j, k, pat:

if not member(sig, permute(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
               pat := [pi[i],pi[j],pi[k]]:
               if redu(pat) = sig then
                      co:= co +1;
               fi:
          od:
      od:
od:
co:
end:


#problem 4
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]

[seq([seq(coeff(L[i], x, j), i = 1 .. nops(L))], j = 1 .. 10)];
# j=1:  [0, 0, 1, 6, 27, 110, 429, 1638], 
#in the OEIS: A115145

# j=2: [0, 0, 0, 3, 24, 133, 635, 2807], 
#in the OEIS: A001089

# j=3: [0, 0, 0, 0, 7, 70, 461, 2528], 
#not in the OEIS!
  
# j=4: [0, 0, 0, 1, 9, 74, 507, 3008], 
#not in the OEIS!

# j=5: [0, 0, 0, 0, 6, 54, 395, 2570], 
#not in the OEIS!
  
# j=6: [0, 0, 0, 0, 0, 37, 387, 2864], 
#not in the OEIS!

# j=7: [0, 0, 0, 0, 4, 32, 320, 2544], 
#not in the OEIS!
  
# j=8: [0, 0, 0, 0, 0, 24, 260, 2389], 
#not in the OEIS!

# j=9: [0, 0, 0, 0, 0, 12, 232, 2182], 
#not in the OEIS!
  
# j=10: [0, 0, 0, 0, 1, 16, 191, 2077]
#not in the OEIS!

#only j=1,2 are in the OEIS


#problem 5
#[1,3,2]
L := [seq(WtE(permute(n), pi -> NumPat3(pi, [1, 3, 2]), x), n = 1 .. 8)];
#L := [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]

[seq([seq(coeff(L[i], x, j), i = 1 .. nops(L))], j = 1 .. 10)];
# j=1: [0, 0, 1, 5, 21, 84, 330, 1287], 
#not in the OEIS

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

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

# j=4 [0, 0, 0, 0, 12, 96, 526, 2593], 
#not in the OEIS

# j=5: [0, 0, 0, 0, 5, 55, 394, 2225], 
#not in the OEIS

# j=6: [0, 0, 0, 0, 3, 64, 475, 2858], 
#not in the OEIS

# j=7: [0, 0, 0, 0, 0, 37, 365, 2489], 
#not in the OEIS

# j=8: [0, 0, 0, 0, 0, 29, 360, 2682], 
#not in the OEIS

# j=9: [0, 0, 0, 0, 0, 22, 298, 2401], 
#not in the OEIS

# j=10: [0, 0, 0, 0, 0, 10, 281, 2620]
#not in the OEIS

#none are in the OEIS

#[2,1,3]

L := [seq(WtE(permute(n), pi -> NumPat3(pi, [2, 1, 3]), x), n = 1 .. 8)];
#L := [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]

[seq([seq(coeff(L[i], x, j), i = 1 .. nops(L))], j = 1 .. 10)];
# j=1: [0, 0, 1, 5, 21, 84, 330, 1287], 
#not in the OEIS

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

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

# j=4 [0, 0, 0, 0, 12, 96, 526, 2593], 
#not in the OEIS

# j=5: [0, 0, 0, 0, 5, 55, 394, 2225], 
#not in the OEIS

# j=6: [0, 0, 0, 0, 3, 64, 475, 2858], 
#not in the OEIS

# j=7: [0, 0, 0, 0, 0, 37, 365, 2489], 
#not in the OEIS

# j=8: [0, 0, 0, 0, 0, 29, 360, 2682], 
#not in the OEIS

# j=9: [0, 0, 0, 0, 0, 22, 298, 2401], 
#not in the OEIS

# j=10: [0, 0, 0, 0, 0, 10, 281, 2620]
#not in the OEIS

#none are in the OEIS

#[2,3,1]

L := [seq(WtE(permute(n), pi -> NumPat3(pi, [2, 3, 1]), x), n = 1 .. 8)];
#L := [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]

[seq([seq(coeff(L[i], x, j), i = 1 .. nops(L))], j = 1 .. 10)];
# j=1: [0, 0, 1, 5, 21, 84, 330, 1287], 
#not in the OEIS

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

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

# j=4 [0, 0, 0, 0, 12, 96, 526, 2593], 
#not in the OEIS

# j=5: [0, 0, 0, 0, 5, 55, 394, 2225], 
#not in the OEIS

# j=6: [0, 0, 0, 0, 3, 64, 475, 2858], 
#not in the OEIS

# j=7: [0, 0, 0, 0, 0, 37, 365, 2489], 
#not in the OEIS

# j=8: [0, 0, 0, 0, 0, 29, 360, 2682], 
#not in the OEIS

# j=9: [0, 0, 0, 0, 0, 22, 298, 2401], 
#not in the OEIS

# j=10: [0, 0, 0, 0, 0, 10, 281, 2620]
#not in the OEIS

#none are in the OEIS


#[3,1,2]
L := [seq(WtE(permute(n), pi -> NumPat3(pi, [3, 1, 2]), x), n = 1 .. 8)];
#L := [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]

[seq([seq(coeff(L[i], x, j), i = 1 .. nops(L))], j = 1 .. 10)];
# j=1: [0, 0, 1, 5, 21, 84, 330, 1287], 
#not in the OEIS

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

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

# j=4 [0, 0, 0, 0, 12, 96, 526, 2593], 
#not in the OEIS

# j=5: [0, 0, 0, 0, 5, 55, 394, 2225], 
#not in the OEIS

# j=6: [0, 0, 0, 0, 3, 64, 475, 2858], 
#not in the OEIS

# j=7: [0, 0, 0, 0, 0, 37, 365, 2489], 
#not in the OEIS

# j=8: [0, 0, 0, 0, 0, 29, 360, 2682], 
#not in the OEIS

# j=9: [0, 0, 0, 0, 0, 22, 298, 2401], 
#not in the OEIS

# j=10: [0, 0, 0, 0, 0, 10, 281, 2620]
#not in the OEIS

#none are in the OEIS


#[3,2,1]
L := [seq(WtE(permute(n), pi -> NumPat3(pi, [3, 2, 1]), 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]

[seq([seq(coeff(L[i], x, j), i = 1 .. nops(L))], j = 1 .. 10)];
# j=1: [0, 0, 1, 6, 27, 110, 429, 1638], 
#in the OEIS: A115145

# j=2: [0, 0, 0, 3, 24, 133, 635, 2807], 
#in the OEIS: A001089

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

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

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

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

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

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

# j=9: [0, 0, 0, 0, 0, 12, 232, 2182], 
#not in the OEIS

# j=10: [0, 0, 0, 0, 1, 16, 191, 2077]
#not in the OEIS

#Only j=1 and j=2 are in the OEIS.


#problems 6-9 are optional