#Ok to post
#Michael Yen, 11/1/20, Assignment 16

#Lecture 16: Due Nov. 1, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

#hw16FirstLast.txt

#Indicate whether it is OK to post

#1. An involution is a permutation whose cycle structure consists only of cycles of length 1 and 
#2. Let p_3(n) be the number of permutations whose cycle structure consists of cycles of length 1, 
#2, or 3. Find a linear recurrence satisfied by p_3(n), and express the linear recurrence operator #ope(n,N) annihilating it. What is the order of the recurrence? Using procedure SeqFromRec in in 
#ComboProject4.txt find p_3(200).

Linear Recurrence
#p_3(n)=p_3(n-1)+(n-1)*p_3(n-2)+nChoose2*p_3(n-3)
#nChoose2 = n(n-1)/2
#-p_3(n+3)+p_3(n+2)+(n-1)*p_3(n+1)+n(n-1)/2*p_3(n)=0

p_3(n):=p_3(n-1)+(n-1)*p_3(n-2)+n(n-1)/2*p_3(n-3);
ope:=-N^3+N^2+(n-1)*N+(n(n-1)/2); #Annihilates it

#The order of this is 3.

#p_3(1)=1
#p_3(2)=2
#p_3(3)=7

SeqFromRec(ope,n,N,[1,2,7],200)[200]

#This takes too long for me, I wasn't able to reach the end.

#3. Write a procedure that inputs a positive integer n and outputs the sum of binomial(n,k)^6 from #k=0 to n. Call is S6(n). Then write a one-line procedure S6seq(N) that inputs a positive integer 
#N and outputs the first N terms of the sequence S6(n).
#Using procedure Findrec in ComboProject4.txt find a linear recurrence operator annihilating it 
#(equivalently a recurrence) and the initial condition, and write procedure S6seqClever(N) that 
#uses procedure SeqFromRec from the same Maple package to do the same thing as S6seq(N).

S6:=proc(n)  local k:
add(binomial(n,k)^6,k=0..n)
end:

S6seq:=proc(N)
seq(S6(n),n=1..N):
end:

L := [S6seq(100)];
ope := Findrec(L, n, N, 100):
deg:=degree(ope,N)

S6seqClever:=proc(k)
SeqFromRec(ope, n, N, [seq(S6(i),i=1..deg)],k):
end:

#What are
#time(S6seq(1000));
#and
#time(S6seqClever(1000));

#time(S6seq(1000)) is 7.000
#time(S6seqClever(1000)) is 0.125
#So S6seqClever is a lot faster