#OK to post
#Sam Minkin, 11/01, Assignment 16

QUESTION #1:

The recurrene can be found through the following reasoning:
The last cycle structure can be of length 1, 2, or 3. Therefore, we can find all cycle decompositions consisting of length 1, 2, or 3 cycles of size n-1, n-2, and n-3, respectively, and append a cycle of length 1, 2, or 3 to give a cycle from 1 to n as desired. This leads to the recurrence:

p_3(n) = p_3(n-1) + p_3(n-2) + p_3(n-3).
Equivalently, p_3(n+3) - p_3(n+2) - p_3(n+1) - p_3(n) = 0.
ope(n,N) = N^3 - N^2 - N - 1

The recurrence has order three.
Our initial conditions are p_3(0) = 0, p_3(1) = 1, p_3(2) = 2
We can get p_3(200) by running:
SeqFromRec(N^3 - N^2 - N - 1,n,N,[0,1,2],200):
p_3(200) = 24012263187173292438733091914788756514219413052446981.


QUESTION #3:

S6:=proc(n):

add(binomial(n,k)^6,k=0..n):

end:

S6seq:=proc(N):

seq(S6(i),i=0..(N-1)):

end:

Using Findrec,
First we run L:=[S6seq(100)];
Then, running Findrec(L, n, N, 11) results in:
-8*n^3*(6*n - 1)*(2*n + 1)*(510578*n + 701841)*(6*n + 1)/((n + 2)*(68821*n + 89555)*(n + 3)^5) + (1220155462*n^7 + 7630525053*n^6 + 24102407415*n^5 + 48083389345*n^4 + 61153339323*n^3 + 47245035102*n^2 + 20060238220*n + 3581016180)*N/(3*(n + 2)*(68821*n + 89555)*(n + 3)^5) - (329726969*n^7 + 4510478951*n^6 + 25961601810*n^5 + 81977886100*n^4 + 153836556389*n^3 + 171830219751*n^2 + 105853624100*n + 27749509650)*N^2/(3*(n + 2)*(68821*n + 89555)*(n + 3)^5) - 2*(4178086*n^6 + 56022252*n^5 + 315184056*n^4 + 947849628*n^3 + 1599524688*n^2 + 1429257735*n + 525439145)*N^3/(3*(68821*n + 89555)*(n + 3)^5) + N^4

The initial conditions are [1, 2, 66, 1460]

S6seqClever:=proc(M):

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

end:


time(S6seq(1000)) returns:
7.390 seconds

time(S6seqClever(1000)) returns:
0.156 seconds