#OK to post homework
#William Wang, 10/30/2020, Assignment 16

#1.
#p_3(n):=number of permutations whose cycle structure consists of length 1,2, or 3 in the alphabet {1,...,n}
#Case 1: (n), other n-1 members are left to themselves p_3(n-1) ways
#Case 2: n can pick n-1 choices to be its cycle mate, leaving the remaining n-2 to form an involution
#Case 3: n can pick (n-1)*(n-2) choices to be its cycle mate, leaving the remaining n-3 to form an involution
#p_3(n) = p_3(n-1)+(n-1)*p_3(n-2)+(n-1)*(n-2)*p_3(n-3), p_3(0) = 1, p_3(1)=1, p_3(2)=2
#p_3(n)-p_3(n-1)-(n-1)*p_3(n-2)-(n-1)*(n-2)*p_3(n-3)=0
#p_3(n+3)-p_3(n+2)-(n+2)*p_3(n+1)-(n+1)(n+2)*p_3(n)=0
#ope(n,N)=N^3 - N^2 - (n + 2)*N - (n + 1)(n + 2)
#The order of the recurrence is 3

p_3 := proc(n) option remember:
if n = 0 or n = 1 then 1:
elif n = 2 then 2:
else p_3(n - 1) + (n - 1)*p_3(n - 2) + (n - 1)*(n - 2)*p_3(n - 3):
fi:
end:

seq(p_3(i), i = 1 .. 20);
  1, 2, 6, 18, 66, 276, 1212, 5916, 31068, 171576, 1014696, 

    6319512, 41143896, 281590128, 2007755856, 14871825936, 

    114577550352, 913508184096, 7526682826848, 64068860545056


p_3(200);
1235537739494407586650546438672364079145075087043344177939726573\

  88544873168386808354322568042936555931391881814305960293327313\

  68210392179835083580051916832273736042507363224879500637664122\

  01151455790542790393051794133976081480109115439664124797121023\

  312920576


ope := N^3 - N^2 - (n + 2)*N - (n + 1)(n + 2);
eval(SeqFromRec(ope, n, N, [1, 1, 2], 10));
          [1, 1, 2, 7, 18, 61, 204, 739, 2798, 11081]

#I believe there is something wrong with the SeqFromRec function for this specific operator, seq(p(i),i=1..10) should be exactly the same as SeqFromRec(N^3 - N^2 - (n + 2)*N - (n + 1)(n + 2),n,N,[1,1,2],10), and the output of the latter is incorrect



#3.
S6 := proc(n) local k: add(binomial(n, k)^6, k = 0 .. n): end:
S6seq := proc(N) local i: seq(S6(i), i = 0 .. N - 1): end:

S6seq(10);
     1, 2, 66, 1460, 54850, 2031252, 86874564, 3848298792, 

       180295263810, 8709958973540


findrec([S6seq(200)], 9, 4, n, N);
/     3                               /                        2
\144 n  (6 n - 1) (2 n + 1) (6 n + 1) \1483153037013688073771 n 

                                                      \\//        
   + 3663902389166004703698 n + 2249997630719094581592// \(n + 2) 

  /                       3                          2
  \623213205070535514071 n  + 975089346750003130446 n 

                                                   \        5\   
   + 192842080470164489130 n + 45273616936198792090/ (n + 3) / + 

  /  /                          9                             8
  \6 \179485403060314228052448 n  - 522074724653160464680057 n 

                                7                              6
   - 4539822520435989688648345 n  - 8940308186426530684614615 n 

                                5                              4
   - 7368243259602727667482323 n  - 2296998769737180770551588 n 

                            \  \//        /                      
   + 29416338267133232734740/ N/ \(n + 2) \623213205070535514071 

   3                          2                          
  n  + 975089346750003130446 n  + 192842080470164489130 n

                         \        5\   //                          
   + 45273616936198792090/ (n + 3) / - \\1053853529774275554294061 

   9                               8
  n  + 14633277335084682825932706 n 

                                 7
   + 85848984394381145516933045 n 

                                  6
   + 278793681834135662830444470 n 

                                  5
   + 546951841178022998244666729 n 

                                  4
   + 659482555376066293986922248 n 

                                  3
   + 472726028519471954035518705 n 

                                  2
   + 184463557852004737030567716 n 

                                                             \  2
   + 35294547308636823330301380 n + 4786578820974358679561100/ N 

  \//        /                       3                          2
  / \(n + 2) \623213205070535514071 n  + 975089346750003130446 n 

                                                   \        5\   
   + 192842080470164489130 n + 45273616936198792090/ (n + 3) / - 

  //                         8                             7
  \\23682101792680349534698 n  + 324180749362922359698047 n 

                                6                              5
   + 1881482009189856139730181 n  + 5915827810478787172717423 n 

                                 4
   + 10679905808239089743714065 n 

                                 3                              2
   + 10765433155113414712963038 n  + 5375307166578544797200164 n 

                                                           \  3\/
   + 1053564061416478949542020 n + 172179454703812855702020/ N / 

  //                       3                          2
  \\623213205070535514071 n  + 975089346750003130446 n 

                                                   \        5\
   + 192842080470164489130 n + 45273616936198792090/ (n + 3) /

      4
   + N 


SeqFromRec(%, n, N, [1, 2, 66, 1460], 10);
    [1, 2, 66, 1460, 54850, 2031252, 86874564, 3848298792, 

      180295263810, 8709958973540]

S6seqClever := proc(N1) local ope:
ope := 24*n^3*(6*n - 1)*(2*n + 1)*(6*n + 1)*(91*n^3 + 364*n^2 + 490*n + 222)/((n + 1)*(91*n^3 + 91*n^2 + 35*n + 5)*(n + 2)^5) - (153881*n^9 + 1077167*n^8 + 3262931*n^7 + 5608805*n^6 + 6031994*n^5 + 4217708*n^4 + 1924994*n^3 + 556580*n^2 + 93320*n + 6960)*N/((n + 1)*(91*n^3 + 91*n^2 + 35*n + 5)*(n + 2)^5) - (3458*n^8 + 29393*n^7 + 105980*n^6 + 209980*n^5 + 247796*n^4 + 177067*n^3 + 75006*n^2 + 17660*n + 1800)*N^2/((91*n^3 + 91*n^2 + 35*n + 5)*(n + 2)^5) + N^3:
SeqFromRec(ope, n, N, [1, 2, 66], N1):
end:

time(S6seq(1000));
                             11.750

time(S6seqClever(1000));
                             0.187