#OK to post homework
#Karnaa Mistry, 11/1/20, Assignment HW #16

with(combinat):

# 1. 

#(a1) (a2) ... (ak) (b1,b2) ... (b_{r-1},b_r)   (c1,c2,c3) ... (c_{r-2},c_{r-1},c_r)
#Case 1: singleton (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 remaining n-2 people to form an involution
#Case 3: n can pick (n-1)(n-2) choices to be its two cycle-mates, leaving remaining n-3 people 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 (NOTE: to use SeqFromRec, we should note p_3(3) = 6)
# -->  p_3(n+3) = p_3(n+2) + (n+2)*p_3(n+1) + (n+2)*(n+1)*p_3(n)
# -->  p_3(n+3) - p_3(n+2) - (n+2)*p_3(n+1) - (n+2)*(n+1)*p_3(n) = 0

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

# This recurrence is of order 3

# SeqFromRec(N^3-N^2-(n+2)*N-(n+1)*(n+2),n,N,[1,2,6],200)[200] = p_3(200) =
# 123553773949440758665054643867236407914507508704334417793972657388544873168386808354322568042936555931391...
# ...8818143059602933273136821039217983508358005191683227373604250736322487950063766412201151455790542790393051794133976081480109115439664124797121023312920576




# 3.

#S6(n):outputs sum of binomial(n,k)^6 from k=0 to n
S6:=proc(n) local k,s:
s:=0:

for k from 0 to n do:
    s:=s+binomial(n,k)^6:
od:

s:
end:


#S6seq(N): outputs first N terms of the sequence S6(n)
S6seq:=proc(N) local i: seq(S6(i),i=0..N-1): end:


#Findrec([1, 2, 66, 1460, 54850, 2031252, 86874564, 3848298792, 180295263810, 8709958973540, 433617084579316, 22071658807720392, 1145600816547477316, 
# 60423221241495866600, 3231675487858598367240, 174928470621208572186960, 9568929614185118483080770, 528312173436681791506408260, 29410084375652468835825953700,
# 1649306291835755062635565266600],n,N,c) kept failing for me, for various values of c (0,1,2,3, etc.)

# I was unable to get a S6seqClever(N), but I got time(S6seq(1000)) = 7.593