#OK to post
#Soham Palande, Assignment 16, 11/01/2020




#PART 1

#p_3(n) is the number of permutations whose cycle structure consists of cycles of length 1, 2, or 3
#Then, p_3(n-1) can have either 1,2, or 3 cycles as well.

#Suppose a permutation has 1 cycle:
#Then, n can be inserted in n-1 different positions OR n can form its own cycle. Thus there are n possible 
#permutations

#If a permutation has two cycles:
#Then, n can be inserted in (n-1) positions OR n can form its own cycle. Thus there are (n) possible 
#permutations


#If a permutation has three cycles:
#Then, n can be inserted in n-1 different positions. Thus there are n-1 possible permutations.


p_3(n) = 






#PART 2







#PART 3


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

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


#EXAMPLE:
S6seq(5)
   1, 2, 66, 1460, 54850, 2031252

#Using FindRec

ope:= Findrec([S6seq(100)],n,N,15)

 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



S6SeqClever:=proc(k):
SeqFromRec(ope,n,N,[1, 2, 66, 1460],k)
end:



time(S6SeqClever(1000))
4.062
time(S6seq(1000))
Warning,  computation interrupted.  # took too long!