#OK to post homework
#Kent Mei, 11/1/20, Assignment 16

#---------------------------------
#Part 1

#p_3(n) = p_3(n-1) + (n-1)*(p_3(n-2) + (n-2)*p_3(n-3))
#Equivalently:
#p_3(n) = p_3(n-1) + (n-1)*p_3(n-2) + (n^2-3*n+2)*p_3(n-3)
#or:
#p_3(n) - p_3(n-1) - (n-1)*p_3(n-2) - (n^2-3*n+2)*p_3(n-3) = 0
#p(0) = 1, p(1) = 1, p(2) = 2, p(3) = 5

#p_3(n+3) - p_3(n+2) - (n+2)*(p_3(n+1) + (n+1)*p_3(n)) = 0

#If we look at element n, there are two possibilities:
#i) If n maps to itself, there are p_3(n-1) ways to create a permutation whose cycle structure consists of cycles of length 1,2,or 3 out of the remaining elements.
#ii) If n maps to another element, which we denote m, there are two possibilities for m:
#--i) If m maps to n, there are p_3(n-2) ways to arrange the other n-2 elements. 
#--ii) If m maps to a different element which we denote k, k has to map back to n to ensure a cycle of length at most 3. Then, there are p_3(n-3) ways to arrange the other elements. Note there are n-2 choices for k. 
#Also note that there are n-1 choices for m.



#ope(n,N) = I - N^(-1) - (n-1)*N^(-2) - (n^2-3*n+2)*N^(-3)


#p_3(n+3) - p_3(n+2) - (n+2)*(p_3(n+1) + (n+1)*p_3(n)) = 0

#ope(n,N) =  N^3 - N^2 - (n+2)*N - (n^2 + 3*n + 2)*I
#The order of the recurrence relation is 3.

#ope := N^3 - N^2 - (n+2)*N - (n^2 + 3*n + 2)
#SeqFromRec(ope, n, N, [1,2,5],200)[200]
#p_3(200) = 1128229342224250409977571477237602211005224534912356350930443615542857213566496891997776513837813244158753769620566503215847518434710389045756669563685354991503389333552591617962022597374604028294248769634453145378584484248158483438208939923996110880239517696


#---------------------------------
#Part 2

#p_k(n) - p_k(n-1) - (n-1)*p_k(n-2) - (n-1)*(n-2)*p_k(n-3) - ... - (n-1)*(n-2)*...*(n-k+1)*p_k(n-k) = 0.

#p_k(n+k) - p_k(n+k-1) - (n+k-1)*p_k(n+k-2) - (n+k-1)*(n+k-2)*p_k(n+k-3) - ... - (n+k-1)*(n+k-2)*...*(n+1)*p_k(n) = 0.

#The order is k. 

#---------------------------------
#Part 3

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

S6seq:=proc(N): [seq(S6(n), n = 0..N-1)]: end:

#Findrec(S6seq(200), n, N, 20)
#-8*n^3*(6*n-1)*(2*n+1)*(510578*n+701841)*(6*n+1)/((n+2)*(68821*n+89555)*(n+3)^5)+(1/3)*(1220155462*n^7+7630525053*n^6+24102407415*n^5+48083389345*n^4+61153339323*n^3+47245035102*n^2+20060238220*n+3581016180)*N/((n+2)*(68821*n+89555)*(n+3)^5)-(1/3)*(329726969*n^7+4510478951*n^6+25961601810*n^5+81977886100*n^4+153836556389*n^3+171830219751*n^2+105853624100*n+27749509650)*N^2/((n+2)*(68821*n+89555)*(n+3)^5)-(2/3)*(4178086*n^6+56022252*n^5+315184056*n^4+947849628*n^3+1599524688*n^2+1429257735*n+525439145)*N^3/((68821*n+89555)*(n+3)^5)+N^4

#Seems like degree = 7 and order = 4

#So, initial conditions would be [1,2,66,1460]


#I changed the parameter name from N to K so that there isn't a shared variable name between S6seqClever and SeqFromRec.

S6seqClever:=proc(K) local ope: 

ope:= -8*n^3*(6*n-1)*(2*n+1)*(510578*n+701841)*(6*n+1)/((n+2)*(68821*n+89555)*(n+3)^5)+(1/3)*(1220155462*n^7+7630525053*n^6+24102407415*n^5+48083389345*n^4+61153339323*n^3+47245035102*n^2+20060238220*n+3581016180)*N/((n+2)*(68821*n+89555)*(n+3)^5)-(1/3)*(329726969*n^7+4510478951*n^6+25961601810*n^5+81977886100*n^4+153836556389*n^3+171830219751*n^2+105853624100*n+27749509650)*N^2/((n+2)*(68821*n+89555)*(n+3)^5)-(2/3)*(4178086*n^6+56022252*n^5+315184056*n^4+947849628*n^3+1599524688*n^2+1429257735*n+525439145)*N^3/((68821*n+89555)*(n+3)^5)+N^4

SeqFromRec(ope,n,N,[1,2,66,1460],K):

end:


#time(S6seq(1000));
#6.531

#time(S6seqClever(1000));
#.156